Lesson 8.5: Fragmentation

01 Introduction

Lesson 8.4 presented contiguous allocation and the three placement algorithms. It showed that first-fit is generally the best of the three on real workloads, that worst-fit fails on the canonical example, and that the free list is maintained by splitting regions when they are allocated and coalescing them when they are freed. In passing, it introduced the term fragmentation and used it to explain why worst-fit fails and why coalescing is necessary. This lesson examines fragmentation directly. It defines the two forms of fragmentation, explains their causes, quantifies their impact, and presents the techniques that reduce them.

The problem is simple to state. A memory system has a fixed total capacity, and it must serve a stream of allocation and free requests whose sizes vary over time. After a while of operation, the memory is divided into a pattern of allocated blocks and free holes. If a new request arrives and no hole is large enough — even though the total free memory is larger than the request — the request fails. The memory is not full; it is fragmented. The free memory is present but in the wrong shape.

Fragmentation is not an implementation detail; it is a fundamental consequence of the way allocation and freeing interact. Any system that allocates variable-sized blocks from a shared pool and frees them in a different order than they were allocated will fragment. The fragmentation is not caused by a bug in the allocator; it is caused by the workload's pattern of requests. It can be reduced by clever allocation policies, but it cannot be eliminated in a scheme that allocates variable-sized blocks.

This lesson presents the two forms of fragmentation, with examples of each. It presents the 50-percent rule, a statistical observation about first-fit allocators that quantifies the amount of memory lost to fragmentation. It presents the fragmentation ratio as a metric for measuring the fragmentation of a system. And it presents the three principal techniques for reducing fragmentation: compaction (revisited from Lesson 8.4), the buddy system, and segregated free lists including the Linux kernel's slab allocator. The lesson closes with a discussion of the relationship between fragmentation and paging, which is the ultimate solution to the problem.

Prerequisites

This lesson builds directly on Lesson 8.4. The free list, the placement algorithms, splitting, and coalescing are assumed. Familiarity with the canonical workload from Lesson 8.4 — five holes and four requests — is useful for the worked example, which reuses the same setup. The base-and-limit scheme from Lesson 8.2 is referenced in the discussion of compaction. No prior knowledge of the buddy system or the slab allocator is assumed; both are introduced here.

02 Learning objectives

By the end of this lesson you will be able to

Define external fragmentation and internal fragmentation and distinguish between them.
Explain how fragmentation arises from the interaction of allocation and freeing.
State the 50-percent rule and explain its significance for first-fit allocators.
Measure the fragmentation of a memory system using the fragmentation ratio.
Describe the buddy system, segregated free lists, and the slab allocator, and explain how each reduces fragmentation.

This lesson contributes to U8.4 and U8.5, and to course learning outcomes CLO1, CLO4, and CLO6.

03 Required reading

Operating System Concepts — Chapter 9, Section 9.2, Contiguous Memory Allocation, and Section 9.3, Paging, through the discussion of fragmentation. The classical definitions of external and internal fragmentation.
Tanenbaum & Bos — Modern Operating Systems, Chapter 3, Section 3.2, A Memory Abstraction: Address Spaces. The discussion of fragmentation in the context of variable-size partitions, and the presentation of the buddy system.
OSTEP — Chapter 17, Free Space Management. The clearest available treatment of the mechanisms that reduce fragmentation: segregated free lists, the binary buddy allocator, and the allocation policies that keep fragmentation low.
Silberschatz et al. — Chapter 9, Sections 9.2–9.3. Read the discussion of the 50-percent rule and its derivation; the rule is stated in almost every textbook but its derivation is rarely given in full.
Knuth, D. E. — The Art of Computer Programming, Volume 1: Fundamental Algorithms, Section 2.5, Dynamic Storage Allocation. The classical treatment of the statistical behaviour of storage allocators, including the derivation of the 50-percent rule.
Wilson, P. R., Johnstone, M. S., Neely, M., & Boles, D. — Dynamic Storage Allocation: A Survey and Critical Review. Proceedings of the International Workshop on Memory Management, 1995. The most thorough empirical study of fragmentation in real allocators. Read sections 3 and 4 for the empirical results.
Peterson, J. L., & Norman, T. A. — Buddy Systems. Communications of the ACM, 1977. The original paper on the binary buddy allocator.
Bonwick, J. — The Slab Allocator: An Object-Caching Kernel Memory Allocator. USENIX Summer Conference, 1994. The original paper on the slab allocator, which is the basis for the modern kernel allocator.
Linux man pages: man 3 malloc, man 3 malloc_info, man 3 mallopt, man 5 proc (the /proc/buddyinfo and /proc/slabinfo interfaces), man 2 mmap.

Reading strategy

Read the Silberschatz section first for the classical definitions and the 50-percent rule. Then read OSTEP Chapter 17 for the modern techniques — the buddy system and the segregated free list — which are the practical responses to the fragmentation problem. Finally, read the Wilson et al. survey for the empirical results: the theoretical analysis of fragmentation is a poor predictor of the actual behaviour of real allocators on real workloads, and the survey is the best available account of the gap. Pay particular attention to the distinction between fragmentation as a property of the free list and internal fragmentation as a property of an individual allocation; they are different phenomena with different causes and different remedies.

04 Core content

4.1 What is fragmentation?

Fragmentation is the loss of usable memory caused by the way that memory is divided into allocated blocks and free holes. It takes two forms, distinguished by where the wasted memory is located.

External fragmentation: The free memory is present, but it is scattered in pieces that are individually too small to satisfy a request. The total free memory may be larger than the request, but no single contiguous region is large enough. The waste is external to the allocated blocks — it is between them — and it is the characteristic problem of variable-size contiguous allocation.
Internal fragmentation: The memory that has been allocated to a process is larger than the request that the process actually made. The waste is internal to the allocated block: it is the difference between the block's size and the process's request. It is the characteristic problem of fixed-size allocation, where a request for N bytes is satisfied by a block of the next size up.

The two forms of fragmentation are different in their causes, their locations, and their remedies. External fragmentation is caused by the allocation pattern: it is a property of the free list, and it arises because freed blocks are not always adjacent to other free blocks. It is reduced by policies that keep the free list in a useful shape (first-fit, coalescing) or eliminated by paging, which does not require contiguity. Internal fragmentation is caused by the allocation unit: it is a property of the individual allocation, and it arises because the allocator rounds a request up to the next available block size. It is reduced by having many sizes available (so the rounding is small), and it is eliminated only by using variable-size allocation with no minimum block size.

Figure 8.5 — External versus internal fragmentation. External fragmentation is the loss of usable memory because the free regions are too small to satisfy a request; it is a property of the free list, and its remedy is a policy that keeps the free list in a useful shape. Internal fragmentation is the waste within an allocated block when the block is larger than the request; it is a property of the allocation unit, and its remedy is a finer granularity of size classes.

