Chapter 17: Free-Space Management

Overview

• Free-space management is crucial in memory management systems, both in user-level libraries (e.g., malloc) and operating systems.
• The challenge arises in handling variable-sized free spaces due to external fragmentation.

Problem of External Fragmentation

• Occurs when free space is divided into non-contiguous chunks.
• Results in failed requests despite sufficient total space because the space is not contiguous.

Key Questions

• How to manage free space for variable-sized requests?
• Strategies to minimize fragmentation.
• Time and space overheads of different approaches.

Assumptions

• Focus on allocators in user-level memory allocation libraries.
• Interface similar to malloc and free.
• Primary concern is external fragmentation.
• Memory cannot be relocated once allocated.

Low-level Mechanisms

Splitting and Coalescing

• Splitting: Divides a free chunk to satisfy a smaller request.
• Coalescing: Merges contiguous free chunks when memory is freed.

Tracking Allocated Region Size

• Uses a header before each allocated block to store size and other metadata, allowing size retrieval during free.

Embedding a Free List

• Builds the free list within the free space itself.
• Initializes with a single large chunk when the system starts.

Growing the Heap

• When the heap is out of space, allocators may request more memory from the OS, e.g., using sbrk in UNIX.

Basic Strategies for Free-Space Management

Best Fit

• Searches for the smallest free chunk that fits the request.
• Reduces wasted space but can be inefficient due to exhaustive search.

Worst Fit

• Opposite of best fit, using the largest chunk available.
• Generally performs poorly due to fragmentation.

First Fit

• Finds the first chunk that fits the request.
• Faster but can lead to fragmentation at the beginning of the list.

Next Fit

• Similar to first fit but continues search from the last allocation point.
• Spreads allocations more uniformly.

Advanced Approaches

Segregated Lists

• Uses separate lists for frequently requested sizes to reduce fragmentation and speed up allocation.

Buddy Allocation

• Divides memory into blocks of power-of-two sizes.
• Simplifies coalescing by maintaining buddy pairs.

Challenges and Considerations

• Scalability issues in searching the free list.
• Advanced data structures can improve performance.
• Importance of understanding workload for allocator tuning.

Summary

• Allocators exist at various levels, from user programs to the OS.
• Building efficient and scalable allocators remains a challenge.