FIFO vs LRU vs Optimal: Key Differences and Usage in OS

In operating systems, FIFO replaces the oldest page first, LRU replaces the least recently used page, and Optimal replaces the page that will not be used for the longest time in the future. Optimal is the best in theory but impractical, while FIFO is simple and LRU balances performance and complexity.

Quick Comparison

Here is a quick comparison of the three page replacement algorithms based on key factors.

Factor	FIFO	LRU	Optimal
Replacement Strategy	Oldest page replaced first	Least recently used page replaced	Page not used for longest future time replaced
Implementation Complexity	Low (simple queue)	Medium (tracking usage history)	High (requires future knowledge)
Performance	Can cause Belady's anomaly	Better than FIFO, avoids some anomalies	Best possible performance (theoretical)
Practical Use	Simple systems, teaching	Common in real OS	Not practical, used as benchmark
Memory Overhead	Low	Higher (needs tracking)	N/A (impractical)

Key Differences

FIFO (First-In-First-Out) replaces pages in the order they were loaded, ignoring how often or recently they were used. This simplicity can lead to poor performance, including Belady's anomaly where more memory causes more faults.

LRU (Least Recently Used) improves on FIFO by replacing the page that has not been used for the longest time, assuming pages used recently will be used again soon. It requires tracking page usage, which adds complexity but generally improves performance.

Optimal algorithm replaces the page that will not be used for the longest time in the future. It provides the lowest possible page fault rate but is impossible to implement in real systems because it needs future knowledge of memory references. It is mainly used as a benchmark to compare other algorithms.

Code Comparison

Here is a simple Python example showing how FIFO handles page replacement for a given reference string and frame size.

python

def fifo_page_replacement(pages, frame_size):
    frames = []
    page_faults = 0
    for page in pages:
        if page not in frames:
            if len(frames) < frame_size:
                frames.append(page)
            else:
                frames.pop(0)  # Remove oldest page
                frames.append(page)
            page_faults += 1
    return page_faults

pages = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2]
frame_size = 3
print(f"FIFO Page Faults: {fifo_page_replacement(pages, frame_size)}")

Output

FIFO Page Faults: 9

LRU Equivalent

This Python code shows how LRU replaces pages by tracking recent usage for the same reference string and frame size.

python

def lru_page_replacement(pages, frame_size):
    frames = []
    page_faults = 0
    for page in pages:
        if page not in frames:
            if len(frames) < frame_size:
                frames.append(page)
            else:
                # Remove least recently used page
                frames.pop(0)
                frames.append(page)
            page_faults += 1
        else:
            # Move the used page to the end to mark it recently used
            frames.remove(page)
            frames.append(page)
    return page_faults

pages = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2]
frame_size = 3
print(f"LRU Page Faults: {lru_page_replacement(pages, frame_size)}")

Output

LRU Page Faults: 8

When to Use Which

Choose FIFO when simplicity and low overhead are more important than performance, such as in teaching or very simple systems.

Choose LRU for most real-world systems where better performance is needed and some overhead for tracking usage is acceptable.

Optimal is not practical but useful as a theoretical benchmark to measure how well other algorithms perform.

Key Takeaways

FIFO replaces the oldest page first and is simple but can perform poorly.

LRU replaces the least recently used page and balances performance with complexity.

Optimal algorithm is the best in theory but requires future knowledge, making it impractical.

Use FIFO for simplicity, LRU for better real-world performance, and Optimal as a benchmark.

Tracking page usage is key to LRU's improved performance over FIFO.