Bird
Raised Fist0
Interview Prepoperating-systemsmediumAmazonGoogleMicrosoftRazorpayPhonePe

Page Replacement - FIFO, LRU, Optimal Algorithm

Choose your preparation mode3 modes available
🎯
Page Replacement - FIFO, LRU, Optimal Algorithm
mediumOSAmazonGoogleMicrosoft

Imagine your computer's memory as a small desk where you can keep only a few books open at once. When you need a new book but the desk is full, you must decide which book to close to make space. This decision is what page replacement algorithms solve in operating systems.

💡 Beginners often confuse page replacement algorithms with simple caching or think all algorithms behave similarly under all conditions, missing nuances like Belady's anomaly or the difference between practical and theoretical optimality. Think of page replacement as managing a limited workspace where you must decide which items to remove to make room for new ones, balancing simplicity and efficiency.
📋
Interview Question

Explain the concept of page replacement in operating systems and compare the FIFO, LRU, and Optimal page replacement algorithms. What are their working principles, advantages, disadvantages, and typical use cases?

Page fault and its impact on system performanceHow FIFO, LRU, and Optimal algorithms decide which page to evictTrade-offs between simplicity, accuracy, and implementation complexity
💡
Scenario & Trace
ScenarioA system with limited physical memory frames receives a sequence of page requests from a running process.
When a requested page is not in memory (page fault), the OS must select a page to evict. FIFO evicts the oldest loaded page regardless of usage; LRU evicts the page that was least recently used, approximating future usage; Optimal evicts the page that will not be used for the longest time in the future, which is ideal but impractical to implement.
  • When all pages in memory are equally old (FIFO) → FIFO evicts the oldest without considering usage
  • When multiple pages have the same least recent use time (LRU) → tie-breaking strategies may vary
  • Belady's anomaly in FIFO → increasing frames can sometimes increase page faults
  • When future page references are unknown (Optimal) → Optimal algorithm is theoretical and cannot be implemented exactly
⚠️
Common Mistakes
Confusing Optimal algorithm as practically implementable

Interviewer doubts your understanding of theoretical vs practical algorithms

✅ Clarify that Optimal is a theoretical benchmark requiring future knowledge, not implementable in real systems

Assuming FIFO always improves with more frames

Interviewer suspects lack of knowledge about Belady's anomaly

✅ Explain that FIFO can suffer from Belady's anomaly where more frames can increase page faults

Thinking LRU is free of overhead

Interviewer questions your grasp of implementation complexity

✅ Mention that LRU requires tracking usage history, which can be costly in time or hardware

Mixing page replacement with page fault handling mechanisms

Interviewer finds your explanation unfocused or inaccurate

✅ Separate the concept of page fault detection from the replacement strategy used after a fault

🧠
Basic Definition - What It Is
💡 This level covers the fundamental idea of page replacement and why it is needed in operating systems. Think of it as understanding the problem before diving into solutions.

Intuition

Page replacement algorithms decide which memory page to remove when new pages need to be loaded into limited physical memory.

Explanation

In operating systems, physical memory is limited and divided into fixed-size frames. When a process requests a page not currently in memory, a page fault occurs. To handle this, the OS must replace an existing page with the new one. Page replacement algorithms provide strategies to select which page to evict. FIFO removes the oldest loaded page, LRU removes the least recently used page, and Optimal removes the page that will not be needed for the longest time in the future.

Memory Hook

💡 Think of a revolving door where the first person in is the first person out (FIFO), versus a library where you remove the book you haven't read in the longest time (LRU), versus a crystal ball that tells you which book you won't need for the longest time (Optimal).

Interview Questions

❓ What is the main goal of a page replacement algorithm?
  • To decide which page to evict on a page fault
  • To minimize page faults and improve system performance
⏱
Depth Level
Interview Time30 seconds
Depthbasic

Covers the core concept and basic differences between FIFO, LRU, and Optimal.

Interview Target: Minimum floor - never go below this

Knowing only this will help you pass initial screening but is insufficient for deeper technical rounds.

🧠
Mechanism Depth - How It Works
💡 This level explains the internal workings, trade-offs, and practical considerations of each algorithm. Understanding these details helps you discuss implementation and performance in interviews.

