Introduction to Dynamic Storage Allocation

Key Insight

The need for dynamic storage allocation arises when data structures, which may independently grow and shrink, share a common pooled memory area and require variable-sized nodes. While some applications can use a uniform node size by taking the maximum needed or by 'planting a link' to additional storage, many others necessitate nodes of varying sizes. These variable-size blocks must consist of consecutive memory locations and are managed by dynamic storage allocation algorithms. Different approaches exist based on typical block sizes: small (e.g., 1 to 10 words) for simulation programs, or large for operating systems.

A primary challenge is representing the partitioning of memory into reserved (in use) and free (available) blocks. A typical memory map, or 'checkerboard', shows this mix, for example, 53 reserved blocks mixed with 21 free blocks. The conventional solution is to maintain a list of available space, often within the available space itself, rather than a separate directory. The first word of each free storage area typically contains its size and the address of the next free area. These free blocks can be linked together in increasing or decreasing order of size, in order of memory address, or in essentially random order.

For instance, consider a memory of 131072 words, addressed from 0 to 131071. If available blocks are linked by memory location, a variable AVAIL would point to the first free block (e.g., location 0). Locations 0 through 100 might form the first available block. After reserved areas like 101–290 and 291–631, more free space might exist in locations 632–673. This structure allows the system to track and utilize available memory segments effectively for subsequent reservation requests.