Page Replacement FIFO LRU Optimal: Operating System Guide

Introduction and Core Concepts

Page replacement is a fundamental memory management technique in modern operating systems that handles the decision of which memory pages to evict when physical memory becomes full. In virtual memory systems, processes operate as if they have access to a large, contiguous address space, while the operating system transparently maps virtual pages to physical frames in RAM. When a process references a page that is not currently resident in memory, a page fault occurs, forcing the OS to load the required page from secondary storage. If no free frame is available, the system must select a victim page to replace, and the quality of this decision directly impacts system performance, throughput, and responsiveness.

The study of page replacement fifo lru optimal algorithms forms the cornerstone of understanding virtual memory behavior. FIFO (First-In First-Out), LRU (Least Recently Used), and Optimal page replacement represent three distinct philosophies for victim selection, each with different assumptions about program locality and future behavior. FIFO relies on simple chronological order, LRU leverages temporal locality by evicting the least recently accessed page, and Optimal provides a theoretical upper bound by evicting the page that will not be used for the longest period in the future. Understanding these three algorithms together gives students, developers, and system designers a complete spectrum from naive to ideal replacement strategies.

Why does page replacement fifo lru optimal matter beyond academic exams? In any system where demand paging is used — from desktop operating systems like Linux and Windows to embedded systems, hypervisors, and database buffer managers — page faults are among the most expensive operations, often 1000x slower than a memory hit due to disk I/O. A poor replacement policy can cause thrashing, where the system spends more time swapping pages than executing useful work. By analyzing FIFO, LRU, and Optimal, we can quantify the trade-offs between implementation simplicity, runtime overhead, and fault rate, which informs the design of practical approximations like Clock, Second Chance, and Enhanced LRU used in real kernels.

Key Terminology

Before diving deeper, it is essential to define the core metrics. A page hit occurs when the referenced page is already in memory, requiring no disk access. A page fault occurs when the page is absent, requiring a replacement decision if frames are full. The page fault rate, calculated as (number of faults / total references), is the primary metric for comparing algorithms. Reference string is the ordered sequence of page numbers accessed by a process, and number of frames denotes the fixed-size physical memory allocated to that process. Belady's Anomaly is a counterintuitive phenomenon where increasing the number of frames can increase page faults, observed specifically with FIFO.

How It Works

FIFO page replacement operates on the simplest possible principle: the page that has been in memory the longest is evicted first. The operating system maintains a queue of pages in the order they were loaded. When a page fault occurs and all frames are occupied, the page at the front of the queue is removed and the new page is appended to the rear. This approach requires minimal bookkeeping — only a pointer to the oldest page — and is easy to implement in hardware or software. However, FIFO completely ignores usage patterns; a heavily used page that was loaded early may be evicted even if it will be needed again immediately, leading to suboptimal performance for programs with strong locality.

LRU page replacement is built on the principle of temporal locality: if a page has not been used for a long time, it is unlikely to be needed soon. Conversely, pages that were recently referenced are likely to be referenced again. To implement LRU, the system must track the order of last use for every resident page. On a page fault, the page whose last access timestamp is oldest is selected as the victim. LRU generally achieves a significantly lower fault rate than FIFO because it adapts to program behavior, but it comes at a cost. Maintaining precise LRU order requires either a timestamp update on every memory reference, a stack manipulation, or specialized hardware support, all of which add overhead to the critical path of memory access.

Optimal page replacement, also known as Belady's Optimal Algorithm or MIN, is a theoretical algorithm that provides the best possible fault rate for a given reference string. It works by looking into the future: when a replacement is needed, it evicts the page whose next use is farthest in the future, or the page that will never be used again. While impossible to implement in a real online system because it requires perfect knowledge of future references, Optimal serves as a gold standard benchmark. Operating system researchers use it to evaluate how close practical algorithms like LRU come to the ideal, and it proves that no online algorithm can beat Optimal's fault count for the same frame allocation.

Mechanism Comparison at a Glance

Conceptually, FIFO is history-oblivious beyond load time, LRU is past-aware, and Optimal is future-aware. This distinction determines their fault behavior. FIFO can suffer from Belady's Anomaly, LRU is stack-based and provably free from this anomaly, and Optimal is by definition anomaly-free and minimal. In terms of implementation, FIFO needs a simple circular queue, LRU needs counters, stacks, or hash maps with doubly linked lists, and Optimal needs offline analysis of the entire reference string. These differences explain why real operating systems never implement pure FIFO or pure Optimal, but instead implement efficient approximations of LRU.