Intuition

Each algorithm uses a different heuristic to approximate the best page to evict, balancing complexity and performance.

Explanation

FIFO maintains a queue of pages in the order they were loaded; when a page fault occurs, it evicts the page at the front of the queue. This is simple but can lead to suboptimal decisions, including Belady's anomaly where more frames cause more faults. LRU tracks page usage over time, evicting the page that has not been used for the longest period, approximating the optimal future knowledge. Implementing LRU requires additional data structures or hardware support, such as counters or stacks. The Optimal algorithm, while not implementable in practice, serves as a benchmark by evicting the page that will not be used for the longest time in the future, minimizing page faults theoretically. Understanding these mechanisms helps in analyzing trade-offs between implementation complexity and fault rates.

Memory Hook

💡 Imagine FIFO as a queue line, LRU as a 'last touched' list, and Optimal as a perfect oracle predicting future needs.

Illustrative Code

def fifo_page_replacement(pages, capacity):
    queue = []  # Queue to store pages in FIFO order
    page_set = set()  # Set for O(1) lookup
    page_faults = 0
    for page in pages:
        if page not in page_set:
            page_faults += 1
            if len(queue) == capacity:
                removed = queue.pop(0)  # Remove oldest page
                page_set.remove(removed)
            queue.append(page)
            page_set.add(page)
    return page_faults

def lru_page_replacement(pages, capacity):
    page_faults = 0
    page_map = {}  # Map page to its last used index
    pages_in_memory = set()
    for i, page in enumerate(pages):
        if page not in pages_in_memory:
            page_faults += 1
            if len(pages_in_memory) == capacity:
                # Evict least recently used page
                lru_page = min(page_map, key=page_map.get)
                pages_in_memory.remove(lru_page)
                del page_map[lru_page]
            pages_in_memory.add(page)
        page_map[page] = i  # Update last used index
    return page_faults

def optimal_page_replacement(pages, capacity):
    page_faults = 0
    pages_in_memory = set()
    for i in range(len(pages)):
        page = pages[i]
        if page not in pages_in_memory:
            page_faults += 1
            if len(pages_in_memory) == capacity:
                # Find page with farthest future use
                farthest = -1
                page_to_remove = None
                for p in pages_in_memory:
                    try:
                        next_use = pages[i+1:].index(p)
                    except ValueError:
                        next_use = float('inf')
                    if next_use > farthest:
                        farthest = next_use
                        page_to_remove = p
                pages_in_memory.remove(page_to_remove)
            pages_in_memory.add(page)
    return page_faults

Interview Questions

