The difference between heap and stack in an operating system

Preliminary knowledge:

The executable program is stored in three parts: code area, data area and uninitialized data area (BSS).

  1. Code area: holds machine instructions executed by the CPU. The common code area is shareable (it can be called by other executables) because frequently executed programs require only one piece of code in memory. Also, code areas are usually read-only to prevent programs from accidentally modifying their instructions. There are also code areas that plan local variable related information.

  2. Global initialization/static data area: contains global variables that are explicitly initialized in the program, static variables (including global and local static variables), and constant data. For example, a declaration (global data) that is not in any function: int maxcount=99; Causes the variable maxCount to be stored in the initialization data area based on its initial value.

  3. Uninitialized data area (BBS) : Stores global uninitialized variables. BSS data is initialized to 0 or NULL by the kernel before program execution begins. For example, a declaration that is not in any function:

long sum[1000]; Store the variable sum in the uninitialized data area.

The memory occupied by a running C compiler includes the code area, initialized data area, uninitialized data area, and heap area and stack area:

  1. Code area: code area instructions are executed sequentially according to the program design process. For sequential instructions, each process will only execute once. If repeated, jump instructions need to be used. The instructions in the code area include the opcode and the object (or object address reference) to operate on. If it is an immediate number (that is, a concrete value, such as 5), it will be included directly in the code; If the data is local, space is allocated in the stack area and the data address is referenced. If it is a BSS section and a data section, the data address will also be referenced in the code.

  2. Globally initialized data area/static data area: initialized only once.

  3. Uninitialized data area (BSS) : Changes its value at run time.

  4. Stack: Automatically allocated by the compiler to hold function parameter values, local variable values, etc. It operates like a stack in a data structure. Whenever a function is called, the function returns the address and some information about the call, such as the contents of certain registers, is stored in the stack area. The called function then allocates space on the stack for its automatic and temporary variables. This is how C implements recursive calls to functions. For each recursive function call, a new stack frame is used so that variables in the new instance stack are not confused with variables in the other instance stack of the function.

  5. Heap: Used for dynamic memory allocation. The heap is located in memory between the BSS area and the stack area. Generally, it is allocated and released by the programmer. If the programmer does not release it, it may be reclaimed by the OS when the program ends.

The difference between heap and stack

  1. Management is different. Stack compiler automatic management, without programmer manual control; However, the application and release of heap space is controlled by programmers, which is easy to cause memory leakage.

  2. Space sizes vary. A stack is a data structure that extends to a lower address and is a contiguous area of memory. The address of the top of the stack and the maximum capacity of the stack are predetermined by the system. If the requested space exceeds the remaining space of the stack, the overflow will be prompted. Therefore, the user gets less space from the stack. A heap is a data structure that extends to a higher address and is a discontinuous area of memory. Because the system uses a linked list to store free memory addresses, and the traversal direction of the list is from low address to high address. Thus, the heap has more flexible and larger space. The elements in the stack are one-to-one, and there is no memory block popping out of the middle of the stack.

  3. Whether fragments are generated. In the case of the heap, frequent malloc/free (new/delete) is bound to cause discontinuity in memory space, resulting in a large amount of fragmentation, which makes the program inefficient (although the operating system manages memory reclamation after the program exits). For stacks, this problem does not exist.

  4. Growth is going in different directions. The heap grows in an upward direction, that is, in the direction of increasing memory addresses; The stack grows downward, in the direction of decreasing memory addresses.

  5. The distribution is different. The heap is allocated dynamically by the malloc() function in the program and freed by the free() function; Stack allocation is done by the compiler. Dynamic allocation of the stack is done by the alloca() function, but dynamic allocation of the stack is different from that of the heap. Dynamic allocation of the stack is allocated and freed by the compiler without manual implementation.

  6. The efficiency of allocation is different. The stack is a data structure provided by the machine system. The computer provides support for the stack at the bottom level: special registers are allocated to store the address of the stack, and special instructions are executed to push and unload the stack. Heap is a C function library, its mechanism is very complex, for example in order to allocate a block of memory, library functions will be according to certain algorithm (specific algorithm can reference data structure/operating system) search in the heap memory has enough space available, if there is no enough space (which may be due to too much memory fragments), there is need to reorganize the operating system memory space, This gives you a chance to get enough memory and return. Obviously, the heap is much less efficient than the stack.

Differences in data structures

The heap

Similar to a tree structure, there are large root heaps (the value of the parent is less than or equal to the value of the children) and small root heaps (the value of the parent is greater than or equal to the value of the children)

The stack

The stack is a first-in-last-out (FILO) data structure