Memory Management in OS — Swapping & Fragmentation

Section 01

The Story That Explains Memory Management

📖 Real World Analogy

The Mall Parking Lot

A multi-storey mall has 500 parking bays and 2,000 shoppers arriving through the day. A parking attendant sits at the gate. When a car arrives, she checks whether a bay of the right size is free (a small hatchback in a compact bay, an SUV in a large bay). If yes, she assigns it. If no, the car waits or is turned away.

As cars come and go, the lot ends up looking like a comb: a used bay, then two empty bays, then five used, then one empty, then three used. Total empty bays: maybe 60 — but no single stretch of 6 adjacent bays for a tour bus. That bus goes home unhappy despite there being space. This is external fragmentation.

An operating system's memory manager is that attendant, only much faster and running thousands of times per second. It decides where each process lives in RAM, when to swap a process out to disk, and how to fight the fragmentation that eats into usable space. This chapter covers the mechanics.

💡

The Core Problem

RAM is a finite, shared resource. Every process needs some of it. The OS must decide: (a) where each process's code and data live, (b) how to translate the address a program generates into the actual RAM cell it means, and (c) what to do when memory runs low. Prevention of chaos = memory management.

Section 02

Address Binding — When Do Addresses Become Real?

A program's variable counter is not at address 42 forever. Where it actually lives in RAM depends on when that decision is made. Galvin identifies three stages at which addresses can be bound.

🛠️

Compile Time

absolute code

Compiler produces absolute addresses. If the memory location changes, the whole program must be recompiled. Old DOS .COM files worked this way.

📁

Load Time

relocatable code

Compiler produces relocatable addresses. Actual RAM address is fixed when the loader places the program. To move it, reload. Traditional executables.

⚡

Execution Time

MMU + relocation register

Binding happens on every memory access, using hardware (MMU). This is what every modern OS uses because it enables swapping and paging. Requires special hardware.

Section 03

Logical vs Physical Address — Meet the MMU

A CPU running a user program generates logical addresses (also called virtual addresses). The memory unit sees only physical addresses. The Memory Management Unit (MMU) is the hardware that translates one to the other.

In the simplest scheme, a relocation register holds a base value. The MMU simply adds this to every logical address. A separate limit register ensures the program can't reach outside its allotted range — any violation causes a trap to the OS (segmentation fault).

🎮 Interactive — Address Translation Step by Step

Setup: relocation register = 14 000, limit register = 1000. A user program generates logical addresses. Click Next to walk through valid and invalid accesses.

MMU translation with base and limit registers

Step 0 of 7

START Relocation register = 14 000, limit register = 1 000. User program will emit logical addresses; the MMU translates them to physical. Click Next to fire the first access.

Section 04

Swapping

RAM is limited. When too many processes are ready to run, the OS may swap processes out to a backing store (fast disk / SSD) to free RAM for others. Later, the swapped-out process is swapped back in and continues.

📋 Standard Swapping Overview

Backing Store

A fast disk large enough to hold copies of all user processes. Traditionally a dedicated swap partition on Linux; a hidden file (pagefile.sys) on Windows.

Ready Queue

Processes are ready to run; some are in RAM, some on the backing store.

Swap Out

OS moves a process's memory image from RAM to the backing store. RAM is freed.

Swap In

OS reads the process's image back from the backing store into RAM (possibly at a different address — hence the MMU relocation register).

Swap Time Calculation — The Bottleneck

# Time to swap out a 100 MB process to a disk with 50 MB/s transfer rate
time_out  = 100 MB / 50 MB/s = 2 seconds

# Then load a different 100 MB process from disk
time_in   = 100 MB / 50 MB/s = 2 seconds

# Total context switch involving swap
total    = 2 + 2 = 4 seconds  (plus seek + rotational latency)

⚠️

Why Standard Swapping Died

With multi-GB processes, swap times of many seconds are unacceptable. Modern systems use swapping only under memory pressure and prefer paging (swapping fixed-size pages, not whole processes). The concept still matters — Galvin teaches standard swapping to build intuition before introducing paging.

🎮 Interactive — Swapping Animation

Standard Swapping — RAM ↔ Backing Store

Step 0 of 5

START Process A (100 MB) is running in RAM. Process B (100 MB) is waiting on the backing store. Disk transfer rate = 50 MB/s. Click Next to trigger a swap.

Section 05

Contiguous Memory Allocation

In the simplest scheme, each process occupies a single contiguous section of memory. The OS kernel typically sits in low memory (with the interrupt vector); user processes live above it. Two hardware registers per process guard the boundaries.

Contiguous Layout with Relocation + Limit

🔑

Two Registers per Process

Each process is described by a pair: base register (where it starts in physical RAM) and limit register (how many bytes it may access from base). The MMU uses both on every access — the classic scheme still used inside modern paging systems.

Section 06

Dynamic Storage Allocation — First-Fit, Best-Fit, Worst-Fit

