Demand Paging, Translation Faults & Second-Chance Clock Page Replacement

The memory subsystem is one of the most performance-critical domains of an operating system kernel. Physical memory (RAM) is finite, expensive, and subject to fragmentation. By decoupling the programmer's view of memory from physical hardware addresses, Virtual Memory provides process isolation, uniform contiguous address spaces, and the illusion of near-limitless storage capacity. Through multi-level hierarchical page tables, Translation Lookaside Buffers (TLB), demand paging fault handlers, and clock-based frame replacement algorithms, operating systems dynamically balance cache performance against disk I/O bottlenecks.

1. Formal Foundations of Virtual Memory & Multi-Level Paging#

Before virtual memory, programs executed directly against physical memory addresses. This model suffered from three fatal flaws: lack of process isolation (any errant pointer could overwrite kernel memory or other processes), severe external fragmentation, and inability to run programs whose code and data exceeded physical RAM capacity.

+----------------------------------------------------------------------------------------------------+
|                                    VIRTUAL-TO-PHYSICAL PAGING MODEL                                |
+----------------------------------------------------------------------------------------------------+
  Process Virtual Address Space (4 KB Pages)                    Physical RAM (4 KB Frames)
  +-------------------------------------+                      +-------------------------------------+
  | Virtual Page 0 (Code Segment)       | -------------------> | Physical Frame #14                  |
  +-------------------------------------+                      +-------------------------------------+
  | Virtual Page 1 (Data Segment)       | -------------------> | Physical Frame #2                   |
  +-------------------------------------+                      +-------------------------------------+
  | Virtual Page 2 (Unused / Guard)     | (Not Mapped)         | Physical Frame #99 (Other Process)  |
  +-------------------------------------+                      +-------------------------------------+
  | Virtual Page 3 (Heap Segment)       | -------------------> | Physical Frame #45                  |
  +-------------------------------------+                      +-------------------------------------+
  | Virtual Page 4 (Stack Segment)      | ----------+          | Physical Frame #7                   |
  +-------------------------------------+           |          +-------------------------------------+
                                                    +--------> | Physical Frame #88                  |
                                                               +-------------------------------------+
  Invariant: Contiguous virtual pages map to non-contiguous, arbitrary physical frames!
+----------------------------------------------------------------------------------------------------+

The 48-Bit x86-64 Hierarchical 4-Level Paging Model#

On modern x86-64 architectures, physical memory addresses are translated using a 4-level hierarchical page table structure. A virtual address is 48 bits wide (sign-extended across 64 bits):

+----------------------------------------------------------------------------------------------------+
|                               x86-64 48-BIT VIRTUAL ADDRESS DECOMPOSITION                          |
+----------------------------------------------------------------------------------------------------+
   47        39 38        30 29        21 20        12 11                        0
  +------------+------------+------------+------------+---------------------------+
  | PML4 Index | PDPT Index |  PD Index  |  PT Index  | Physical Page Offset (12) |
  +------------+------------+------------+------------+---------------------------+
    9 Bits       9 Bits       9 Bits       9 Bits       12 Bits (4096 Byte Range)
    (512 Ent)    (512 Ent)    (512 Ent)    (512 Ent)
+----------------------------------------------------------------------------------------------------+

1. PML4 (Page Map Level 4): Bits 47:39 index into the PML4 table, located via physical address stored in CPU register %cr3.
2. PDPT (Page Directory Pointer Table): Bits 38:30 index into the PDPT table.
3. PD (Page Directory): Bits 29:21 index into the Page Directory.
4. PT (Page Table): Bits 20:12 index into the lowest-level Page Table.
5. Physical Page Offset: The lowest 12 bits (bits 11:0) are passed directly through to address the exact byte within the 4 KB (2^12 = 4096 bytes) physical frame.

Why Hierarchical Paging is Mandatory#

A single flat page table mapping a 48-bit address space would require:

2^48 bytes / 4096 bytes = 2^36 Page Table Entries (PTEs).

At 8 bytes per PTE: 2^36 · 8 bytes = 512 Gigabytes of memory just to store the page table for a single process!

Multi-level paging allocates intermediate tables on-demand. If a process uses only 10 MB of memory, unmapped intermediate branches remain null pointers, reducing page table overhead to a few kilobytes.

Anatomy of a 64-Bit Page Table Entry (PTE)#