4.2 External fragmentation

External fragmentation is the characteristic problem of variable-size contiguous allocation. It arises from the simple fact that allocated blocks and free holes are interspersed, and that a freed block is not always adjacent to another free block. Over time, the memory becomes a patchwork of allocated blocks and holes, and the holes grow smaller and more numerous.

The canonical illustration is the workload from Lesson 8.4. After first-fit allocates the four processes, the free list is 276, 83, 200, 300, and 174 KB. If a new process requests 400 KB, it cannot be allocated: the largest hole is 300 KB, even though the total free memory is 1,033 KB. The memory is not full; it is fragmented.

The severity of external fragmentation depends on three factors.

The size distribution of requests. If all requests are similar in size, the holes that are produced are also similar in size, and they tend to be useful for future requests. If requests vary widely in size, small holes are produced for small requests and large holes for large requests, and the two kinds of holes do not substitute for each other. The distribution of request sizes in most real workloads is heavy-tailed: many small requests, and a few very large ones. The small requests produce small holes, which are useful only for other small requests; the few large requests produce large holes, which are useful for other large requests. The system's effective capacity is therefore split between the two classes.
The pattern of allocation and freeing. If processes are allocated and freed in the same order (a stack discipline), the holes that are produced are adjacent to each other, and coalescing merges them into a single large hole. If processes are freed in a different order (a heap discipline), the holes are scattered, and coalescing cannot merge them. The former is common in a strictly nested computation; the latter is the norm in a long-running system.
The allocation policy. As Lesson 8.4 showed, the choice of first-fit, best-fit, or worst-fit affects the sizes of the holes that are produced. The policy determines the distribution of hole sizes, and the distribution determines how much of the free memory is usable for future requests.

4.3 Internal fragmentation

Internal fragmentation is the characteristic problem of fixed-size allocation. It arises when a request for N bytes is satisfied by allocating a block of a fixed size S > N. The difference S − N is wasted: it is allocated to the process, but the process cannot use it, and it cannot be given to another process.

Internal fragmentation appears in three common forms.

Fixed partitions. The original multiprogramming systems divided memory into fixed-size partitions. A process that needed less than its partition's size wasted the difference; this was the original motivation for the term "internal fragmentation".
Fixed-size blocks. A memory allocator that provides blocks of a single size (for example, the block allocator of a kernel) rounds every request up to that size. A request for 30 bytes in a system with 64-byte blocks wastes 34 bytes.
Size classes. An allocator that provides a fixed set of block sizes (for example, powers of two, or a geometric progression) rounds every request up to the next size class. A request for 100 bytes in a system with size classes of 64, 128, 256, 512, ... is rounded up to 128 bytes, wasting 28 bytes. The finer the size classes, the smaller the waste per request, but the more classes the allocator must maintain.

The average internal fragmentation of a size-class allocator can be estimated. If the classes are powers of two and the requests are uniformly distributed within each octave, the average waste is about 25 percent of the allocated block. If the classes are more finely spaced — for example, a geometric progression with ratio 1.25 — the average waste drops to about 10 percent, at the cost of more classes and more complex bookkeeping.

4.4 The 50-percent rule

In 1965, Knuth analysed the behaviour of first-fit allocators under a statistical model of allocation and freeing. The result is a remarkable and widely cited observation: under a simple random model, a first-fit allocator loses about 50 percent of its memory to external fragmentation. This is known as the 50-percent rule.

The model is as follows. The allocator serves a stream of requests. Each request has a size drawn from some distribution. The allocator uses first-fit, and it coalesces adjacent free regions when a block is freed. Under a set of statistical assumptions — the request sizes are independent, the interleaving of allocations and frees is random, and the memory is large enough that boundary effects are negligible — the expected number of holes is proportional to the number of allocated blocks, and the expected total size of the holes is about half the memory.

The precise statement is that in the steady state, about half the memory is in holes and about half is in allocated blocks. Of the half that is in holes, most of it is in holes that are large enough to be useful, but a substantial fraction is in holes that are too small for any future request. The effective capacity of the memory — the fraction that can actually be used for future allocations — is therefore less than the nominal total, typically about 50 percent.

The 50-percent rule is a statistical result, not a guarantee. On a workload with a favourable pattern of requests, the fragmentation may be much less; on an unfavourable workload, it may be much more. The rule is valuable as a rough estimate: a first-fit allocator with M bytes of memory can be expected to serve requests whose total size is roughly M/2 before fragmentation prevents further allocations. Beyond that point, the allocator's performance depends on the workload and on the coalescing policy.

The 50-percent rule and real systems

The 50-percent rule applies to a first-fit allocator on a random workload. Real systems rarely match the model exactly: the workloads are not random, the allocators are not pure first-fit, and the memory is not a single uniform pool. The rule is therefore best read as a warning — fragmentation is a serious and roughly-quantifiable problem — rather than as a prediction that will hold for any given system. The Wilson et al. survey found that real allocators on real workloads fragment considerably less than the rule predicts, because real workloads have more structure than the random model assumes.

4.5 Measuring fragmentation

Fragmentation is measured by several related quantities, each capturing a different aspect of the problem.

Fragmentation ratio: The ratio of the largest hole to the total free memory. A ratio of 1.0 means all free memory is in a single hole and any request up to that size can be satisfied. A ratio near 0 means the free memory is scattered into many small holes and few requests can be satisfied. The fragmentation ratio is a useful summary of the free list's shape, but it ignores the distribution of the other holes: a system with one large hole and many small ones may be quite usable, or not, depending on the future requests.
Allocation failure rate: The fraction of allocation requests that cannot be satisfied even though the total free memory is larger than the request. This is the most direct measure of the practical impact of fragmentation. A system with a high failure rate is not usable for its workload, no matter how much total free memory it has.
Effective capacity: The total size of allocations that the system can serve before fragmentation prevents further allocations. A system with M bytes of memory and 50-percent fragmentation has an effective capacity of about M/2. The effective capacity is determined by the workload and by the allocation policy, and it is the quantity that matters most in practice.
Internal fragmentation overhead: For an allocator with fixed size classes, the average difference between the allocated block size and the request size. This is the internal fragmentation of the allocator, and it is measured per allocation rather than in aggregate.

The four measures are complementary. The fragmentation ratio describes the shape of the free list; the allocation failure rate measures the practical impact; the effective capacity summarises the system's throughput; and the internal fragmentation overhead describes the allocator's per-allocation waste. A complete analysis of a memory system considers all four.

4.6 Compaction, revisited