Implementation

Implementing page replacement algorithms in Python is an excellent way to internalize their logic and to simulate fault rates for arbitrary reference strings. The implementations below are designed for clarity and educational value, using standard data structures like collections.deque, OrderedDict, and lists. Each function takes a reference string and a frame count, simulates the replacement process step-by-step, and returns the total number of page faults along with the evolution of frames. Note that production kernel implementations would be written in C and optimized for speed, but the algorithmic logic remains identical.

The FIFO implementation uses a queue to track insertion order and a set for O(1) hit detection. The LRU implementation uses a dictionary to track recency or an OrderedDict to maintain access order efficiently, updating the order on every hit. The Optimal implementation scans the future reference string on each fault to find the victim with the farthest next use, which is O(n) per fault and illustrates why it cannot be used online. All code escapes comparison operators for HTML safety and includes detailed comments for learning purposes.

FIFO Implementation

from collections import deque

def fifo_page_replacement(ref_string, num_frames):
    """
    Simulate FIFO page replacement.
    ref_string: list of page numbers
    num_frames: number of physical frames
    Returns: (total_faults, fault_history)
    """
    frames = set()
    queue = deque()  # maintains load order
    faults = 0
    history = []

    for page in ref_string:
        # Page hit: do nothing to queue order
        if page in frames:
            history.append((list(queue), False))
            continue

        # Page fault
        faults += 1
        # If frames not full, simply add
        if len(frames) < num_frames:
            frames.add(page)
            queue.append(page)
        else:
            # Evict oldest page (front of queue)
            victim = queue.popleft()
            frames.remove(victim)
            frames.add(page)
            queue.append(page)
        history.append((list(queue), True))

    return faults, history

# Example usage
ref = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2]
faults, _ = fifo_page_replacement(ref, 3)
print(f"FIFO Faults: {faults}")

LRU Implementation

from collections import OrderedDict

def lru_page_replacement(ref_string, num_frames):
    """
    Simulate LRU using OrderedDict.
    Most recently used at end, least recently at beginning.
    """
    cache = OrderedDict()
    faults = 0

    for page in ref_string:
        if page in cache:
            # Hit: move to end to mark as most recently used
            cache.move_to_end(page)
        else:
            # Fault
            faults += 1
            if len(cache) >= num_frames:
                # Evict least recently used (first item)
                cache.popitem(last=False)
            cache[page] = True  # value is irrelevant

    return faults

def lru_with_timestamps(ref_string, num_frames):
    """
    Alternative LRU using explicit timestamps - more illustrative
    """
    frames = []
    last_used = {}  # page -> last access index
    faults = 0

    for i, page in enumerate(ref_string):
        if page in frames:
            last_used[page] = i
            continue

        faults += 1
        if len(frames) < num_frames:
            frames.append(page)
        else:
            # Find page with smallest last_used value
            lru_page = min(frames, key=lambda p: last_used.get(p, -1))
            idx = frames.index(lru_page)
            frames[idx] = page
        last_used[page] = i

    return faults

# Example usage
ref = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2]
print(f"LRU Faults: {lru_page_replacement(ref, 3)}")

Optimal Implementation

def optimal_page_replacement(ref_string, num_frames):
    """
    Simulate Optimal (MIN) page replacement.
    Looks ahead to find page with farthest next use.
    """
    frames = []
    faults = 0

    for i, page in enumerate(ref_string):
        if page in frames:
            continue

        faults += 1
        if len(frames) < num_frames:
            frames.append(page)
        else:
            # Find victim: page with farthest next use or never used again
            farthest_idx = -1
            victim_idx = -1

            for j, f in enumerate(frames):
                try:
                    # Find next occurrence of f after i
                    next_use = ref_string.index(f, i + 1)
                except ValueError:
                    # f never used again - best victim
                    victim_idx = j
                    break
                if next_use > farthest_idx:
                    farthest_idx = next_use
                    victim_idx = j

            frames[victim_idx] = page

    return faults

# Example usage
ref = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2]
print(f"Optimal Faults: {optimal_page_replacement(ref, 3)}")

Unified Simulator for Comparison

