Dynamic Data Structures: The Heap
A typical personal computer or workstation today has somewhere between 16 and 64 megabytes of RAM installed. Using a technique called virtual memory, the system can swap pieces of memory on and off the machine's hard disk to create an illusion for the CPU that it has much more memory, for example 200 to 500 megabytes. While this illusion is complete as far as the CPU is concerned, it can sometimes slow things down tremendously from the user's perspective. Despite this drawback, virtual memory is an extremely useful technique for "increasing" the amount of RAM in a machine in an inexpensive way. Let's assume for the sake of this discussion that a typical computer has a total memory space of, for example, 50 megabytes (regardless of whether that memory is implemented in real RAM or in virtual memory).
The operating system on the machine is in charge of the 50-megabyte memory space. The operating system uses the space in several different ways, as shown here.
This is, of course, an idealization, but the basic principles are correct. As you can see, memory holds the executable code for the different applications currently running on the machine, along with the executable code for the operating system itself. Each application has certain global variables associated with it. These variables also consume memory. Finally, each application uses an area of memory called the stack, which holds all local variables and parameters used by any function. The stack also remembers the order in which functions are called so that function returns occur correctly. Each time a function is called, its local variables and parameters are "pushed onto" the stack. When the function returns, these locals and parameters are "popped." Because of this, the size of a program's stack fluctuates constantly as the program is running, but it has some maximum size.
As a program finishes execution, the operating system unloads it, its globals and its stack space from memory. A new program can make use of that space at a later time. In this way, the memory in a computer system is constantly "recycled" and reused by programs as they execute and complete.
In general, perhaps 50 percent of the computer's total memory space might be unused at any given moment. The operating system owns and manages the unused memory, and it is collectively known as the heap. The heap is extremely important because it is available for use by applications during execution using the C functions malloc (memory allocate) and free. The heap allows programs to allocate memory exactly when they need it during the execution of a program, rather than pre-allocating it with a specifically-sized array declaration.