How does memory layout of a program depend on address binding technique?

Question

I have learned that with run-time address binding, the program can be allocated frames in the physical memory non-contiguously. Also, as described here and here, every segment of the program in the logical address space is contiguous, but not all segments are placed together side-by-side. The text, data, BSS and heap segments are placed together, but the stack segment is not. In other words, there are pages between the heap and the stack segments (between the program break and stack top) in the logical address space that are not mapped to any frames in the physical address space, thus implying that the logical address space is non-contiguous in the case of run-time address binding.

But what about the memory layout in the case of compile-time or load-time binding ? Now that the logical address space in not an abstract address space but the actual physical address space, how is a program laid out in the physical memory ? More specifically, how is the stack segment placed in the physical address space of a program ? Is it placed together with the rest of the segments or separately just as in the case of run-time binding ?

Answer 1

Stacks grows from top to bottom. Stack segment is used to store all local variables and is used for passing arguments to the functions along with the return address of the instruction which is to be executed after the function call is over. Local variables have a scope to the block which they are defined in, they are created when control enters into the block. All recursive function calls are added to stack.

In order to support dynamic memory allocation heap is used, it may happen that we require some more memory then calculated so heap comes in picture

Text, data and BSS  spaced is reserved during compile time itself.

Different OS uses space between stack and heap differently.

Space between heap and stack  is contiguous most of the time, and is reserved. but if program want more space then allocated here comes heap into picture OS gives virtual memory to program, when ever there is need of physical memory the some data which is not currently in use is swapped in secondary memory and demand of program is fulfilled, after completion of task that data is swapped in into physical memory.

Stack segment is placed in physical address space of program

Comments

So, do you mean to say that the memory layout of a program remains the same (as depicted in the question's diagram) for all address binding techniques ?

If no, then my question remains unresolved because your response does not state how the program is laid out in memory differently for the compile-time or load-time address binding techniques in comparison to the run-time address binding technique.

If yes (which it also seems to be), then let me give you the reasons which make me believe that a program must be laid out differently. Then, perhaps, while giving counter arguments you could point me to some solid resources (books, article, blog, etc) that support your claim.

As you have illustrated with an example, the run-time address binding technique (unlike the compile-time and load-time binding techniques) causes the logical address space (LAS) of a program to be different from its physical address space (PAS). The Paging scheme, like the Relocation register scheme you mentioned, is another memory management scheme which is used by the OS to perform run-time address binding by mapping the LAS of a program to its PAS (with the help of page tables).

So, assuming that the OS uses the Paging scheme, it is known (from here and here) that the pages between the heap and stack segments in the program's LAS (i.e., the area between the program break and the stack top, shown in the question's diagram) are not mapped to any physical frame. In other words, the entries for these pages in the page table of the program are marked as invalid, and any access by the program to such an invalid page results in a segmentation fault. But, as the stack or the heap grow in size, these pages are marked as valid and physical frames are assigned to them.

On a typical system running on a 32-bit processor, the LAS of a program is 4GB in size, and the heap and stack are very far apart so as to allow the heap to grow without limit. The point I am trying to make is that when run-time binding is used, there exist a large no. of pages in the program's LAS between the heap and the stack which are never accessed by the program and no physical frames are assigned to them.

In the case of compile-time or load-time binding technique, the LAS and PAS of a program are equal. Every page of the program is assigned a physical frame. Due to this, the pages between the heap and the stack will also be assigned frames. But, because these pages are not accessed, and they are very large in number, wouldn't the main memory space be tremendously WASTED ? Also, what would happen if the program erroneously tries to access such a page between the heap and the stack ? Now that the LAS of the program is its PAS itself, and there is no need to map the program's LAS to its PAS, the OS does not maintain a page table for the program. So, how can a segmentation fault be caught by the OS when it does not have a page table to determine if a page to be accessed is valid or not ?

---

the LAS and PAS of a program are equal. Every page of the program is assigned a physical frame. Due to this, the pages between the heap and the stack will also be assigned frames. But, because these pages are not accessed, and they are very large in number, wouldn't the main memory space be tremendously WASTED ?

They are not assigned any physical frame unless needed.

The Paging scheme, like the Relocation register scheme you mentioned, is another memory management scheme which is used by the OS to perform run-time address binding by mapping the LAS of a program to its PAS (with the help of page tables).
 

reallocation is not an scheme it is addressing mode it is implemented irrespective of paging.

What you are asking is exact implementation, which is hard to tell from any book as various operating system uses various scheme.

The point I am trying to make is that when run-time binding is used, there exist a large no. of pages in the program's LAS between the heap and the stack which are never accessed by the program and no physical frames are assigned to them.

no pages exist between them unless needed that is why virtual memory is used it gives an false impression that there is an space to grow, whenever heap or stack want to grow then only they are given LAS and while executing its MMU which maps logical address space to physical space.

In short if you want actual implementation then i suggest you ask some seniors like arjun suresh, because it is out of my scope

Regarding source of my information "Operating System Concept 8th edition by Galvin"  chapter 8 Memory management strategies, subtopic 8.1.2 Address binding  & 8.1.3 Logical versus Physical address space as well as some other chapters of this book and little knowledge of compilers

Regarding your sources anatomy of programming i am not sure information is correct and stack overflow has only one answer without any up votes so. This is all i can do

---

Okay. I started using GATE Overflow only recently. May be I'll try and find out a way to ask the seniors on this site.

For the sake of discussion though, I feel the need to tell you that you are using the term "virtual memory" in the wrong context. Virtual memory is not a memory, but a technique (pg. 317, Galvin, 6th ed.) that implements the concept of Demand Paging. My question only pertains to simple paging, not demand paging, and so it is of no concern to the question.
Also, I never referred "Relocation" as a memory management scheme. I used the term "Relocation Register" scheme which is a generalization of the base-register scheme (pg. 277, Galvin, 6th ed). Relocation is not an addressing mode, but a process of converting a relative address to a more concrete address. And, one of many uses of this process is in the implementation of addressing modes like the base register addressing mode.

As far as the references are concerned, they are sufficiently thorough. The author of the article "Anatomy of a Program in Memory" has mentioned in the comment section that the article is based on the contents of the book “Understanding the Linux Kernel”. You are free to search and go through the book. Also, on StackOverflow, the reputation of the author matters more than the no. of upvotes to his/her answer, and in my experience a reputation of 9k is decent enough.