A small detour — and a debt to pay. The segmentation chapter ended with physical memory full of odd-sized holes; this chapter is about living with them. The problem is fundamental to any memory manager, whether a malloc malloc The C library call requesting heap bytes (size via sizeof()); returns a pointer, or NULL on failure. A library call, not a system call. defined in ch. 14 — open in glossary library managing a process’s heap heap Memory region for explicitly requested dynamic allocations — malloc() and free() in C. defined in ch. 4 — open in glossary or the OS itself managing physical memory under segmentation.
When the managed space is divided into fixed-sized units, the job is easy: keep a list of them; a client wants one, return the first entry. (Hold that thought — it’s called paging, and it’s next chapter.) The difficulty — and the fun — arrives with variable-sized units, where external fragmentation external fragmentation Free physical memory chopped into little non-contiguous holes by variable-sized allocations, so a request can fail even though enough total free space exists — e.g. 24KB free in three chunks cannot satisfy a 20KB segment. defined in ch. 16 — open in glossary lurks:
click a region marked ⓘ for details
The free list free list The OS structure tracking unused physical memory ranges, searched at process creation and refilled at termination. defined in ch. 15 — open in glossary for this little heap has two entries — and no answer for a 15-byte request:
The free list: two 10-byte chunks, no 15-byte answer
len:10→addr:20
len:10→NULL
The Crux: How To Manage Free Space
How should free space be managed, when satisfying variable-sized requests? What strategies can be used to minimize fragmentation? What are the time and space overheads of alternate approaches?17.1 Assumptions
The chapter draws on the great history of user-level allocators (Wilson et al.’s survey — nearly 80 pages, so you really have to be interested). The ground rules:
| what we assume | |
|---|---|
| The interface | void *malloc(size_t size) and void free(void *ptr) |
| The arena | a region historically called the heap; its free chunks tracked by a free list |
| The enemy | external fragmentation (mostly) |
| No relocation | once handed out, memory cannot be moved until freed |
| One fixed region | the allocator manages a single contiguous byte range of fixed size |
Two of these deserve a second look. The interface’s missing size parameter means the library must remember, for every outstanding chunk, how big it is — that bookkeeping is where the mechanisms section begins. And no relocation means compaction compaction Rearranging allocated segments into one contiguous region (stop the process, copy its data, update its segment registers) to cure external fragmentation — effective but memory- and CPU-expensive. defined in ch. 16 — open in glossary — chapter 16’s cure — is unavailable here: compacting works for an OS moving whole segments (one base register redirects everything) but not for a library whose clients hold raw C pointers. The allocator must fight fragmentation without ever moving a granted byte.
Check yourself
1.Why is free-space management trivial with fixed-sized units, but a whole chapter with variable-sized ones?
2.free(void *ptr) takes no size parameter. What does that force upon the allocation library?
3.Chapter 16 offered compaction as fragmentation's cure. Why is that off the table for a malloc library?
4.The 30-byte heap: bytes 0–10 free, 10–20 in use, 20–30 free. A request for 15 bytes arrives.