Page Replacement Algorithms

1. First In First Out (FIFO): This is the simplest page replacement algorithm. In this algorithm, the
operating system keeps track of all pages in the memory in a queue, the oldest page is in the front of
the queue. When a page needs to be replaced page in the front of the queue is selected for removal.

Example 1: Consider page reference string 1, 3, 0, 3, 5, 6, 3 with 3 page frames.

Find the number of page faults.

Belady’s anomaly proves that it is possible to have more page faults when increasing the number of
page frames while using the First in First Out (FIFO) page replacement algorithm. For example, if we
consider reference strings 3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4, and 3 slots, we get 9 total page faults, but if
we increase slots to 4, we get 10-page faults.

2. Optimal Page replacement: In this algorithm, pages are replaced which would not be used for the
longest duration of time in the future.

Example-2: Consider the page references 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3 with 4 page frame. Find

Example-3: Consider the page reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3 with 4 page frames.

4. Most Recently Used (MRU): In this algorithm, page will be replaced which has been used recently.

Advantages and Disadvantages of various Page Replacement algorithms

First In First Out (FIFO):

Advantages –

It is simple and easy to understand & implement.

It is efficiently used for small systems

It does not cause more overheads

Fairness: FIFO algorithm is fair in the sense that all pages have an equal chance of being replaced.
The oldest page is replaced first, regardless of its usage frequency or importance.

No starvation: The FIFO algorithm does not suffer from starvation, which means that a page will
eventually be replaced if it has been in memory for a long time, even if it is frequently used.

Predictability: The FIFO algorithm is predictable in the sense that the order in which pages are
replaced is deterministic and does not depend on the page usage patterns or history.

Low overhead: FIFO requires minimal overhead because it only needs to maintain a simple queue of
pages in memory, making it a good choice for systems with limited resources.

Disadvantages –

The process effectiveness is low.

When we increase the number of frames while using FIFO, we are giving more memory to processes.
So, page fault should decrease, but here the page faults are increasing. This problem is called as
Belady’s Anomaly.

Every frame needs to be taken account off.

It uses an additional data structure.

Poor performance: FIFO may not provide optimal performance because it does not take into account
the usage patterns or importance of the pages. It may result in frequent page faults and unnecessary
disk I/O operations, especially if the workload is complex or memory demands are high.

Inefficient use of memory: FIFO can lead to inefficient use of memory because it replaces the oldest
page, regardless of its usage frequency or importance. As a result, some pages that are rarely used or
not important may occupy memory for a long time, while other more critical pages may be swapped
out frequently.

Susceptibility to thrashing: FIFO may be susceptible to thrashing, which occurs when the system
spends a significant amount of time swapping pages in and out of memory without making progress
on the actual workload. This happens when the number of pages needed by the workload exceeds
the available physical memory, and the FIFO algorithm does not efficiently manage the page
swapping.

Unfairness: Although FIFO is fair in the sense that it treats all pages equally, it may not be fair from
the perspective of the workload or the user. Some pages may be more important than others, and
replacing them first can lead to degraded performance or even application crashes.

No consideration of future usage: FIFO does not consider the future usage of pages, which means
that it may replace a page that will be needed again soon, leading to increased page faults and
decreased performance.
2. Least Recently Used (LRU):

Advantages –

It is open for full analysis.

In this, we replace the page which is least recently used, thus free from Belady’s Anomaly.

Easy to choose page which has faulted and hasn’t been used for a long time.

Good performance: LRU is designed to replace the page that has not been accessed for the longest
time. It is considered a “smart” algorithm because it takes into account the usage history of pages,
and it can lead to fewer page faults and faster application response times.

Efficient use of memory: LRU leads to efficient use of memory because it replaces the page that has
not been used for the longest time. This means that pages that are rarely used or not important are
more likely to be swapped out, freeing up memory for more critical pages.

No thrashing: LRU is less susceptible to thrashing compared to FIFO because it considers the usage
history of pages. It can detect which pages are being used frequently and prioritize them for memory
allocation, reducing the number of page faults and disk I/O operations.

Fairness: LRU is considered a fair algorithm because it takes into account the usage history of pages
and replaces the least recently used page first. This means that pages that are rarely used or not
important are more likely to be swapped out, making room for more frequently used pages.

Good balance between complexity and performance: LRU is more complex than FIFO, but it is still
relatively simple and easy to implement compared to other algorithms like optimal page
replacement. It strikes a good balance between complexity and performance, making it a popular
choice for many operating systems.

Disadvantages –

It requires additional Data Structure to be implemented.

Hardware assistance is high.

In LRU error detection is difficult as compared to other algorithms.

It has limited acceptability.

LRU are very costly to operate.

3. Optimal Page Replacement (OPR):

Advantages –

Complexity is less and easy to implement.

Assistance needed is low i.e Data Structure used are easy and light.
Optimal performance: The optimal page replacement algorithm is designed to replace the page that
will not be used for the longest time in the future. It provides the best possible performance because
it minimizes the number of page faults and maximizes the number of hits.

Efficient use of memory: Optimal page replacement leads to efficient use of memory because it
replaces the page that will not be used for the longest time in the future. This means that pages that
are rarely used or not important are more likely to be swapped out, freeing up memory for more
critical pages.

No thrashing: Optimal page replacement is less susceptible to thrashing compared to FIFO or LRU
because it considers the future usage of pages. It can detect which pages are being used frequently
and which pages are likely to be used in the future, prioritizing them for memory allocation and
reducing the number of page faults and disk I/O operations.

Fairness: Optimal page replacement is considered a fair algorithm because it takes into account the
future usage of pages and replaces the page that will not be used for the longest time in the future.
This means that pages that are rarely used or not important are more likely to be swapped out,
making room for more frequently used or critical pages.

Ideal for analysis and simulation: Optimal page replacement is ideal for analysis and simulation
because it provides an upper bound on the performance of other page replacement algorithms. It
can be used to compare the performance of other algorithms and evaluate their effectiveness.

Disadvantages –

It is not possible in practice as the operating system cannot know future requests.

Error handling is tough.

While FIFO and LRU have their share of advantages and disadvantages, OPR is used as a benchmark
to measure the performance of other algorithms. So according to the situation appropriate algorithm
is used.