What and where are the stack and heap?
stackoverflow.com
stackoverflow.com
Threads and processes are both units of execution. (A unit of execution is like a virtual processor -- a separate instruction pointer that makes its way through your code, doing computations and following jumps.)
Both threads and processes have their own stacks. You reserve a new stack when you fork(), or when you spawn a thread.
But only processes have their own heaps. In fact, this is the defining distinction between threads and processes: if you're sharing your heap with other execution-units, you're a thread; if you have your own isolated heap, you're a separate process.
grandparent is confusing the concept of address space and heap.
Why only the heap? Since pointers on the stack can only (coherently) point into the same stack, or to the heap--and pointers on the heap can't point back into any stack--then stacks are already isolated. (Registers follow the same isolation rules as stack entries, if you want a register-machine.)
The reason you want to isolate your heap in the first place, the benefit you get, is that an isolated heap is an isolated graph for any garbage-collection system to pass over, and an isolated set-of-blocks-of-bytes for an exception to throw out or the OOM killer to discard. As soon as you have an isolated heap, in other words, you get all the practical advantages that come with running in a separate process.
If you implement a bytecode interpreter that can concurrently switch between several instruction pointers with their own stacks, then you've implemented green-threads. If each of those instruction pointers also has their own heap, you've implemented virtual processes.
If you are programming to the level of abstraction of POSIX, then address spaces are fundamental and the stack and heap are just convenience interfaces around mmap().
The fact that the StackOverflow question was asking for more OS-level details than the existing explanations they had found suggests that this is the time to provide actual implementation details instead of answering in more abstractions.
I could condescendingly lecture people about blueberry ice cream, but that also wouldn't have any relevance to the topic at hand.
So is a Pseudo-Riemannian manifold. But neither of these is what the person was asking questions about. They were asking about programming on computers with operating systems.
(See: Video games!"
And, as usual, no mention was made of static allocations! :(
Heaps for allocating textures. Object-type-specific heaps for things like sounds and models. "Smart" heaps that can invalidate their contents under memory pressure (and maybe automatically bring stuff back in, possibly speculatively). Heaps that are good for lots of small allocations. Heaps that either do or do not allow multiple threads to use them. Heaps that are position-independent and that can be used in shared memory buffers (which can be mapped to different addresses in different processes). I could go on.
I wrote a lot of the memory management stuff for the Apple Newton, and it had several types of heaps:
- A common "Macintosh-like" heap with both fixed and sliding blocks (even with a VM system managing the page for you, fragmentation matters when memory is tight). Most threads played in this heap, and keeping it sane was kind of hard.
- A couple of heaps for the kernel, for managing its objects (it's been a while, I don't remember why there was more than one).
- A heap that could supply (limited) amounts of memory for interrupt handlers.
- The NewtonScript object heap (owned by the NewtonScript environment).
I'm pretty sure there were a couple more heaps, but I've forgotten the details. Our main worry was fragmentation, and I'd say that things probably weren't segmented enough and that we needed even more heaps than we shipped with.
A heap is just a data structure. Ain't nothing magic.
So that's the stack. The concept of the heap, on the other hand, isn't built into the CPU, and is sort of a vague abstraction implemented by programming languages. The first thing to know about how it differs from the stack: it's not a stack. Stack reads and writes follow LIFO; reads and writes to the heap can potentially be in any order. The heap is usually (always?) located close to the bottom of memory, and grows up. So the stack and heap grow toward each other. At the lowest level, the heap is basically just memory that can be used as the application sees fit. Data on the heap isn't inherently tied to an in-progress function call, so it can last indefinitely (at least, until the process ends). The programming language or the C library typically provide a means to subdivide the heap memory into discrete blocks as needed in response to an explicit or implicit memory allocation request (e.g. malloc(), new), and keep track of what memory is available and what is currently allocated.
Differences between the stack and the heap:
* the stack is limited in size, so it is easy to overflow and crash if you try to store too much data there. the heap, in contrast, is designed to grow as much as needed * the stack is managed primarily by instructions built into the cpu. the heap is managed by library calls and system calls * the difference in speed between the two refers to the speed of allocating or freeing a chunk. the stack can inherently do this quickly, because the location for the memory is predetermined. since the heap can do allocations and deallocations in any order, finding memory for blocks is inherently more complicated and slower. * since the fundamental purpose of the stack is to store data about in-progress functions, it follows that every executing thread has its own stack and usually only accesses its own. the heap, on the other hand, has no association to a thread of execution, which consequently means that multiple threads can share the same heap, and locking and synchronization must come into play when the heap metadata has to change. The locking is typically transparent, but the net result is to make allocations and deallocations even slower in threaded code.
Registers are built into the CPU, but that's a different thing than the stack.
In addition to some explicit stack-related instructions like PUSH/POP, PUSHF/POPF, PUSHA/POPA, PUSHAD/POPAD and many others, certain other operations assume you have a valid stack and act on it. For example, the CALL function (used to call a procedure/function) will push a return address to the stack, and RET (used to return to the caller at the end of a procedure/method) will pop the return address to the stack and jump to it.
These instructions are fairly essential to the function calling conventions for typical code, enough that it's reasonable to say that the concept of the stack is 'built into' x86 processors.
Partly this is because the x86 processor is a beast with an instruction for everything. Other more RISCy architectures tend to not bake in the stack, and instead you use any general-purpose register as a stack pointer and manipulate it manually with regular instructions.
For example, you can pass arguments to an assembly subroutine by putting the data right after the JSR call. The called subroutine pulls the args by manipulating the stack pointer and the return will jump PC after the argument date.
You can also use stack pointer to briefly allocate a small amount of memory for scratch inside a routine instead of allocating heap or using globals. This is a big help on small micros where you might get a scratch register or two normally but now you need 4 or 8 bytes for a quick piece of work.
One interesting thing is that the implementation of these instructions do specify the question of whether the stack grows up or down. On x86 these instructions subtract from rsp when they want to grow the stack, ergo on x86 the stack grows down.
Of course, you can probably write programs with no stack, and never use the stack instructions, or even put them to other purposes. But there are probably performance reasons for having instructions that automatically manipulate a function call stack, and it would be hard to live without any functions.
I suppose on x86 you could create a calling convention where you store a return address in a register or something -- but on 32bit you're already rather short on registers. It would probably be more (if still not really) sensible on amd64.
I only see this as viable for rather simple state-machine designs -- but I suppose you could also just generate machine code that read return addresses from an area of memory or something ("the tape" in Turing parlance).
Management of the stack is done by the program, not by the OS. How the program does it depends on the language and unless you use assembler it is hidden by the compiler. There is a calling convention, not one single way a call works. Some C compilers expose ways to define a different than the standard calling convention for a function. You might say that how a function call works is to much detail and not what you understand about how the stack works. Anyway, some languages have segmented stacks, meaning if a stack is used up a new stack is allocated and referred to by the old one (rust supported this at some point).
There are also languages that have different heaps per thread (rust for gc-ed objects). Per-thread heaps are a good idea because otherwise you would need to use some sort of synchronization for malloc and free, which defeats the purpose of threads. Usually this is done by reserving a memory area for a thread and only when this is exhausted and a new memory area needs to be allocated some sort of potentially blocking call (I think usually mmap?) for another area is called.
Also see http://stackoverflow.com/questions/8468210/stack-vs-heap-c