Dynamic Memory Allocation: Justifiably Taboo?

Anbieter zum Thema

An Overview of Dynamic Memory Management

Dynamic memory allocation was popularized with the C programming language and Unix systems in the late 60’s and early 70’s, and is present in virtually all modern operating systems and programming languages.

To implement dynamic memory allocation, the C runtime library provides malloc() and free() functions that allow applications to allocate and release memory as needed, during a program’s execution. Free memory is colloquially called the “heap.” The function of memory allocation mechanisms used “under the covers” in dynamic allocation (we will refer to these mechanisms as “allocators” or “memory managers”) is to organize the heap in some coherent way. They must satisfy requests for dynamic memory allocation by assigning a portion of the heap to a requesting task, and to return memory to the heap for subsequent use when the task relinquishes that memory.

An allocator keeps track of which parts of memory are in use and which are free. A design goal of any allocator is to minimize wasted memory space, balancing the amount of wasted space against the time and processing resources needed to recover it. A major objective of allocators is to limit the fragmentation that occurs when an application frees memory blocks in a random order.

In dynamic allocation, the heap is commonly managed with what is known as a “list allocator.” It organizes the heap into a singly-linked chain of pointers, where each link in the chain points to a free block of memory. Each free block (in a 32-bit system) requires 8 bytes of overhead that we call “meta-data”; 4 bytes for the chain pointer, and 4 bytes to record the size of the free block (diagram 1).

To satisfy a request for memory allocation, the allocator walks the chain of pointers until it finds a free block that is large enough to satisfy the allocation request. If it cannot find a block of memory large enough, it returns a NULL pointer. If it finds a block large enough, and if the block is exactly the right size, it unlinks the block from the chain and returns a pointer to it back to the application.

Otherwise, the block is divided into one “chunk” that is the requested allocation size, and a remaining piece. The remainder is linked back into the chain and the pointer to the allocated memory is returned to the application. When memory is subsequently freed, it is linked back into the chain. If the newly freed block happens to be adjacent to an already free block, then the free blocks are joined together to form a single larger block, minimizing fragmentation (see below).

(ID:44195367)