Address Spaces and Address Translation

A running program works with an address space: its own view of memory, with numbered byte locations. The operating system places the program's memory in the machine and arranges for its addresses to reach the right physical bytes. The layout the program sees and the layout in hardware are different things.

Why several programs stay in memory

Early systems could keep one program beside the operating system. For example, the OS might occupy the first 64 KB and the program the remaining memory. Multiprogramming kept more than one process ready, so the CPU could work while another process waited for input or output. Time sharing switched the CPU often enough to serve interactive users.

Saving one process's entire memory to disk at every switch would make switching far too slow. Keeping several processes in physical memory avoids that copying, but creates a protection problem. An address generated by one process must not let it overwrite the OS or a neighbor.

Memory sizes here follow the binary convention used in these models: 1 KB is 1,024 bytes, also written 1 KiB; 1 MB is 1,024 KB. A 16 KB address space has 16,384 byte locations, numbered 0 through 16,383. The number 16,384 is the end boundary, not a valid byte address.

Code, data, heap, and stack

In a classic 16 KB teaching layout, code uses the low addresses, from 0 up to the 1 KB boundary. The heap starts above the code and grows upward. The stack begins at the upper boundary and grows downward. The free gap between them gives both regions room to grow. Real layouts differ; for example, each thread has its own stack. The roles of the regions remain useful even when their positions change.

Follow a pointer to the right memory

A virtual address names a byte in a process's address space. A physical address names a byte in the machine's memory hardware. When C code prints printf("%p", (void *) &x), it prints a virtual address. The printed pointer does not reveal the physical byte storing x.

Suppose two processes both use virtual address 1,000. Each address is interpreted within its process's own address space, so the accesses can reach different physical bytes. Likewise, code at virtual address 0 need not occupy physical address 0. The OS can place it elsewhere and configure hardware translation to reach it.

The processor translates instruction fetches, loads, and stores. The OS chooses and manages the mappings, including changing physical locations while keeping the program's virtual addresses stable.

A memory system must do more than translate a number correctly. It must let ordinary programs run without managing physical placement, keep translation cheap, and enforce the boundaries that make sharing safe. These requirements are transparency, efficiency, and protection.

Preserve the program's view

Transparency means a program runs as if it had private memory. It uses its own addresses for code and data without tracking which other processes are present or where their bytes lie. The OS and hardware preserve this view behind the scenes. Moving a process in physical memory should not require the process to rewrite its pointers.

The illusion does not require a distinct physical copy of every byte for every process. For example, protected read-only code can be shared. What matters is that the sharing preserves the behavior and access rights each process is entitled to see.

Count both kinds of cost

Every instruction fetch, load, and store needs translation. Running an OS routine for each access would make ordinary execution too slow. Hardware performs the frequent operations; OS code handles setup, changes, and faults.

Space efficiency matters too. A small, fast translation mechanism can still waste substantial memory. A single base-and-bounds region reserves the unused gap between heap and stack. Segmentation avoids backing that gap, but introduces variable-sized physical regions and holes between them. Metadata, unused reserved space, and holes all affect how much useful work fits in memory.

Make a bad access stop at the boundary

Without protection, a stray pointer in a text editor could overwrite another process or the kernel. Damage might appear much later in unrelated code. With enforced bounds, hardware rejects an access outside the permitted region and raises an exception. The OS handles the exception and usually ends the faulty process, commonly reporting a segmentation fault.

Protection isolates processes from one another. It does not make C memory use safe within a permitted heap region. A write past one allocated block can still hit another block owned by the same process. Process boundaries and allocator block boundaries are different boundaries.

Separate the operation from the choice

A mechanism is how an operation is carried out. Adding a base register and checking a bounds register are mechanisms. A policy chooses among possible actions: where to place a process, which free hole to use, or when to move a segment.

Keeping these separate lets the OS change its placement strategy while keeping the same hardware translation. Virtualizing memory starts with this private, protected view; it is not defined by using disk as extra memory.

A pointer variable and the memory it points to are separate objects. Understanding their lifetimes is the starting point for the C memory API. Ordinary local variables typically use automatic stack storage, heap blocks last until released, and globals and static locals have storage for the program's whole run.

Follow the allocation, not just the pointer