def compare_all_policies(ref_string, num_frames):
    """
    Run all three policies and compare fault rates side-by-side.
    Useful for experiments and visualization.
    """
    fifo_faults, _ = fifo_page_replacement(ref_string, num_frames)
    lru_faults = lru_page_replacement(ref_string, num_frames)
    opt_faults = optimal_page_replacement(ref_string, num_frames)

    total = len(ref_string)
    print(f"Reference length: {total}, Frames: {num_frames}")
    print(f"FIFO:    {fifo_faults} faults, rate = {fifo_faults/total:.2%}")
    print(f"LRU:     {lru_faults} faults, rate = {lru_faults/total:.2%}")
    print(f"Optimal: {opt_faults} faults, rate = {opt_faults/total:.2%}")

    # Verify Optimal <= LRU <= FIFO is not always true, but Optimal is minimal
    assert opt_faults <= fifo_faults and opt_faults <= lru_faults, "Optimal should be minimal"
    return {"FIFO": fifo_faults, "LRU": lru_faults, "Optimal": opt_faults}

# Belady's Anomaly demonstration with FIFO
ref_anomaly = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
for frames in [3, 4]:
    faults, _ = fifo_page_replacement(ref_anomaly, frames)
    print(f"FIFO with {frames} frames: {faults} faults")

Step-by-Step Example

To make the differences concrete, let us walk through the classic reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 with 3 frames. This string is widely used in textbooks because it clearly separates the performance of the three algorithms and exhibits typical locality patterns. We will track the contents of frames after each reference and mark hits and faults.

For FIFO, the process is strictly queue-based. The first three references 7, 0, 1 all cause faults and fill the frames as [7, 0, 1] with 7 being the oldest. Reference 2 causes a fault, evicting 7, resulting in [0, 1, 2]. Reference 0 is a hit. Reference 3 causes a fault, evicting 0 (the oldest), resulting in [1, 2, 3]. Reference 0 then faults again, evicting 1, giving [2, 3, 0]. This pattern continues, and FIFO ends with 15 faults for this string. Notice how FIFO evicts 0 just before it is needed again, illustrating its blindness to reuse.

For LRU, the same initial steps occur: 7, 0, 1 fill frames, 2 evicts 7 (least recently used is 7), giving [0, 1, 2] but with recency order [7 was evicted, 0,1,2]. When 0 is referenced again, it becomes most recently used, so the recency order becomes [1, 2, 0]. When 3 faults, LRU evicts 1 (least recently used), resulting in frames [0, 2, 3] with order [2, 0, 3]. When 0 is referenced again, it moves to most recent: [2, 3, 0]. When 4 faults, LRU evicts 2, giving [3, 0, 4]. LRU finishes with 12 faults, three fewer than FIFO, by preserving frequently reused pages like 0 and 2.

For Optimal, the algorithm looks ahead. After filling [7, 0, 1], reference 2 faults. Optimal examines the future: 7 is never used again after this point, 0 is used at position 5, 1 is used at position 14. Therefore it evicts 7, giving [0, 1, 2]. Next, 0 is a hit. When 3 faults, Optimal looks ahead: 1 is next used at 14, 2 is next used at 9, 0 is next used at 7. The farthest is 1, so it evicts 1, giving [0, 2, 3]. When 0 is hit and 4 faults, it looks ahead: 0 is used at 11, 2 at 9, 3 at 10, so it evicts 0? Actually 0's next use is at 11, which is farther than 2 and 3, but careful analysis shows Optimal evicts the page with farthest next use, which would be 0 in this case, leading to [4, 2, 3]. Optimal finishes with only 9 faults, the theoretical minimum, demonstrating the value of future knowledge.

Fault Summary for the Example

Summarizing the 20-reference example with 3 frames: FIFO incurs 15 faults (75% fault rate), LRU incurs 12 faults (60%), and Optimal incurs 9 faults (45%). This ordering is typical: Optimal <= LRU < FIFO in most real workloads, though FIFO can occasionally beat LRU on pathological strings that defeat recency. The example also highlights that increasing frames from 3 to 4 would reduce faults for LRU and Optimal but might increase faults for FIFO due to Belady's Anomaly, a critical consideration when sizing memory allocations.

Complexity Analysis

