Paging Concepts

Imagine trying to seat guests at a wedding reception where every family must sit together at contiguous tables. If the Johnson family of six arrives after you've already seated several smaller families, you might find that despite having ten empty chairs scattered throughout the hall, there's no group of six adjacent chairs available. This is exactly the problem operating systems faced with contiguous memory allocation—and paging is the elegant solution that revolutionized memory management.

Paging is fundamentally about breaking the assumption of contiguity. Rather than requiring a process's memory to occupy a single continuous block of physical memory, paging allows the operating system to scatter a process's memory across any available physical locations while maintaining the illusion of contiguous memory to the process itself.

Before we can appreciate paging, we must understand the fundamental limitations it addresses. In contiguous memory allocation, each process must occupy a single, unbroken block of physical memory addresses. This requirement creates several severe problems:

External Fragmentation: As processes are loaded and unloaded from memory, the available free space becomes fragmented into many small, non-contiguous holes. Even when the total free memory exceeds a process's requirements, the process cannot be loaded if no single contiguous block is large enough.

Compaction Overhead: The only solution to external fragmentation in contiguous systems is compaction—physically moving processes in memory to consolidate free space. This is extremely expensive because:

• All memory contents must be copied
• All address references within processes must be updated
• The system essentially halts during compaction
• I/O operations become complicated when buffers move

Rigid Allocation: Processes must declare their maximum memory requirements upfront, leading to either:

• Under-allocation: Process crashes when it needs more memory
• Over-allocation: Valuable memory sits unused 'just in case'

Consider this scenario demonstrating external fragmentation:

Initial state: 128 KB total memory

|  Process A (32KB)  |  Process B (24KB)  |  Process C (40KB)  |  Free (32KB)  |

After Process B terminates:

|  Process A (32KB)  |     Hole (24KB)    |  Process C (40KB)  |  Free (32KB)  |

New process D needs 48KB:
- Total free memory: 24KB + 32KB = 56KB ✓
- Largest contiguous block: 32KB ✗
- Result: Process D cannot be loaded!

Despite having 56KB free—more than enough for Process D—the system cannot accommodate the request. This is the fundamental problem paging solves.

Paging introduces a beautifully simple abstraction that eliminates the contiguity problem:

1. Divide logical memory into fixed-size blocks called pages
2. Divide physical memory into fixed-size blocks called frames
3. Pages and frames are the same size
4. Any page can be placed in any available frame

This last point is the key insight: by standardizing the size of allocation units, we ensure that any free frame can hold any page. There's no need to find a block 'large enough'—all blocks are exactly the same size, and therefore all blocks are interchangeable.

The fundamental relationship:

A process sees its memory as a linear sequence of pages numbered 0, 1, 2, and so on. From the process's perspective, these pages are contiguous—page 1 immediately follows page 0 in the logical address space. However, in physical memory, page 0 might be in frame 47, page 1 in frame 12, and page 2 in frame 103. The operating system maintains a page table that records which frame holds each page, enabling transparent translation between the process's view (logical addresses) and reality (physical addresses).

A page is a fixed-size block of contiguous logical addresses within a process's address space. Understanding pages requires understanding how logical addresses are structured in a paging system.

Logical Address Structure:

In a paging system, every logical address generated by the CPU is conceptually divided into two parts:

|<---- Page Number (p) ---->|<---- Page Offset (d) ---->|

• Page Number (p): Identifies which page of the process contains this address
• Page Offset (d): Identifies the specific byte within that page

The size of the page determines how many bits are used for each part. For a page size of 2^n bytes:

• The lower n bits of the address form the offset
• The remaining upper bits form the page number

Page Characteristics:

1. Fixed Size: All pages within a system are exactly the same size. This uniformity is essential for the interchangeability that makes paging work.

2. Logical Entity: Pages exist in the logical address space. A process with a 64KB address space and 4KB pages has exactly 16 pages (numbered 0-15).

3. Internal Contiguity: Within a page, addresses are truly contiguous. Byte 0 of page 3 is followed by byte 1 of page 3, and so on.