void f(void) {
    int x;
    int *p = malloc(sizeof(int));
}

In the usual stack layout, x and p belong to this call of f. The requested integer belongs to the heap. Returning removes the local pointer variable; it does not free the heap block. If no copy of the address remains, the program has lost access to a live allocation: a memory leak.

malloc(size) requests at least that many bytes and returns a pointer, or NULL when it cannot satisfy the request. Its bytes are not initialized for the program. For 10 integers, use malloc(10 * sizeof(int)); where an integer is 4 bytes, that requests 40 bytes. For a string, reserve its characters plus one byte for the terminating null character: malloc(strlen(s) + 1).

sizeof(a) measures the object named a. If a is a pointer, it gives the pointer's size, not the size of the allocation. An 8-byte pointer can refer to a 40-byte block.

Know what each library operation does

free takes the returned pointer, with no size argument. The allocator keeps size metadata, commonly in a header before the block. Pass a currently allocated block's returned pointer; an interior pointer is not a valid substitute. free(NULL) is valid and does nothing. These functions are C library routines, not system calls.

Recognize the error from the lifetime or boundary

A pointer with no valid allocation cannot be used as though it already points to storage. Reading newly allocated bytes before initializing them is an uninitialized read. Writing beyond the allocated end is a buffer overflow; omitting a string's terminator byte can cause one.

After free, old pointers to the block are dangling. Accessing through one is a use-after-free. Freeing the block again is a double free. Freeing an address the allocator did not return for a live block is an invalid free. Leaking a block is different: the block remains allocated, but the program no longer releases it when it should.

Understand what the hardware can check

Compilation can succeed despite all these errors. Hardware normally checks process regions and permissions, not each library allocation. Crossing a block boundary while staying inside the process's legal heap can have undefined behavior without an immediate fault. The program may corrupt data, crash later, read meaningless values, or appear to work. Valgrind and AddressSanitizer can detect many such errors during execution.

The C library and the OS manage memory at different scales. The OS establishes regions in a process's address space and supplies their backing. The allocator divides available heap memory into blocks, records free chunks, and reuses them across calls.

Move the program break

The program break is the address just past the traditional heap's end. brk sets that boundary to a chosen address. sbrk(n) moves it by a byte increment and, on success, returns the old break. sbrk(0) reports the current break without moving it.

Suppose the break is 40,960 and the allocator successfully calls sbrk(8192). The returned value is 40,960. The new boundary is:

The added bytes occupy virtual addresses 40,960 through 49,151. The new break, 49,152, is just beyond the added region. Confusing the returned value with the new boundary shifts every later placement calculation.

Applications use the allocation library instead of moving the break directly. The library tracks which parts of its region it owns. Independent changes to that boundary can invalidate its bookkeeping.

Obtain a separate mapping

mmap can create an anonymous region: memory not tied to a file, initially filled with zero bytes. munmap removes a mapping. An allocator can use separate mappings for large allocations and return those mappings to the OS when they are freed.

In glibc, the default initial threshold for this route is 128 KB, or 131,072 bytes, and it can adjust upward. A sufficiently large allocation is typically mapped separately if it cannot be met from existing free space. This is a library policy, not a universal dividing line in the C language.

Free at the library level or the OS level

A call to free usually puts a small block back into the library's pool. The process can therefore report the same memory footprint afterward. The memory is available for reuse without another OS request.

Process exit reclaims even allocations the program leaked. During a long-running server's lifetime, however, repeated leaks keep consuming its available memory. Reclamation at exit does not prevent that pressure while it runs.

Connect heap growth to translation

In the segmentation model, the heap is a contiguous physical segment. Growing it requires free physical bytes immediately above it. If those bytes are occupied, the OS may move the segment to a larger hole and update its translation state. If no suitable region is available, growth fails. If the allocator cannot obtain enough space, malloc returns NULL.

Dynamic relocation translates addresses while a program runs. In the base-and-bounds model, one process occupies one contiguous physical region. Begin with equal-sized address spaces that fit in physical memory; one register pair then describes the currently running process's region.

Check the virtual address first

The base register holds the physical address of the region's first byte. The bounds register, or limit register, holds the region's size in bytes. For a nonnegative virtual address, the rule is:

If the check succeeds:

Otherwise the hardware raises an exception. A size is a count, so the address equal to the bounds is already outside the region. Negative virtual addresses are invalid too.

Work through the byte boundaries

Take an 8 KB address space with base 20,480 and bounds 8,192. Its virtual bytes run from 0 to 8,191. Virtual address 1,000 passes the check and reaches physical byte 21,480. The last legal virtual byte, 8,191, reaches 28,671. Address 9,000 fails because it is at least 8,192; hardware must reject it before issuing the physical access.

Instruction fetches use the same translation as data. If an instruction at virtual 128 loads from virtual 3,000, the fetch reaches physical 20,608 and the load reaches 23,480. These are two memory accesses with two translated addresses, not one shared translation for the whole instruction.

Keep the bounds convention straight

The same 8 KB region has physical end boundary 28,672. Both conventions permit exactly bytes 20,480 through 28,671. Comparing physical address 21,480 with size 8,192 mixes the two conventions and wrongly rejects a legal access.

Move memory without changing pointers

The MMU, or memory management unit, performs the checks and addition. The OS can pause a process, copy its region elsewhere, and change the base. The process still uses the same virtual addresses, which is why relocation is dynamic.

Static relocation instead has a loader rewrite embedded addresses when loading code. Rewriting a reference from 1,000 to 21,480 records a physical placement in the program. Moving it later requires further rewriting, and rewriting alone does not stop a program from constructing an address outside its region.

Only add a base to a virtual address. Adding it to an already translated physical address shifts the location a second time and destroys the mapping.

The hardware holds translation registers for the process running on a CPU. The OS holds the saved state for processes that are waiting. Protection depends on giving only privileged OS code the power to change that state.

Provide the hardware operations

The CPU needs user and kernel modes, a base-and-bounds pair in its MMU, and circuits for the check and addition. It also needs privileged operations to change the pair and install exception handlers. Illegal addresses and attempts to execute privileged instructions in user mode must raise exceptions.

If a user program could change its base, it could redirect its addresses into the kernel or another process. Bounds checks would then protect the wrong region. Restricting updates is therefore part of the protection mechanism, not just an administrative convenience.

Create and run a process

At boot the OS installs its trap and exception handlers, starts the interrupt timer, and prepares its free-memory records. When a process starts, the OS finds a physical slot for its address space. With equal-sized slots, a free list can simply record which slots are unused.

The OS marks the chosen slot busy, records the process's base and bounds, loads the registers, and enters user mode. The process then runs directly on the CPU. Hardware translates ordinary accesses without calling the OS for each byte.

Restore the right pair on a context switch

A timer interrupt transfers control to the OS. It saves the old process's registers, including base and bounds, in its process control block, then restores the next process's values before returning to user mode.

Suppose A's base is 20,480 and B's base is 40,960, both with bounds 8,192. A's virtual address 1,000 reaches 21,480. After switching to B, the same virtual number reaches 41,960. Restoring the CPU registers without restoring translation state would make B access A's region using B's pointers.

The CPU has the active pair; each process has its own saved pair. Do not picture a single permanent pair for the whole machine or assume every process's pair is simultaneously active on one CPU.

Move, fault, and finish

To move A to physical address 49,152, the OS deschedules A, copies its 8 KB region, and updates A's saved base. Once A resumes with that base installed, virtual 1,000 reaches 50,152. Its virtual pointer values need no edits.

For an invalid access, hardware raises an exception and transfers execution into kernel mode at the registered handler. The OS usually terminates the offending process. On termination it returns the slot to the free list and releases process records.

Base and bounds meets two goals cheaply: translation is transparent, and every address is checked against the allocated region. Its main weakness is the relationship between that region and the bytes the process actually uses.

Reserve the whole span

The hardware needs only an addition and a comparison on the frequent path. A fixed-size-slot allocator can also choose a free slot quickly. Neither benefit means the slot is full of useful data.

In the classic layout, code and heap sit near one end and the stack near the other. One base-and-bounds pair translates the entire interval. The unused gap between heap and stack occupies physical memory just like the useful parts.

For a 16 KB address space using 1 KB of code, 2 KB of heap, and 1 KB of stack:

The waste is internal fragmentation: unused bytes inside a region already allocated to a process. It does not arise from the heap allocator choosing a poor block. Even a perfectly packed 2 KB heap leaves the large middle gap reserved.

Separate three size questions

The address space's span, the bytes currently used, and the available physical memory are different quantities. A 32-bit byte-addressed space spans $2^{32}$ bytes, or 4 GB. Reserving it as one physical block requires the entire 4 GB even if the process currently uses only a few megabytes.

Making slots variable-sized removes the equal-size restriction, but it does not remove the need for a contiguous hole. It also creates a placement problem: the OS must choose among free holes of different sizes. Shrinking one slot cannot preserve both low code addresses and a distant high stack address if the entire span must remain valid in the same simple mapping.

Relocate the regions separately

Code, heap, and stack do not have to be neighbors in physical memory to preserve the program's view. Giving each its own base and bounds lets the OS allocate only their used extents and leave the virtual gap unbacked. This is segmentation, the generalization of one relocation pair to several logical regions.

For the 16 KB layout above, the three used regions need only 4 KB in total before their own management overhead. The space saving comes from changing what is relocated as a unit, not from making the base-register addition faster.

A segment is a contiguous region of an address space with one purpose. In the classic model, code, heap, and stack each get a base-and-size pair. Their physical regions can be placed independently even though the process keeps its familiar virtual layout.

Map only the used extents

Use a 16 KB address space with the following placements. Sizes use binary KB, or KiB.

Code and heap grow toward higher addresses; stack translation uses its upper boundary and a negative offset. The three physical regions use only 7 KB altogether. The virtual holes between them need no physical storage. A segment remains contiguous; it is the relationship between segments that no longer requires adjacency.

Translate an upward-growing segment

First identify the segment. Next compute the offset from its virtual start. Check that the offset is nonnegative and less than its current size, then add it to the physical base:

For virtual address 500, the code offset is 500. It is below 2,048, so the access reaches physical 41,460.

For virtual address 5,000, the heap offset is:

The size check succeeds because 904 is below 3,072. The result is:

Adding the full virtual address to the heap base would produce 31,624. That mistakenly carries the heap's virtual starting position into a calculation that needs only distance within the segment.

Check the segment, not just the address-space span

Virtual address 7,500 still fits in 14 bits, but that does not make it legal. Its heap offset is 3,404, beyond the current 3,072-byte extent. Hardware raises an exception. An address can therefore lie inside the overall address-space span and still lie outside every valid region.

The term segmentation fault originated with invalid segmented accesses and remains in use for illegal accesses on systems with other translation schemes. The error name alone does not identify the translation mechanism in the machine.

Before hardware can use a segment's base and size, it must decide which segment an access names. An explicit design puts that choice in address bits. An implicit design derives it from the way the CPU formed the address.

Split a 14-bit address

Give the top two bits to the segment number and the low twelve bits to the offset. The two-bit field has four possible values. Use 00 for code, 01 for heap, and 11 for stack; leave 10 unused.

The offset field can represent 4,096 different values, from 0 through 4,095. Each segment's maximum virtual window is therefore 4 KB, even when the segment's current valid extent is smaller. Maximum capacity and current size are different limits.

For virtual address 5,000, the 14-bit representation is:

01 0011 1000 1000

The leading 01 selects the heap. The remaining 0011 1000 1000 is decimal 904. With heap size 3,072 and physical base 26,624, the offset passes the size check and reaches physical 27,528.

Use a mask and shift

The same split can be expressed as code:

segment = (va & 0x3000) >> 12;
offset = va & 0x0FFF;

The mask 0x3000 keeps the two selector bits; shifting by twelve moves them to the low positions to give the segment number. The mask 0x0FFF clears those selector bits and keeps the offset. For va = 0x1388, the results are segment 1 and offset 0x388, or 904.

Do not add 0x1388 directly to the heap base. That includes both the segment selector and the offset. The selector chooses the registers; only the offset participates in the within-segment translation. The resulting physical address does not need to retain the selector bit pattern.

Recognize the cost of the split

A two-bit selector creates four windows. Leaving 10 unused makes one quarter of the 16 KB virtual span unavailable. No segment can grow beyond its 4 KB window just because more physical memory becomes free. Other designs can use a different split; combining code and heap into one segment allows a single selector bit to distinguish it from stack.

