Page fault handling in Operating Systems - Time & Space Complexity

Time Complexity: Page fault handling

O(n)

Understanding Time Complexity

When a program accesses memory not currently in physical RAM, the system handles a page fault to load the needed data.

We want to understand how the time to handle page faults grows as the number of memory accesses increases.

Scenario Under Consideration

Analyze the time complexity of the following simplified page fault handler.

function handlePageFault(address) {
  if (pageInMemory(address)) {
    return;
  }
  loadPageFromDisk(address);
  updatePageTable(address);
}
    

This code checks if a page is in memory; if not, it loads it from disk and updates the page table.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking if the page is in memory and loading it if missing.
• How many times: Once per memory access that causes a page fault.

How Execution Grows With Input

Each page fault requires loading a page from disk, which takes significant time compared to normal memory access.

Input Size (memory accesses)	Approx. Page Faults
10	Up to 10 page faults if all pages are new
100	Up to 100 page faults if all pages are new
1000	Up to 1000 page faults if all pages are new

Pattern observation: The time grows linearly with the number of page faults, as each fault triggers a costly load operation.

Final Time Complexity

Time Complexity: O(n)

This means the total time to handle page faults grows directly in proportion to the number of page faults.

Common Mistake

[X] Wrong: "Page fault handling time stays the same no matter how many faults occur."

[OK] Correct: Each page fault requires loading data from disk, which takes time, so more faults mean more total time.

Interview Connect

Understanding how page fault handling time grows helps you explain system performance and memory management in real-world computing.

Self-Check

"What if the system uses a faster SSD instead of a traditional hard drive? How would the time complexity change?"