Over time, memory becomes a mix of used partitions and free holes. When a new process of size k arrives, which hole do we assign? Three classic strategies.

👥

First-Fit

grab the first that works

Scan holes from the start. Allocate the first hole ≥ k. Fastest search, minimal overhead. Simulation studies show it's the best-performing in practice.

🎯

Best-Fit

smallest that works

Search the entire list. Allocate the smallest hole ≥ k. Minimises wasted space per allocation but produces many tiny useless holes. Slower.

🚩

Worst-Fit

largest available

Search the entire list. Allocate the largest hole. Leaves large leftover holes — sounds good, but simulations show it's actually worse than First-Fit or Best-Fit.

🎮 Interactive — Three Strategies on the Same Workload

Initial holes (in address order): 100 KB, 500 KB, 200 KB, 300 KB, 600 KB. Three incoming requests: 212 KB, 417 KB, 112 KB. Click Next to see each strategy handle each request in parallel.

First-Fit vs Best-Fit vs Worst-Fit — same holes, same requests

First-Fit

Hole	Size (KB)
1	100
2	500
3	200
4	300
5	600

Best-Fit

Hole	Size (KB)
1	100
2	500
3	200
4	300
5	600

Worst-Fit

Hole	Size (KB)
1	100
2	500
3	200
4	300
5	600

        Request queue: 212 KB → 417 KB → 112 KB
      

Step 0 of 4

START All three strategies start with the same five holes. Sum of holes = 1700 KB. Three requests will arrive: 212 KB, 417 KB, 112 KB. Watch how each strategy's memory diverges.

Section 07

Numerical Problem 1 — Applying the Three Strategies

Given holes (in address order): 200 KB, 600 KB, 300 KB, 400 KB, 100 KB. Requests arrive in order: 315 KB, 195 KB, 450 KB. Which strategy satisfies all three?

First-Fit

👥 First-Fit Trace

Req 315

Scan: 200 ✗, 600 ✓ → allocate in hole 2. Remaining hole 2 = 600 − 315 = 285.

Req 195

Scan: 200 ✓ → allocate in hole 1. Remaining hole 1 = 200 − 195 = 5.

Req 450

Scan: 5, 285, 300, 400, 100 — largest is 400. 450 > 400 → FAILS.

Verdict

First-Fit satisfies 2 of 3 requests. Final holes: 5, 285, 300, 400, 100.

Best-Fit

🎯 Best-Fit Trace

Req 315

Candidates ≥ 315: 600, 400. Smallest = 400. Allocate. Remaining hole 4 = 400 − 315 = 85.

Req 195

Candidates ≥ 195: 200, 600, 300. Smallest = 200. Allocate. Remaining hole 1 = 200 − 195 = 5.

Req 450

Candidates ≥ 450: only 600. Allocate. Remaining hole 2 = 600 − 450 = 150.

Verdict

✅ Best-Fit satisfies all 3 requests. Final holes: 5, 150, 300, 85, 100.

Worst-Fit

🚩 Worst-Fit Trace

Req 315

Largest hole = 600. Allocate. Remaining hole 2 = 285.

Req 195

Largest hole = 400. Allocate. Remaining hole 4 = 205.

Req 450

Largest hole = 300. 450 > 300 → FAILS.

Verdict

Worst-Fit satisfies 2 of 3 requests. Final holes: 200, 285, 300, 205, 100.

🏆

Result

Best-Fit is the only strategy that satisfies all three requests here. Best-Fit tends to leave larger holes intact for larger future requests. But this depends on the workload — in general simulations, First-Fit tends to win because it's faster and often equally effective.

Section 08

Fragmentation — The Silent Memory Killer

As processes are allocated and freed, memory ends up with lots of small holes that add up to a lot of space — but no single hole big enough for a new large process. This is fragmentation.

📏 Internal Fragmentation

Wasted memory inside an allocated block.

Occurs when a process gets slightly more memory than requested (partition size rounded up)

Example: process asks for 8 KB, gets an 8.192 KB partition → 192 bytes wasted inside the block

Common with fixed-size partitioning and paging

📧 External Fragmentation

Wasted memory between allocated blocks.

Enough total free memory exists, but no single hole is big enough for the request

Example: three 30 KB holes total 90 KB, but a 80 KB process can't fit anywhere

The main problem with contiguous allocation

📈

The 50-Percent Rule

Galvin cites a classic analysis: given N allocated blocks, another N/2 blocks will typically be lost to fragmentation. That means one-third of total memory may become unusable — a striking cost, and the primary motivation for paging.

🎮 Interactive — External Fragmentation and Compaction

Fragmentation → Compaction — memory reorganised to make one big hole

Step 0 of 4

START Memory is 1200 KB total. Currently: P1=200 KB, P2=150 KB, P3=200 KB, P4=50 KB allocated (600 KB used). Free space = 600 KB but split across 5 small holes. Click Next to see what happens when a big process arrives.