Understanding the time and space complexity of page replacement fifo lru optimal algorithms is essential for evaluating their feasibility in high-performance kernels where every memory reference is on the critical path. The analysis must distinguish between per-reference cost (hit handling) and per-fault cost (victim selection), as well as the auxiliary data structures required.

FIFO has the lowest overhead. Hit detection is O(1) using a hash set, and fault handling is O(1) using a queue pointer. No per-hit bookkeeping is needed beyond checking membership. Space overhead is O(F) where F is the number of frames, for the queue and set. This makes FIFO attractive for simple embedded systems or when hardware support is minimal, despite its higher fault rate.

LRU is more expensive. A naive implementation that scans all frames to find the least recently used page costs O(F) per fault and O(1) per hit if timestamps are used, but the scan dominates. An optimized implementation using a doubly linked list plus hash map (like OrderedDict) achieves O(1) per hit and per fault by moving the accessed page to the head on every reference. However, this O(1) still involves pointer manipulation on every memory access, which can be costly in hardware. Space is O(F) for the list and map plus O(1) per page for timestamps if that variant is used.

Optimal is the most expensive and is never used online. For each fault, it must scan the future reference string to find the next use of each resident page. In the worst case, this is O(F * N) per fault where N is the remaining length of the reference string, leading to O(N * F * N) overall or O(N^2) in the worst case. Space is O(F) for frames plus O(N) to store the reference string for lookahead. Its value is purely as an offline benchmark.

Where F = number of frames, N = length of reference string. In practice, the constant factors matter: LRU's per-access update can add 10-20% overhead to memory access latency if implemented in software, which is why hardware-assisted approximations like the Clock algorithm are preferred in production kernels.

Variations and Optimizations

Pure FIFO, LRU, and Optimal are rarely used in isolation in modern systems; instead, their ideas are refined into practical variants that balance fault rate with implementation cost. The most important FIFO variant is Second Chance (also called Clock). It augments FIFO with a reference bit per page. When a page reaches the front of the queue, its reference bit is checked: if it is 1 (recently used), the bit is cleared and the page is moved to the rear, giving it a second chance; if 0, it is evicted. This simple modification dramatically reduces FIFO's fault rate and avoids evicting hot pages, while retaining O(1) overhead and eliminating Belady's Anomaly in practice.

For LRU, the main challenge is reducing per-access overhead. The Clock algorithm is the most widely deployed LRU approximation. It arranges frames in a circular list with a clock hand pointer and a reference bit. On a fault, the hand scans circularly, clearing reference bits that are 1 and evicting the first page with bit 0. This approximates LRU without needing to update data structures on every hit — the reference bit is set by hardware on access. Enhanced Clock (or WSClock) adds dirty bits to prefer clean pages for eviction, reducing write-back costs. Other LRU variants include LRU-K, which considers the K-th most recent access to protect against sequential scans, and 2Q and LIRS, which better handle scan-resistant workloads.

Optimal has no online optimization, but its offline analysis inspires practical prefetching and Belady-inspired cache replacement for CPU caches. For example, Hawkeye and Mockingjay for CPU last-level caches use past access patterns to predict which pages would be evicted by Optimal and emulate its decisions. In operating systems, the concept of working set and page fault frequency, derived from Optimal's future knowledge, is used to dynamically adjust frame allocation per process to prevent thrashing. Additionally, Aging and NFU (Not Frequently Used) algorithms approximate LRU by maintaining counters that decay over time, providing a tunable trade-off between precision and cost.

Choosing an Approximation

When designing a system, the choice among these optimizations depends on hardware support and workload. If hardware provides reference and dirty bits (as x86 does), Clock is the default choice. For database buffer pools where access patterns are more predictable, LRU-K or ARC (Adaptive Replacement Cache) outperforms Clock by adapting to both recency and frequency. For embedded systems with no MMU support, even simple FIFO with Second Chance may be sufficient. The key insight is that page replacement fifo lru optimal theory guides the design, but engineering constraints dictate the final approximation.

Real-World Applications

Although the textbook presentation focuses on operating system virtual memory, the principles of page replacement fifo lru optimal extend far beyond OS kernels. Any system that manages a limited fast cache backed by a larger slow store faces the same replacement problem, and the same algorithms apply with different names and parameters.

