Page Replacement Algorithms

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

Theory: The First-In-First-Out algorithm replaces the page that has been in memory for the longest time. It operates on the principle that older pages are less likely to be used again.

Maintains a queue to track the order pages were brought into memory
When a page fault occurs and all frames are full, the oldest page (at the head of the queue) is removed
The new page is added to the tail of the queue

function FIFO(referenceString, frameCount) {
    // Initialize variables
    let frames = new Array(frameCount).fill(-1);  // -1 indicates empty frame
    let queue = [];  // Queue to track order of pages loaded into memory
    let pageFaults = 0;
    
    // Process each page in the reference string
    for (let page of referenceString) {
        // Check if page is already in memory (page hit)
        if (frames.includes(page)) {
            // Page hit - no action needed in FIFO
            continue;
        }
        
        // Page fault occurred
        pageFaults++;
        
        if (queue.length < frameCount) {
            // If we have empty frames, use them
            frames[queue.length] = page;
            queue.push(page);
        } else {
            // Replace the oldest page (first in the queue)
            let oldestPage = queue.shift();  // Remove the oldest page from queue
            let index = frames.indexOf(oldestPage);
            frames[index] = page;  // Replace oldest page with new page
            queue.push(page);      // Add new page to end of queue
        }
    }
    
    return pageFaults;
}

Advantages:

Simple to understand and implement
Low overhead - requires only a queue
No need to track page access history

Disadvantages:

Does not consider frequency or recency of use
Can suffer from Belady's Anomaly - increasing frames can increase page faults
Often performs poorly compared to more sophisticated algorithms
May remove frequently used pages simply because they were loaded early

Time Complexity: O(1) for page replacement operation

Space Complexity: O(n) where n is the number of frames

2. LRU (Least Recently Used)

Theory: The Least Recently Used algorithm replaces the page that hasn't been accessed for the longest period of time. It's based on the principle of temporal locality - recently used pages are likely to be used again soon.

Requires tracking when each page was last accessed
When a page fault occurs, the page with the oldest access time is replaced
Each time a page is referenced, it becomes the most recently used

function LRU(referenceString, frameCount) {
    // Initialize variables
    let frames = new Array(frameCount).fill(-1);  // -1 indicates empty frame
    let usageHistory = [];  // Tracks order of page usage (most recently used at the end)
    let pageFaults = 0;
    
    // Process each page in the reference string
    for (let page of referenceString) {
        // Check if page is already in memory (page hit)
        if (frames.includes(page)) {
            // Page hit - update usage history (move page to end of history)
            usageHistory = usageHistory.filter(p => p !== page);
            usageHistory.push(page);
            continue;
        }
        
        // Page fault occurred
        pageFaults++;
        
        if (usageHistory.length < frameCount) {
            // If we have empty frames, use them
            frames[usageHistory.length] = page;
            usageHistory.push(page);
        } else {
            // Replace the least recently used page
            let lruPage = usageHistory.shift();  // Get least recently used page
            let index = frames.indexOf(lruPage);
            frames[index] = page;     // Replace LRU page with new page
            usageHistory.push(page);  // Add new page as most recently used
        }
    }
    
    return pageFaults;
}

Advantages:

Generally performs well in practice
Exploits temporal locality of reference
Does not suffer from Belady's Anomaly
Approximates optimal algorithm fairly well in many cases

Disadvantages:

More complex to implement efficiently
Requires additional overhead to track access history
Hardware implementation can be expensive
Does not consider frequency of use

Time Complexity: O(n) for finding least recently used page (can be optimized to O(1) with proper data structures)

Space Complexity: O(n) where n is the number of frames

3. LFU (Least Frequently Used)

Theory: The Least Frequently Used algorithm replaces the page with the lowest reference frequency. If there's a tie, it usually selects the least recently used page among those with the lowest frequency.

Maintains a counter for each page to track access frequency
When a page fault occurs, the page with the lowest counter value is replaced
Each time a page is referenced, its counter is incremented

function LFU(referenceString, frameCount) {
    // Initialize variables
    let frames = new Array(frameCount).fill(-1);  // -1 indicates empty frame
    let frequencies = {};   // Maps page → frequency count
    let timestamps = {};    // Maps page → timestamp (for tie-breaking)
    let pageFaults = 0;
    let time = 0;
    
    // Process each page in the reference string
    for (let page of referenceString) {
        time++;  // Increment timestamp
        
        // Initialize or update frequency counter and timestamp
        frequencies[page] = (frequencies[page] || 0) + 1;
        timestamps[page] = time;
        
        // Check if page is already in memory (page hit)
        if (frames.includes(page)) {
            // Page hit - frequency already updated
            continue;
        }
        
        // Page fault occurred
        pageFaults++;
        
        // If we have empty frames, use them
        let emptyIndex = frames.indexOf(-1);
        if (emptyIndex !== -1) {
            frames[emptyIndex] = page;
            continue;
        }
        
        // Need to replace a page - find the least frequently used
        let minFrequency = Infinity;
        let oldestTimestamp = Infinity;
        let replaceIndex = 0;
        
        for (let i = 0; i < frameCount; i++) {
            let currentPage = frames[i];
            let frequency = frequencies[currentPage];
            let timestamp = timestamps[currentPage];
            
            // Find page with lowest frequency, breaking ties with oldest timestamp
            if (frequency < minFrequency || 
                (frequency === minFrequency && timestamp < oldestTimestamp)) {
                minFrequency = frequency;
                oldestTimestamp = timestamp;
                replaceIndex = i;
            }
        }
        
        // Replace the selected page
        frames[replaceIndex] = page;
    }
    
    return pageFaults;
}