Section 09

Compaction

Compaction physically moves all allocated blocks to one end of memory, coalescing all free holes into one large hole. Only possible when relocation is done at execution time (dynamic binding) — otherwise moving a block would break every hard-coded address.

# Compaction — simplest algorithm
for each allocated block, in address order:
    move it as low as possible (right up against previous block)
    update base register of the process
# All free memory now sits at the top as one big hole.

⚠️

Cost of Compaction

Compaction is expensive — it copies gigabytes of memory. Also, running processes must be paused (they can't observe their addresses changing under them). This is why modern systems avoid contiguous allocation entirely and use paging, which sidesteps the problem: pages don't need to be contiguous in physical memory.

Section 10

Numerical Problem 2 — Fragmentation Analysis

Consider the following memory layout after some allocations. Each row shows one memory block and its status:

Block	Size (KB)	Status
1	100	Used
2	50	Free
3	200	Used
4	30	Free
5	150	Used
6	80	Free
7	100	Used
8	40	Free

Questions

📋 Questions and Solutions

(a)

Total external fragmentation?
Sum of free blocks = 50 + 30 + 80 + 40 = 200 KB.

(b)

Can a 100 KB request be satisfied without compaction?
Free block sizes: 50, 30, 80, 40. Largest = 80 KB < 100 KB → NO.

(c)

Can a 200 KB request be satisfied without compaction?
Largest free block = 80 KB. 80 < 200 → NO.

(d)

What if we compact?
All 200 KB of free space combines into one hole. Now both the 100 KB and 200 KB requests can be satisfied ✓. But we lose CPU time doing the copy.

(e)

Memory usage summary:
Total = 100 + 50 + 200 + 30 + 150 + 80 + 100 + 40 = 750 KB. Used = 550 KB (73.3%). Wasted to external fragmentation = 200 KB (26.7%).

🏆

Key Takeaway

More than a quarter of memory is unusable due to fragmentation — despite there being plenty of free bytes in total. This is exactly why the industry moved from pure contiguous allocation to paging, which we cover in the next tutorial.

Section 11

Real-World Applications

💾

Linux Buddy Allocator

The kernel's low-level physical page allocator uses a variant of best-fit for power-of-two sized blocks. Reduces external fragmentation at the cost of internal fragmentation up to 50%.

Best-Fit · Buddy System

🖥️

JVM Heap Compaction

The G1 and ZGC garbage collectors periodically compact the Java heap, moving live objects to fresh regions to fight long-term fragmentation. Same idea as OS compaction.

Execution-time relocation

📂

malloc / free (glibc)

Uses a hybrid of best-fit and first-fit via size-class bins. Small allocations go to per-size arenas to prevent them from fragmenting large blocks.

Best-Fit + First-Fit hybrid

🔉

Windows Pagefile / Linux Swap

Modern OS "swapping" isn't Galvin's classical swapping — it swaps pages, not whole processes. But the concept and swap-time math are the same.

Paged swap

🎮

Game Engine Memory Pools

Unreal and Unity pre-allocate fixed-size pools for game objects to avoid runtime fragmentation. Trade internal fragmentation (padding) for zero external fragmentation.

Pool allocator

🛠️

Embedded Systems

Deep-embedded OSes (FreeRTOS) often disallow dynamic allocation entirely — all memory is statically partitioned at compile time. Zero fragmentation, zero flexibility.

Static partitioning

Section 12

Golden Rules — Memory Management

🔑 Galvin's Non-Negotiable Rules

Address binding can happen at compile time, load time, or execution time. Modern OSes use execution-time binding via the MMU — required for swapping and paging.

The MMU maps logical addresses generated by the CPU to physical addresses in RAM. The simplest scheme is relocation register + limit register.

The limit register check must execute on every memory access. Violation = trap to OS (segmentation fault). This is what protects processes from each other.

Swapping moves whole processes between RAM and a backing store. Swap time depends on process size and disk transfer rate — often seconds, so use sparingly.

In contiguous allocation, every process gets a single block. Three classic strategies for choosing which hole: First-Fit, Best-Fit, Worst-Fit. Best-Fit and First-Fit outperform Worst-Fit in practice.

First-Fit is fastest and usually just as good as Best-Fit. Best-Fit leaves smaller residues but scans the whole list. Worst-Fit is the loser — avoid it.

Internal fragmentation = wasted memory inside an allocated block (rounding up). External fragmentation = free memory that exists but cannot be used because it's split across small holes.

The 50-percent rule: given N allocated blocks, expect roughly N/2 blocks lost to fragmentation. About one-third of memory becomes unusable in the worst case.

Compaction moves allocated blocks to combine fragmented holes into one big hole. Requires execution-time binding. Expensive — copies entire blocks.

Contiguous allocation is instructive but obsolete for user processes on general-purpose OSes. Modern systems use paging, which eliminates external fragmentation entirely. That's the next chapter.