Let the access type choose instead

In an implicit design, instruction fetches use the code segment because their address comes from the program counter. Stack-pointer or frame-pointer references use the stack segment. Other accesses use the heap segment in this simplified model.

The stack grows toward lower addresses. Its translation needs a direction bit as well as a base and size. In this model, 1 marks upward growth and 0 downward growth. Access permissions add another independent check: a byte can be within bounds and still forbid the requested operation.

Treat the stack base as an upper boundary

For an upward-growing segment, the base names its first physical byte. For a downward-growing segment, the base names the boundary just above its highest physical byte. In the running layout, stack base 53,248 and size 2,048 cover physical bytes 51,200 through 53,247.

For the 4 KB stack window selected by 11, convert the twelve-bit offset field into a negative displacement:

The field ranges from 0 to 4,095, so this displacement is always negative. It is valid when its magnitude does not exceed the current stack size. Then add the signed displacement to the base.

Work through a legal stack access

Virtual address 15,500 selects stack. Its window starts at virtual 12,288, so its offset field is 3,212. Convert the field:

The depth 884 is within size 2,048. Translation gives:

Adding positive 3,212 to the base would point above the stack. The field is not yet the displacement required for a downward-growing segment.

Virtual address 13,000 instead gives field 712 and displacement −3,384. Its depth exceeds 2,048, so hardware faults. If the OS successfully grows the stack, increasing its size can make more low addresses valid.

Keep the lower endpoint

A displacement of −2,048 reaches the stack's lowest byte, 51,200, and is legal. A displacement of −2,049 is outside. The downward check therefore includes the magnitude equal to the size. This matches the upward rule's byte count even though that rule excludes an offset equal to the size: the upward base is a byte, while the downward base is an end boundary.

Check the requested operation

Protection bits record read, write, and execute permission. Code is typically read-execute; heap and stack are typically read-write. A write to read-execute code faults even when its offset is valid. Executing data also faults when execute permission is absent.

Read-only code can be shared. The OS can point two processes' code segments at the same physical region and deny writes in both. The instruction bytes occupy one physical copy, while each process keeps a separate heap and stack.

Segmentation replaces one large region with several smaller ones. This avoids backing empty virtual gaps, but the OS must now place and grow regions of different sizes while preserving each process's translation state.

Save every part of the mapping

At a context switch, base and size alone are no longer enough. The OS saves and restores each segment's base, size, growth direction, and permissions. Restoring a stack with the wrong direction or code with the wrong permissions would change the meaning of otherwise identical addresses.

When an allocator needs more heap space, the OS must extend the physical heap segment. Free bytes immediately above it allow direct growth. Otherwise the OS can move it to a suitable larger hole and update its base. If it cannot obtain a suitable region, growth fails.

Choose the granularity

Multics used fine-grained segmentation. More segments allow smaller units of control, but require more translation metadata and management.

Find a sufficiently large hole

Variable-sized physical segments leave variable-sized free holes as processes start, grow, and exit. External fragmentation occurs when enough bytes are free in total, but no single hole can hold the requested segment.

Suppose the free holes are 8 KB, 6 KB, and 10 KB. Their total is 24 KB. A 12 KB heap segment still cannot fit: the largest available hole is only 10 KB. Joining the holes on paper does not make their physical addresses adjacent.

Compaction can repair this layout. The OS pauses processes, copies segments next to one another, and updates their bases. Virtual addresses keep working because translation hides the physical moves. The result is a large contiguous free region, but the copying is costly and new allocations can fragment memory again.

Placement policies such as first fit and best fit try to limit bad leftovers without copying. No variable-sized placement policy removes external fragmentation for every request sequence. A single large segment can also waste space within its own extent when only scattered parts are used.

Recognize the model in modern systems

Paging divides memory into fixed-sized pieces and avoids requiring each logical region to occupy one physical hole. The segmentation model remains useful for understanding regions, protection, and sharing. In x86-64's 64-bit mode, ordinary code, data, and stack segmentation bases act as zero and their limits are not checked; FS and GS retain useful bases for per-thread or per-CPU data. An illegal-access message called a segmentation fault does not mean the classic three-segment model is active.