Lesson 8.4 introduced compaction as the technique of moving all allocated blocks to one end of memory, consolidating the free memory into a single region. Compaction eliminates external fragmentation entirely: after compaction, the free memory is one large hole, and any future request can be satisfied from it.

Compaction's cost is the cost of copying every process's address space to a new location and updating its base register. For a system with many processes and large address spaces, this is milliseconds of work, during which the processes must be suspended. Frequent compaction is therefore impractical, and compaction is used only when the fragmentation has grown bad enough that further allocations are failing.

Compaction's principal limitation is that it requires execution-time binding. If the process's internal addresses are absolute, moving the process requires adjusting every reference inside it, which is impractical at runtime. With execution-time binding, the process's addresses are logical, and moving it requires only updating the base register. This is one of the reasons execution-time binding is universal in modern systems, and it is why compaction is possible at all.

In practice, compaction is used less often than the techniques described in the next section. Its cost is high, its benefit is temporary (fragmentation accumulates again after compaction), and the alternative techniques — the buddy system and segregated free lists — reduce fragmentation without requiring the processes to be moved.

4.7 The buddy system

The buddy system is an allocator that allocates memory in blocks whose sizes are powers of two. It was introduced by Knowlton in 1965 and described in detail by Peterson and Norman in 1977. The system is designed to make both splitting and coalescing fast and predictable.

The memory pool is treated as a single large block whose size is a power of two. The allocator maintains a free list per size class: one list for blocks of size 2⁰, one for 2¹, one for 2², and so on up to the size of the pool. When a request for n bytes arrives, the allocator rounds n up to the next power of two, say 2^k, and looks in the list for size 2^k. If the list is non-empty, the first block is allocated. If the list is empty, the allocator looks in the list for 2^k+1; if that list is non-empty, it takes a block, splits it into two blocks of size 2^k — the two buddies — puts one on the 2^k list, and allocates the other. If the 2^k+1 list is also empty, the allocator recurses up the size classes until it finds a block, and then splits it repeatedly on the way down.

When a block is freed, the allocator checks whether its buddy is also free. If so, the two are merged into a block of the next size up, and the process is repeated for the merged block. The buddy of a block is determined by the block's address: two blocks of size 2^k are buddies if they are adjacent and their combined size is 2^k+1, with one starting at an address that is a multiple of 2^k+1 and the other starting at that address plus 2^k. The buddy's address can be computed from the block's address by flipping the appropriate bit.

Figure 8.5b — The buddy system. The memory pool begins as a single block of size 1024. A request for 100 bytes is rounded up to 128, and the allocator splits the pool down through the size classes, allocating one 128-byte block and placing the other split-off blocks on their respective free lists. When the allocated block is freed, the allocator coalesces it with its buddy, and the merge propagates up the tree, restoring the original 1024-byte block. The buddy's address can be computed from the block's address by flipping the appropriate bit.

The buddy system has three properties that make it attractive.

Fast allocation and free. Because blocks are always powers of two, the size class of a request is computed by rounding up to the next power of two, which is a few bit operations. The free lists for the size classes are simple linked lists, and finding a free block is a lookup followed by a pointer-following.
Fast coalescing. The buddy of a block is determined by the block's address, which means the allocator does not need to search the free list to find a block's adjacent neighbours. It computes the buddy's address by flipping a bit, checks whether that address is free, and if so merges. This is much faster than the coalescing in a general contiguous allocator, where the allocator must search a sorted list.
Bounded internal fragmentation. A request for n bytes is rounded up to the next power of two, so the internal fragmentation is at most a factor of two (and on average about 25 percent). This is more waste per allocation than a finer-grained allocator, but it is bounded and predictable.

The buddy system's disadvantage is the internal fragmentation from the power-of-two rounding. A request for 65 bytes is allocated a 128-byte block, wasting 63 bytes — nearly 50 percent of the block. On workloads with many requests just above a power of two, this waste is significant. The system also suffers from external fragmentation within each size class: if a size class has no free blocks but a larger size class does, the allocator must split a larger block, and the split-off pieces may not fit any future request in that size class.

The buddy system is used in the Linux kernel for allocating physical pages. The kernel's page allocator maintains free lists for blocks of 2⁰ through 2¹⁰ pages (that is, from 4 KB to 4 MB), and it uses the buddy algorithm to split and coalesce. The current state of the allocator is visible in /proc/buddyinfo.

4.8 Segregated free lists

A segregated free list allocator maintains a separate free list for each size class. Unlike the buddy system, the size classes need not be powers of two; they can be any set of sizes chosen to match the workload. When a request arrives, the allocator rounds it up to the smallest size class that is at least as large, and it allocates from that class's free list. When a block is freed, it is returned to its size class's free list.

The segregated approach has three advantages.

Fast allocation. The size class of a request is determined by a lookup, and the allocation is a pop from the corresponding free list. No search of a general free list is required, and the allocation time is independent of the size of the free list.
Low internal fragmentation. The size classes can be chosen to match the workload, so that most requests fall into a class that is only slightly larger than the request. A system with size classes at 16, 32, 48, 64, 80, ... has at most 16 bytes of waste per allocation, instead of the factor-of-two waste of a power-of-two scheme.
No external fragmentation within a size class. All blocks in a size class are the same size, so any free block in the class can serve any request for that class. There is no fragmentation within the class.

The disadvantage of the segregated approach is that blocks cannot be moved between size classes. A block allocated for a size-64 request cannot be used for a size-128 request, even if it is free and no size-64 requests are pending. Over time, one size class may accumulate many free blocks while another has none. The allocator must either leave the imbalance uncorrected (which wastes memory in the over-supplied class) or move blocks between classes (which requires splitting and coalescing across classes, reintroducing the complexity that segregation was meant to avoid).

The most sophisticated segregated allocators, such as dlmalloc and its descendants (ptmalloc, jemalloc, tcmalloc), use a two-level scheme: a set of exact-size bins for small requests, and a set of range-based bins for larger requests, with splitting and coalescing across the range-based bins. The result is a fast path for small allocations and a flexible path for large ones.

4.9 The slab allocator

The slab allocator, introduced by Jeff Bonwick in 1994, is a specialised segregated allocator designed for the kernel. Its central observation is that kernels allocate and free objects of specific types — process descriptors, file descriptors, inodes, network buffers — and that most objects of a given type are the same size. The slab allocator exploits this by maintaining a cache for each object type, and a cache pre-allocates a slab of memory — typically one or more pages — for a set of objects of that type.

The slab allocator's cache has three states for its slabs: full, with all objects allocated; partial, with some objects allocated and some free; and empty, with no objects allocated. When an allocation for an object arrives, the allocator takes a free object from a partial slab if one exists, or from an empty slab, or it allocates a new slab. When a free arrives, the object is returned to its slab, and the slab is moved to the appropriate list based on its state.

