Page replacement algorithms

Introduction

In operating systems, efficient memory management is crucial for ensuring optimal performance and resource utilization. One of the key aspects of memory management is handling the allocation and deallocation of memory pages. As processes execute, they frequently need to load and unload pages from physical memory, often necessitating the replacement of pages that are currently in memory. This is where page replacement algorithms come into play.

Page replacement algorithms are strategies used by the operating system to decide which memory pages to swap out, write to disk, or replace when a new page needs to be loaded into memory. The goal of these algorithms is to minimize the page fault rate, thereby enhancing the overall system performance.

Page Fault

A page fault is an event that occurs when a running program tries to access a portion of memory that is not currently mapped to the physical memory (RAM). This event triggers the operating system to intervene and load the required memory page from secondary storage (like a hard drive or SSD) into the RAM. Page faults are a normal part of virtual memory management, allowing systems to run programs that require more memory than is physically available.

Page Replacement Algorithms

Page replacement algorithms are used to decrease the maximum number of page faults.

Page Replacement Algorithm decides which page needs to be removed or needs to swap out when a new page needs to be loaded into the main memory. When a page requested by the CPU is not present in the main memory, and the available space is not sufficient for allocation to the requested page, page replacement happens.

When the page selected for replacement was paged out and referenced again, it must be read in from disk, requiring I/O completion. This process helps determine the algorithm’s quality: the less the waiting time for page-ins, the better is the algorithm.

A page replacement algorithm selects which pages should be replaced to minimize the total number of page misses. There are various different page replacement algorithms. These algorithms are evaluated by running them on particular strings of memory references and computing the number of page faults.

Page Fault means the page referenced by the CPU is not present in the main memory. Page Replacement Algorithm is used when a page fault occurs. The fewer the page faults, the better is the algorithm for that situation.

Page Replacement Algorithms in (OS) Operating System

There are various types of page replacement algorithms in operating systems; some of them are:

First In First Out (FIFO) Page Replacement Algorithm:

FIFO is the simplest way of page replacement, where FIFO is referred to as First In First Out. This algorithm is implemented by replacing the pages that have been present in the main memory for the longest time (or oldest pages).

The implementation of this algorithm is done by keeping track of all pages using a queue.
When the new pages are requested and swapped in, they are added at the end of the queue, and the page presented at the head of the queue becomes the victim.
This algorithm can be used for small systems, but it is not an effective page replacement.

Example

Consider a system with 3 physical memory frames and a sequence of page requests:

Page request sequence: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Step-by-Step Execution

1. Initial State:

Memory Frames: [Empty, Empty, Empty]
Page Faults: 0

2. Page Request 1:

Memory Frames: [1, Empty, Empty]
Page Faults: 1 (Page 1 causes a fault and is loaded into the first frame)

3. Page Request 2:

Memory Frames: [1, 2, Empty]
Page Faults: 2 (Page 2 causes a fault and is loaded into the second frame)

4. Page Request 3:

Memory Frames: [1, 2, 3]
Page Faults: 3 (Page 3 causes a fault and is loaded into the third frame)

5. Page Request 4:

Memory Frames: [4, 2, 3]
Page Faults: 4 (Page 4 causes a fault, replaces Page 1 which is the oldest)

6. Page Request 1:

Memory Frames: [4, 1, 3]
Page Faults: 5 (Page 1 causes a fault, replaces Page 2 which is the oldest)

7. Page Request 2:

Memory Frames: [4, 1, 2]
Page Faults: 6 (Page 2 causes a fault, replaces Page 3 which is the oldest)

8. Page Request 5:

Memory Frames: [5, 1, 2]
Page Faults: 7 (Page 5 causes a fault, replaces Page 4 which is the oldest)

9. Page Request 1:

Memory Frames: [5, 1, 2]
Page Faults: 7 (Page 1 is already in memory, no fault)

10. Page Request 2:

Memory Frames: [5, 1, 2]
Page Faults: 7 (Page 2 is already in memory, no fault)

11. Page Request 3:

Memory Frames: [3, 1, 2]
Page Faults: 8 (Page 3 causes a fault, replaces Page 5 which is the oldest)

12. Page Request 4:

Memory Frames: [3, 4, 2]
Page Faults: 9 (Page 4 causes a fault, replaces Page 1 which is the oldest)

13. Page Request 5:

Memory Frames: [3, 4, 5]
Page Faults: 10 (Page 5 causes a fault, replaces Page 2 which is the oldest)

So, we will have:

Total Page Faults: 10
Final Memory Frames: [3, 4, 5]

Advantages of FIFO page replacement algorithm

FIFO page replacement algorithm is a simple algorithm and easy to use and implement.
FIFO does not cause more overheads in comparison to other algorithms.

Disadvantages of FIFO page replacement algorithm

This algorithm has the worst performance.
This algorithm does not consider the frequency of use or last used time,it simply replaces the oldest page.
Generally, we know if we increase the number of frames then page fault will reduce. But unlike all page replacement algorithms, FIFO has a disadvantage that for some page reference strings, page faults increases when the number of frames increases. This is called Belady’s Anomaly.

LRU Page Replacement Algorithm:

LRU stands for Least Recently Used. This algorithm helps the OS(operating system) search the pages used over a short duration of time.

In the LRU page replacement algorithm, the page that has not been used for the longest time in the main memory will be selected for replacement.

Example

Consider a system with 3 physical memory frames and a sequence of page requests:

Page request sequence: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Step-by-Step Execution

1. Initial State:

Memory Frames: [Empty, Empty, Empty]
Page Faults: 0

2. Page Request 1:

Memory Frames: [1, Empty, Empty]
Page Faults: 1 (Page 1 causes a fault and is loaded into the first frame)
LRU Order: [1]

3. Page Request 2:

Memory Frames: [1, 2, Empty]
Page Faults: 2 (Page 2 causes a fault and is loaded into the second frame)
LRU Order: [1, 2]

4. Page Request 3:

Memory Frames: [1, 2, 3]
Page Faults: 3 (Page 3 causes a fault and is loaded into the third frame)
LRU Order: [1, 2, 3]

5. Page Request 4:

Memory Frames: [4, 2, 3]
Page Faults: 4 (Page 4 causes a fault, replaces Page 1 which is the least recently used)
LRU Order: [2, 3, 4]

6. Page Request 1:

Memory Frames: [4, 1, 3]
Page Faults: 5 (Page 1 causes a fault, replaces Page 2 which is the least recently used)
LRU Order: [3, 4, 1]

7. Page Request 2:

Memory Frames: [4, 1, 2]
Page Faults: 6 (Page 2 causes a fault, replaces Page 3 which is the least recently used)
LRU Order: [4, 1, 2]

8. Page Request 5:

Memory Frames: [5, 1, 2]
Page Faults: 7 (Page 5 causes a fault, replaces Page 4 which is the least recently used)
LRU Order: [1, 2, 5]

9. Page Request 1:

Memory Frames: [5, 1, 2]
Page Faults: 7 (Page 1 is already in memory, no fault)
LRU Order: [2, 5, 1]

10. Page Request 2:

Memory Frames: [5, 1, 2]
Page Faults: 7 (Page 2 is already in memory, no fault)
LRU Order: [5, 1, 2]

11. Page Request 3:

Memory Frames: [3, 1, 2]
Page Faults: 8 (Page 3 causes a fault, replaces Page 5 which is the least recently used)
LRU Order: [1, 2, 3]

12. Page Request 4:

Memory Frames: [3, 4, 2]
Page Faults: 9 (Page 4 causes a fault, replaces Page 1 which is the least recently used)
LRU Order: [2, 3, 4]

13. Page Request 5:

Memory Frames: [3, 4, 5]
Page Faults: 10 (Page 5 causes a fault, replaces Page 2 which is the least recently used)
LRU Order: [3, 4, 5]

So, we will have:

Total Page Faults: 10
Final Memory Frames: [3, 4, 5]

Advantages of LRU page replacement algorithm

This algorithm helps identify the faulty pages that are not used for a long time and thus can be handled.
It also helps in the full analysis.
LRU is an efficient algorithm which means its performance is better.

Disadvantages of LRU page replacement algorithm

It is very expensive and time-consuming, and also more complex.
An additional data structure is needed here.

MRU Page Replacement Algorithm

The MRU (Most Recently Used) page replacement algorithm is based on the principle that the page most recently used is the least likely to be used again soon. Therefore, it should be the first to be replaced when a new page needs to be loaded. This is in contrast to the LRU (Least Recently Used) algorithm, which replaces the least recently used page.

In the MRU algorithm, the most recently accessed page is replaced when a page fault occurs, as it is assumed that the least recently accessed pages will be needed again soon.

Example

Consider a system with 3 physical memory frames and a sequence of page requests:

Page request sequence: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Step-by-Step Execution

1. Initial State:

Memory Frames: [Empty, Empty, Empty]
Page Faults: 0

2. Page Request 1:

Memory Frames: [1, Empty, Empty]
Page Faults: 1 (Page 1 causes a fault and is loaded into the first frame)
MRU Page: 1

3. Page Request 2:

Memory Frames: [1, 2, Empty]
Page Faults: 2 (Page 2 causes a fault and is loaded into the second frame)
MRU Page: 2

4. Page Request 3:

Memory Frames: [1, 2, 3]
Page Faults: 3 (Page 3 causes a fault and is loaded into the third frame)
MRU Page: 3

5. Page Request 4:

Memory Frames: [1, 2, 4]
Page Faults: 4 (Page 4 causes a fault, replaces Page 3 which is the most recently used)
MRU Page: 4

6. Page Request 1:

Memory Frames: [1, 2, 4]
Page Faults: 4 (Page 1 is already in memory, no fault)
MRU Page: 1

7. Page Request 2:

Memory Frames: [1, 2, 4]
Page Faults: 4 (Page 2 is already in memory, no fault)
MRU Page: 2

8. Page Request 5:

Memory Frames: [1, 5, 4]
Page Faults: 5 (Page 5 causes a fault, replaces Page 2 which is the most recently used)
MRU Page: 5

9. Page Request 1:

Memory Frames: [1, 5, 4]
Page Faults: 5 (Page 1 is already in memory, no fault)
MRU Page: 1

10. Page Request 2:

Memory Frames: [2, 5, 4]
Page Faults: 6 (Page 2 causes a fault, replaces Page 1 which is the most recently used)
MRU Page: 2

11. Page Request 3:

Memory Frames: [3, 5, 4]
Page Faults: 7 (Page 3 causes a fault, replaces Page 2 which is the most recently used)
MRU Page: 3

12. Page Request 4:

Memory Frames: [3, 5, 4]
Page Faults: 7 (Page 4 is already in memory, no fault)
MRU Page: 4

13. Page Request 5:

Memory Frames: [3, 5, 4]
Page Faults: 7 (Page 5 is already in memory, no fault)
MRU Page: 5

So, we will have:

Total Page Faults: 7
Final Memory Frames: [3, 5, 4]

Advantages of MRU

Simple to Implement: The MRU algorithm is straightforward and easy to implement.
Good for Certain Workloads: MRU can be effective for workloads where the most recently used pages are less likely to be used again soon.

Disadvantages of MRU

Not Universally Optimal: The assumption that the most recently used page is the least likely to be used again is not always valid, leading to suboptimal performance in many scenarios.
Inconsistent Performance: MRU can perform poorly with certain types of access patterns, such as those with high temporal locality, where the most recently used pages are likely to be accessed again soon.

