When a page fault occurs and all physical memory frames are currently in use, the operating system must decide which page to remove from memory (the "victim page") to make space for the incoming page. This decision is critical because choosing the "wrong" page can lead to more frequent page faults and degrade system performance. Page replacement algorithms aim to minimize the number of page faults.

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

• Principle: The page that has been in physical memory for the longest time is selected as the victim page. It operates like a queue: the page that entered first is the first to be replaced.
• Implementation: A queue data structure is typically used to keep track of the order in which pages were loaded. The page at the head of the queue is the next victim.
• Example (3 Frames):
  • 7: [7, -, -] (Fault)
  • 0: [7, 0, -] (Fault)
  • 1: [7, 0, 1] (Fault)
  • 2: [2, 0, 1] (Fault, 7 removed)
  • 0: [2, 0, 1] (Hit)
  • 3: [2, 3, 1] (Fault, 0 removed)
  • 0: [0, 3, 1] (Fault, 2 removed)
  • 4: [0, 4, 1] (Fault, 3 removed)
  • ...and so on.
• Pros: Simple to implement and understand. Low overhead.
• Cons: Can be inefficient. A frequently used page might be replaced just because it was loaded early. Suffers from Belady's Anomaly, where increasing the number of available physical frames can sometimes lead to more page faults for certain reference strings.

2. Optimal (OPT / MIN)

• Principle: This algorithm replaces the page that will not be used for the longest period of time in the future. It's an oracle algorithm that requires perfect foresight.
• Implementation: Practically impossible to implement in a real-time operating system because it needs to know the entire future page reference string.
• Example (3 Frames):
  • 7: [7, -, -] (Fault)
  • 0: [7, 0, -] (Fault)
  • 1: [7, 0, 1] (Fault)
  • 2: [7, 0, 2] (Fault, 1 removed because 1 is used furthest in future compared to 7 and 0)
  • 0: [7, 0, 2] (Hit)
  • 3: [7, 3, 2] (Fault, 0 removed because 0 is used furthest in future compared to 7 and 2)
  • ...and so on.
• Pros: Provides the theoretical minimum number of page faults for any given reference string. Used as a benchmark to compare the efficiency of other algorithms.
• Cons: Cannot be implemented in practice.

3. LRU (Least Recently Used)

• Principle: The page that has not been used for the longest period of time (i.e., its most recent access was furthest in the past) is chosen as the victim page. This algorithm attempts to approximate the Optimal algorithm by leveraging the principle of locality of reference (if a page has been used recently, it's likely to be used again soon).
• Implementation: Challenging and expensive to implement precisely in hardware.
  • Counters: Attach a time-of-use counter to each page. On every memory reference, update the counter for the referenced page. During replacement, scan all pages to find the one with the smallest counter. High overhead.
  • Stack: Maintain a stack of page numbers. When a page is referenced, move it to the top of the stack. When a page needs to be replaced, the page at the bottom of the stack is the LRU. This requires frequent stack manipulation.
  • Approximations: Real systems often use approximation algorithms like the Clock Algorithm (or Second-Chance algorithm) that use a "reference bit" associated with each page. When a page is referenced, its reference bit is set to 1. During replacement, the algorithm scans pages, giving a "second chance" to pages with a reference bit of 1 by clearing the bit and moving on. Only pages with a 0 reference bit are candidates for replacement.
• Example (3 Frames):
  • 7: [7, -, -] (Fault, 7 recently used)
  • 0: [7, 0, -] (Fault, 0 recently used)
  • 1: [7, 0, 1] (Fault, 1 recently used)
  • 2: [2, 0, 1] (Fault, 7 is LRU)
  • 0: [2, 0, 1] (Hit, 0 is now most recently used)
  • 3: [2, 0, 3] (Fault, 1 is LRU)
  • 0: [2, 0, 3] (Hit, 0 is now most recently used)
  • 4: [0, 3, 4] (Fault, 2 is LRU)
  • ...and so on.
• Pros: Generally performs very well and often comes close to the performance of the Optimal algorithm. Does not suffer from Belady's Anomaly.
• Cons: High implementation overhead for exact LRU. Approximation algorithms are common.

Counting-based Algorithms

These algorithms make replacement decisions based on the frequency of page access.

LFU (Least Frequently Used)

• Principle: The page with the smallest reference count (i.e., the one used least often) is chosen for replacement.
• Implementation: A counter is associated with each page. When a page is referenced, its counter is incremented. When a page replacement is needed, the page with the lowest count is selected. Periodically, counters might need to be reset or aged to reflect current usage patterns.
• Pros: Can identify pages that are genuinely not used often.
• Cons: Does not consider recency. A page that was very popular in the past but is no longer being used might remain in memory indefinitely if its count is still high, while newly active pages with low counts are evicted.

MFU (Most Frequently Used)

• Principle: The page with the largest reference count (i.e., the one used most often) is chosen for replacement. The rationale is that a page with a high count has just had a burst of activity and may soon become less active, while a page with a low count might have just entered memory and is about to be heavily used.
• Pros/Cons: Rarely used in practice as its effectiveness is generally poor compared to LRU or FIFO.

Working-Set Model

The Working-Set Model is not just a page replacement algorithm but a broader memory management strategy aimed at keeping a process's actively used pages in physical memory to minimize page faults and prevent thrashing. It is based on the empirical observation of locality of reference.
- Working Set Definition: The "working set" of a process at a specific point in time t is defined as the set of pages that have been referenced by the process during a fixed time interval (a "window" of recent references) looking backward from t. This window is denoted by Δ (delta).
- A small Δ captures temporal locality; a large Δ captures both temporal and spatial locality more broadly.
- Principle: The working-set model posits that if a process's entire working set can be kept in memory, the process will execute with a low page-fault rate. If the sum of all processes' working set sizes exceeds the total available physical memory, then the system is likely to experience thrashing.
- Implementation: Requires tracking references within the Δ window. This often involves hardware support (e.g., reference bits) and periodic scans by the OS.
- The OS attempts to keep the working set of each active process in memory.
- When memory is scarce, if a page is not part of any process's working set (i.e., it hasn't been referenced in the last Δ time units), it becomes a candidate for replacement.
- If memory pressure is very high and even after replacing non-working-set pages, there isn't enough space, the OS might decide to suspend (swap out) an entire process to free up memory for others.
- Pros:
- Effectively captures the dynamic memory needs of processes.
- A good strategy for preventing thrashing by ensuring processes have adequate memory.
- Pages that are no longer actively used naturally fall out of the working set and become candidates for replacement.
- Cons:
- Difficult to implement accurately due to the need to precisely track historical references.
- Choosing an optimal value for Δ is challenging and can vary between workloads.
- The overhead of maintaining and tracking working sets can be significant.