The slab allocator has three properties that make it particularly suited to the kernel.

No external fragmentation within a cache. All objects in a cache are the same size, so any free object can serve any request for that cache. The fragmentation that a general allocator would suffer is completely eliminated for the object type.
Object initialisation caching. Because objects of the same type share a cache, the allocator can keep an object's constructor and destructor at the cache level. When an object is freed and reallocated, its constructor does not need to be called again if the object can be reused directly. This is a significant performance win for objects that are expensive to initialise.
Hardware cache alignment. Objects within a slab are laid out so that they are aligned to the hardware cache lines. This reduces cache-line conflicts and improves the kernel's performance on modern hardware.

The slab allocator was introduced in Solaris and was adopted by Linux in the 2.2 kernel. The Linux implementation has evolved into SLUB (the default since 2.6.23), which simplifies the metadata and improves performance, and SLOB for memory-constrained systems. The current state of the slab caches is visible in /proc/slabinfo.

4.10 The relationship to paging

Fragmentation is a problem of contiguous allocation. It arises because contiguous regions must be large enough to hold their contents, and freed regions are not always adjacent to other free regions. Every technique in this lesson reduces or manages fragmentation, but none of them eliminates it. The buddy system rounds to powers of two; segregated free lists segregate by size; the slab allocator specialises to object types. Each reduces the fragmentation within its domain, but the fundamental problem — that contiguous allocation fragments — remains.

Paging, the subject of Unit 9, eliminates external fragmentation entirely. A process's address space is divided into fixed-size pages, and the pages are mapped to physical frames that need not be contiguous. Any free frame can hold any page, so there is no requirement that a contiguous region be found. The process's address space can be scattered across physical memory, and the MMU's page table provides the mapping.

Paging does not eliminate internal fragmentation, because a page is a fixed-size unit and the last page of an address space may not be fully used. But the internal fragmentation is bounded by the page size — typically 4 KB on x86-64, or 2 MB with huge pages — and this is small compared to the fragmentation that a contiguous allocator would suffer. The trade-off is that paging requires more complex hardware (a page table and a TLB) and more complex operating-system support, but the fragmentation benefit is so large that every modern general-purpose system uses paging for the memory that it manages dynamically.

The techniques of this lesson — compaction, the buddy system, segregated free lists, the slab allocator — remain relevant in a paging system. The page allocator uses the buddy system; the kernel's object allocator uses the slab algorithm; the C library's malloc uses a segregated free list. These allocators manage the memory within the pages that the page allocator provides, and they face the same fragmentation problems at a smaller scale. The complete picture of memory management in a modern system is a layering of allocators, each specialised to its level and each using the techniques of this lesson.

4.11 Common misconceptions

"Fragmentation means the memory is full."

Fragmentation means the memory is not usable for a particular request, even though the total free memory may be large. The failure is caused by the shape of the free memory, not by its quantity.

"External and internal fragmentation are the same thing."

They are different. External fragmentation is scattered free memory; internal fragmentation is waste within an allocated block. They have different causes and different remedies.

"Best-fit eliminates fragmentation."

Best-fit minimises the immediate waste per allocation, but it produces small remainders that accumulate as fragments. It does not eliminate fragmentation; on some workloads it makes it worse.

"The 50-percent rule means half the memory is always wasted."

The rule is a statistical prediction under a specific random workload. Real workloads have more structure than the model assumes, and real allocators fragment less than the rule predicts.

"Compaction is free because it only updates the base register."

The process's address space must be copied to its new location, and the process must be suspended during the copy. Updating the base register is the cheap part; the copy is the expensive part.

"The buddy system is the same as segregated free lists."

Both use multiple free lists, but the buddy system's sizes are powers of two, and its coalescing is address-based. Segregated free lists can use any size classes, and their coalescing is more complex.

"The slab allocator eliminates fragmentation entirely."

The slab allocator eliminates external fragmentation within a cache, but it introduces the possibility of imbalance between caches. If one object type is heavily used and another is not, the cache for the first may be short on slabs while the second has many empty ones.

"Paging is a form of compaction."

Paging eliminates the need for compaction, but it is not a form of compaction. Compaction moves allocated blocks to consolidate free memory; paging avoids the need for contiguity entirely by allowing a process's pages to be scattered.

05 Worked example

The following example traces the buddy system through a sequence of allocations and frees, showing the state of the free lists at each step. It compares the buddy system's behaviour to a simple first-fit allocator on the same workload.

The buddy system on a sequence of requests

The memory pool is a single block of 1024 bytes. The buddy system maintains free lists for sizes 128, 256, 512, and 1024 (the sizes below 128 are omitted for brevity; assume a minimum allocation of 128). The requests arrive in the following order: P₁ = 100 bytes, P₂ = 200 bytes, P₃ = 50 bytes, P₄ = 400 bytes. Then P₁ and P₂ are freed.

Allocations

Step	Request	Rounded to	Action	Free lists (sizes)
0	—	—	Initial state	1024: [B@0]
1	P₁ = 100	128	1024 → 512+512; 512 → 256+256; 256 → 128+128; allocate one 128	128: [B@128], 256: [B@256], 512: [B@512]
2	P₂ = 200	256	Allocate from the 256 free list	128: [B@128], 512: [B@512]
3	P₃ = 50	128	Allocate from the 128 free list	512: [B@512]
4	P₄ = 400	512	Allocate from the 512 free list	(empty)

After all four allocations, the free lists are empty, and the four processes occupy blocks at addresses 0, 128, 256, and 512. The total allocated is 128 + 128 + 256 + 512 = 1024 bytes, which is the entire pool. Note that the internal fragmentation is significant: P₁ requested 100 bytes and got 128; P₃ requested 50 bytes and got 128; P₄ requested 400 bytes and got 512. The total requested was 750 bytes, but 1024 bytes were allocated — an internal fragmentation of 274 bytes, or about 27 percent.

Frees and coalescing

Now P₁ and P₂ are freed.

Step	Action	Effect on free lists
5	Free P₁ (block at 0, size 128)	The buddy of the block at 0 is the block at 128, which is held by P₃. So no merge; the block at 0 goes on the 128 free list.
6	Free P₂ (block at 256, size 256)	The buddy of the block at 256 is the block at 512, which is held by P₄. So no merge; the block at 256 goes on the 256 free list.
7	Free P₃ (block at 128, size 128)	The buddy of the block at 128 is the block at 0, which is free. Merge to a 256-byte block at 0. Now the buddy of the merged block is the block at 256, which is free. Merge to a 512-byte block at 0. Now the buddy of the merged block is the block at 512, which is held by P₄. Stop.

