Page Faults and Binary Page Offset Calculations

This article explains the concept of a page fault in modern operating systems and explores the mathematical mechanics of virtual address translation. It breaks down what happens when the memory management unit encounters unmapped data, and details how binary bit shifts and power-of-two page sizes enable the fast extraction of page numbers and page offsets without computationally expensive arithmetic.

What Is a Page Fault?

A page fault is an exception (or hardware interrupt) raised by the Memory Management Unit (MMU) when a running program attempts to access a virtual memory address that is not currently mapped to physical random-access memory (RAM). Despite its name, a page fault is not an error; it is a normal and essential mechanism used by modern operating systems to implement virtual memory and demand paging.

When a program requests access to a virtual address, the MMU references the process’s page table:

  1. Check Validity: If the page’s “present” (or valid) bit is set to zero, the requested page is not in physical RAM.
  2. Trap to OS: The CPU halts execution of the instruction and transfers control to the operating system’s page fault handler.
  3. Fetch from Secondary Storage: If the address is legitimate, the OS locates the required data in secondary storage (such as an SSD, hard drive, or swap file).
  4. Load to RAM: The OS finds a free physical frame in RAM, reads the data from the disk into that frame, and updates the page table entry with the new frame number and marks the present bit as valid.
  5. Resume Execution: The OS instructs the CPU to restart the instruction that originally triggered the fault, now allowing the memory access to succeed.

If the virtual address accessed is completely outside the program’s allocated address space, the OS treats the event as an illegal memory access (e.g., a segmentation fault) and terminates the process.

Virtual Address Anatomy

To understand address translation, virtual memory is divided into fixed-size blocks called pages, while physical memory is divided into matching fixed-size blocks called page frames.

Every virtual address consists of two distinct components: 1. Virtual Page Number (VPN): Identifies which specific page contains the data. 2. Page Offset: Identifies the exact byte location within that page.

Why Page Offsets Rely on Bit Shifts

Page sizes in modern computing architectures are virtually always configured as powers of two (for example, 4 KB, which is \(2^{12}\) bytes, or 2 MB, which is \(2^{21}\) bytes). Choosing a power of two simplifies address translation by replacing division and modulo operations with binary bit shifts and bitwise masking.

1. Extracting the Page Offset

In standard decimal arithmetic, finding the position within a block would require a modulo operation (Address % Page_Size). Because page sizes are powers of two (\(2^k\)), the offset corresponds precisely to the lowest \(k\) bits of the address.

For a 4 KB (\(2^{12}\) bytes) page size, \(k = 12\). The offset is isolated using a bitwise AND mask:

\[\text{Offset} = \text{Address} \ \& \ (2^{12} - 1)\]

In binary, \(2^{12} - 1\) is represented as 12 consecutive ones (0x00000FFF), which directly extracts the lower 12 bits without mathematical division.

2. Extracting the Virtual Page Number Using Right Bit Shifts

Determining which page an address belongs to mathematically requires integer division (Address / Page_Size). In the binary system, dividing an integer by a power of two (\(2^k\)) is equivalent to a logical right bit shift by \(k\) positions:

\[\text{Virtual Page Number} = \text{Address} \gg 12\]

Shifting the entire address 12 bits to the right discards the offset bits, leaving only the Virtual Page Number, which is then used as an index into the page table.

3. Reconstructing the Physical Address Using Left Bit Shifts

Once the MMU maps the Virtual Page Number to a Physical Frame Number (PFN), it must construct the final physical memory address. It achieves this by shifting the PFN to the left by \(k\) bits to clear room for the offset, and then combining it with the offset using a bitwise OR operation:

\[\text{Physical Address} = (\text{PFN} \ll 12) \ | \ \text{Offset}\]

Why Bit Shifts Matter for Performance

Hardware processors can execute bit shifts and bitwise operations in a single clock cycle, whereas arithmetic division and modulo operations require dozens of cycles. By structuring memory addresses as binary strings split by bit shifts, the MMU translates billions of virtual memory requests per second with negligible performance overhead.