Memory allocation and fragmentation
Covers how OSes assign RAM to processes, the types and causes of fragmentation, allocation algorithms (first/best/worst-fit, buddy), compaction and paging trade-offs, with formulas and exam-style examples.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Memory allocation and fragmentation matter because an operating system must place process code and data into RAM efficiently. Engineers need these ideas to design allocators (kernel heaps, user malloc), to tune page size and compaction policies, and to reason about performance and wasted memory in embedded, server and cloud systems.
Key ideas
Fragmentation: wasted memory that prevents useful allocations.
- Internal fragmentation: wasted space inside an allocated block because the allocator gives a larger block than requested (example: rounding up to alignment or page size). Exact definition: internal_fragmentation = sum_over_allocations(allocated_size - requested_size).
- External fragmentation: wasted space outside allocated blocks — free space split into small pieces so a large request cannot be satisfied even though total free memory is sufficient. Exact definition used below in Formulas.
Allocation strategies for contiguous memory (assume free-list of holes ordered by address):
- First-fit: scan from start, choose first hole big enough.
- Best-fit: choose smallest hole that fits (minimizes leftover in that hole).
- Worst-fit: choose largest hole, leaving a large remainder (intended to reduce small fragments).
- Next-fit: like first-fit but resume the search from the location of the last allocation; reduces search time but can lead to slightly worse memory utilization than first-fit. For each, state time/space trade-offs: first-fit tends to be fast and creates moderate-sized leftovers near start; next-fit resumes from the last position (often slightly faster scans than first-fit) but can yield worse memory utilization; best-fit reduces leftover sizes but can create many tiny holes; worst-fit can avoid tiny holes but is often poor.
The 50% rule (Knuth's rule): Under a random sequence of allocations and deallocations with sizes chosen independently from a distribution and using first-fit or next-fit, the expected number of holes (free blocks) tends to be roughly 0.5 times the number of allocated blocks in steady state. Assumptions: large number of operations, random independent sizes, allocator uses simple splitting but no coalescing anomalies. This is an empirical/analytic result; see Formulas and reviewer note. A common corollary used in exams: if average hole size ≈ average allocated block size, then free space ≈ 50% of allocated space, so roughly one-third of total memory is unusable due to external fragmentation (in that model).
Buddy system: memory is maintained in blocks of sizes that are powers of two. Allocation: round requested size up to nearest 2^k; split larger buddies recursively until exact size; free: coalesce with buddy if the buddy is free. Buddy gives O(log2(total_memory/min_block_size)) allocation/splitting (number of levels) and makes coalescing fast. It reduces external fragmentation relative to naive splitting, but causes internal fragmentation up to nearly half a block.
Compaction (memory defragmentation): moving allocated blocks to coalesce free holes into larger contiguous free space. Requires relocation support (loaders, base+limit or MMU with dynamic updating) and is costly: O(number_of_bytes_moved) and requires stopping processes or doing copy-on-write + remapping.
Paging vs fragmentation: paging divides physical memory into fixed-size pages and maps process pages to frames. Paging eliminates external fragmentation because any free frame can satisfy a page. But it introduces internal fragmentation: on average, each process wastes about half a page for its last page (assuming uniform distribution of process sizes). If page size is P, average internal waste ≈ P/2 per process (assumption: process size uniformly distributed across page boundary). If a process uses multiple independent regions (code, data, heap, stack), each region may incur ≈ P/2 waste on its last page.
Heap allocators (malloc/free): user-space allocators implement free-lists, bins by size, or segregated fits; they try to minimize fragmentation and allocation time. Kernel allocators may use slab allocators for fixed-size objects to avoid internal fragmentation.
Diagram you should be able to draw (for exam): draw a horizontal line labelled 0 .. M (addresses). Mark allocated rectangles (A1, A2, ...) and free rectangles (H1, H2, ...). Label sizes in KB and addresses at block boundaries. Show how an allocation request fits into first-fit (choose earliest hole) vs best-fit (choose smallest sufficient hole). Also draw a buddy split tree: root block size 1024KB split into two 512KB children, etc., and mark which child is allocated.
Reviewer note (uncertainties): 1) the precise mathematical derivation and constants for the 50% rule depend on model details — I summarize the rule and its assumptions but did not include a full proof. 2) Average internal fragmentation = P/2 is the commonly used approximation under uniform assumption; verify if your exam requires a different distribution model.
Formulas
internal_fragmentation = Σ (allocated_size_i - requested_size_i)
- allocated_size_i: size actually given to allocation i (B, KB). Applies always for contiguous allocators and paging. Unless stated otherwise, 1 KB = 1024 B (1 KiB).
external_fragmentation_ratio = (total_free_memory - largest_free_block) / total_free_memory
- total_free_memory: sum of all free holes (B).
- largest_free_block: size of the largest single free hole (B).
- Values range from 0 up to (but not including) 1 when total_free > 0. Higher means worse external fragmentation.
utilization = total_allocated / total_memory
- total_allocated: sum of allocated sizes (B), total_memory: RAM managed (B).
pages_needed = ceil(process_size / page_size)
- process_size, page_size in B. Applies for paging.
internal_waste_per_process_average ≈ page_size / 2
- approximate average wasted bytes on last page per process under uniform distribution of sizes across page boundary.
C allocator syntax to remember:
void *malloc(size_t size); — allocate at least size bytes, returns pointer or NULL.
void free(void *ptr); — deallocate previously allocated block.
void *realloc(void *ptr, size_t size); — resize block.
Worked examples
- First-fit allocation and measuring fragmentation Given holes (in KB) along memory in address order: [100, 500, 200, 300, 600]. Requests (KB) in sequence: 212, 417, 112, 426. Use first-fit. Steps:
- Request 212 KB: first hole ≥212 is 500 KB (the second hole). Allocate 212 KB there, leftover = 500 - 212 = 288 KB. Holes become [100, 288, 200, 300, 600].
- Request 417 KB: scan holes: 100 no, 288 no, 200 no, 300 no, 600 yes. Allocate 417 in 600 → leftover 183 KB. Holes → [100, 288, 200, 300, 183].
- Request 112 KB: scan: 100 no, 288 yes. Allocate 112 in 288 → leftover 176 KB. Holes → [100, 176, 200, 300, 183].
- Request 426 KB: scan all holes: none ≥426. Allocation fails (external fragmentation) even though total_free = 100+176+200+300+183 = 959 KB, which is >426 KB. Compute fragmentation measures:
- total_allocated = 212+417+112 = 741 KB.
- total_free = 959 KB.
- largest_free_block = 300 KB.
- external_fragmentation_ratio = (959 - 300)/959 = 659/959 ≈ 0.687 → 68.7% external fragmentation (by this measure).
- internal fragmentation = 0 if allocator gives exact sizes. Final answer (bold): 426 KB request fails due to external fragmentation; external fragmentation ratio ≈ 68.7%.
- Buddy system splitting (KB) Memory managed: 1024 KB (one block). Minimal allocation unit: 32 KB (so powers of two from 32 up to 1024). Allocate request 100 KB. Steps:
- Round 100 KB up to next power-of-two block size: 128 KB.
- Split 1024 → two 512s.
- Split one 512 → two 256s.
- Split one 256 → two 128s.
- Allocate one 128 KB buddy to the request. Remaining free blocks: one 128 KB (the sibling), one 256 KB, one 512 KB (the other half), etc., totaling 1024 - 128 = 896 KB free in structured buddy sizes. Internal fragmentation for this allocation = 128 - 100 = 28 KB.
- Paging internal fragmentation Process size = 18 KB, page size = 4 KB. pages_needed = ceil(18 / 4) = ceil(4.5) = 5 pages. Allocated memory = 5 × 4 KB = 20 KB. Internal fragmentation = 20 - 18 = 2 KB. Average internal waste per process ≈ 4/2 = 2 KB under uniform assumption.
Common mistakes
- Forgetting to round up when calculating pages_needed or buddy block size.
- Using total free memory as proof that a request must fit (ignores external fragmentation). Always check largest contiguous free block for contiguous allocation.
- Misapplying the 50% rule without listing its assumptions (random sizes, steady state).
- For buddy examples: failing to show splitting tree and buddy pairings when asked to prove coalescing correctness.
For your exam
Typical question types and what full-marks answers include:
- Definitions: define internal and external fragmentation with formulas and short examples.
- Short notes: compare first-fit, next-fit, best-fit, worst-fit, buddy system — explain time complexity, fragmentation behavior, and when each is used.
- Derivations: show pages_needed = ceil(process_size/page_size); derive average internal fragmentation ≈ page_size/2 under uniform assumptions; state the 50% rule and its assumptions.
- Numericals: perform allocation sequences (first-fit/best-fit), compute leftover holes, internal/external fragmentation, and show step-by-step arithmetic.
- Diagrams: draw memory line with addresses, label allocated and free blocks and show how a request fits or fails; draw buddy splitting tree and label sizes.
- Practical: explain compaction cost and list OS support needed (relocation, MMU mapping updates, stopping threads or using copy-on-write). A full answer always: (1) define terms, (2) state assumptions, (3) show steps with numbers/addresses, (4) give final numeric results with units.
Quick check
- What wastes space inside allocated blocks when the allocator rounds up to a fixed block size? 2) Which allocation strategy picks the smallest hole that fits a request? 3) With page size 4 KB, a 10 KB process needs how many pages and how much internal fragmentation? Answers: 1) Internal fragmentation. 2) Best-fit. 3) pages_needed = ceil(10/4) = 3 pages, internal fragmentation = 3*4 - 10 = 2 KB.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?