Program stack and heap, how do they work?

Question

I know that every running process has pages associated with it in virtual memory and few of them will be loaded into main memory as required. I also know that program will have a stack and also a heap to allocate dynamic memory. Here are my questions.

1. Is stack also part of some page in main memory?
2. What happens when the program is moved to waiting state? Where are the stack pointer, program counter and other info stored?
3. Why stack grows down and heap grows up?
4. Can L1, L2 cache contain only one chunk of contiguous memory, or can it have some part of stack and heap?

Can you recommend any good book that covers these things?

Answer 1

1. Yes - the stack is typically stored in the "low" addresses of memory and fills upward toward its upper limit. The heap is typically stored at the "top" of the address space and grows toward the stack.

2. The O/S stores a "context" per running process. The operation of saving and restoring process state is called a "context switch."

3. Just a convention AFAIK. The stack doesn't really "grow" it's got fixed allocation.

4. Caches simply contain snapshots of parts of RAM that have been used (either recently or nearby). At any moment in time they can have memory from any part of the address space in them. What shows up where depends heavily on the structural parameters of the cache (block length, associativity, total size, etc.).

I would suggest Computer Architecture: A Quantitative Approach as a good reference on the underlying hardware and any book on Operating Systems for how the hardware is "managed."

Answer 2

You should check out my professor's slides, from my Architecture Class. Unit 6. Really helped me understand, all that you have asked and others have answered, and MORE, if you want a more in-depth knowledge.

Answer 3

3. Why stack grows down and heap grows up?

Note that on some systems (some HP systems, for example), the stack grows up instead of down. And on other systems (e.g., IBM/390) there is no real hardware stack at all, but rather a pool of pages that are dynamically allocated from user space memory.

The heap can, in general, grow in any direction, since it may contain many allocation and deallocation holes, so it is better to think of it as a loose collection of pages than as a LIFO-stack type structure. That being said, most heap implementations expand their space usage within a predetermined address range, growing and shrinking it as necessary.

Answer 4

This is my understanding of those questions:

1. Is stack also part of some page in main memory?

   Yes, the stack is usually also stored in the process address space.

2. What happens when the program is moved to waiting state, where is the stack pointer, program counter and other info stored?

   When the operative system takes the process from active to waiting, it stores all registers (that includes the stack pointer and the program counter) in the kernel's process table. Then, when it becomes active again, the OS copies all that information back into place.

3. Why stack grows down and heap grows up?

   That because they usually have to share the same address space, and as a convenience they each begin on one end of the address space. Then they grow towards each other, giving that grow down-grow up behavior.

4. Can L1,L2 cache contain only one chunk of contiguous memory or can it have some part of stack and heap?

   The CPU caches will store recently used chunks of the memory. Because both the stack and the heap are stored in main memory, the caches can contain portions of both.

Answer 5

When one uses a protected mode operating system (like Windows or Linux), each process has whole bunch of memory pages made available to the given process. If more memory is required, more can be paged in.

Typically the process divides the memory given to it into two parts. One is the heap and the other is the stack. The bottom of the stack is designated by the stack pointer r13 on arm and esp on x86. When one creates a variable on the stack the stack pointer is moved to allow for the extra space needed. This is done by the assembler instruction PUSH. Similarly when a variable is out of scope it is POPed off the stack.

Typically PUSH causes the stack pointer to be decremented leaving the value above the stack pointers value "on the stack".

The other portion of memory may be used for a heap. This is then available for allocation with the use of malloc or new. Each thread must have its own stack but may share the heap with other threads in the process.

When the kernel reschedules a thread, it stores the stack register and changes the stack register to the new stack. if may or may not need to store the program counter depending on the way is does scheduling.

The cache has nothing to do with either stack or heap. It is managed by the processor and provides a way to ensure that data needed by the CPU is close at hand so that it does not have to wait for the bus to fetch it. It is totally up to the CPU to ensure that what is in main memory is the same as what is stored in the cache. The only time one really needs to worry about cache is when using DMA. The one will have to manually flush or sync the cache to ensure that the CPU does not trust the cache and actually fetches data from main memory.