Advantages:

Works well for workloads with clear frequency patterns
Takes advantage of frequency-based locality
Does not suffer from Belady's Anomaly
Can outperform LRU in certain workloads

Disadvantages:

Does not consider recency for pages with same frequency
May retain pages with initially high frequency even if they won't be used again
More complex to implement than FIFO
Historical frequency may not be relevant to future usage

Time Complexity: O(n) for finding least frequently used page

Space Complexity: O(m) where m is the number of unique pages in reference string

4. Optimal Algorithm

Theory: The Optimal algorithm replaces the page that won't be used for the longest time in the future. It requires knowing the future page reference pattern, which is impossible in real systems, making it theoretical.

When a page fault occurs, it looks ahead in the reference string
Chooses to replace the page that will not be used for the longest period of time
If multiple pages won't be used again, it replaces any of them

function Optimal(referenceString, frameCount) {
    // Initialize variables
    let frames = new Array(frameCount).fill(-1);  // -1 indicates empty frame
    let pageFaults = 0;
    
    // Process each page in the reference string
    for (let currentIndex = 0; currentIndex < referenceString.length; currentIndex++) {
        let page = referenceString[currentIndex];
        
        // Check if page is already in memory (page hit)
        if (frames.includes(page)) {
            // Page hit - no action needed
            continue;
        }
        
        // Page fault occurred
        pageFaults++;
        
        // If we have empty frames, use them
        let emptyIndex = frames.indexOf(-1);
        if (emptyIndex !== -1) {
            frames[emptyIndex] = page;
            continue;
        }
        
        // Need to replace a page - find the one that won't be used for the longest time
        let farthestUseIndex = -1;
        let replaceIndex = 0;
        
        for (let i = 0; i < frameCount; i++) {
            let currentPage = frames[i];
            
            // Find the next use of this page in the reference string
            let nextUse = -1;
            for (let j = currentIndex + 1; j < referenceString.length; j++) {
                if (referenceString[j] === currentPage) {
                    nextUse = j;
                    break;
                }
            }
            
            // If this page won't be used again, replace it immediately
            if (nextUse === -1) {
                replaceIndex = i;
                break;
            }
            
            // If this page will be used later than the current farthest, update
            if (nextUse > farthestUseIndex) {
                farthestUseIndex = nextUse;
                replaceIndex = i;
            }
        }
        
        // Replace the selected page
        frames[replaceIndex] = page;
    }
    
    return pageFaults;
}

Advantages:

Guarantees minimum possible page faults
Serves as a theoretical benchmark to evaluate other algorithms
Does not suffer from Belady's Anomaly

Disadvantages:

Cannot be implemented in real systems (requires knowledge of future)
Used only for theoretical comparison
Computationally expensive to simulate

Time Complexity: O(n²) where n is the length of reference string

Space Complexity: O(n) where n is the number of frames

Note: The Optimal algorithm is also known as Belady's Optimal algorithm or OPT.

5. Random Algorithm

Theory: The Random algorithm simply selects a random page to replace when a page fault occurs and all frames are full. It makes no assumptions about future page references.

Requires no history tracking or complex data structures
Randomly selects a victim frame when replacement is needed
Extremely simple to implement

function Random(referenceString, frameCount) {
    // Initialize variables
    let frames = new Array(frameCount).fill(-1);  // -1 indicates empty frame
    let pageFaults = 0;
    
    // Process each page in the reference string
    for (let page of referenceString) {
        // Check if page is already in memory (page hit)
        if (frames.includes(page)) {
            // Page hit - no action needed
            continue;
        }
        
        // Page fault occurred
        pageFaults++;
        
        // If we have empty frames, use them
        let emptyIndex = frames.indexOf(-1);
        if (emptyIndex !== -1) {
            frames[emptyIndex] = page;
            continue;
        }
        
        // Choose a random frame to replace
        let randomIndex = Math.floor(Math.random() * frameCount);
        frames[randomIndex] = page;
    }
    
    return pageFaults;
}

Advantages:

Extremely simple to implement
No overhead for tracking page history
Can avoid worst-case scenarios that affect deterministic algorithms
Sometimes performs surprisingly well

Disadvantages:

Unpredictable performance
No theoretical performance guarantees
May replace important pages
Typically performs worse than more intelligent algorithms

Time Complexity: O(1) for page replacement

Space Complexity: O(n) where n is the number of frames

Performance Comparison

Algorithm	Time Complexity	Space Complexity	Belady's Anomaly	Implementation Difficulty	Performance
FIFO	O(1)	O(n)	Yes	Easy	Fair
LRU	O(1) with optimized structures	O(n)	No	Moderate	Good
LFU	O(n) or O(log n) with heap	O(m)	No	Moderate to Hard	Good
Optimal	O(n²)	O(n)	No	N/A (Theoretical)	Best
Random	O(1)	O(n)	Probabilistic	Very Easy	Unpredictable

Note: In the above table, 'n' refers to the number of frames and 'm' refers to the number of unique pages in the reference string.

Page Replacement Algorithms - Theoretical Explanations

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

Advantages:

Disadvantages:

2. LRU (Least Recently Used)

Advantages:

Disadvantages:

3. LFU (Least Frequently Used)

Advantages:

Disadvantages:

4. Optimal Algorithm

Advantages:

Disadvantages:

5. Random Algorithm

Advantages:

Disadvantages:

Performance Comparison