❓
    ⏱
    Depth Level
    Interview Time
    Depth

    FIFO uses a queue and set for O(1) operations per page, resulting in O(n) time. LRU requires searching for least recently used page, which can be O(capacity) per page, leading to O(n * capacity). Optimal requires scanning future pages to find farthest use, also O(n * capacity). Space is proportional to capacity for all.

    Interview Target: Target level for FAANG on-sites

    Mastering this level distinguishes you from most candidates and prepares you for system design discussions.

    📊
    Explanation Depth Levels
    💡 Choose your explanation depth based on interview stage and company expectations.
    LevelInterview TimeSuitable ForRisk
    Basic Definition30sScreening call or initial roundsToo shallow for on-site or system design interviews
    Mechanism Depth2-3 minutesOn-site interviews at FAANG and top tech companiesRequires good understanding of trade-offs and implementation details
    💼
    Interview Strategy
    💡 Use this guide to structure your explanation clearly and confidently before every interview. Analogies and clear stepwise explanations help interviewers follow your thought process.

    How to Present

    Start with a clear definition of page replacement and why it is necessary.Give a simple analogy or example to illustrate the concept.Explain the working principles of FIFO, LRU, and Optimal algorithms.Discuss edge cases like Belady's anomaly and practical limitations.Conclude with trade-offs and typical use cases.

    Time Allocation

    Definition: 30s → Example: 1min → Mechanism: 2min → Edge cases: 30s. Total ~4min

    What the Interviewer Tests

    Your ability to explain concepts clearly, understand trade-offs, and handle edge cases distinguishes pass from fail.

    Common Follow-ups

    • What is Belady's anomaly and why does it occur?
    • How can LRU be implemented efficiently in hardware or software?
    💡 These follow-ups test deeper understanding and practical knowledge beyond definitions.
    🔍
    Pattern Recognition

    When to Use

    Interviewers ask about page replacement when discussing memory management, virtual memory, or system performance optimization.

    Signature Phrases

    'Explain page replacement algorithms''Compare FIFO, LRU, and Optimal''What happens when a page fault occurs?'

    NOT This Pattern When

    Similar Problems

    Practice

    (1/5)
    1. Trace the sequence of events when a user program invokes a system call to read a file. Which step happens immediately after the CPU switches to kernel mode?
    easy
    A. The kernel verifies the system call number and arguments
    B. The hardware raises an interrupt to the device
    C. The user program resumes execution in user mode
    D. The kernel copies data directly to the user buffer without validation

    Solution

    1. Step 1: User program issues system call

      The user program executes a special instruction causing a trap to kernel mode.
    2. Step 2: CPU switches to kernel mode

      Control transfers to the OS kernel with elevated privileges.
    3. Step 3: Kernel validates system call

      The kernel inspects the system call number and arguments to ensure they are valid and safe.
    4. Step 4: Why other options are incorrect

      The kernel copies data directly to the user buffer without validation is unsafe; kernel must validate before copying data. The user program resumes execution in user mode happens after system call completion, not immediately after mode switch. The hardware raises an interrupt to the device is unrelated here; hardware interrupts occur asynchronously, not immediately after mode switch.
    5. Final Answer:

      Option A -> Option A
    6. Quick Check:

      System call trap -> kernel mode -> validate call -> execute service [OK]
    Hint: Kernel validates system call immediately after mode switch
    Common Mistakes:
    • Assuming kernel copies data before validation
    • Confusing interrupt handling with system call flow
    • Thinking user mode resumes immediately after trap
    2. Why is it generally inefficient to keep a process in the Ready state for a long time without scheduling it to Running, especially in a multi-core system?
    medium
    A. Because the process wastes CPU cache locality and increases context switch overhead when scheduled later
    B. Because the process holds resources like memory and I/O devices exclusively while Ready
    C. Because the process consumes CPU cycles even in Ready state, reducing overall throughput
    D. Because the process cannot perform I/O operations while in Ready state, causing system deadlocks

    Solution

    1. Step 1: Understand Ready state resource usage

      Processes in Ready state do not consume CPU cycles but occupy scheduling queues.
    2. Step 2: Analyze each option

      A: Correct. Long Ready times cause loss of CPU cache locality and increase context switch overhead when finally scheduled.
      B: Incorrect. Processes do not hold exclusive I/O or memory resources just by being Ready.
      C: Incorrect. Ready processes do not consume CPU cycles.
      D: Incorrect. Ready processes do not cause deadlocks by not performing I/O.
    3. Final Answer:

      Option A -> Option A
    4. Quick Check:

      Ready state delays hurt cache locality and increase context switch costs [OK]
    Hint: Ready state processes wait without CPU but lose cache locality and increase context switch overhead [OK]
    Common Mistakes:
    • Believing Ready processes consume CPU cycles
    • Assuming Ready processes hold exclusive resources
    • Confusing Ready state with Waiting state regarding I/O
    3. Why might using multiple threads within a single process not always improve performance compared to multiple processes?
    medium
    A. Because thread context switching is slower than process context switching
    B. Because threads have higher memory overhead than processes
    C. Because threads share the same memory space, leading to potential synchronization bottlenecks
    D. Because threads cannot run on multiple CPU cores simultaneously

    Solution

    1. Step 1: Analyze memory overhead

      Threads share memory, so they have lower memory overhead than processes, making Because threads have higher memory overhead than processes incorrect.
    2. Step 2: Consider synchronization issues

      Shared memory requires synchronization mechanisms (locks, mutexes), which can cause contention and reduce performance.
    3. Step 3: Evaluate context switching speed

      Thread context switching is generally faster than process switching, so Because thread context switching is slower than process context switching is false.
    4. Step 4: Understand CPU core utilization

      Threads can run on multiple cores simultaneously, so Because threads cannot run on multiple CPU cores simultaneously is false.
    5. Final Answer:

      Option C -> Option C
    6. Quick Check:

      Synchronization overhead can limit thread performance gains [OK]
    Hint: Threads share memory but need locks; locks can slow things down [OK]
    Common Mistakes:
    • Assuming threads always outperform processes
    • Confusing context switch overhead between threads and processes
    • Believing threads cannot utilize multiple cores
    4. Suppose a disk scheduler uses C-SCAN but the disk head speed varies dynamically, sometimes moving faster or slower between tracks. How does this affect the fairness and average wait time guarantees of C-SCAN, and what modification could mitigate this issue?
    hard
    A. Variable head speed causes starvation in C-SCAN; switching to SSTF is the best mitigation.
    B. Variable head speed does not affect C-SCAN fairness since it always services requests in one direction; no modification is needed.
    C. Variable head speed improves average wait time by allowing faster servicing of distant requests; no modification is necessary.
    D. Variable head speed breaks C-SCAN's uniform wait time guarantee; adding a dynamic priority queue based on estimated seek time can mitigate this.

    Solution

    1. Step 1: Understand C-SCAN fairness assumptions

      C-SCAN assumes uniform head movement speed to provide uniform wait times.
    2. Step 2: Impact of variable head speed

      Variable speed causes some requests to wait longer, breaking fairness and uniform wait time guarantees.
    3. Step 3: Mitigation strategies

      Introducing a dynamic priority queue that accounts for estimated seek time can help balance servicing order and restore fairness.
    4. Step 4: Evaluate other options

      Variable head speed does not affect C-SCAN fairness since it always services requests in one direction; no modification is needed. ignores the impact of speed variation; Variable head speed causes starvation in C-SCAN; switching to SSTF is the best mitigation. incorrectly claims starvation occurs and suggests SSTF, which can worsen starvation; Variable head speed improves average wait time by allowing faster servicing of distant requests; no modification is necessary. incorrectly claims variable speed improves wait times.
    5. Final Answer:

      Option D -> Option D
    6. Quick Check:

      Variable head speed breaks C-SCAN's uniform wait time guarantee; adding a dynamic priority queue based on estimated seek time can mitigate this. correctly identifies the problem and a plausible mitigation.
    Hint: C-SCAN fairness depends on constant head speed; variable speed needs dynamic adjustments
    Common Mistakes:
    • Assuming C-SCAN fairness is speed-independent
    • Confusing starvation with fairness degradation
    • Believing variable speed always improves performance
    5. If a system uses a multi-level page table and a TLB, how does this affect the calculation of Effective Access Time (EAT) compared to a single-level page table system?
    hard
    A. EAT remains the same because TLB hides all page table lookup costs
    B. EAT decreases because multi-level page tables reduce page faults
    C. EAT increases because page table lookup time is longer, so TLB misses are more expensive
    D. EAT is unaffected by page table structure, only by TLB hit ratio

    Solution

    1. Step 1: Understand multi-level page tables

      Multi-level page tables require multiple memory accesses per lookup, increasing page table access time.
    2. Step 2: Impact on EAT

      On TLB miss, page table lookup is longer, so miss penalty increases, raising EAT.
    3. Step 3: Analyze options

      A: Incorrect, TLB does not hide all page table lookup costs.
      B: Incorrect, multi-level page tables do not reduce page faults.
      C: Correct, longer page table lookup time increases EAT on misses.
      D: Incorrect, page table structure affects miss penalty and thus EAT.
    4. Final Answer:

      Option C -> Option C
    5. Quick Check:

      Longer page table lookup -> higher miss penalty -> higher EAT.
    Hint: Multi-level page tables -> longer lookup -> higher EAT on TLB miss [OK]
    Common Mistakes:
    • Assuming TLB hides all page table lookup costs
    • Confusing page fault rate with page table lookup time
    Recommended

    Ready to prove it?

    Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

    10 questions~5 mineasy hard