Optimal Page Replacement Algorithm:

This algorithm will replace the page used after the longest interval. In other words, the page which is farthest to come in the upcoming sequence is replaced.

The practical implementation of the optimal page replacement algorithm is impossible as we cannot predict the pages that will not be used for the longest time in the future.
The page faults in this algorithm are fewer, and thus, this is the best-known algorithm.

Example

Consider a system with 3 physical memory frames and a sequence of page requests:

Page request sequence: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Step-by-Step Execution

1. Initial State:

Memory Frames: [Empty, Empty, Empty]
Page Faults: 0

2. Page Request 1:

Memory Frames: [1, Empty, Empty]
Page Faults: 1 (Page 1 causes a fault and is loaded into the first frame)

3. Page Request 2:

Memory Frames: [1, 2, Empty]
Page Faults: 2 (Page 2 causes a fault and is loaded into the second frame)

4. Page Request 3:

Memory Frames: [1, 2, 3]
Page Faults: 3 (Page 3 causes a fault and is loaded into the third frame)

5. Page Request 4:

Memory Frames: [4, 2, 3]
Page Faults: 4 (Page 4 causes a fault, replaces Page 1 which will not be used for the longest time)

6. Page Request 1:

Memory Frames: [4, 1, 3]
Page Faults: 5 (Page 1 causes a fault, replaces Page 2 which will not be used for the longest time)

7. Page Request 2:

Memory Frames: [4, 1, 2]
Page Faults: 6 (Page 2 causes a fault, replaces Page 3 which will not be used for the longest time)

8. Page Request 5:

Memory Frames: [5, 1, 2]
Page Faults: 7 (Page 5 causes a fault, replaces Page 4 which will not be used for the longest time)

9. Page Request 1:

Memory Frames: [5, 1, 2]
Page Faults: 7 (Page 1 is already in memory, no fault)

10. Page Request 2:

Memory Frames: [5, 1, 2]
Page Faults: 7 (Page 2 is already in memory, no fault)

11. Page Request 3:

Memory Frames: [5, 1, 3]
Page Faults: 8 (Page 3 causes a fault, replaces Page 2 which will not be used for the longest time)

12. Page Request 4:

Memory Frames: [4, 1, 3]
Page Faults: 9 (Page 4 causes a fault, replaces Page 5 which will not be used for the longest time)

13. Page Request 5:

Memory Frames: [4, 1, 5]
Page Faults: 10 (Page 5 causes a fault, replaces Page 3 which will not be used for the longest time)

So, we will have:

Total Page Faults: 10
Final Memory Frames: [4, 1, 5]

Advantages of Optimal page replacement algorithm

This algorithm has less complexity compared to other page replacement algorithms like LRU.
Data structures used in this algorithm are simple and easy to use.

Disadvantages of Optimal page replacement algorithm

Error handling is quite challenging in this page replacement algorithm.
It is a perfect algorithm but practically impossible as any operating system cannot know the future requests.

Frequently Asked Questions

What is the best page replacement algorithm?

The Optimal Page Replacement algorithm is the best in theory, providing the lowest page fault rate but requiring future knowledge of memory references.

What is the most frequently used page replacement algorithm?

The Least Recently Used (LRU) algorithm is the most frequently used due to its balance of simplicity and effectiveness in reducing page faults.

Which replacement algorithm is most efficient?

The Optimal Page Replacement algorithm is the most efficient theoretically, minimizing page faults, but is impractical due to its requirement for future memory access information.

Conclusion

In this blog, we learned about page faults and thus page replacement algorithms to avoid page faults. We also learned about different page fault algorithms like FIFO(First in First Out), LRU(Least recently used), and Optimal page replacement algorithms, along with the various advantages and disadvantages of using these algorithms.

Check Out - Anomalies In DBMS.

You can visit here to learn more about different topics related to database management systems. Also, try Code360 to practice programming problems for your complete interview preparation.