Memory Management
System Design

Four documents close, freeing their memory back to the OS. A fifth document opens, needing 400K. There's 600K free in total — but not in one piece. This is fragmentation: memory that's free, in aggregate, but useless because it isn't contiguous where a request needs it to be.

Why memory needs managing at all

Every process needs three things from the OS's memory manager: relocation (a process can't know in advance which physical addresses it'll get, so every address it uses has to be translatable at runtime), protection (one process's memory must be invisible and untouchable to another's), and sharing (sometimes deliberately the opposite — letting two processes see the same physical memory, for a shared library, say). Every scheme in this chapter is a different answer to the same three requirements.

A process itself distinguishes logical addresses (what the program's own instructions refer to, starting from 0 as far as the program is concerned) from physical addresses (where that data actually lives in RAM). The mapping between them is exactly what the rest of this chapter is about.

Two kinds of waste

Choosing where a request goes: four policies

With dynamic partitioning (variable-sized chunks handed out on demand), every request has a choice of which free block to use. Four standard policies, in increasing order of how hard they look before deciding:

Worked example: same requests, four different outcomes

Free memory, left to right: 100K, 500K, 200K, 300K, 600K (1700K total). Four documents open in sequence, needing 212K, 417K, 112K, and 426K.

Only best fit manages to place all four requests here — the other three all run out of a single block large enough for doc4's 426K, even though enough total memory is technically free in every case. This is a real, verified result for this exact request sequence, not a universal ranking: best fit's own well-known weakness is exactly what's visible in Figure 1 below.

Figure 1 · where the free memory actually went

Practice 5.1

1. Free blocks of 50K, 200K, and 90K exist, in that order. A request for 80K arrives. Which block does first fit choose? Which does best fit choose?
   Show solution

   First fit: the 200K block (the first one large enough, scanning from the start). Best fit: the 90K block (the smallest of the two that fit, since 50K is too small).

2. Variation. Using this section's worked example, if doc4 needed only 174K instead of 426K, would first fit now succeed?
   Show solution

   Yes. First fit's leftover fragments after the first three requests were 288K, then reduced as later requests consumed parts of it; checking the specific fragment sizes, a 174K request fits within first fit's available leftovers where a 426K request did not — the STUCK outcome was specific to needing a block bigger than any single fragment first fit had left, not a general failure of first fit itself.

3. Interpretation. A system reports 40% of its memory is "free." Is that enough to say whether a new 100MB process can be loaded?
   Show solution

   No — exactly Figure 1's lesson. 40% free could be one contiguous block (100MB loads fine) or scattered across many small external-fragmentation gaps (100MB might not fit anywhere, no matter how much total free space exists). Total free memory and largest contiguous free block are different numbers, and only the second one answers this question.

4. Synthesis. Explain why internal fragmentation, unlike external fragmentation, can never be fixed by compaction.
   Show solution

   Compaction moves allocated blocks around to consolidate free space between them — it does nothing to the wasted space inside a block that's already larger than what was requested. Internal fragmentation is fixed only by changing the allocation granularity itself (smaller fixed-size units, or variable-size allocation in the first place), not by rearranging what's already allocated.

Section 5.1's fragmentation problems both trace back to one design choice: allocating memory in variable-sized chunks that have to match what's requested. The two schemes below fix that in opposite ways — one by making every chunk exactly the same size, the other by embracing variable sizes but tracking them cleverly.

Paging: uniform pieces, no external fragmentation

Paging divides logical memory into fixed-size pages and physical memory into equal-sized frames. A logical address is a pair (page number, offset); a per-process page table maps each page number to whichever frame currently holds it — frames don't need to be contiguous, which is exactly what eliminates external fragmentation: any free frame, anywhere in physical memory, can satisfy any page.

The cost moves, rather than disappears: the last page of a process is almost never exactly full, wasting the unused remainder — internal fragmentation, capped at just under one page per process instead of scaling with request size the way Section 5.1's partitioning did.

Segmentation: pieces that mean something

Segmentation divides a program into variable-sized logical units that actually correspond to something — code, data, stack, heap — each with its own entry in a segment table holding a base address and a limit (its length). A logical address is a pair (segment number, offset); translation checks the offset against the limit before adding it to the base, catching an out-of-bounds access directly.

Because segments are still variable-sized, external fragmentation is back — but each segment now maps onto something a programmer or compiler already understands, which makes per-segment protection and sharing (Section 5.5) far more natural than trying to protect an arbitrary fixed-size page.

Figure 2 · the same idea, two different lookups

Figure 3 · try your own address

Paging with segmentation: both at once

Real systems (x86 is the standard example) often combine them: divide a program into meaningful segments first, then page each segment internally. A logical address becomes (segment number, page number, offset); translation looks up the segment table for that segment's own page table, then looks up the page table for a frame, exactly as in plain paging from there.

This gets close to the best of both: segments still give meaningful, protectable, shareable units, but external fragmentation is gone, because each segment's physical footprint is now made of ordinary interchangeable page frames rather than one contiguous block. Internal fragmentation returns, but only in the last page of each segment — concretely, a 10,000-byte heap segment paged in 4,096-byte pages needs 3 pages, with the last one holding only 1,808 bytes and wasting 2,288 — not the whole segment, just its tail.

Practice 5.2

1. With a 4,096-byte page size, which page and offset does logical address 9,000 fall on?
   Show solution

   Page = 9000 ÷ 4096 = 2 (integer division), offset = 9000 − 2×4096 = 808. Page 2, offset 808.

2. Variation. A segment has base 2,000 and limit 500. Is offset 500 itself valid?
   Show solution

   No. A limit of 500 means valid offsets run from 0 to 499 — the segment holds exactly 500 bytes, addressed 0 through 499. Offset 500 is one past the end and triggers a protection fault, the same off-by-one boundary that makes array bounds checking easy to get wrong in general.

3. Interpretation. A programmer argues "paging is strictly better than segmentation, it doesn't even have external fragmentation." What's missing from that argument?
   Show solution

   It ignores what segmentation buys in exchange: natural, semantically-meaningful units for protection and sharing (Section 5.5). Comparing the two on fragmentation alone is comparing them on only one of several axes Section 5.4 evaluates properly — "better" depends on which cost you're more willing to pay.

4. Synthesis. Explain why paging-with-segmentation's internal fragmentation is bounded by "one page per segment" rather than "one page per process," connecting back to plain paging.
   Show solution

   In plain paging, the whole process is one continuous run of pages, so only its single last page can be partially empty — one page of waste, total. In paging-with-segmentation, each segment gets its own independent run of pages (code's pages, data's pages, stack's pages, each paged separately), so each segment can independently have a partially- empty last page — the worst case scales with the number of segments, not with process count, which is still far better than segmentation alone but not quite as tight as plain paging's single-process bound.

Sections 5.1 and 5.2 both assumed memory gets handed out in convenient units — a partition, a page. The kernel itself needs something much smaller, constantly: a new task_struct every time Chapter 1's clone() creates a thread, a small buffer every time a network packet arrives. Handing out a full page (typically 4,096 bytes) for a 1,400-byte request would waste more than half of it, every single time.

The buddy system: split what you have, merge what you free

The buddy allocator only ever deals in power-of-two sized blocks. A request for n bytes is rounded up to the next power of two; if no block of exactly that size is free, a larger free block is split in half repeatedly — each half is the other's buddy — until a block of the right size exists. Freeing works in reverse: when a block is freed, the allocator checks whether its buddy is also free, and if so, merges them back into the larger block, recursively, as far up as the merging goes.

Worked example: split down, then merge all the way back up

Starting from one free 512K block, three kernel allocations arrive, then all three are freed, in an order chosen to show the merge cascade.

Freeing the last-allocated block first triggers nothing; freeing it last triggers a chain reaction all the way back to the original block, because by then every other buddy up the chain happened to already be free too. Order of release, not just what's released, decides how much coalescing actually happens.

The slab allocator: pre-built objects, not raw bytes

Buddy's power-of-two rounding is expensive specifically for objects that are small, a fixed known size, and allocated/freed constantly — exactly what task_struct is. Worse, every buddy allocation of a fresh task_struct would need re-initialising from scratch, and every free would tear it back down, even though the next thread created a moment later will need an almost identical structure.

Jeff Bonwick's slab allocator (1994) fixes both problems at once: a cache exists per object type (a task_struct cache, an inode cache, and so on), backed by one or more slabs — contiguous pages divided into equal-sized slots, each slot big enough for exactly one object of that cache's type. Freed objects go back into their slot still mostly initialised, ready for instant reuse, sidestepping both buddy's rounding waste and repeated setup/teardown cost.

Practice 5.3

1. A request for 36K arrives in a buddy system. What size block does it actually receive, and how much is wasted?
   Show solution

   The next power of two above 36 is 64, so a 64K block is allocated, wasting 28K to internal fragmentation — the same mechanism as the 90K→128K case in the worked example, just with different numbers.

2. Variation. In the worked example, if T_save_heap were freed first, before doc_cache and T_ui_stack, would any merge happen at that point?
   Show solution

   No. T_save_heap's buddy is the other 128K half of the 256K region starting at 0K — but that region still contains T_ui_stack (allocated) plus some smaller free fragments, not one single free 128K block. A merge requires the entire buddy region to be free as one block of that exact size; a partially-used buddy blocks the merge regardless of how much of it happens to be free.

3. Interpretation. Why does a slab allocator make sense specifically for task_struct, but not for a request to load an entire 50MB video file into memory?
   Show solution

   Slabs exist to amortise the cost of repeated, frequent, fixed-size allocation of the same object type — exactly task_struct's pattern. A 50MB video file is large, variable-sized, and not requested with anything like the same frequency; there's no repeated setup/teardown cost to amortise, so buddy's page-granularity allocation (or a general-purpose allocator built on it) is the appropriate tool, not a dedicated object cache.

4. Synthesis. Connect the slab allocator's "keep objects initialised between uses" idea back to Chapter 3's mutex discussion: why might a slab-cached object need its own embedded lock initialised only once, ever?
   Show solution

   If a kernel object's slab slot is reused directly rather than freshly allocated and zeroed each time, any lock embedded inside that object (many kernel structures embed one) can stay initialised across reuses too, skipping repeated lock-initialisation cost the same way the object itself skips repeated general initialisation — provided the allocator correctly resets only the fields that need resetting, not the whole structure.

Section 5.2 described what each scheme does. This section prices it: how big is the translation table, how many steps does a single memory access cost, and what does each scheme's fragmentation actually take out of usable memory.

Worked example: what a page table actually costs

A 32-bit logical address space is 2³² bytes. At 4,096 (2¹²) bytes per page, that's 2³²÷2¹² = 2²⁰ = 1,048,576 pages. A single-level page table needs one entry per page; at a realistic 4 bytes per entry, that's 4,194,304 bytes — 4MB — of page table, for one process, even though most real processes use only a small fraction of their address space. A segment table for the same process, covering perhaps 6 segments (code, data, heap, stack, and a couple of shared libraries) at 8 bytes per entry, costs 48 bytes.

Practice 5.4

1. At 8 bytes per page-table entry instead of 4, what would the single-level page table in the worked example cost?
   Show solution

   2²⁰ entries × 8 bytes = 8,388,608 bytes = 8MB — double the 4MB figure, scaling linearly with entry size exactly as the formula predicts.

2. Variation. If the page size were doubled to 8,192 bytes, what happens to the page table size, and what happens to internal fragmentation?
   Show solution

   The page table shrinks by half (half as many pages needed to cover the same address space), but internal fragmentation's worst case doubles — a partially-used last page can now waste up to 8,191 bytes instead of 4,095. Page size is itself a trade-off between table overhead and fragmentation, not a free parameter.

3. Interpretation. A system with segmentation reports zero internal fragmentation. Does that mean it's using memory more efficiently than a paged system overall?
   Show solution

   Not necessarily — it may simply have traded internal fragmentation for external fragmentation (Section 5.1), which can waste just as much memory, just differently. "Zero internal fragmentation" describes one specific cost, not overall memory efficiency.

4. Synthesis. Explain why paging-with-segmentation's table overhead sits between plain paging and plain segmentation, rather than simply adding both costs together.
   Show solution

   Each segment only needs a page table covering its own size, not the full 2³²-byte address space plain paging assumes — a small data segment gets a small page table, not a slice of one enormous process-wide table. The segment table itself stays as cheap as in plain segmentation (Section 5.4's table above); what's added is several small, appropriately -sized page tables rather than one maximally-sized one, which is why the combination avoids the 4MB worst case while still eliminating external fragmentation.

Both schemes were introduced as ways to organise memory. Both also happen to be the OS's primary tool for keeping one process's memory invisible to another's, and for stopping a program from treating its own data as instructions — which is exactly what most real-world exploits try to do.

Permission bits, at whatever granularity the scheme offers

Every page table entry and every segment table entry carries permission bits alongside the address information: readable, writable, and critically, executable. A valid/invalid bit per page marks whether that page is even mapped to real memory at all — accessing an invalid page is the mechanism behind the classic "segmentation fault," regardless of which scheme is actually in use underneath.

Segmentation's natural fit shows up here directly: WriteWell's code segment is marked read+execute (never writable — running code shouldn't be able to modify itself), its data segment is read+write (never executable), and its stack is read+write and, critically, not executable. Paging applies the identical idea per page instead of per segment; compilers and linkers deliberately page-align each region specifically so a single page never straddles code and data with different permission needs.

Worked example: the NX bit stops a classic exploit

A buffer overflow in T_save's document-parsing code writes past the end of a stack-allocated buffer, overwriting the function's return address with the address of attacker-supplied bytes — also sitting on the stack, disguised as data. Classically, the function returns "into" those bytes, which are really machine code, and the attacker's code runs with WriteWell's own privileges.

The NX (No-eXecute) bit doesn't stop the overflow — that's a separate bug, still worth fixing. It stops the overflow from being useful to an attacker, by making the one region they can usually write to (the stack) a region the CPU will never treat as instructions.

Practice 5.5

1. A page is marked read+write but not execute. What happens if the CPU tries to fetch an instruction from it?
   Show solution

   A hardware fault, exactly like the NX-protected stack in the worked example — the permission bits are checked by hardware on every access, regardless of which specific exploit technique (or ordinary bug) caused the attempt.

2. Variation. If a compiler accidentally placed a small piece of executable code inside what should be a data-only page, what would happen when that code tried to run?
   Show solution

   It would fault, the same as any other attempt to execute a non-executable page — the hardware doesn't know or care whether code ended up there by attacker action or by an honest compiler mistake; the permission check is identical either way. This is exactly why compilers and linkers are careful to page-align segment boundaries (Section 5.5's opening paragraph).

3. Interpretation. A system has NX enabled but no ASLR. Is a buffer-overflow attack against it definitely blocked?
   Show solution

   Not definitely — NX blocks the classic "inject and run new code" version of the attack, but without ASLR, an attacker who already knows the fixed addresses of existing executable code can potentially chain together pieces of legitimate, already-executable code to do damage (return-oriented programming) without ever needing to execute injected bytes at all. NX and ASLR defend against overlapping but not identical attack techniques.

4. Synthesis. Explain why segmentation's per-segment permissions are described as more "natural" than paging's per-page permissions, using Section 5.2's definitions.
   Show solution

   A segment is defined to correspond to one meaningful program region (Section 5.2) — code, data, stack — so one permission setting per segment automatically matches how the program is actually structured. A page is a fixed-size, arbitrary slice of memory that happens to hold whatever fell within its boundaries; applying one permission per page only works cleanly because compilers deliberately align regions to page boundaries so that a mismatch (code and data sharing one page) doesn't occur, an extra constraint segmentation never needed in the first place.