+----------------------------------------------------------------------------------------------------+
|                                    x86-64 64-BIT PAGE TABLE ENTRY                                  |
+----------------------------------------------------------------------------------------------------+
  63  62        52 51                                          12 11 9 8 7 6 5 4 3 2 1 0
  +--+------------+----------------------------------------------+----+---+-+-+-+-+-+-+-+-+
  |NX| Available  |         Physical Frame Base Address          |Ign | G |P|D|A|P|P|U|R|P|
  |  |            |               (40 Bits)                      |    |   |S| | |C|W|/|/| |
  |  |            |                                              |    |   | | | |D|T|S|W| |
  +--+------------+----------------------------------------------+----+---+-+-+-+-+-+-+-+-+
+----------------------------------------------------------------------------------------------------+

• P (Present, Bit 0): Set to 1 if the page resides in physical RAM; 0 if the page is swapped out to disk or unallocated.
• R/W (Read/Write, Bit 1): 0 = Read-Only; 1 = Read-Write.
• U/S (User/Supervisor, Bit 2): 0 = Ring 0 Supervisor only; 1 = Ring 3 User accessible.
• A (Accessed, Bit 5): Set to 1 by MMU hardware whenever the page is read or written (used by page replacement algorithms).
• D (Dirty, Bit 6): Set to 1 by MMU hardware whenever a write operation modifies data on this page.
• PS (Page Size, Bit 7): If set in intermediate levels, enables HugePages (2 MB or 1 GB pages), bypassing lower levels and expanding TLB reach.
• NX (No-Execute, Bit 63): If set to 1, instruction execution from this memory page triggers a hardware fault (crucial security defense against buffer-overflow shellcode execution).

2. The Translation Lookaside Buffer (TLB) & Effective Memory Access Time#

Because resolving a single virtual memory read under 4-level paging requires 4 sequential memory reads in RAM to traverse the page directory tables plus 1 memory read to fetch the actual data, memory access latency would slow down by 500% without hardware acceleration.

+----------------------------------------------------------------------------------------------------+
|                               HARDWARE MMU & TLB TRANSLATION ACCELERATION                          |
+----------------------------------------------------------------------------------------------------+
  Virtual Address from CPU
             |
             v
  +--------------------------------------+
  |  Translation Lookaside Buffer (TLB)  |
  |  - Fully Associative Hardware Cache  |
  +--------------------------------------+
             |
             +-----> [ TLB HIT! (99% Probability) ]
             |       - Returns Physical Frame Base in < 1 nanosecond!
             |       - CPU directly accesses physical RAM.
             |
             +-----> [ TLB MISS! (1% Probability) ]
                     - Hardware Page Table Walker initiates 4-Level traversal in RAM.
                     - Reads PML4 -> PDPT -> PD -> PT (Incurs 4 memory bus cycles!).
                     - Loads translation into TLB, evicts stale entry.
                     - Resumes execution.
+----------------------------------------------------------------------------------------------------+

Effective Memory Access Time (EMAT)#

Let:

• alpha = TLB Hit Ratio (typically 0.98 to 0.995).
• t_{tlb} = Hardware TLB lookup time (approx 1 nanosecond).
• t_{ram} = Physical RAM access latency (approx 50 nanoseconds).

Under a 4-level paging architecture:

• Upon a TLB Hit: Requires 1 TLB lookup + 1 RAM access = t_{tlb} + t_{ram}.
• Upon a TLB Miss: Requires 1 TLB lookup + 4 page table walks in RAM + 1 final RAM access = t_{tlb} + 4 · t_{ram} + t_{ram} = t_{tlb} + 5 · t_{ram}.

The Effective Memory Access Time (EMAT) is:

EMAT = alpha · (t_{tlb} + t_{ram}) + (1 - alpha) · (t_{tlb} + 5 · t_{ram})

EMAT = t_{tlb} + t_{ram} + (1 - alpha) · (4 · t_{ram})

Numerical Demonstration:

With alpha = 0.99, t_{tlb} = 1 ns, t_{ram} = 50 ns:

EMAT = 1 + 50 + (0.01) · (200) = 51 + 2 = 53 nanoseconds.

Despite a 4-level page table, the 99% hit rate limits performance degradation to less than 4%!

Process Context Identifiers (PCID / ASID)#

Historically, changing CPU register %cr3 during a process context switch forced the hardware to invalidate (flush) the entire TLB. The incoming process started with an empty TLB, suffering thousands of expensive TLB misses.

Modern CPUs introduce Process Context Identifiers (PCID) (or ASID on ARM):

• TLB entries are tagged with a 12-bit process identifier.
• Context switching between processes no longer flushes the TLB, preserving hot cache entries across context switches and eliminating switch overhead.

3. Demand Paging & Page Fault Resolution Dynamics#

Demand Paging is a memory allocation paradigm where pages are loaded into physical RAM only at the precise instant they are accessed by executing code.

