This document provides some basic information that you may need to fully understand the topical documents provided at this web site.
Figure 1 is used to define the memory elements of any program via a graphical representation. This diagram is a depiction of memory and will be used to illustrate how the various entities of a C or C++ program are stored within the computer memory.
The entire area of figure 1 represents the memory in the computer, including the area to the right that looks like a ladder. All of the executable code and all of the variables within any given program are stored within the area illustrated by this diagram. The big question is, “How are the various entities stored in this space?”
There are three areas of memory that have special capabilities assigned by the compiler and linker. They are listed as follows;
Stack – The area that looks like a ladder on the right part of the diagram is the stack. The stack is allocated by the system to be a fixed size and is filled as needed from the bottom to the top one element at a time. Elements are removed from the top to the bottom one element at a time. Thus the last element added to the stack is the first element that is removed when no longer needed. Any element on the stack is potentially available for reference or modification by the executing code, but elements are added and removed only from the top.
Heap – This is the area within the box named the heap. This is allocated by the system to be of a fixed size and is used by the system as needed in a random fashion. By random, it does not mean that there is any disorder to the way this area is used, it means the memory is not assigned in any particular order. It can in fact be assigned in blocks as needed from anyplace within the heap. Any memory within the heap that is not currently allocated for use by the program is stored in the “free list”, a list of memory blocks that can be assigned to the program as needed.
Global Memory – This is all of the memory on the machine that is not assigned to the stack or the heap.
As an aid to clarity, all keywords, identifiers, and function names used in the text portion of these documents will be given in bold type.
WHAT ABOUT A MULTI-USER ENVIRONMENT?
We are assuming a single user computer for simplicity. In the case of a multi-user system, each user is assigned a block of memory which is carved up as shown here so that the same principles apply to each user.
HOW IS GLOBAL MEMORY ASSIGNED
The block of code that is the main() program is stored in global memory and every function that is required for the program to execute is also stored somewhere in global memory. Even though the system will assign the various blocks of code in a very orderly manner, we must assume that they are actually assigned in no particular order. In fact we should assume that they are randomly assigned all over the global storage area and that any particular function is not contiguous to any other function.
Note that some compilation/linking systems permit you to locate code and variables where you want them in memory, but that is beyond the scope of this document.
Figure 1 contains a box with the title main(). This box represents the block of code for the main() program. Even though all of the functions in any program appear as code blocks within the global memory, we will not include them in any of the remaining figures since they don’t interact in a manner that is conducive to this discussion. You can therefore assume that the code is there, ready to be executed, but since it will clutter up the drawings, we will not show it or discuss it any further.
A GLOBAL VARIABLE
We are very interested in the small boxes near the top of figure 1 because they represent global variables which are stored in global memory. The system carves out enough memory to store the variable in question and assigns that memory to the variable. The global variable exists for the entire time of program execution.
Note that a char type variable usually uses only one byte of storage, but a double type variable will use about 8 bytes of storage. Even though they use different amounts of memory, we will not be concerned with that in this discussion since we are not interested in that level of detail. Therefore, the box labeled variable can store a char, an int, a double, or any other simple variable and the system will assure that there is enough room to store the entity that we have requested. Even though the boxes are all the same size in this graphical representation, they may be referring to different amounts of physical memory.
We may have several global variables declared in our program, but we will not assume that they are stored contiguously, since the compiler is not compelled to store them in any order convenient to us. We will assume that they are randomly stored throughout the available global memory even though we know that every C or C++ compiler will probably assign them in some contiguous manner.
A GLOBAL POINTER
The box labeled pointer has the ability to store any one pointer of any type. Pointers are generally the same size for all data types on any given combination of hardware and run-time system, so they are probably all allocated the same number of bytes. The dot is the authors convention to indicate that the box is a pointer rather than a simple variable, and when the dot is unadorned as shown here, the pointer has not yet been assigned to point to anything in particular. In fact it may contain any value which means it may be pointing anywhere within the entire memory space of the computer, although by definition, a global pointer is initialized to NULL. When the pointer has been assigned an address, it will have an arrow pointing from the dot to the entity to which it is pointing. This will be clear when you see it used in the discussions.
Any number of pointers and variables can be stored in the global memory up to the limit of available memory.
HOW IS THE STACK USED?
As variables or pointers are needed by the system, they will be assigned to the stack sequentially starting at the bottom with each successive element being “stacked” on top of the others, or assigned the next location towards the top of the diagram. Each box in the pictorial of the stack can store any one of the simple variables in the same manner as we defined for global memory storage, independent of the size of the variable. (The system knows how many bytes it takes to store each type of variable and it will take care of the various sizes automatically.) Once a variable is stored on the stack, it can be referred to by the code that put it on the stack, so it is a variable available for use in much the same manner as the global variables are available. However, when the program is done using the data on the stack, it can be discarded to allow the stack to be used for other data when needed. This is probably unclear at this point, but it will make more sense when we get to the actual usage.
Think of the stack as growing upward as needed and shrinking downward when some of the data is discarded because it is no longer needed.
HOW IS THE HEAP USED?
The heap is a contiguous block of memory that is available for use by any part of the program whenever it needs it and for as long as it needs it. When the program requests a block of data, the dynamic allocation scheme carves out a block from the heap and assigns it to the user by returning a pointer to the beginning of the block. When the system is finished using the block, it returns the block to the heap where it is returned to the pool of available memory called the free list. This is called deallocation.