4. Page Boundaries: Pages begin at addresses that are multiples of the page size. With 4KB pages, pages start at addresses 0x0000, 0x1000, 0x2000, etc.

5. Process-Specific Numbering: Page numbers are local to each process. Process A's page 5 and Process B's page 5 are completely unrelated.

A frame (also called a page frame or physical frame) is a fixed-size block of contiguous physical memory. Frames are the physical counterpart to logical pages—if pages are containers in a process's imagination, frames are actual containers in RAM.

Physical Address Structure:

Just as logical addresses decompose into page number and offset, physical addresses decompose into:

|<---- Frame Number (f) ---->|<---- Frame Offset (d) ---->|

• Frame Number (f): Identifies which frame in physical memory
• Frame Offset (d): Identifies the specific byte within that frame

Critical insight: Because pages and frames are the same size, the offset is identical in both the logical and physical addresses. Only the page/frame number changes during address translation.

The Frame Table:

The operating system maintains a system-wide frame table that tracks the state of every physical frame:

Frame Table:
┌───────┬────────────┬─────────────┬─────────────┐
│ Frame │   Status   │   Process   │    Page     │
├───────┼────────────┼─────────────┼─────────────┤
│   0   │  Reserved  │    Kernel   │      -      │
│   1   │  Reserved  │    Kernel   │      -      │
│   2   │ Allocated  │   PID 201   │    Page 0   │
│   3   │    Free    │      -      │      -      │
│   4   │ Allocated  │   PID 105   │    Page 3   │
│   5   │ Allocated  │   PID 201   │    Page 2   │
│   6   │    Free    │      -      │      -      │
│   7   │ Allocated  │   PID 105   │    Page 0   │
│  ...  │    ...     │     ...     │     ...     │
└───────┴────────────┴─────────────┴─────────────┘

Notice how frames 2 and 5 belong to the same process (PID 201) but hold different pages (0 and 2). This illustrates the non-contiguous nature of paging: process 201's pages are scattered across frames 2 and 5, with frame 4 (belonging to a different process) in between.