Free-space management records available memory and chooses where each request goes. Equal-sized requests can use a list of interchangeable chunks. Variable sizes are harder: both a heap allocator and an OS placing segments must find a contiguous chunk large enough for the next request.

Locate external fragmentation

Consider a 60-byte region with free bytes 0–19, an allocated chunk at 20–39, and free bytes 40–59. Forty bytes are free, but neither free hole can hold a 25-byte request. The live middle chunk prevents treating those holes as one region.

This is external fragmentation: capacity is free outside allocated chunks, but its arrangement makes it unusable for a particular contiguous request. The free bytes have not disappeared. They can still serve smaller requests or become useful when intervening chunks are freed.

Locate internal fragmentation

An allocator that rounds requests to multiples of 16 gives a 20-byte request a 32-byte chunk. The 12 extra bytes sit inside an allocation already handed out. That waste is internal fragmentation.

The unused heap–stack gap in a base-and-bounds slot is another example. Buddy allocation introduces the same kind of waste when it rounds to powers of two. The level of management differs, but the location of the unused space is the defining feature.

One allocator can suffer both. Rounding a request may waste bytes inside its chunk while other free chunks remain separated elsewhere.

Merge free neighbors without moving live data

Coalescing merges physically adjacent free chunks. If the middle chunk in the 60-byte region is freed, all three pieces can join into one 60-byte hole. If the middle chunk stays allocated, coalescing cannot cross it. Merging reduces external fragmentation but does not guarantee a large enough hole for every request.

Adding more memory to a heap can relieve pressure, but does not change the addresses of existing live blocks. Their placement can still leave unusable small gaps.

Explain why the OS can compact segments

The OS may copy physical segments and update their bases. Programs keep virtual addresses, so the mapping can hide those moves. A general C heap allocator lacks a translation layer between returned pointers and locations within the heap. A program may have copied a pointer into many objects, and the allocator cannot discover and rewrite every copy.

Moving a live heap block on its own would leave those pointers aimed at its old location. Consequently, ordinary malloc management keeps live blocks at their returned addresses until they are freed. It must manage fragmentation through placement, reuse, splitting, and merging free space.

A free list records free chunks by address and size. Allocating splits a chunk or removes it from the list; freeing returns a chunk and may merge it with neighbors. The size convention matters: a recorded size may mean usable payload or the whole chunk including metadata.

Split and coalesce simple ranges

Ignore headers first. In a 60-byte region with free entries (0, 20) and (40, 20), an 8-byte request placed at the start returns address 0. The remaining entries are (8, 12) and (40, 20).

Starting again from the original layout, free the middle allocated bytes 20–39. Without merging, three 20-byte entries still cannot individually serve a 30-byte request. Coalescing adjacent ranges produces (0, 60), which can. Address order helps the allocator recognize neighbors; list adjacency alone is not enough unless their physical ranges touch.

Recover the header from the user pointer

free(ptr) receives no size. A simple allocator stores a size header immediately before the payload, sometimes with a checking value or magic number. Subtracting the header length finds the metadata.

With a 16-byte header, a 96-byte request occupies 112 bytes in all. The program receives a pointer 16 bytes after the chunk start. Freeing it returns the whole 112-byte extent, including the header, for future management. Alignment can add rounding; these example sizes already meet 16-byte alignment.

Trace an embedded free list

Suppose a 4,096-byte heap starts at 32,768. A free node uses 16 bytes and records usable bytes after the node. Initially it records 4,080 usable bytes.

Three 96-byte requests each consume 112 bytes:

The remaining free node starts at 33,104. Its usable size is 3,744 bytes. The accounting is:

Freeing pointer 32,896 finds header 32,880. That chunk becomes a free node with 96 usable bytes. It cannot join the tail node at 33,104 because the third allocation lies between them. When all three allocations are freed and coalesced, one node again describes 4,080 usable bytes. Absorbing the old interior headers makes their bytes available inside the merged extent.

Keep bookkeeping inside the managed region

Embedded list nodes live in free memory itself, so managing the list does not require a separate allocation for every entry. The node contains a size and a link to the next free chunk. If no chunk fits, the allocator can request more memory with sbrk or mmap; failure to obtain enough memory leads to NULL.

An overflow can overwrite a neighboring header or node. That explains why the visible failure may occur during a later malloc or free, after the write that damaged the list.