After all three frees, the free lists contain a single block of 512 bytes at address 0 (the merged result of P₁, P₃, and the split-off remainders), and P₄ still holds its 512-byte block. The memory is back to two 512-byte blocks, which is exactly what it was after the first split in step 1. The coalescing worked perfectly: the three small blocks merged back into the large block that spawned them.

This perfect coalescing is the buddy system's signature property. Because a block's buddy is determined by its address, the coalescing is deterministic and fast: the allocator computes the buddy's address, checks whether it is free, and if so merges. There is no search of a free list, and no dependence on the order in which the frees occurred. As long as both buddies are free, they merge; if they merge, the result can merge with its own buddy, and so on up the tree.

Comparison with first-fit

On the same workload, a simple first-fit allocator with a single free list would produce a different result. Starting with a 1024-byte pool, first-fit would allocate P₁ (100 bytes) from the pool, leaving a 924-byte hole. It would then allocate P₂ (200 bytes) from the hole, leaving 724 bytes; P₃ (50 bytes) from the hole, leaving 674 bytes; and P₄ (400 bytes) from the hole, leaving 274 bytes. The total allocated is 750 bytes (the actual request sizes), and the free memory is a single 274-byte hole. The internal fragmentation is zero, and the external fragmentation is a single hole, so the memory is in a useful state.

The comparison illustrates the trade-off between the two schemes. First-fit allocates exactly what is requested, so it has no internal fragmentation, but its external fragmentation depends on the workload and can grow. The buddy system has bounded internal fragmentation (at most a factor of two, typically about 25 percent), but it coalesces perfectly and its external fragmentation is confined to the pattern of the buddy tree. On workloads where requests are highly variable in size, first-fit is often better; on workloads where the request sizes cluster around a few values, the buddy system's predictable behaviour is an advantage.

Fragmentation ratio comparison

The fragmentation ratio is the largest hole divided by the total free memory. Let's compute it for the two allocators after all four allocations.

Allocator	Total allocated	Total free	Largest hole	Fragmentation ratio
First-fit	750	274	274	1.00
Buddy system	1024	0	0	—

After all four allocations, the buddy system has no free memory at all: the total allocated is the full 1024 bytes, even though the total requested was only 750. The difference is internal fragmentation. First-fit has 274 bytes free, in one hole. If a fifth request for 200 bytes arrived, first-fit could serve it from its hole; the buddy system could not, because it has no free block of 256 bytes. This is the trade-off in concrete form.

The buddy system's coalescing advantage

The advantage of the buddy system is visible in the coalescing step. After freeing P₁, P₂, and P₃, the buddy system has a single 512-byte block available. A first-fit allocator that does not coalesce would have three separate holes of sizes 128, 128, and 256 — but with coalescing, it would also have a single 512-byte block, provided the three holes were adjacent. In the buddy system, the adjacency is guaranteed by the tree structure, and the coalescing is deterministic. In a first-fit allocator, the adjacency depends on the order of allocation and freeing, and coalescing may not always produce the largest possible block.

The buddy system's guarantee — that if two buddies are free they will be merged, and that the merge can propagate arbitrarily far up the tree — is what makes its fragmentation predictable. The system may internally fragment due to the power-of-two rounding, but its external fragmentation is bounded by the pattern of the buddy tree, which is a fixed structure determined by the size of the pool.

06 Interactive activity

Activity · measure fragmentation and implement the buddy system

The goal of this activity is to measure fragmentation on a real system, implement the buddy system, and observe the difference between the two approaches. Work through the steps in your course VM.

Inspect the kernel's buddy allocator. On a Linux system, read /proc/buddyinfo to see the state of the kernel's page allocator.
```
cat /proc/buddyinfo
```
The output shows, for each memory zone, the number of free blocks at each order. Order 0 is 4 KB (one page), order 1 is 8 KB (two pages), and so on up to order 10 (4 MB). Compute the total free memory in the zone and the fraction of it that is in blocks of each order. Is the free memory mostly in small blocks or in large ones?
Inspect the kernel's slab allocator. Read /proc/slabinfo to see the state of the kernel's object caches.
```
head -20 /proc/slabinfo
# columns: name  active_objs  num_objs  objsize  objperslab  pagesperslab
```
For each cache, compute the fraction of its objects that are active. Then compute the total memory used by the caches and the fraction that is idle. This is the internal fragmentation of the slab allocator — memory that is allocated to a cache but not currently used for an object.
```
awk '/^[a-zA-Z]/ {print $1, $2, $3, $4}' /proc/slabinfo | \
    head -20
```
Measure malloc's internal fragmentation. Write a program that allocates blocks of various sizes and uses malloc_usable_size to see how much memory each allocation actually consumes. Run it for many sizes and plot or tabulate the ratio of requested to usable size.
```
#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>

int main(void) {
    printf("  req   usable   ratio\n");
    for (size_t n = 1; n <= 512; n += 1) {
        void *p = malloc(n);
        size_t u = malloc_usable_size(p);
        if (n % 16 == 0 || n < 16)
            printf("%5zu   %6zu   %.2f\n", n, u, (double)u / n);
        free(p);
    }
    return 0;
}
```
The ratio is the internal fragmentation of the C library's allocator. For small sizes, the ratio is often 1.5 or more, because the allocator rounds up to the next size class. For larger sizes, the ratio approaches 1.

Implement the buddy system. Write a program that implements the buddy system. The program should maintain free lists for each power-of-two size and support allocation and free operations.

#define MIN_ORDER 4         /* minimum block size = 2^4 = 16 bytes */
#define MAX_ORDER 16        /* maximum block size = 2^16 = 65536 bytes */

struct block {
    struct block *next;
};

struct block *free_list[MAX_ORDER + 1];

void buddy_init(void) {
    /* place a single block of size 2^MAX_ORDER on the free list */
}

void *buddy_alloc(size_t n) {
    /* find the smallest order k such that 2^k >= n */
    /* if free_list[k] is empty, recurse upward to find a larger block
       and split it down to size 2^k */
    /* return a block from free_list[k] */
}

void buddy_free(void *p, size_t n) {
    /* determine the order of the block */
    /* compute the buddy's address */
    /* if the buddy is free, merge and repeat at the next order */
}

Test it with the workload from the worked example and verify that the free lists match the trace.

