# Page Replacement Algorithms in Operating Systems

Difficulty Level Medium
Frequently asked in Amazon Cognizant Factset Microsoft PayPal
Operating Systems TheoryViews 5477

## 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 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.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

// 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
// add the page to queue
// 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
// add the new page to queue

// it is page fault, increment faults
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.

Translate ยป