A placement policy chooses among chunks large enough for a request. Different choices leave different holes for future requests. Search time matters along with fragmentation, and no policy wins for every workload.

Compare the search rules

For best and worst fit, a plain unsorted list needs a full search. Other structures can find suitable sizes more quickly. First fit means first in the chosen list order, which need not mean smallest address unless the list is address-ordered.

Trace the first request

Take free chunks of 30, 12, 50, and 20 bytes in address order. Ignore headers and assume splitting can preserve each leftover. An 18-byte request changes the list as follows:

• Best fit uses 20 and leaves 30, 12, 50, 2.
• Worst fit uses 50 and leaves 30, 12, 32, 20.
• First fit uses 30 and leaves 12, 12, 50, 20.
• Next fit starting at the fourth chunk uses 20 and leaves 30, 12, 50, 2.

Next fit needs a starting position to determine its choice. The name alone does not imply the list's first entry. A trace must retain that search state between requests.

See why the next request changes the verdict

A following request asks for 45 bytes. Best fit and first fit both preserved the 50-byte chunk, so both succeed. Worst fit's largest remaining chunk is 32 bytes, so it fails despite 94 bytes free overall:

This failure is external fragmentation. The earlier decision broke the only sufficiently large hole. Conversely, best fit left a 2-byte sliver that may be too small for useful future requests. An immediate small remainder is not evidence that a policy will use space well over the full request sequence.

Balance policy and data structure

Scanning thousands of entries can be expensive even when each placement is good. Practical allocators group chunks by size or use searchable structures such as balanced trees. An address-ordered list also supports coalescing by making physical neighbors easier to find.

The allocation mechanism—find, split, update metadata—can stay the same while the policy changes. To compare policies fairly, trace the same requests and frees, keep overhead rules fixed, and account for both the resulting holes and the amount of search.

General free-list search is flexible but can be expensive. Specialized allocators make common requests predictable by grouping sizes, retaining reusable objects, or restricting block sizes to powers of two.

Reuse popular sizes and initialized objects

Segregated lists keep separate free lists for popular sizes, with a general allocator for other requests. Serving a common size can take a chunk directly from its list. Equal-sized chunks do not create external fragmentation among themselves, but dividing capacity among lists is a policy choice: spare chunks of one size may not serve another size.

A slab allocator keeps an object cache for a recurring kernel object type, such as an inode, lock, or process descriptor. A slab is divided into objects of that type. The cache obtains more slabs when needed and can return an entirely free slab to a general allocator. Jeff Bonwick designed this approach for Solaris.

The cache keeps freed objects in an initialized state, avoiding repeated setup and destruction. That saves time beyond the search itself.

Split a buddy region

A binary buddy allocator starts with a power-of-two region and rounds each request to a power-of-two block size. It repeatedly splits a free block into equal halves until a half just fits. The two halves from one split are buddies.

For a 5 KB request in a 64 KB region, round 5 KB to 8 KB. Split 64 into two 32 KB blocks, then the chosen 32 into two 16 KB blocks, then the chosen 16 into two 8 KB blocks. Returning the first 8 KB block leaves free buddies at offsets 8 KB, 16 KB, and 32 KB, with sizes 8 KB, 16 KB, and 32 KB respectively.

The allocation wastes 3 KB inside its 8 KB block. This is internal fragmentation, accepted in exchange for regular splitting and merging.

Find the one legal merging partner

Using offsets measured from the managed region's start:

Exclusive OR flips the bit corresponding to the block size. For an 8 KB block at offset 0, its buddy is at offset 8,192. For a 16 KB block at offset 16,384, its buddy is at 0.

When the first 8 KB block is freed, it merges with its free 8 KB buddy. The resulting 16 KB block can merge with its free buddy, then the resulting 32 KB block can merge again. Merging stops if the required same-size buddy is in use. Being adjacent and free is insufficient when two blocks are not buddies from the same split.

A 20 KB request receives 32 KB, wasting 12 KB, or 37.5% of the block. Linux combines physical-memory buddy allocation with slab-style object caches. Multithreaded allocators also use local caches or multiple arenas to reduce waiting for one shared allocation lock; glibc, jemalloc, and tcmalloc use versions of these ideas.