Paging Concepts

Imagine you're organizing books in a library. Traditional contiguous allocation is like requiring all volumes of an encyclopedia to sit on adjacent shelves—Volume 1 next to Volume 2 next to Volume 3. When the library fills up, you might have empty space scattered throughout, but inserting a new 20-volume encyclopedia becomes impossible because there's no single shelf section with 20 adjacent empty spaces.

Non-contiguous allocation is the revolutionary insight that volumes don't need to be adjacent. Volume 1 can be on shelf A4, Volume 2 on shelf C12, Volume 3 on shelf B7—as long as you have a good catalog (the page table), readers can find any volume instantly. The total number of empty shelf spaces is all that matters, not their arrangement.

This simple shift—from requiring contiguous placement to allowing scattered placement—fundamentally transforms memory management.

Before paging, memory allocation suffered from a fundamental constraint: a process's entire memory had to occupy a single, contiguous region of physical addresses. This requirement created cascading problems:

The Fitting Problem:

As processes come and go, memory becomes fragmented:

Time T1: Three processes loaded
┌────────────┬────────────┬────────────┬────────────┐
│  Process A │  Process B │  Process C │    Free    │
│   (32 KB)  │   (24 KB)  │   (40 KB)  │   (32 KB)  │
└────────────┴────────────┴────────────┴────────────┘

Time T2: Process B terminates
┌────────────┬────────────┬────────────┬────────────┐
│  Process A │    Hole    │  Process C │    Free    │
│   (32 KB)  │   (24 KB)  │   (40 KB)  │   (32 KB)  │
└────────────┴────────────┴────────────┴────────────┘

Time T3: New process D needs 48 KB
- Total free space: 24 KB + 32 KB = 56 KB ✓
- Largest contiguous block: 32 KB ✗
- Process D CANNOT be loaded!

Despite having 56 KB free—more than enough for Process D—the system cannot accommodate it because no single contiguous region is large enough.

Why Did Early Systems Require Contiguity?

Contiguity was required because of how address translation worked:

1. Base-and-Bound Translation: The hardware used a 'base register' plus an offset. Every address in a process was calculated as physical = base + logical. This only works if all addresses are contiguous from the base.

2. Simple Hardware: Early computers had limited transistor budgets. Complex address translation was impractical.

3. Single Process Systems: When only one program ran at a time, contiguity was natural—the program owned all memory.

4. No Abstraction Layer: Programs often contained absolute physical addresses. Moving a program meant patching every address reference.

Paging breaks free from all these limitations with a simple but powerful abstraction.

Paging solves the contiguity problem through a fundamental insight: if all allocation units are the same size, any free unit can hold any allocation. There's never a problem of 'fitting' because everything fits everywhere.

The Key Mechanism:

1. Divide logical memory into fixed-size pages (e.g., 4 KB each)
2. Divide physical memory into fixed-size frames (same size as pages)
3. Any page can be placed in any free frame
4. The page table records which frame holds each page

Because all pages are identical in size, and all frames are identical in size, the problem transforms from 'finding a large enough hole' to simply 'having enough frames total.'

What Changed Fundamentally:

Non-contiguous allocation is only possible because of the page table acting as an indirection layer between logical and physical addresses. This indirection is what allows the process to see contiguous memory while physical memory is scattered.

The Power of Indirection:

