Dynamic Memory Management: Strategies and Techniques

8.5 Dynamic Memory with Reservation — 8.5.1 General Features

Dynamic memory is essential for managing dynamic structures like lists, trees, and graphs. It's heavily used in object-oriented programming, where each object resides in the heap.

Key heap operations include allocation (e.g., malloc in C, new in C++) and deallocation (e.g., free in C, delete in C++). These operations are handled by a dedicated library that manages dynamic memory.

Allocation involves assigning a memory block of a specific size. Deallocation frees a memory block, allowing its reuse for future allocations. Effective heap management requires techniques to optimize space usage and the execution time of allocation and deallocation operations.

8.5.2 Fixed-Length Blocks

In this approach, the heap is managed as a linked list of equally sized blocks. Only the pointer to the first block is stored. Allocation involves assigning the first block, while deallocation places the freed block back as the first block.

8.5.3 Heap with Simple Structure

Here, the heap is managed as a linked list of variably sized blocks. Again, only the pointer to the first block is stored. Each block's structure is as follows:

Allocation

• First-Fit Strategy: Traverse the list until a block of sufficient size is found. The block is split into two: the allocated memory is returned, and the remaining portion becomes a new, smaller block.
• Best-Fit Strategy: Search for the block with the size closest to the requested memory. This strategy can lead to fragmentation and is less common.
• Worst-Fit Strategy: Always allocate the largest available block. This can be problematic as it depletes large blocks needed for larger objects.

Deallocation

• Place the freed block at the top of the list. This can fragment larger blocks, hindering contiguous block merging.
• Maintain a list sorted by memory location. This requires inserting the freed block in its correct position (slower), but facilitates faster block merging.