+----------------------------------------------------------------------------------------------------+
|                                    DEMAND PAGING FAULT RESOLUTION PIPELINE                         |
+----------------------------------------------------------------------------------------------------+
  1. CPU generates virtual address. MMU inspects PTE.
  2. Present Bit is 0! MMU raises Page Fault Exception (#PF, Vector 14).
  3. CPU saves error code and saves faulting virtual address into register %cr2.
  4. Kernel Trap Handler intercepts fault:
     +---------------------------------------------------------------+
     | Checks Virtual Memory Areas (vm_area_struct):                 |
     | - Is address outside allocated process segments?              |
     |   ===> Trigger SIGSEGV (Segmentation Fault)! Terminate proc.  |
     | - Is access illegal (Write to Read-Only text)?                |
     |   ===> If Copy-On-Write: Perform COW frame allocation.        |
     |   ===> Otherwise: Trigger SIGSEGV!                            |
     | - Is page valid but residing on backing storage (swap/disk)?  |
     |   ===> INITIATE DEMAND PAGING PAGE-IN!                        |
     +---------------------------------------------------------------+
  5. Kernel locates a free physical frame in RAM.
     (If RAM is full: runs Page Replacement Algorithm to evict a victim page!)
  6. Disk controller initiates DMA transfer, reading page from swap file into frame.
  7. Process is placed into TASK_UNINTERRUPTIBLE sleep awaiting I/O.
  8. Disk interrupt fires; kernel updates PTE with physical frame address, sets Present = 1.
  9. Kernel restores process to TASK_RUNNING; restarts the exact faulting instruction!
+----------------------------------------------------------------------------------------------------+

The Cost of a Page Fault#

Physical RAM access occurs at nanosecond speeds (50 ns). Accessing persistent NVMe SSD or rotational disk storage requires milliseconds:

• NVMe SSD Random Read: 20 to 50 microseconds (20,000 to 50,000 ns).
• Rotational Hard Drive: 5 to 10 milliseconds (5,000,000 to 10,000,000 ns).

A single page fault is 100,000 to 200,000 times slower than a physical memory access. Even a tiny page fault probability of p = 0.001 (0.1% of memory accesses faulting) increases average memory access latency by over 100x!

4. Page Replacement Algorithms & The Second-Chance Clock#

When a page fault occurs and physical RAM contains zero free frames, the operating system kernel must select an existing frame in memory to evict. If the victim page's Dirty Bit is set (D = 1), the kernel must write its contents back to swap space before reallocating the physical frame.

+----------------------------------------------------------------------------------------------------+
|                                PAGE REPLACEMENT ALGORITHM COMPARISON                               |
+----------------------------------------------------------------------------------------------------+
  Algorithm         Operational Principle                             Practical Viability
  --------------------------------------------------------------------------------------------------
  OPT (Belady)      Evict page unused for longest time in FUTURE      Impossible (Requires clairvoyance)
  FIFO              Evict oldest allocated page                       Poor; suffers from Belady's Anomaly
  LRU               Evict page unused for longest time in PAST        Optimal approximation; high HW cost
  Second-Chance     Circular buffer with 1-bit reference clock hand   Ubiquitous in production kernels
  Enhanced Clock    Evaluates (Reference, Dirty) tuple pairs          Prioritizes clean page evictions
+----------------------------------------------------------------------------------------------------+

1. Optimal Page Replacement (OPT / Belady's MIN)#

Evict the page that will not be referenced for the longest period of time in the future.

• Status: Impossible to implement in a real-time operating system because the kernel cannot predict future memory accesses.
• Purpose: Serves as the mathematical theoretical upper bound against which all real-world algorithms are benchmarked.

2. First-In, First-Out (FIFO) & Belady's Anomaly#

Maintains a FIFO queue of allocated frames. Evicts the oldest loaded frame.

• Belady's Anomaly (1969): In most algorithms, allocating additional physical memory frames strictly reduces the number of page faults. In FIFO, however, increasing physical memory frames can paradoxically INCREASE the number of page faults!
• Root Cause: FIFO ignores temporal locality; a heavily referenced page loaded early will be continually evicted and immediately faulted back into RAM.

+----------------------------------------------------------------------------------------------------+
|                                THE SECOND-CHANCE (CLOCK) ALGORITHM                                 |
+----------------------------------------------------------------------------------------------------+
                                      [ Frame 0: Ref = 0 ]
                                          ^          \
                                         /            \
                       [ Frame 3: Ref = 1 ]          [ Frame 1: Ref = 1 ]
                                         \            /
                                          \          v
                                      [ Frame 2: Ref = 0 ]
                                         (Clock Hand)
                                         
  Execution Logic:
  1. Inspect frame at Clock Hand.
  2. If Reference Bit == 1:
     - Clear Reference Bit to 0 ("Give a second chance").
     - Advance Clock Hand to next frame.
  3. If Reference Bit == 0:
     - VICTIM FOUND! Evict this frame!
     - Replace with incoming page; set Reference Bit = 1.
     - Advance Clock Hand.
+----------------------------------------------------------------------------------------------------+

3. The Second-Chance (Clock) Algorithm#

Approximates LRU with near-zero overhead by tracking the 1-bit Accessed / Reference Bit maintained automatically by CPU MMU hardware:

• Frames are arranged logically in a circular ring buffer. A pointer (Clock Hand) tracks the next candidate for inspection.
• When a page replacement is triggered:

- If the candidate frame has Reference Bit == 1: The MMU accessed it recently. Clear the bit to 0, advance the hand to the next frame.

- If the candidate frame has Reference Bit == 0: It was not accessed during a full rotation of the hand. This page is selected as the victim!

4. The Enhanced Clock Algorithm#

Differentiating between clean pages and dirty pages minimizes disk write-backs. The algorithm evaluates the tuple (Reference Bit, Dirty Bit):

1. Class (0, 0): Neither recently used nor modified. Best candidate to evict (zero disk I/O required!).
2. Class (0, 1): Not recently used, but modified. Requires writing to disk before frame reuse.
3. Class (1, 0): Recently used, but clean.
4. Class (1, 1): Recently used and modified. Worst candidate for eviction.

The clock hand sweeps looking for Class (0, 0). If none are found, it sweeps looking for Class (0, 1), clearing reference bits along the way.

5. Thrashing, The Working Set Model & Kernel Memory Reclaim#

+----------------------------------------------------------------------------------------------------+
|                                    THE PHENOMENON OF THRASHING                                     |
+----------------------------------------------------------------------------------------------------+
   CPU Utilization (%)
       ^
   100 |             /-----------\
       |            /             \
    50 |           /               \  <--- SUDDEN CLIFF: THRASHING COLLAPSE!
       |          /                 \      - Pages evicted faster than they can be read.
       |         /                   \     - Disk queues reach 100% saturation.
     0 +--------+---------------------+-------------------------> Multiprogramming Degree
                Low Load           Optimum Load    System Spends 99% of Time Swapping!
+----------------------------------------------------------------------------------------------------+

Thrashing Mechanics#

When the total memory demand of all active processes exceeds the physical RAM capacity of the system, pages are evicted and immediately required again milliseconds later.

1. Process A faults, initiates disk I/O, and blocks.
2. The OS scheduler picks Process B. Process B immediately faults, evicting Process A's freshly loaded page!
3. The system enters Thrashing: CPU utilization drops to near zero as all CPU cores sit idle waiting for saturated disk I/O queues.

Peter Denning's Working Set Model (1968)#

The Working Set W(t, Delta) of a process at time t is the set of unique pages referenced by the process during the most recent sliding time window of length Delta:

• If a process is allocated frames >= |W(t, Delta)|, it executes smoothly with negligible page faults (satisfying temporal locality).
• Let D = Sum |W_i| be the total demand across all active processes.
• If D > Total Physical RAM, Thrashing is inevitable.
• OS Mitigation: The scheduler must preempt and completely swap out (suspend) one or more entire processes, reclaiming all their frames to allow remaining processes to run smoothly.

Linux Kernel Memory Reclaim: `kswapd` & The OOM Killer#

The Linux kernel monitors physical memory using three watermarks: watermark[WMARK_MIN], watermark[WMARK_LOW], and watermark[WMARK_HIGH]:

1. When free memory drops below WMARK_LOW: The background kernel swap daemon `kswapd` wakes up, scanning page lists and evicting clean page cache buffers to restore memory above WMARK_HIGH.
2. If memory continues dropping below WMARK_MIN: Processes are forced into Direct Reclaim, stalling application threads to free memory synchronously.
3. If free memory reaches absolute zero: The Out-Of-Memory (OOM) Killer activates. It computes an oom_badness score across all active processes:

badness = (RAM_consumed + Swap_consumed) + oom_score_adj

The process with the highest score is abruptly terminated with SIGKILL to prevent a total kernel panic.

6. Industrial Implementation: Production-Grade Page Replacement Simulator#

Below is an authentic, production-grade Python program simulating and comparing FIFO, LRU, Optimal (OPT), and Second-Chance Clock page replacement algorithms over an identical page reference string:

from typing import List, Dict, Tuple, Set, Optional

def simulate_fifo(pages: List[int], capacity: int) -> Tuple[int, List[str]]:
    '''First-In, First-Out (FIFO) Page Replacement.'''
    frames: List[int] = []
    faults = 0
    history: List[str] = []

    for p in pages:
        if p not in frames:
            faults += 1
            if len(frames) == capacity:
                frames.pop(0) # Evict oldest frame
            frames.append(p)
            history.append(f"Page {p:2}: FAULT -> Frames: {frames}")
        else:
            history.append(f"Page {p:2}: HIT   -> Frames: {frames}")
    return faults, history

def simulate_lru(pages: List[int], capacity: int) -> Tuple[int, List[str]]:
    '''Least Recently Used (LRU) Page Replacement.'''
    frames: List[int] = []
    faults = 0
    history: List[str] = []

    for p in pages:
        if p not in frames:
            faults += 1
            if len(frames) == capacity:
                frames.pop(0) # Evict least recently used (head of list)
            frames.append(p)
            history.append(f"Page {p:2}: FAULT -> Frames: {frames}")
        else:
            # Move accessed page to end of list (most recently used)
            frames.remove(p)
            frames.append(p)
            history.append(f"Page {p:2}: HIT   -> Frames: {frames}")
    return faults, history

def simulate_second_chance(pages: List[int], capacity: int) -> Tuple[int, List[str]]:
    '''Second-Chance (Clock) Page Replacement.'''
    frames: List[Optional[int]] = [None] * capacity
    ref_bits: List[int] = [0] * capacity
    clock_hand = 0
    faults = 0
    history: List[str] = []

    for p in pages:
        if p in frames:
            idx = frames.index(p)
            ref_bits[idx] = 1 # Set reference bit
            history.append(f"Page {p:2}: HIT   -> Frames: {frames} (Bits: {ref_bits})")
        else:
            faults += 1
            # Sweep clock hand looking for reference bit == 0
            while True:
                if frames[clock_hand] is None:
                    # Found empty slot
                    frames[clock_hand] = p
                    ref_bits[clock_hand] = 1
                    clock_hand = (clock_hand + 1) % capacity
                    break
                elif ref_bits[clock_hand] == 1:
                    # Give second chance
                    ref_bits[clock_hand] = 0
                    clock_hand = (clock_hand + 1) % capacity
                else:
                    # Evict victim page
                    frames[clock_hand] = p
                    ref_bits[clock_hand] = 1
                    clock_hand = (clock_hand + 1) % capacity
                    break
            history.append(f"Page {p:2}: FAULT -> Frames: {frames} (Bits: {ref_bits})")
    return faults, history

# Verification Execution
if __name__ == "__main__":
    reference_string = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2]
    num_frames = 3

    fifo_faults, _ = simulate_fifo(reference_string, num_frames)
    lru_faults, _ = simulate_lru(reference_string, num_frames)
    clock_faults, _ = simulate_second_chance(reference_string, num_frames)

    print(f"Page Reference String: {reference_string}")
    print(f"Allocated Physical Frames: {num_frames}\n")
    print(f"FIFO Page Faults:          {fifo_faults}")
    print(f"LRU Page Faults:           {lru_faults}")
    print(f"Second-Chance Clock Faults:{clock_faults}")

7. Real-World Case Study: The Linux Memory Overcommit & OOM Killer Catastrophe#

In high-concurrency production systems (e.g., Redis databases and Kubernetes nodes), an architectural feature called Memory Overcommit frequently creates severe outages:

• The Rationale for Overcommit: Many legacy applications allocate vast virtual address spaces (e.g., malloc(100GB)) but touch only a fraction of that memory. To optimize RAM utilization, the Linux kernel defaults to vm.overcommit_memory = 0 (optimistic overcommit), granting virtual allocations that exceed physical RAM plus swap.
• The Redis `BGSAVE` Trap:

1. Redis holds 24 GB of data in RAM on a 32 GB server.

2. To create a background snapshot on disk, Redis calls fork().

3. Thanks to Copy-On-Write, fork() succeeds instantaneously.

4. While the background child writes data to disk, the active parent processes thousands of incoming write operations.

5. Each write triggers a COW page fault, forcing the kernel to allocate new physical 4 KB frames for modified pages.

6. Physical RAM and swap space reach 100% saturation!

• The Outcome: The kernel cannot satisfy pending memory writes. The Out-Of-Memory (OOM) Killer awakens, identifies Redis as the single largest memory consumer, and terminates the primary database process with SIGKILL, dropping millions of active user sessions.
• Production Solution: Configure sysctl vm.overcommit_memory=2 (strict bounding against physical RAM + swap) or set echo -1000 > /proc/(pgrep redis)/oom_score_adj to immunize critical database processes from OOM termination.

8. Common Engineering Pitfalls & Anti-Patterns#

Pitfall 1: Row-Major vs. Column-Major Stride Memory Thrashing#

In languages like C and C++, 2D arrays are stored in Row-Major Order (elements of row 0 are contiguous, followed by row 1). Iterating over a 10,000 x 10,000 matrix column-by-column jumps across 40,000-byte strides:

// DISASTROUS: Column-major iteration over row-major array
for (int col = 0; col < 10000; col++) {
    for (int row = 0; row < 10000; row++) {
        matrix[row][col] = 0; // Triggers a cache and TLB miss on EVERY single iteration!
    }
}

Traversing along rows (matrix[row][col]) exhibits spatial locality, loading 16 integers per cache line and executing up to 30 times faster!

Pitfall 2: Neglecting HugePages for Memory-Intensive Workloads#

By default, operating systems map memory using 4 KB pages. A database server managing 128 GB of RAM requires 128 GB / 4 KB = 33,554,432 Page Table Entries. A hardware TLB caching 1,024 entries covers only 4 MB of memory (0.003% of the database), causing continuous TLB misses.

Remediation: Configure Linux HugePages (2 MB or 1 GB pages). A 2 MB page expands TLB coverage by 512x, slashing page table memory overhead and increasing database throughput by 20% to 40%.

Pitfall 3: Disabling Swap Completely#

System administrators frequently disable swap (swapoff -a) believing it prevents latency spikes. However, disabling swap forces the kernel to reclaim memory exclusively by dropping executable file-backed pages from the Page Cache. Under memory pressure, the system thrashes trying to reload code instructions from disk rather than swapping out completely idle background memory. Always configure at least a small swap buffer to maintain healthy page cache ratios.

9. Comprehensive Checkpoint Practice Problems#

Problem 1: x86-64 4-Level Virtual Address Decomposition#

Scenario: An application running on an x86-64 architecture dereferences the 64-bit virtual memory address:

Virtual Address = 0x00007F8A3B2C1E48

(a) Convert the address to binary and verify that it conforms to canonical 48-bit address representation.

(b) Decompose the 48-bit virtual address into its constituent 4-level paging indices:

- PML4 Index (Bits 47:39)

- PDPT Index (Bits 38:30)

- PD Index (Bits 29:21)

- PT Index (Bits 20:12)

- Physical Page Offset (Bits 11:0)

(c) Express each index as both a binary string and a decimal integer.

Step-by-Step Solution:

Part (a): Canonical Address Verification:

In x86-64 48-bit paging, bits 63:47 must be a sign-extension of bit 47.

Hex: 0x0000 7F8A 3B2C 1E48.

Bits 63:48 are all zero (0x0000).

Bit 47 is the MSB of 0x7, which is binary 0 (since 7 = 0111).

Because bit 47 is 0, bits 63:48 are correctly sign-extended with 0. The address is canonical!

Part (b) & (c): Binary Decomposition:

Expand the lower 48 bits (7F8A 3B2C 1E48) into binary:

Hex:    7    F    8    A    3    B    2    C    1    E    4    8
Binary: 0111 1111 1000 1010 0011 1011 0010 1100 0001 1110 0100 1000

Group bits into 9-bit indices and 12-bit offset:

1. PML4 Index (Bits 47:39):

- Bits: 0111 1111 1

- Decimal: 256 + 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 255 (Index in PML4 table).

1. PDPT Index (Bits 38:30):

- Bits: 000 1010 00

- Decimal: 32 + 8 = 40 (Index in PDPT table).

1. PD Index (Bits 29:21):

- Bits: 11 1011 001

- Decimal: 256 + 128 + 64 + 16 + 8 + 1 = 473 (Index in PD table).

1. PT Index (Bits 20:12):

- Bits: 0 1100 0001

- Decimal: 128 + 64 + 1 = 193 (Index in Page Table).

1. Physical Page Offset (Bits 11:0):

- Bits: 1110 0100 1000

- Hex: 0xE48.

- Decimal: 2048 + 1024 + 512 + 64 + 8 = 3,656 bytes within the physical 4 KB frame.

Problem 2: Page Replacement Simulation: FIFO vs. LRU vs. Second-Chance#

Scenario: A process executes memory accesses generating the following page reference stream:

Reference String: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

The system allocates 3 physical memory frames initialized to empty.

Trace the exact frame contents and total page faults for:

(a) First-In, First-Out (FIFO).

(b) Least Recently Used (LRU).

(c) Second-Chance (Clock) Algorithm.

Step-by-Step Solution:

Part (a): FIFO Trace (Capacity = 3):

1. Access 1: FAULT. Frames: [1]
2. Access 2: FAULT. Frames: [1, 2]
3. Access 3: FAULT. Frames: [1, 2, 3]
4. Access 4: FAULT. Evict 1 (oldest). Frames: [2, 3, 4]
5. Access 1: FAULT. Evict 2. Frames: [3, 4, 1]
6. Access 2: FAULT. Evict 3. Frames: [4, 1, 2]
7. Access 5: FAULT. Evict 4. Frames: [1, 2, 5]
8. Access 1: HIT. Frames: [1, 2, 5]
9. Access 2: HIT. Frames: [1, 2, 5]
10. Access 3: FAULT. Evict 1. Frames: [2, 5, 3]
11. Access 4: FAULT. Evict 2. Frames: [5, 3, 4]
12. Access 5: HIT. Frames: [5, 3, 4]

Total FIFO Page Faults = 9 faults.

Part (b): LRU Trace (Capacity = 3):

1. Access 1: FAULT. [1]
2. Access 2: FAULT. [1, 2]
3. Access 3: FAULT. [1, 2, 3]
4. Access 4: FAULT. Evict 1 (least recently used). [2, 3, 4]
5. Access 1: FAULT. Evict 2. [3, 4, 1]
6. Access 2: FAULT. Evict 3. [4, 1, 2]
7. Access 5: FAULT. Evict 4. [1, 2, 5]
8. Access 1: HIT. Order: 2, 5, 1.
9. Access 2: HIT. Order: 5, 1, 2.
10. Access 3: FAULT. Evict 5 (least recently used: 5). Frames: [1, 2, 3].
11. Access 4: FAULT. Evict 1. Frames: [2, 3, 4].
12. Access 5: FAULT. Evict 2. Frames: [3, 4, 5].

Total LRU Page Faults = 10 faults.

Part (c): Second-Chance (Clock) Algorithm Trace:

Frames [F0, F1, F2], Bits [B0, B1, B2], Hand = 0.

1. Access 1: FAULT. F0=1, B0=1, Hand=1. [1, -, -]
2. Access 2: FAULT. F1=2, B1=1, Hand=2. [1, 2, -]
3. Access 3: FAULT. F2=3, B2=1, Hand=0. [1, 2, 3], Bits: [1, 1, 1].
4. Access 4: FAULT.

- Hand at 0 (page 1, bit 1): clear bit to 0, advance to 1.

- Hand at 1 (page 2, bit 1): clear bit to 0, advance to 2.

- Hand at 2 (page 3, bit 1): clear bit to 0, advance to 0.

- Hand at 0 (page 1, bit 0): VICTIM! Replace page 1 with 4. F0=4, B0=1, Hand=1.

Frames: [4, 2, 3], Bits: [1, 0, 0].

1. Access 1: FAULT.

- Hand at 1 (page 2, bit 0): VICTIM! Replace page 2 with 1. F1=1, B1=1, Hand=2.

Frames: [4, 1, 3], Bits: [1, 1, 0].

1. Access 2: FAULT.

- Hand at 2 (page 3, bit 0): VICTIM! Replace page 3 with 2. F2=2, B2=1, Hand=0.

Frames: [4, 1, 2], Bits: [1, 1, 1].

1. Access 5: FAULT.

- Sweeps clearing bits: B0->0, B1->0, B2->0.

- Replaces page 4 with 5 at F0. F0=5, B0=1, Hand=1.

Frames: [5, 1, 2], Bits: [1, 0, 0].

1. Access 1: HIT. Sets B1=1. Bits: [1, 1, 0].
2. Access 2: HIT. Sets B2=1. Bits: [1, 1, 1].
3. Access 3: FAULT.

- Hand at 1 (page 1, bit 1): clear to 0, Hand=2.

- Hand at 2 (page 2, bit 1): clear to 0, Hand=0.

- Hand at 0 (page 5, bit 1): clear to 0, Hand=1.

- Hand at 1 (page 1, bit 0): VICTIM! F1=3, B1=1, Hand=2.

Frames: [5, 3, 2], Bits: [0, 1, 0].

1. Access 4: FAULT.

- Hand at 2 (page 2, bit 0): VICTIM! F2=4, B2=1, Hand=0.

Frames: [5, 3, 4], Bits: [0, 1, 1].

1. Access 5: HIT. Sets B0=1. Bits: [1, 1, 1].

Total Second-Chance Faults = 9 faults.

Problem 3: Formal Proof & Demonstration of Belady's Anomaly#

Scenario: Demonstrate Belady's Anomaly under First-In, First-Out (FIFO) page replacement using the classic 12-page reference string:

Reference String: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

(a) Compute the exact number of page faults using a system with 3 physical frames.

(b) Compute the exact number of page faults using a system with 4 physical frames.

(c) State the anomaly result and explain the architectural cause.

Step-by-Step Solution:

Part (a): FIFO with 3 Frames (M = 3):

From Problem 2, Part (a):

Total Page Faults for M = 3 is 9 page faults.

Part (b): FIFO with 4 Frames (M = 4):

Trace reference string across 4 frames:

1. Access 1: FAULT. [1]
2. Access 2: FAULT. [1, 2]
3. Access 3: FAULT. [1, 2, 3]
4. Access 4: FAULT. [1, 2, 3, 4] (Frames full).
5. Access 1: HIT. [1, 2, 3, 4]
6. Access 2: HIT. [1, 2, 3, 4]
7. Access 5: FAULT. Evict 1 (oldest). Frames: [2, 3, 4, 5]
8. Access 1: FAULT. Evict 2. Frames: [3, 4, 5, 1]
9. Access 2: FAULT. Evict 3. Frames: [4, 5, 1, 2]
10. Access 3: FAULT. Evict 4. Frames: [5, 1, 2, 3]
11. Access 4: FAULT. Evict 5. Frames: [1, 2, 3, 4]
12. Access 5: FAULT. Evict 1. Frames: [2, 3, 4, 5]

Counting faults:

1(F), 2(F), 3(F), 4(F), 1(H), 2(H), 5(F), 1(F), 2(F), 3(F), 4(F), 5(F).

Total Faults = 4 + 6 = 10 page faults!

Part (c): Anomaly Conclusion:

• With 3 physical frames: 9 page faults.
• With 4 physical frames: 10 page faults.

Adding 33% more physical memory increased the number of page faults!

This occurs because FIFO does not belong to the class of Stack Algorithms (such as LRU and Optimal), where the set of pages in memory for n frames is always a strict subset of the pages in memory for n + 1 frames.

Problem 4: Effective Memory Access Time (EMAT) & Page Fault Impact#

Scenario: A memory subsystem has the following performance characteristics:

• Hardware TLB lookup time: t_{tlb} = 2 nanoseconds.
• Physical RAM access latency: t_{ram} = 60 nanoseconds.
• TLB Hit Rate: alpha = 98% (0.98).
• The system uses 4-level paging (PML4, PDPT, PD, PT).
• When a page fault occurs, handling the fault (disk swap read, interrupt service, and context switch) requires:

T_{fault} = 8 milliseconds = 8,000,000 nanoseconds.

(a) Calculate the Effective Memory Access Time (EMAT) assuming zero page faults (pure TLB and RAM dynamics).

(b) If 1 out of every 10,000 memory accesses generates a page fault (Page Fault Probability p = 0.0001), calculate the new overall EMAT.

(c) Determine the maximum tolerable page fault rate p if system architects mandate that EMAT must not degrade by more than 10% beyond the baseline calculated in Part (a).

Step-by-Step Solution:

Part (a): Baseline Memory Latency (Zero Page Faults):

• On TLB Hit: t_{tlb} + t_{ram} = 2 + 60 = 62 ns.
• On TLB Miss: t_{tlb} + (4 + 1) · t_{ram} = 2 + 5 · 60 = 302 ns.

EMAT_{base} = alpha · (62) + (1 - alpha) · (302)

EMAT_{base} = 0.98 · (62) + 0.02 · (302) = 60.76 + 6.04 = 66.80 nanoseconds.

Part (b): EMAT with Page Faults (p = 0.0001):

Formula:

EMAT_{total} = (1 - p) · EMAT_{base} + p · T_{fault}

Substitute values:

EMAT_{total} = (1 - 0.0001) · 66.80 + (0.0001) · (8,000,000)

EMAT_{total} = 66.79 + 800 = 866.79 nanoseconds.

Impact:

A page fault rate of just 0.01% (1 in 10,000 accesses) slowed the memory subsystem down from 66.8 ns to 866.8 ns—a 1,197% performance degradation!

Part (c): Maximum Tolerable Page Fault Rate (10% Degradation Cap):

Allowed EMAT:

EMAT_{target} = 1.10 · EMAT_{base} = 1.10 · 66.80 = 73.48 ns.

Target Equation:

EMAT_{base} + p · T_{fault} <= 73.48

66.80 + p · 8,000,000 <= 73.48

p · 8,000,000 <= 6.68

p <= 6.68 / 8,000,000 = 0.000000835 (approx 8.35 · 10^-7).

Conclusion:

To keep memory performance within 10% of hardware speed, fewer than 1 in every 1,200,000 memory accesses can trigger a page fault.