Process P's View (Logical)         Page Table          Physical Memory
┌─────────────────────┐         ┌───────────┐      ┌─────────────────────┐
│   Page 0            │──────▶  │ 0 → 47    │      │  Frame 0  (kernel)  │
│   (0x0000-0x0FFF)   │         │ 1 → 12    │      │  Frame 1  (kernel)  │
├─────────────────────┤         │ 2 → 91    │      │  ...                │
│   Page 1            │──────▶  │ 3 → 5     │      │  Frame 5  (P's pg 3)│
│   (0x1000-0x1FFF)   │         │ 4 → 203   │      │  ...                │
├─────────────────────┤         └───────────┘      │  Frame 12 (P's pg 1)│
│   Page 2            │──────▶                     │  ...                │
│   (0x2000-0x2FFF)   │                            │  Frame 47 (P's pg 0)│
├─────────────────────┤                            │  ...                │
│   Page 3            │──────▶                     │  Frame 91 (P's pg 2)│
│   (0x3000-0x3FFF)   │                            │  ...                │
├─────────────────────┤                            │  Frame 203(P's pg 4)│
│   Page 4            │──────▶                     │  ...                │
│   (0x4000-0x4FFF)   │                            └─────────────────────┘
└─────────────────────┘

The process executes code referencing addresses 0x0000 through 0x4FFF as if they were contiguous. The page table seamlessly redirects each access to the correct, scattered physical frame.

Properties Enabled by Indirection:

1. Location Independence: A page's logical address is fixed, but its physical location can change. The OS can move pages between frames by updating the page table.

2. Dynamic Rearrangement: The OS can relocate pages at any time (e.g., during memory optimization) without the process knowing or caring.

3. Lazy Allocation: Pages can be added to the address space without immediately consuming physical frames (demand paging).

4. Sparse Address Spaces: A process can have a large logical address space with only some pages actually allocated.

5. Memory Sharing: Multiple processes can have page table entries pointing to the same frame, sharing data or code efficiently.

The Cost of Indirection:

Indirection isn't free. Every memory access now requires:

1. Decompose logical address into page number + offset
2. Lookup page table entry (another memory access!)
3. Combine frame number with offset
4. Access physical memory

This is why TLBs exist—to cache recent translations and avoid the page table lookup overhead.

Understanding exactly how pages are allocated reveals why non-contiguous allocation works so smoothly.

When a New Process Starts:

Process creation: 5 logical pages required

Step 1: Determine page requirements
- Code segment: 10 KB → 3 pages (0, 1, 2)
- Data segment: 4 KB → 1 page (3)
- Stack segment: 4 KB → 1 page (4)
- Total: 5 pages needed

Step 2: Consult free frame list
- Free frames available: [7, 12, 18, 21, 37, 42, 56, 89, 103, 127, ...]
- Grab 5 frames: 7, 12, 18, 21, 37

Step 3: Build page table
┌──────┬────────┐
│ Page │ Frame  │
├──────┼────────┤
│  0   │   7    │
│  1   │  12    │
│  2   │  18    │
│  3   │  21    │
│  4   │  37    │
└──────┴────────┘

Step 4: Load process content
- Load code into frames 7, 12, 18
- Initialize data in frame 21
- Set up stack in frame 37

Step 5: Update frame table
- Mark frames 7, 12, 18, 21, 37 as allocated to this process

The Free Frame List:

The operating system maintains a free frame list (or pool) containing all unallocated frames. This can be implemented as:

1. Linked List: Each free frame contains a pointer to the next free frame. O(1) allocation, O(1) deallocation.

2. Bitmap: One bit per frame (0=free, 1=allocated). O(n) to find free frame, but compact representation.

3. Stack: Free frame numbers pushed/popped. O(1) operations, commonly used.

Key Insight: Order Doesn't Matter

When allocating frames, the OS can grab any available frames—it doesn't matter which ones or in what order. This is fundamentally different from contiguous allocation where you need frames that are physically adjacent.

Contiguous: Need frames 10, 11, 12, 13, 14 specifically (adjacent)
Paging: Any 5 frames work: 7, 42, 18, 103, 21 are fine!

This freedom means allocation almost never fails due to fragmentation. If you have N free frames anywhere in memory, you can allocate N pages.

Non-contiguous allocation dramatically improves memory utilization. Let's quantify this improvement.

Utilization Under Contiguous Allocation:

With external fragmentation, memory utilization degrades over time:

Simulation: 100 process arrivals/departures

Time    Allocated    Free    Usable Free    Utilization
T=0     0 KB         128 KB  128 KB         0%
T=10    96 KB        32 KB   32 KB          75%
T=50    80 KB        48 KB   20 KB (holes)  62%
T=100   72 KB        56 KB   8 KB (holes!)  56%

Despite 56 KB being 'free', only 8 KB is usable as the rest is in scattered holes too small for any waiting process.

Utilization With Paging:

With non-contiguous allocation, utilization stays high:

Simulation: Same 100 process arrivals/departures

Time    Allocated    Free    Usable Free    Utilization
T=0     0 KB         128 KB  128 KB         0%
T=10    96 KB        32 KB   32 KB          75%
T=50    80 KB        48 KB   48 KB          62%
T=100   72 KB        56 KB   56 KB          56%

Every free frame is usable! The 56 KB free at T=100 can accommodate any process up to 56 KB.

The 50% Rule Validation:

Under contiguous allocation, the '50% rule' states that external fragmentation consumes approximately one-third of memory (N holes of size N/2 each, wasting N/2 of total 3N/2 memory = 1/3 = 33%).

With paging, this waste disappears entirely because there are no holes—every frame is either fully used or fully free.

Real-World Impact:

Consider a server with 128 GB RAM:

• Contiguous allocation: ~40-50 GB lost to fragmentation
• Paging: ~2-4 GB overhead for page tables, rest fully usable

That's potentially 35+ GB of recovered memory—equivalent to significant hardware savings.

From the process's viewpoint, nothing changes. The process has no idea—and no need to know—that its memory is scattered across physical RAM.

The Contiguous Illusion:

Process P's mental model:

     0x0000 ┌─────────────────────┐
            │       Code          │  } 12 KB code segment
     0x3000 ├─────────────────────┤
            │       Data          │  } 8 KB data segment
     0x5000 ├─────────────────────┤
            │       Heap          │  } grows upward
            │         ↓           │
            │         .           │
            │         .           │
            │         ↑           │
            │       Stack         │  } grows downward
     0xFFFF └─────────────────────┘

Process P sees a simple, contiguous 64 KB address space.
It can access any address from 0x0000 to 0xFFFF.
Pointers work normally. Arrays are contiguous. Stack grows down.

The process codes, compiles, and executes exactly as if memory were contiguous. This abstraction gives us the best of both worlds:

• Logical simplicity for programmers
• Physical flexibility for the OS

What the Process Can't See:

The process is unaware of:

• Which physical frames hold its pages
• That its pages might be scattered
• Other processes existing in memory
• Frame numbers, page tables, or any memory management details

What the Process Does See:

• A private, contiguous address space
• Memory starting at address 0 (typically)
• Its own code, data, heap, and stack
• Valid addresses it can access

Protection Through Invisibility:

This isolation isn't just convenient—it's essential for security and stability. Process P cannot:

• Access Process Q's memory (no way to form those addresses)
• Corrupt kernel data (protected pages trigger faults)
• Know where anything is in physical memory

The page table defines what exists for each process. Anything not in the page table simply doesn't exist from that process's perspective.

Non-contiguous allocation enables capabilities far beyond just avoiding fragmentation. The flexibility it provides is foundational for modern operating system features.

1. Page-Level Sharing:

Multiple processes can share physical frames by having page table entries point to the same frame:

Process A's Page Table:        Process B's Page Table:
┌──────┬─────────┐            ┌──────┬─────────┐
│ Pg 0 │ Frm 47  │            │ Pg 0 │ Frm 12  │  ← Different
│ Pg 1 │ Frm 200 │←─────┬─────│ Pg 1 │ Frm 200 │  ← Same! Shared code
│ Pg 2 │ Frm 201 │←─────┼─────│ Pg 2 │ Frm 201 │  ← Same! Shared code
│ Pg 3 │ Frm 53  │      │     │ Pg 3 │ Frm 88  │  ← Different (private data)
└──────┴─────────┘      └─────└──────┴─────────┘

Frames 200 and 201 contain shared library code.
Both processes read from the same physical memory!

This is how shared libraries (libc, DLLs) work without duplicating code in every process.

2. Sparse Address Spaces:

Non-contiguous allocation permits sparse address spaces—large logical address spaces with most addresses unmapped:

64-bit process address space (theoretical 16 EB):

0x0000000000000000 ┌─────────────────┐
                   │   Code (4 MB)   │  ← mapped, 1024 pages
                   ├─────────────────┤
                   │     unmapped     │
                   │   (huge gap)     │
0x0000700000000000 ├─────────────────┤
                   │   Heap (64 MB)  │  ← mapped, 16384 pages
                   ├─────────────────┤
                   │     unmapped     │
                   │   (huge gap)     │
0x00007FFFE0000000 ├─────────────────┤
                   │   Stack (8 MB)  │  ← mapped, 2048 pages
0x00007FFFFFFFFFFF └─────────────────┘

Actual physical memory used: 76 MB (19456 pages)
Address space spanned: ~140 TB
Ratio: > 99.999% of address space is unmapped but costs nothing!

The OS only needs page table entries (and frames) for actually-used regions. The gaps cost nothing.

While non-contiguous allocation eliminates external fragmentation, it introduces its own implementation complexities that the OS must handle.

Frame Tracking:

The OS must efficiently track which frames are free and which are allocated:

Common Data Structures:

1. Stack-based free list:
   ┌─────┐
   │ 127 │ ← Top: next frame to allocate
   │ 89  │
   │ 56  │
   │ 42  │
   │ 37  │
   │ ... │
   └─────┘
   - O(1) allocation: pop
   - O(1) deallocation: push

2. Bitmap:
   Frame:  0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15
   Bit:    1  1  0  0  1  1  1  0  0  0  1  1  0  0  0  0
           ▲     ▲              ▲        ▲
           Used  Free           Used     Free
   - Compact: 1 bit per frame
   - O(n) to find free frame (can optimize with hierarchical bitmap)

Page Table Management:

Each process needs its own page table, and these tables themselves consume memory:

1. Page Table Allocation: Page tables are stored in kernel memory, typically in frames themselves (page tables are paged!).

2. Context Switch Updates: When switching processes, the Page Table Base Register must be updated to point to the new process's page table.

3. TLB Flushing: Context switches typically require TLB flushes since cached translations belong to the previous process. (Some TLBs support ASIDs to avoid this.)

4. Hierarchical Tables: For 64-bit systems, multi-level page tables are required to avoid impossible memory overhead.

Memory Overhead Analysis:

For a 32-bit system with 4KB pages and 4-byte PTEs:

• Per-process page table: up to 4 MB
• 100 processes: up to 400 MB in page tables
• This is why sparse page tables and hierarchical structures matter!

For a 64-bit system with hierarchical tables:

• Typical process uses 10 KB - 100 KB for page tables
• Overhead is proportional to address space used, not possible

Non-contiguous allocation is perhaps paging's most transformative feature. Let's consolidate what we've learned:

What's Next:

We've seen that paging eliminates external fragmentation through non-contiguous allocation. But what about the fragmentation it does have? The next page explores why paging has no external fragmentation at all, providing a rigorous understanding of this critical property and its implications.