In operating system kernels, Linux uses a variant of Clock called LRU with active/inactive lists, while Windows uses a combination of Clock and working set trimming. The page frame reclamation daemon (kswapd in Linux) periodically scans pages, using reference bits to approximate LRU and selecting victims for swapping to disk. Database management systems like PostgreSQL, MySQL InnoDB, and Oracle use buffer pool replacement policies to decide which disk blocks to keep in RAM. InnoDB's buffer pool uses a modified LRU with midpoint insertion to avoid polluting the cache with sequential scans, directly addressing LRU's weakness with scanning workloads.

Web servers and content delivery networks (CDNs) use page replacement concepts for HTTP caching. Varnish, Nginx, and Cloudflare's edge caches use LRU or variants like TinyLFU to decide which objects to evict when cache memory is full. The fault rate translates to cache miss rate, which directly impacts latency and origin load. Similarly, CPU hardware caches (L1, L2, L3) implement replacement policies in silicon: Intel and AMD use pseudo-LRU (tree-based approximation) for set-associative caches because true LRU would require too many bits per set, while Optimal is used offline to evaluate cache design.

Other applications include virtualization hypervisors (VMware ESXi ballooning and transparent page sharing), mobile operating systems (Android's low memory killer uses LRU-like ordering), and even application-level caches like Redis and Memcached, which offer LRU, LFU, and FIFO eviction policies for key-value stores. Understanding page replacement fifo lru optimal thus provides a transferable mental model for any caching problem.

Comparison with Alternatives

FIFO, LRU, and Optimal are not the only page replacement strategies. Several other algorithms exist, each with different trade-offs in terms of fault rate, overhead, and anomaly behavior. Understanding how page replacement fifo lru optimal compares to these alternatives helps in selecting the right policy for a given workload and in answering system design interview questions.

Least Frequently Used (LFU) evicts the page with the lowest access frequency, which captures frequency rather than recency. It works well for workloads where hot pages are accessed many times, but it suffers from cache pollution: a page that was frequently used in the past but is no longer needed will remain resident. Most Frequently Used (MFU) is the opposite and is rarely useful. Random replacement selects a victim uniformly at random; surprisingly, it performs reasonably well, has zero bookkeeping overhead, and is free from Belady's Anomaly, making it a baseline for hardware caches. Not Recently Used (NRU) classifies pages into four categories based on reference and dirty bits and randomly picks from the lowest non-empty category, offering a low-overhead approximation.

More advanced algorithms include Working Set, which keeps pages that were referenced in the last Δ time units, and Page Fault Frequency, which dynamically adjusts frame allocation to keep fault rate within bounds. ARC (Adaptive Replacement Cache) dynamically balances recency and frequency by maintaining two LRU lists (T1 for recent, T2 for frequent) and adapting their sizes based on workload, outperforming pure LRU on many traces without tuning.

In practice, no single algorithm dominates all workloads. FIFO is never chosen for performance but for simplicity. LRU is the conceptual ideal for general-purpose systems, but Clock is its practical embodiment. Optimal remains the yardstick. Modern systems often use hybrid or adaptive policies like ARC or LIRS that outperform pure LRU by learning workload characteristics online.

Common Mistakes and Best Practices

Students and practitioners often make several recurring mistakes when implementing or reasoning about page replacement fifo lru optimal algorithms. The first mistake is assuming FIFO is always worse than LRU in a monotonic way. While LRU generally has fewer faults, specific reference strings can cause LRU to perform worse than FIFO, especially with looping patterns that exceed frame size. Always simulate rather than assume ordering.

A second common pitfall is mishandling LRU updates on hits. A frequent bug is to only update recency on faults, forgetting that a hit must also move the page to the most-recently-used position. Failing to do so turns LRU into FIFO and inflates fault counts. Another implementation error is using wall-clock time for timestamps instead of logical access counters, which can overflow or be expensive to compare. Using a monotonic counter or linked list avoids these issues.

A third mistake is misunderstanding Belady's Anomaly. Many assume more frames always means fewer faults, which is true for LRU and Optimal but not for FIFO. Demonstrating the anomaly requires a specific reference string like 1,2,3,4,1,2,5,1,2,3,4,5 where FIFO with 3 frames yields 9 faults but with 4 frames yields 10 faults. Forgetting to check for this anomaly in exams or system sizing can lead to incorrect capacity planning.

Best practices include: always validate implementations against known examples with 3 and 4 frames; use the unified simulator to compare policies on the same trace; prefer Clock over pure LRU in production code to avoid per-access overhead; consider dirty page costs — evicting a clean page is cheaper than a dirty page that requires write-back, so enhanced algorithms that factor dirty bits should be used when write costs matter; and use Optimal as a lower bound to measure how much headroom remains for optimization. When benchmarking, use realistic traces with locality (e.g., 80% of accesses to 20% of pages) rather than random strings, which do not reflect real program behavior.

Debugging Checklist

• Verify that FIFO queue order is not updated on hits, only on faults.
• Ensure LRU moves hit pages to most-recent position and that eviction picks the least recent.
• Confirm Optimal scans forward from i+1, not from 0, and handles pages never used again correctly.
• Test edge cases: empty reference string, single frame, frames > unique pages, and all hits.
• Escape < and > correctly in HTML code blocks to prevent rendering issues.

Interview Questions

Page replacement is a favorite topic in operating system interviews for roles in systems, backend, and performance engineering. Below are common questions with concise model answers that demonstrate depth.

1. What is Belady's Anomaly and which algorithms suffer from it?

Belady's Anomaly is the phenomenon where increasing the number of page frames results in an increase in the number of page faults for a given reference string. It occurs with FIFO and some other algorithms like Random with certain configurations, but not with stack algorithms. LRU and Optimal are stack algorithms and are proven to be free from Belady's Anomaly — more frames can never increase faults. An example string for FIFO is 1,2,3,4,1,2,5,1,2,3,4,5 where 3 frames give 9 faults and 4 frames give 10 faults. Interviewers often ask to demonstrate this with a trace, so be prepared to walk through the queue step-by-step.

2. Why is LRU considered better than FIFO, and why don't we always use pure LRU?

LRU is better than FIFO because it exploits temporal locality — recently used pages are likely to be used again soon, so evicting the least recently used page preserves the working set and typically yields a lower fault rate. However, pure LRU requires updating data structures on every memory reference, which is expensive in software and requires specialized hardware like counters or a stack. The overhead can outweigh the benefit, especially at high memory access rates. Therefore, real systems use approximations like Clock, which uses a reference bit set by hardware and scans circularly, achieving near-LRU fault rates with O(1) amortized cost and no per-hit list manipulation.

3. Explain Optimal page replacement and why it is not implementable. How is it still useful?

Optimal page replacement evicts the page whose next use is farthest in the future, or a page that will never be used again. It yields the minimum possible number of page faults for any given reference string and frame count, as proven by Belady. It is not implementable online because it requires perfect knowledge of future references, which the OS does not have at runtime. Its usefulness is as a theoretical benchmark: by simulating Optimal offline on a trace, we can compute the lower bound on faults and measure how close practical algorithms like LRU or Clock come to ideal. It also guides the design of replacement policies that try to predict future reuse, such as Belady-inspired cache policies in modern CPUs.

4. How would you implement LRU cache with O(1) get and put operations?

This is a classic coding question that tests understanding of LRU. The solution uses a hash map plus a doubly linked list. The hash map maps keys to nodes in the list for O(1) lookup, and the doubly linked list maintains recency order with most recent at head and least recent at tail. On get(key), if present, move the node to head and return value. On put(key, value), if key exists, update value and move to head; else if cache is full, evict tail node and remove its hash entry, then insert new node at head. In Python, collections.OrderedDict provides this out of the box with move_to_end and popitem(last=False). Time is O(1) for both operations, space is O(capacity). Be ready to code this with proper handling of edge cases and to explain why a singly linked list or array would not achieve O(1).

5. How do you handle dirty pages and what is the difference between Clock and Enhanced Clock?

A dirty page is one that has been modified in memory and must be written back to disk before eviction, making its eviction more expensive than a clean page. Basic Clock only considers the reference bit. Enhanced Clock (also called WSClock or Clock with dirty bit) considers both reference and dirty bits, classifying pages into four classes: (0,0) not recently used, clean — best victim; (0,1) not recently used, dirty — needs write-back; (1,0) recently used, clean; (1,1) recently used, dirty. The algorithm scans for the first (0,0) page, and if none, it may write back (0,1) pages in the background. This reduces I/O by preferring clean victims, which is crucial for performance when disk writes are slow. Interviewers look for awareness that replacement cost is not uniform.