Measure fragmentation for different workloads. Generate three workloads with different size distributions:
- Uniform: sizes uniformly distributed between 16 and 1024 bytes.
- Power-of-two-heavy: sizes chosen as powers of two, with some variation.
- Heavy-tailed: sizes drawn from a log-normal distribution, which is closer to real workloads.
For each workload, run a first-fit allocator and the buddy system. Measure the allocation failure rate and the internal fragmentation. Which allocator does better on each workload? Explain the results.
Compare compaction to allocator design. Consider the canonical workload from Lesson 8.4 where first-fit and best-fit both succeed but worst-fit fails. If the free memory in the worst-fit case were compacted, would the failed request succeed? What is the cost of the compaction compared to the cost of using a different allocator?
Investigate the C library's allocator. The C library's malloc uses a segregated free list with coalescing (glibc's is called ptmalloc). Use mallinfo or malloc_info to inspect the allocator's internal state after a workload.
```
#include <malloc.h>
#include <stdio.h>

int main(void) {
    void *blocks[1000];
    for (int i = 0; i < 1000; i++)
        blocks[i] = malloc(i + 1);
    for (int i = 0; i < 1000; i += 2)
        free(blocks[i]);

    struct mallinfo info = mallinfo();
    printf("arena:    %d\n", info.arena);
    printf("ordblks:  %d\n", info.ordblks);
    printf("uordblks: %d\n", info.uordblks);
    printf("fordblks: %d\n", info.fordblks);
    return 0;
}
```
arena is the total memory the allocator has obtained from the system; uordblks is the memory currently in use; fordblks is the free memory the allocator holds. The difference between arena and uordblks is the allocator's internal overhead and fragmentation.
Read the Linux kernel's slab documentation. The Linux kernel source tree contains documentation for its slab allocator. If you have access to the kernel source, read Documentation/vm/slub.rst (or slab.rst in older kernels). What does it say about the slab allocator's design and its advantages over a general-purpose allocator? Write a short summary.

Reflect: fragmentation is a fundamental consequence of variable-size allocation from a shared pool. Every technique in this lesson reduces it, but none eliminates it within the scheme it applies to. The techniques are always trade-offs: the buddy system trades internal fragmentation for fast coalescing; segregated free lists trade the cost of many free lists for low internal fragmentation; the slab allocator trades the generality of a single pool for the elimination of external fragmentation within a type. Is there a universal allocator that avoids all these trade-offs? If not, what would a universal allocator have to look like, and why is that impossible in practice?

07 Knowledge check

Check your understanding

Question 1

Define external fragmentation and internal fragmentation. Give an example of each, and explain the difference in their causes and their remedies.

Show answer

External fragmentation is the loss of usable memory because the free memory is scattered in pieces that are individually too small to satisfy a request, even though the total free memory is larger than the request. An example: a free list with holes of 20, 25, 30, and 40 KB. A request for 60 KB cannot be satisfied, because no single hole is large enough, even though the total free memory is 115 KB. The cause of external fragmentation is the pattern of allocation and freeing: freed blocks are not always adjacent to other free blocks, so coalescing cannot always merge them. Its remedies are policies that keep the free list in a useful shape (first-fit, coalescing), the buddy system (which guarantees that adjacent buddies merge), and paging (which eliminates the requirement that a process's memory be contiguous). Internal fragmentation is the waste within an allocated block, when the block is larger than the request. An example: a size-class allocator with classes of 64, 128, 256, 512 bytes. A request for 100 bytes is rounded up to 128, wasting 28 bytes inside the allocated block. The cause of internal fragmentation is the allocation unit: fixed-size blocks or size classes force a request to be rounded up to the next available size. Its remedies are finer size classes (which reduce the average waste per allocation), or variable-size allocation (which eliminates the waste but reintroduces external fragmentation). The two forms of fragmentation are different in their locations (between blocks vs. within a block), their causes (allocation pattern vs. allocation unit), and their remedies. A scheme that reduces one often affects the other: finer size classes reduce internal fragmentation but increase the number of free lists and the potential for external fragmentation across classes.

Question 2

State the 50-percent rule. What workload does it assume, and what does it claim? Why is the rule considered a rough estimate rather than a guarantee?

Show answer

The 50-percent rule states that, under a simple random workload, a first-fit allocator loses about half its memory to external fragmentation. The rule was derived by Knuth in 1965 from a statistical model in which the request sizes are independent, the interleaving of allocations and frees is random, and the memory is large enough that boundary effects can be ignored. Under these assumptions, the expected number of holes is proportional to the number of allocated blocks, and the expected total size of the holes is about half the memory. Of that half, most is in holes large enough to be useful, but a substantial fraction is in holes too small for any future request. The effective capacity — the total size of allocations that the system can serve before fragmentation prevents further allocation — is therefore about half the physical memory. The rule is considered a rough estimate rather than a guarantee for three reasons. First, it assumes a random workload, and real workloads are not random: they have structure, such as the stack-discipline pattern in which processes are freed in the reverse order of allocation, which allows coalescing to merge the freed blocks and reduces fragmentation substantially. Second, it assumes a first-fit allocator with coalescing, and real allocators are more sophisticated — the buddy system and segregated free lists fragment differently. Third, it assumes a single uniform pool, and real memory systems are layered: the page allocator uses the buddy system, the kernel object allocator uses the slab algorithm, and the C library's malloc uses a segregated free list, each with its own fragmentation behaviour. The empirical study by Wilson et al. found that real allocators on real workloads fragment considerably less than the rule predicts, precisely because real workloads have more structure than the random model assumes. The rule is valuable as a warning — fragmentation is serious and roughly quantifiable — and as an order-of-magnitude estimate, but it should not be taken as a prediction for any specific system.

Question 3

Describe the buddy system. How does it allocate memory, and how does it coalesce? What are its advantages and disadvantages compared to a general first-fit allocator?

Show answer

The buddy system allocates memory in blocks whose sizes are powers of two. The pool is a single block of size 2ⁿ, and the allocator maintains a free list for each size 2⁰, 2¹, ..., 2ⁿ. When a request for n bytes arrives, the allocator rounds n up to the next power of two, say 2^k, and looks in the free list for size 2^k. If the list is non-empty, it allocates the first block. If the list is empty, it looks in the next larger size (2^k+1); if that list is non-empty, it takes a block, splits it into two blocks of size 2^k (the two buddies), puts one on the 2^k list, and allocates the other. If that list is empty too, the allocator recurses up the size classes until it finds a free block, and then splits it repeatedly on the way down. Coalescing works the same way in reverse. When a block is freed, the allocator computes its buddy's address by flipping the appropriate bit of the block's address — the buddy is the other half of the block that would be formed by merging. If the buddy is free, the two are merged into a block of the next size up, and the merge is repeated for the merged block. The buddy's address is determined by the block's address alone, so the allocator does not need to search the free list to find adjacent blocks. The advantages of the buddy system are: (1) fast allocation — the size class of a request is a few bit operations, and the free-list lookup is a constant-time operation; (2) fast coalescing — the buddy's address is computed, not searched, so coalescing is deterministic and fast; (3) bounded internal fragmentation — a request is rounded up to the next power of two, so the waste is at most a factor of two and on average about 25 percent; (4) predictable external fragmentation — the buddy tree structure bounds the number and sizes of holes. The disadvantages are: (1) internal fragmentation — the power-of-two rounding wastes memory on workloads with many requests just above a power of two; a request for 65 bytes gets a 128-byte block, wasting nearly 50 percent; (2) external fragmentation across size classes — a free block in one size class cannot be used for a request in a smaller class without splitting, and the split-off pieces may not fit any pending request. Compared to a general first-fit allocator, the buddy system sacrifices some internal fragmentation for much faster coalescing and more predictable behaviour. On workloads where the request sizes cluster around powers of two, the buddy system is efficient; on workloads with sizes just above the boundaries, it wastes significantly.

Question 4

What is a segregated free list? How does it differ from the buddy system, and how does it reduce fragmentation? What is the slab allocator, and how does it specialise the segregated approach for the kernel?

Show answer

A segregated free list allocator maintains a separate free list for each size class. The size classes need not be powers of two; they can be any set of sizes chosen to match the workload. When a request arrives, the allocator rounds it up to the smallest size class that is at least as large, and allocates from that class's free list. When a block is freed, it is returned to its size class's free list. This differs from the buddy system in two ways. First, the size classes need not be powers of two — they can be set to 16, 32, 48, 64, 80, ..., giving at most 16 bytes of waste per allocation, compared to the factor-of-two waste of the buddy system. Second, the coalescing is more complex: whereas the buddy system's buddy is determined by address alone, a segregated free list may need to search across size classes to find adjacent free blocks. Segregated free lists reduce fragmentation by eliminating external fragmentation within a size class (all blocks in a class are the same size, so any free block in the class can serve any request for that class) and by reducing internal fragmentation (the size classes can be chosen to match the workload, so most requests fall into a class only slightly larger than the request). The slab allocator, introduced by Bonwick in 1994, is a specialised segregated allocator for the kernel. Its central observation is that kernels allocate and free objects of specific types — process descriptors, file descriptors, inodes, network buffers — and that most objects of a given type are the same size. The slab allocator maintains a cache for each object type, and a cache pre-allocates a slab of memory (typically one or more pages) for a set of objects of that type. The cache tracks its slabs as full, partial, or empty. When an allocation arrives, the allocator takes a free object from a partial slab or from an empty slab, or allocates a new slab. The slab allocator has three properties that make it particularly suited to the kernel: (1) no external fragmentation within a cache, (2) object initialisation caching — the allocator can keep an object's constructor at the cache level and skip re-initialising objects that are reused, and (3) hardware cache alignment. The slab allocator is used in Solaris, Linux (as SLUB), and several other kernels.

Question 5

Explain the relationship between fragmentation and paging. Why does paging eliminate external fragmentation? Does it also eliminate internal fragmentation? What is the complete picture of memory management in a modern system, and where do the techniques of this lesson fit into it?

Show answer

Paging eliminates external fragmentation by removing the requirement that a process's memory be contiguous. In a paged system, a process's address space is divided into fixed-size pages, and the pages are mapped to physical frames that need not be adjacent. Any free frame can hold any page, so there is no requirement that a contiguous region be found. The process's address space can be scattered across physical memory, and the MMU's page table provides the mapping. This is the fundamental difference from contiguous allocation: in a contiguous system, a process's memory must be a single region, and the free memory must be available in a single contiguous piece of the required size. In a paged system, the memory is used in fixed-size units, and the fragmentation that arises from variable-size allocation is impossible. Paging does not eliminate internal fragmentation. Because a page is a fixed-size unit, the last page of a process's address space may not be fully used. A process with 10 KB of data, in a system with 4 KB pages, occupies three pages (12 KB), wasting 2 KB in the last page. This internal fragmentation is bounded by the page size — typically 4 KB — which is small compared to the fragmentation that a contiguous allocator would suffer on the same workload. The complete picture of memory management in a modern system is a layering of allocators. At the bottom, the page allocator manages physical frames, using the buddy system to allocate and free blocks of pages. Above that, the kernel's slab allocator (or SLUB) manages kernel objects, using a segregated cache per object type. Above that, the C library's malloc manages user-space heap memory, using a segregated free list with coalescing. Each level uses the techniques of this lesson, adapted to its workload. The buddy system handles the coarse granularity (pages), the slab allocator handles the kernel's object types, and the segregated free list handles the user's variable-size requests. Fragmentation is a problem at every level, and the techniques that reduce it — the buddy system, segregated free lists, the slab allocator — are used at every level. Paging solves the problem at the coarsest level — it is what makes the page allocator's job possible — but it does not solve it at the finer levels. The techniques of this lesson are therefore not obsolete; they are the techniques that a modern memory system uses to manage the memory that paging provides.

08 Unit discussion

Discussion prompt

Fragmentation is a fundamental problem of variable-size allocation. It cannot be eliminated within a contiguous allocation scheme; it can only be reduced or managed. The techniques presented in this lesson — the buddy system, segregated free lists, the slab allocator — each reduce fragmentation within their domain, at the cost of some other property: internal fragmentation, the complexity of many free lists, or the loss of generality.

This pattern is pervasive in system design. A general-purpose mechanism is simple and flexible but inefficient; a specialised mechanism is efficient but constrained. The right choice depends on the workload and on the acceptable trade-offs. The Linux kernel uses the buddy system for pages because it needs fast coalescing and can tolerate the internal fragmentation; it uses the slab allocator for objects because it needs the object-type specialisation and can tolerate the cache imbalance. The C library uses a segregated free list because it must handle variable-size requests and can tolerate the multi-list overhead.

Is there a limit to this specialisation? Could a universal allocator achieve the best of all worlds — low internal fragmentation, fast coalescing, no external fragmentation, and low overhead? Or is the specialisation inherent, and the proliferation of allocators a permanent feature of system design?

Consider the trade-offs in the context of a specific system: an embedded device with 16 MB of RAM, a mobile phone with 4 GB, a server with 256 GB. Would your answer be the same for all three? Post your response to the Unit 8 discussion forum and reply to at least two classmates. Supports CLO1, CLO4, and CLO6.

09 Practice exercise

This ungraded exercise consolidates the lesson and prepares you for Lesson 8.6. Aim to spend 60–90 minutes on it.

Classify fragmentation. For each of the following, state whether it is external fragmentation, internal fragmentation, both, or neither. Explain your answer.
- A first-fit allocator with holes of 100, 50, 80, and 60 KB, and a request for 120 KB.
- A size-class allocator with classes of 64, 128, 256 bytes, and a request for 200 bytes.
- The Linux kernel's slab cache for inodes, with some slabs full and some empty.
- A process's address space with 10 KB of data, in a 4 KB page system.
- The free list of a first-fit allocator with 500 KB free, all in one hole.
Compute the fragmentation ratio. Given the following free lists, compute the fragmentation ratio (largest hole / total free memory) for each:
- Holes of 500, 300, 100 KB.
- Holes of 900 KB.
- Holes of 200, 200, 200, 200, 100 KB.
- Holes of 50, 50, 50, 50, 50, 50, 50, 50, 50, 50 KB.
For each, state whether the free memory is well-suited to satisfying a request for 300 KB, and why.
Trace the buddy system. Starting from a pool of 512 bytes, trace the buddy system through the following sequence of requests: 50, 100, 200, 100. After each allocation, show the state of the free lists. Then free the first two allocations and show the coalescing process.
```
Sizes: 512 pool. Minimum block size 32.
Round up requests to the next power of two.
```
Design a size-class set. A workload consists of requests with the following size distribution: 40 percent of requests are 16–32 bytes, 30 percent are 33–64 bytes, 20 percent are 65–128 bytes, and 10 percent are 129–256 bytes. Design a set of size classes that minimises the expected internal fragmentation. What is the average waste per allocation with your design? Compare to a power-of-two scheme.
Compare first-fit and the buddy system. On a workload of 100 requests with sizes drawn from a uniform distribution between 1 and 1000 bytes, allocate each request with both first-fit and the buddy system (using powers of two and a minimum block size of 16). Measure the total allocated memory and the total requested memory for each allocator. What is the internal fragmentation of each? What is the external fragmentation (as measured by the largest hole)?
Analyse a real workload. The Wilson et al. survey found that real allocators fragment less than the 50-percent rule predicts. Read sections 3 and 4 of the survey and write a paragraph explaining why. What properties of real workloads reduce fragmentation? What properties of real allocators reduce it?
Investigate the kernel's allocators. On a Linux system, run the following commands and interpret the output:
```
cat /proc/buddyinfo
head -30 /proc/slabinfo
cat /proc/meminfo | grep -i -E 'slab|page'
```
How much memory is in the buddy allocator's free lists? How much is in the slab caches? What fraction of the total memory is in each? Is the fragmentation of the page allocator visible in the buddyinfo output?
Reflect. In your own words, explain why fragmentation is fundamental to contiguous allocation. Then describe one situation in your own experience — a program you have written or a system you have used — where fragmentation could plausibly have affected performance. What was the workload, and what technique would you use to reduce the fragmentation?

10 Summary

Fragmentation is the loss of usable memory caused by the way memory is divided into allocated blocks and free holes. It comes in two forms: external fragmentation, in which the free memory is scattered in pieces too small to satisfy a request, and internal fragmentation, in which an allocated block is larger than the request it satisfies.
External fragmentation is a property of the free list, and it arises because freed blocks are not always adjacent to other free blocks. Its remedies are policies that keep the free list in a useful shape (first-fit, coalescing), the buddy system, and paging. It cannot be eliminated within a contiguous allocation scheme.
Internal fragmentation is a property of the allocation unit, and it arises because a request is rounded up to the next available block size. Its remedies are finer size classes or variable-size allocation. It is bounded by the granularity of the size classes.
The 50-percent rule states that, under a simple random workload, a first-fit allocator loses about half its memory to external fragmentation. The rule is a statistical prediction, not a guarantee; real workloads have more structure than the model assumes, and real allocators fragment less than the rule predicts.
Fragmentation is measured by the fragmentation ratio (largest hole / total free memory), the allocation failure rate, the effective capacity, and the internal fragmentation overhead. The measures are complementary, and a complete analysis considers all four.
Compaction moves all allocated blocks to one end of memory, consolidating the free memory into a single region. It requires execution-time binding, and it is expensive because it requires copying the processes' address spaces. It is rarely used in modern systems.
The buddy system allocates memory in blocks whose sizes are powers of two, with a free list per size class. Its coalescing is fast and deterministic because a block's buddy is determined by its address. Its internal fragmentation is bounded by a factor of two. It is used in the Linux kernel's page allocator.
A segregated free list maintains a separate free list for each size class, which need not be powers of two. It reduces internal fragmentation by using finer size classes, at the cost of more complex coalescing across classes. It is used in the C library's malloc and in modern allocators like jemalloc and tcmalloc.
The slab allocator specialises the segregated approach for kernel object types. It maintains a cache per object type, with slabs in full, partial, and empty states. It eliminates external fragmentation within a cache, supports object initialisation caching, and aligns objects to hardware cache lines. It is used in Linux (as SLUB) and several other kernels.
Paging eliminates external fragmentation entirely, by removing the requirement that a process's memory be contiguous. It does not eliminate internal fragmentation, which is bounded by the page size. Modern memory management is a layering of allocators — the buddy system for pages, the slab allocator for kernel objects, the segregated free list for user requests — each using the techniques of this lesson at its own level.

Looking ahead

This lesson presented fragmentation and the techniques that reduce it. Lesson 8.6 presents segmentation: a memory-management scheme that divides a process's address space into logical segments — code, data, heap, stack — each with its own base and limit. Segmentation allows each segment to be placed in a different part of physical memory, so a process's memory need not be contiguous as a whole. This reduces external fragmentation, and it introduces a finer-grained protection model than the base-and-limit scheme of Lesson 8.2. Segmentation is the historical bridge between contiguous allocation and paging, and understanding it is prerequisite to understanding the design of paging in Unit 9.

11 References

Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 9, Sections 9.2–9.3.
Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapter 17, Free Space Management. Available online at ostep.org.
Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 3, Section 3.2.
Knuth, D. E. The Art of Computer Programming, Volume 1: Fundamental Algorithms, 3rd ed., Section 2.5, Dynamic Storage Allocation. Addison-Wesley, 1997. The classical treatment of the statistical behaviour of storage allocators, including the derivation of the 50-percent rule.
Wilson, P. R., Johnstone, M. S., Neely, M., & Boles, D. Dynamic Storage Allocation: A Survey and Critical Review. Proceedings of the International Workshop on Memory Management, 1995.
Peterson, J. L., & Norman, T. A. Buddy Systems. Communications of the ACM, 1977.
Knowlton, K. C. A Fast Storage Allocator. Communications of the ACM, 1965. The paper that introduced the buddy system.
Bonwick, J. The Slab Allocator: An Object-Caching Kernel Memory Allocator. USENIX Summer Conference, 1994.
Evans, J. A Scalable Concurrent malloc for Linux. The design of jemalloc, a modern segregated allocator.
Love, R. Linux Kernel Development, 3rd ed., Chapter 12, Memory Management. The kernel's page allocator (buddy system) and its object allocator (slab/slub).
Linux man-pages: man 3 malloc, man 3 free, man 3 malloc_usable_size, man 3 mallinfo, man 5 proc.