Page Replacement Algorithms in Operating Systems

What is Page Replacement?

The modern operating systems use paging for memory management and many times there is a need for page replacement. Page replacement is the process of replacing a page that is currently present in the memory with a page that is needed but is not present in the memory. Such a condition is termed as Page Fault.

The Page Replacement Algorithm’s goal is to reduce the number of Page Faults so as to increase the overall performance. There are many algorithms for page replacement. We are discussing a few here.

First In First Out(FIFO)

First In First Out Page Replacement Algorithm is the simplest algorithm for page replacement. It maintains a queue to keep track of all the pages. We always add a new page to the end of a queue. When the queue is full and there is a Page Fault, we remove the page present at the front of the queue and add a new page at the end of the queue.
In this manner we maintain the first in first out technique, that is, the page which is inserted into the memory first will be removed from the memory first.

Example

Let the page reference string be {1, 0, 1, 2, 5, 7, 3, 4, 3, 4, 1} and there are total 4 page slots. Then,

Belady’s Anomaly

Belady proved that it is possible for some page reference strings that increasing the page slots may result in higher number of page faults.

Example
Consider the page reference string {3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4} with 3 page slots and 4 page slots.
Page Faults with 3 page slots = 3
Page Faults with 4 page slots = 4

Optimal Page Replacement

This algorithm says that if we know which page we are gonna use in future then we can optimize the page replacement technique.
According to Optimal Page Replacement algorithm, it is always optimal to replace the page which is going to be used least in the future.

Example

Let the page reference string be {2, 3, 4, 2, 1, 3, 7, 5, 4, 3} and there are total 3 page slots. Then,

Least Recently Used

This algorithm is based on caching technique. The algorithm says that replace the page which least used in the recent times.

Example

Let the page reference string be {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4} and there are total 3 page slots. Then,

Implementation of First In First Out

Java code for Page Replacement Algorithms in Operating Systems

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

class FirstInFirstOutPageReplacement {
    private static int pageFaults(int[] pageString, int pageSlots) {
        int faults = 0;

        // Set to store the elements present in queue, used to check if a page is present or not
        HashSet<Integer> set = new HashSet<>();
        // Queue to maintain the order of insertion
        Queue<Integer> queue = new LinkedList<>();

        // traverse the page string
        for (int i = 0; i < pageString.length; i++) {
            // if there are some empty slots
            if (queue.size() < pageSlots) {
                if (!set.contains(pageString[i])) {
                    // and the current page is missing
                    // add the page to set
                    set.add(pageString[i]);
                    // add the page to queue
                    queue.add(pageString[i]);
                    // it is a page fault, increment faults
                    faults++;
                }
            } else {
                // there are no empty slots and if current page is absent
                if (!set.contains(pageString[i])) {
                    // remove the first page in queue
                    int removedPage = queue.poll();
                    // remove the page from set
                    set.remove(removedPage);

                    // add the new page to set
                    set.add(pageString[i]);
                    // add the new page to queue
                    queue.add(pageString[i]);

                    // it is page fault, increment faults
                    faults++;
                }
            }
        }

        // return total number of page faults
        return faults;
    }

    public static void main(String[] args) {
        // Example
        int pageString[] = new int[] {1, 0, 1, 2, 5, 7, 3, 4, 3, 4, 1};
        int pageSlots = 4;
        System.out.println(pageFaults(pageString, pageSlots));
    }
}

Page String = {1, 0, 1, 2, 5, 7, 3, 4, 3, 4, 1}
Page Slots = 4

8

C++ code for Page Replacement Algorithms in Operating Systems

#include <bits/stdc++.h> 
using namespace std; 

int pageFaults(int *pageString, int pageSlots, int n) {
    int faults = 0;
    
    // Set to store the elements present in queue, used to check if a page is present or not
    unordered_set<int> set;
    // Queue to maintain the order of insertion
    queue<int> q;
    
    // traverse the page string
    for (int i = 0; i < n; i++) {
        // if there are some empty slots
        if (q.size() < pageSlots) {
            if (set.find(pageString[i]) == set.end()) {
                // and the current page is missing
                // add the page to set
                set.insert(pageString[i]);
                // add the page to queue
                q.push(pageString[i]);
                // it is a page fault, increment faults
                faults++;
            }
        } else {
            // there are no empty slots and if current page is absent
            if (set.find(pageString[i]) == set.end()) {
                // remove the first page in queue
                int removedPage = q.front();
                q.pop();
                // remove the page from set
                set.erase(removedPage);
                
                // add the new page to set
                set.insert(pageString[i]);
                // add the new page to queue
                q.push(pageString[i]);
                
                // it is page fault, increment faults
                faults++;
            }
        }
    }
    
    return faults;
}

int main() {
    // Example
    int pageString[] = {1, 0, 1, 2, 5, 7, 3, 4, 3, 4, 1};
    int pageSlots = 4;
    cout<<pageFaults(pageString, pageSlots, sizeof(pageString) / sizeof(pageString[0]))<<endl;
    
    return 0;
}

Page String = {1, 0, 1, 2, 5, 7, 3, 4, 3, 4, 1}
Page Slots = 4

8

Complexity Analysis

Time complexity

Using HashSet has allowed us to run the given algorithm in linear time. Thus the algorithm has linear time complexity O(N).

Space Complexity

O(pageSlots), we have been keeping only pageSlots number of pages in the queue. Thus space complexity is dependent on the pageSlots.