The heart of paging is the mapping between pages and frames. This mapping is maintained in a structure called the page table, which exists for each process (we'll explore page tables in detail in the next module). For now, let's understand the concept of the mapping itself.

The Mapping Function:

Conceptually, the page table implements a function:

f(page_number) → frame_number

For a given process, if page 5 is stored in frame 27, the page table entry for page 5 contains the value 27. When the CPU accesses logical address X within page 5, the Memory Management Unit (MMU) uses the page table to translate this to the corresponding address within frame 27.

Key Properties of the Mapping:

1. One Process's View: Each process has its own page table, its own mapping. Process A's page 3 might map to frame 50, while Process B's page 3 maps to frame 12.

2. Dynamic Nature: The mapping can change. The OS might move a page to a different frame if needed (after updating the page table, of course).

3. Sparse Possibility: Not all page table entries need to be valid. A process might only use a small portion of its potential address space, with most pages marked as 'invalid' (not present in memory).

4. Offset Preservation: The offset within a page equals the offset within the corresponding frame. If you're accessing byte 500 of page 7, you'll access byte 500 of whatever frame holds page 7.

Let's visualize how memory is divided into pages and frames, and how the mapping works in practice.

Physical Memory (Frames):

Physical Memory: 64KB (16 frames of 4KB each)

┌─────────────────┐ ← 0x0000
│     Frame 0     │   Kernel reserved
├─────────────────┤ ← 0x1000
│     Frame 1     │   Kernel reserved
├─────────────────┤ ← 0x2000
│     Frame 2     │   Process A, Page 0
├─────────────────┤ ← 0x3000
│     Frame 3     │   FREE
├─────────────────┤ ← 0x4000
│     Frame 4     │   Process B, Page 0
├─────────────────┤ ← 0x5000
│     Frame 5     │   Process A, Page 2
├─────────────────┤ ← 0x6000
│     Frame 6     │   Process B, Page 1
├─────────────────┤ ← 0x7000
│     Frame 7     │   FREE
├─────────────────┤ ← 0x8000
│     Frame 8     │   Process A, Page 1
├─────────────────┤ ← 0x9000
│     Frame 9     │   Process B, Page 2
├─────────────────┤ ← 0xA000
│    Frame 10     │   FREE
├─────────────────┤ ← 0xB000
│    Frame 11     │   Process A, Page 3
├─────────────────┤ ← 0xC000
│    Frame 12     │   FREE
├─────────────────┤ ← 0xD000
│    Frame 13     │   Process B, Page 3
├─────────────────┤ ← 0xE000
│    Frame 14     │   FREE
├─────────────────┤ ← 0xF000
│    Frame 15     │   FREE
└─────────────────┘ ← 0x10000

Paging requires intimate cooperation between hardware and software. The Memory Management Unit (MMU), a hardware component usually integrated into the CPU, performs address translation for every memory access. This is critical because even a single machine instruction might generate multiple memory accesses, and software-based translation would be far too slow.

The MMU's Role:

1. Intercept every logical address generated by the CPU
2. Extract the page number from the logical address
3. Look up the corresponding frame in the page table
4. Substitute the frame number for the page number
5. Generate the physical address for the memory system

This entire process must happen in hardware, transparently, on every single memory reference—millions or billions of times per second.

The Translation Process in Detail:

1. CPU executes instruction that references logical address LA
2. MMU receives LA
3. MMU splits LA into (page_number, offset)
4. MMU checks if (page_number, frame) is cached in TLB
   - If TLB hit: Use cached frame number
   - If TLB miss: Read page table entry from memory
5. MMU checks valid bit in page table entry
   - If valid: Extract frame number
   - If invalid: Raise page fault exception
6. MMU checks protection bits
   - If access permitted: Continue
   - If access denied: Raise protection fault exception
7. MMU combines frame_number with offset to form physical address PA
8. Physical address PA sent to memory controller
9. Memory returns/accepts data at that address

This entire sequence must complete in nanoseconds. The TLB is crucial—without it, every memory access would require two memory accesses (one to read the page table entry, one for the actual data), halving memory performance.

Paging was not invented in isolation—it emerged from decades of struggle with memory management limitations. Understanding this history illuminates why paging works the way it does.

The Evolution of Memory Management:

1. Bare Machine (1950s): Programs loaded at fixed addresses. No protection, no abstraction. A single program occupied all of memory.

2. Fixed Partitions (Early 1960s): Memory divided into fixed-sized partitions. Each partition could hold one process. Problems: internal fragmentation within partitions, inflexibility.

3. Variable Partitions (Mid 1960s): Partitions sized to fit processes exactly. Eliminated internal fragmentation but created external fragmentation. Compaction required but expensive.

4. Paging (Late 1960s): The breakthrough. Fixed-size pages solved the fitting problem—any page fits in any frame. First major implementation: Multics (1969) and IBM System/370 (1970).

5. Virtual Memory (1970s-present): Combined paging with demand loading—pages can be on disk, loaded on demand. Enabled address spaces larger than physical memory.

The Atlas Computer:

The Atlas computer, developed at the University of Manchester and operational in 1962, deserves special mention. It was the first machine to implement what we now call virtual memory with demand paging. The Atlas pioneers introduced:

• The concept of 'paging' with fixed-size blocks
• Automatic page replacement
• The two-level memory hierarchy (main memory + drum storage)

Many concepts we treat as fundamental—page tables, page faults, and replacement policies—were invented for Atlas. The basic architecture of paging has remained remarkably stable for over 60 years, a testament to the elegance of the original design.

We've covered the foundational concepts of paging. Let's consolidate the essential knowledge:

What's Next:

Now that we understand the fundamental concepts of pages and frames, we'll explore the critical topic of page size. The choice of page size has profound implications for system performance, memory utilization, and page table overhead. Different systems have made different choices, and understanding the tradeoffs is essential for systems engineering work.