What is FIFO page replacement

Operating-systemsConceptBeginner · 3 min read

FIFO Page Replacement: How It Works and When to Use It

The FIFO page replacement algorithm removes the oldest page in memory when a new page needs space. It works like a queue, replacing pages in the order they were loaded, without considering how often or recently they were used.

⚙️

How It Works

Imagine a line of people waiting to enter a room. The person who arrived first leaves first when the room is full. FIFO page replacement works the same way for memory pages in an operating system.

When the memory is full and a new page needs to be loaded, FIFO removes the page that has been in memory the longest. It keeps track of pages in the order they arrived, like a queue, and always replaces the oldest one.

This method is simple and easy to implement but does not consider if a page is still useful or frequently accessed, which can sometimes lead to less efficient memory use.

💻

Example

This example simulates FIFO page replacement with a fixed memory size of 3 pages. When a new page arrives and memory is full, the oldest page is removed.

python

def fifo_page_replacement(pages, capacity):
    memory = []
    page_faults = 0

    for page in pages:
        if page not in memory:
            if len(memory) == capacity:
                removed = memory.pop(0)  # Remove oldest page
                print(f"Removed page: {removed}")
            memory.append(page)
            page_faults += 1
            print(f"Added page: {page} | Current memory: {memory}")
        else:
            print(f"Page {page} already in memory: {memory}")

    print(f"Total page faults: {page_faults}")

# Example usage
pages = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
capacity = 3
fifo_page_replacement(pages, capacity)

Output

Added page: 1 | Current memory: [1] Added page: 2 | Current memory: [1, 2] Added page: 3 | Current memory: [1, 2, 3] Removed page: 1 Added page: 4 | Current memory: [2, 3, 4] Page 1 already in memory: [2, 3, 4] Page 2 already in memory: [2, 3, 4] Removed page: 2 Added page: 5 | Current memory: [3, 4, 5] Page 1 already in memory: [3, 4, 5] Page 2 already in memory: [3, 4, 5] Removed page: 3 Added page: 3 | Current memory: [4, 5, 3] Removed page: 4 Added page: 4 | Current memory: [5, 3, 4] Removed page: 5 Added page: 5 | Current memory: [3, 4, 5] Total page faults: 9

🎯

When to Use

FIFO page replacement is useful when simplicity and low overhead are important, such as in systems with limited resources or simple hardware. It is easy to implement because it only needs to track the order pages arrived.

However, it may not be the best choice for systems where performance is critical, because it can remove pages that are still needed, causing more page faults.

Real-world use cases include embedded systems or educational examples where understanding basic page replacement concepts is the goal.

✅

Key Points

FIFO stands for First-In, First-Out, meaning the oldest page is replaced first.
It uses a simple queue structure to track pages.
Does not consider page usage frequency or recency.
Easy to implement but can cause more page faults in some cases.
Best suited for simple or resource-limited systems.

✅

Key Takeaways

FIFO replaces the oldest page in memory first, following a queue order.

It is simple to implement but may cause inefficient memory use.

Best for systems where simplicity is more important than performance.

Does not consider how often or recently a page is used.

Useful for learning and simple embedded systems.