If this article is news for you, this might be a helpful corollary:
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.
Address spaces are just an implementation detail. You can have both processes and threads on an architecture without any such concept. The point -- the theory -- behind processes, is to separate your heap from your neighbor's heap, so pointers in your heap pointing at addresses in theirs won't be valid, or vice-versa. You could do this with virtual-memory mapping, memory segmentation, tagged pointers, domain-taint as static type checking, etc. and you'd get the same result.
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 an ISO C or C++ program (or a higher-level language/abstraction), then the stack and heap are your primitives and address spaces are an implementation detail.
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'm not talking about programming, I'm talking about computer science. A heap (really, an object reference digraph) is a mathematical object that you can prove theorems about. An address space is just one way to isolate a block of memory, a way to enforce on a Von Neumann architecture the preconditions that allow for that mathematical object to be instantiated and manipulated. Not every machine is an x86 with an MMU.
> A heap (really, an object reference digraph) is a mathematical object that you can prove theorems about.
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.
I'd argue against there being "only 1 heap". Only one OS provided heap, sure, but in C++ it is quite common to overload new and allocate into a separate statically declared buffer.
(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.
I wouldn't call a heap a "data structure", though. It will lead to mighty confusion, as heap-the-data-structure has nothing to do with heap-in-which-you-allocate-memory.
The CLR has at least two that I'm aware of, the "regular" heap (not sure if it has a special name) and the Large Object Heap. Pretty sure there are unmanaged heaps associated with a single .NET process as well -- certainly there are if you are mucking around with things like managed C++.
The stack is a concept that's built into the CPU to handle function calls. Every time you call a function, there is a return address that needs to be stored. Since you need to hang on to a return address for every function that is currently in progress, and you use them in the reverse order that they were stored, what you need is exactly a stack. The stack is usually (always?) located at the top of memory and grows down. In addition to return addresses, it can be used to store data associated with an in-progress function, like arguments, local variables, and cpu state data that needs to be temporarily stored.
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.
The concept of the stack is built into the CPU? That's news to me... I mean, I'm not a hardware guy so I guess I could have been misinformed, but I thought it was something the OS managed as a reserved chunk of main memory (like the heap).
Registers are built into the CPU, but that's a different thing than the stack.
In the x86 family anyway, it's kinda-sorta 'built in'. It is possible to avoid using the stack -- it's done in interrupt handlers which do not have a stack of their own and must avoid clobbering it -- but most code uses it fairly frequently and there are many auxiliary instructions that push and pop from 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.
Lots of smaller microprocessors live by the stack. Aside from the typical JSR/RET stuff with pushing the program counter, you can also do very lightweight programming tricks with the stack pointer.
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.
Yes I think it's better to say this in a more limited way: certain CPU instructions such as push, pop, and call manipulate the stack pointer register in a way that assumes common stack conventions.
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.
I don't know about all architectures, but I took a peek at ARM and it has a stack pointer register and built-in instructions that use the stack. So that's Intel and at least one RISC cpu that assume a stack.
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.
It would quickly become painful to only transfer execution with JMP-instructions -- you'd need some way to keep track of either how to return, or where you'd be going next (this is exactly equivalent to only using GOTOs for control flow -- and as we know, considered harmful).
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).
While some architectures have some special instructions/registers for handling stacks I still wouldn't say it's built into CPUs. The direction in which a stack grows depends on the architecture. Some programming languages don't have one stack and one heap that grow into each other but instead several memory areas while still being single threaded (I think prolog or some logic oriented languages have such a more complicated concept).
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.
The call instruction on x86 automatically writes a return address to the stack, and I suspect that that's a standard instruction across architectures. That's sufficient to make my point that the CPU expects a stack.
Some architectures write the return address into a register and not onto the stack. The calling function has to preserve it's return address somehow, yes, but that isn't done for you (well, a compiler does it for you, but not an assembler). So if all parameters are passed via registers and the function does not need more memory than the registers provide for the calculation, then this kind of function does not need to access the stack at all.
I remember the first time when I worked on multithreaded C++ project. I allocated a structure on the stack and passed its address to a queue which was received by another thread and the inevitable segfault happened. My mistake provided a lot of laughs for the entire team.
I understand what you meant but to be a bit pedantic, you can freely allocate structures on the stack and pass it around. You might have heard of a few of them .. cout, cin :P
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.