Home

Learning Hub

Articles

Understanding Page Replacement Algorithms in OS

Page replacement is an important element of operating systems. This ensures that the data most often used is kept in the system’s RAM, which makes the system work faster. It is crucial for effective operation in the course of its functions, particularly in virtual memory systems.

Virtual memory is a feature found in operating systems that enables a computer to utilise more memory than what is physically installed within the hardware. This is accomplished by copying data from the random access memory resources (RAM) to the disk. Nevertheless, this process can cause page faults, which arise when the program accesses a memory location that does not contain a valid page. This is where page replacement algorithms come into play.

The page replacement algorithms in OS determine the pages to be evicted from memory when new pages are brought in. Their objectives include reducing the number of page faults and increasing system performance. For this reason, comprehending these algorithms is crucial to understanding how memory management works when learning about operating systems.

Fundamentals of Paging and Virtual Memory in Operating Systems

Paging

Paging is a system of memory management that allows the process to be spread into different areas, not just following one another in physical memory. Memory is divided into blocks referred to as “pages.” Here, whenever a program is running, it is in the form of “pages,” which are then put in the memory frames. This method simplifies memory management and helps avoid fragmentation.

Virtual Memory

Virtual memory, a technological marvel, gives the illusion of a large, continuous memory space. It empowers the system to execute big applications or a number of programs concurrently, even when the physical memory stock may be limited. Virtual memory functions by setting hard drive sections as RAM extension storage. If the amount of data in the RAM reaches the limit, the operating system intelligently transfers only some data to another file placed on the hard drive, called the swap file.

Demand Paging

Demand paging is a part of virtual memory. It loads pages into memory only when they are needed, not in advance. This technique saves memory but can lead to page faults when the required page is not in memory. Page replacement algorithms manage these page faults by deciding which pages to swap out.

Also Read: What is the Process in OS (Operating System)?

The Necessity of Page Replacement Algorithms in OS

Page replacement algorithms are essential for efficient memory management in operating systems.

Why Are They Needed?

When a page fault occurs, the system must decide which page to remove from memory to make space for the new one. Without a good algorithm, the system might remove pages that will be needed soon, leading to more page faults and reduced performance.

Objectives

The primary goal of page replacement algorithms in OS is to minimise page faults. This helps in keeping the system responsive and efficient. Different algorithms have different strategies to achieve this goal. Understanding these strategies helps us choose the right algorithm for specific situations.

First in First Out (FIFO) Page Replacement Algorithm in OS

Detailed Explanation of FIFO

The FIFO page replacement algorithm is one of the simplest algorithms. It operates on the principle that the oldest page in memory is the first to be replaced. Imagine a queue at a ticket counter where the first person in line is the first to be served. Similarly, the oldest page (the first one that entered) is the first to be removed.

Example of FIFO Algorithm in Action

Let’s walk through an example. Suppose we have three memory frames and a page reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.

1. Initial State: All frames are empty.
   • Reference: 1
   • Frames: [1, -, -]
   • Page Faults: 1
2. Reference 2: Load page 2.
   • Reference: 2
   • Frames: [1, 2, -]
   • Page Faults: 2
3. Reference 3: Load page 3.
   • Reference: 3
   • Frames: [1, 2, 3]
   • Page Faults: 3
4. Reference 4: Replace the oldest page (1) with 4.
   • Reference: 4
   • Frames: [4, 2, 3]
   • Page Faults: 4
5. Reference 1: Replace the oldest page (2) with 1.
   • Reference: 1
   • Frames: [4, 1, 3]
   • Page Faults: 5
6. Reference 2: Replace the oldest page (3) with 2.
   • Reference: 2
   • Frames: [4, 1, 2]
   • Page Faults: 6
7. Reference 5: Replace the oldest page (4) with 5.
   • Reference: 5
   • Frames: [5, 1, 2]
   • Page Faults: 7
8. Reference 1: Page 1 is already in memory.
   • Reference: 1
   • Frames: [5, 1, 2]
   • Page Faults: 7
9. Reference 2: Page 2 is already in memory.
   • Reference: 2
   • Frames: [5, 1, 2]
   • Page Faults: 7
10. Reference 3: Replace the oldest page (5) with 3.
    • Reference: 3
    • Frames: [3, 1, 2]
    • Page Faults: 8
11. Reference 4: Replace the oldest page (1) with 4.
    • Reference: 4
    • Frames: [3, 4, 2]
    • Page Faults: 9
12. Reference 5: Replace the oldest page (2) with 5.
    • Reference: 5
    • Frames: [3, 4, 5]
    • Page Faults: 10

Here’s a table summarising the example:

Advantages and Disadvantages of FIFO

Advantages:

• Simple to implement.
• Easy to understand.

Disadvantages:

• Can lead to a high number of page faults.
• Suffers from Belady’s anomaly, where increasing the number of frames can lead to more page faults.

Understanding Belady’s Anomaly with FIFO

Belady’s anomaly is a phenomenon where increasing the number of page frames results in an increase in the number of page faults. This counterintuitive situation occurs with FIFO. For example, in the sequence above, adding more frames doesn’t necessarily reduce page faults. This anomaly highlights the inefficiency of FIFO in certain scenarios.

Also Read- Memory Management in OS

Optimal Page Replacement Algorithm in OS

How Optimal Page Replacement Works

The Optimal page replacement algorithms in OS are the best in terms of minimising page faults. It works by replacing the page that will not be used for the longest period in the future. While this sounds ideal, it requires future knowledge of the page reference string, making it impractical for real-world use. However, it serves as a benchmark for evaluating other algorithms.

Example of Optimal Algorithm in Practice

Let’s consider a page reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3. We have three frames available.

1. Initial State: All frames are empty.
   • Reference: 7
   • Frames: [7, -, -]
   • Page Faults: 1
2. Reference 0: Load page 0.
   • Reference: 0
   • Frames: [7, 0, -]
   • Page Faults: 2
3. Reference 1: Load page 1.
   • Reference: 1
   • Frames: [7, 0, 1]
   • Page Faults: 3
4. Reference 2: Replace page 7, which is not needed soon.
   • Reference: 2
   • Frames: [2, 0, 1]
   • Page Faults: 4
5. Reference 0: Page 0 is already in memory.
   • Reference: 0
   • Frames: [2, 0, 1]
   • Page Faults: 4
6. Reference 3: Replace page 1, which is used farthest in the future.
   • Reference: 3
   • Frames: [2, 0, 3]
   • Page Faults: 5
7. Reference 0: Page 0 is already in memory.
   • Reference: 0
   • Frames: [2, 0, 3]
   • Page Faults: 5
8. Reference 4: Replace page 2.
   • Reference: 4
   • Frames: [4, 0, 3]
   • Page Faults: 6
9. Reference 2: Replace page 0.
   • Reference: 2
   • Frames: [4, 2, 3]
   • Page Faults: 7
10. Reference 3: Page 3 is already in memory.
    • Reference: 3
    • Frames: [4, 2, 3]
    • Page Faults: 7
11. Reference 0: Replace page 4.
    • Reference: 0
    • Frames: [0, 2, 3]
    • Page Faults: 8
12. Reference 3: Page 3 is already in memory.
    • Reference: 3
    • Frames: [0, 2, 3]
    • Page Faults: 8
13. Reference 2: Page 2 is already in memory.
    • Reference: 2
    • Frames: [0, 2, 3]
    • Page Faults: 8
14. Reference 3: Page 3 is already in memory.
    • Reference: 3
    • Frames: [0, 2, 3]
    • Page Faults: 8

Here’s a table summarising the example:

Benefits and Drawbacks of Optimal Algorithm

Benefits:

• Minimises page faults.
• Sets a benchmark for other algorithms.

Drawbacks:

• Requires future knowledge, which is impractical.
• Not usable in real-time systems.

Least Recently Used (LRU) Page Replacement Algorithm

Mechanism of LRU Algorithm

The LRU algorithm replaces the page that has not been used for the longest time. It is based on the principle of temporal locality, which states that recently accessed pages are likely to be accessed again soon.

Example Illustrating LRU in Action

Let’s use the page reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3. We have three frames.

1. Initial State: All frames are empty.
   • Reference: 7
   • Frames: [7, -, -]
   • Page Faults: 1
2. Reference 0: Load page 0.
   • Reference: 0
   • Frames: [7, 0, -]
   • Page Faults: 2
3. Reference 1: Load page 1.
   • Reference: 1
   • Frames: [7, 0, 1]
   • Page Faults: 3
4. Reference 2: Replace page 7, least recently used.
   • Reference: 2
   • Frames: [2, 0, 1]
   • Page Faults: 4
5. Reference 0: Page 0 is already in memory.
   • Reference: 0
   • Frames: [2, 0, 1]
   • Page Faults: 4
6. Reference 3: Replace page 1.
   • Reference: 3
   • Frames: [2, 0, 3]
   • Page Faults: 5
7. Reference 0: Page 0 is already in memory.
   • Reference: 0
   • Frames: [2, 0, 3]
   • Page Faults: 5
8. Reference 4: Replace page 2.
   • Reference: 4
   • Frames: [4, 0, 3]
   • Page Faults: 6
9. Reference 2: Replace page 3.
   • Reference: 2
   • Frames: [4, 0, 2]
   • Page Faults: 7
10. Reference 3: Replace page 4.
    • Reference: 3
    • Frames: [3, 0, 2]
    • Page Faults: 8
11. Reference 0: Page 0 is already in memory.
    • Reference: 0
    • Frames: [3, 0, 2]
    • Page Faults: 8
12. Reference 3: Page 3 is already in memory.
    • Reference: 3
    • Frames: [3, 0, 2]
    • Page Faults: 8
13. Reference 2: Page 2 is already in memory.
    • Reference: 2
    • Frames: [3, 0, 2]
    • Page Faults: 8
14. Reference 3: Page 3 is already in memory.
    • Reference: 3
    • Frames: [3, 0, 2]
    • Page Faults: 8

Here’s a table summarising the example:

Pros and Cons of Using LRU

Pros:

• Effective in practice.
• Does not suffer from Belady’s anomaly.

Cons:

• Complex to implement.
• Requires additional data structures.

Most Recently Used (MRU) Page Replacement Algorithm

Functionality of MRU Algorithm

The MRU algorithm replaces the most recently used page. This is based on the idea that the most recently used page is less likely to be needed again soon. It works well in certain scenarios where the most recently used data is unlikely to be reused quickly.

Example and Practical Application of MRU

Using the same reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3. Let’s see MRU in action with three frames.

1. Initial State: All frames are empty.
   • Reference: 7
   • Frames: [7, -, -]
   • Page Faults: 1
2. Reference 0: Load page 0.
   • Reference: 0
   • Frames: [7, 0, -]
   • Page Faults: 2
3. Reference 1: Load page 1.
   • Reference: 1
   • Frames: [7, 0, 1]
   • Page Faults: 3
4. Reference 2: Replace the most recently used page (1).
   • Reference: 2
   • Frames: [7, 0, 2]
   • Page Faults: 4
5. Reference 0: Page 0 is already in memory.
   • Reference: 0
   • Frames: [7, 0, 2]
   • Page Faults: 4
6. Reference 3: Replace the most recently used page (2).
   • Reference: 3
   • Frames: [7, 0, 3]
   • Page Faults: 5
7. Reference 0: Page 0 is already in memory.
   • Reference: 0
   • Frames: [7, 0, 3]
   • Page Faults: 5
8. Reference 4: Replace the most recently used page (3).
   • Reference: 4
   • Frames: [7, 0, 4]
   • Page Faults: 6
9. Reference 2: Replace the most recently used page (4).
   • Reference: 2
   • Frames: [7, 0, 2]
   • Page Faults: 7
10. Reference 3: Replace the most recently used page (2).
    • Reference: 3
    • Frames: [7, 0, 3]
    • Page Faults: 8
11. Reference 0: Page 0 is already in memory.
    • Reference: 0
    • Frames: [7, 0, 3]
    • Page Faults: 8
12. Reference 3: Page 3 is already in memory.
    • Reference: 3
    • Frames: [7, 0, 3]
    • Page Faults: 8
13. Reference 2: Replace the most recently used page (3).
    • Reference: 2
    • Frames: [7, 0, 2]
    • Page Faults: 9
14. Reference 3: Replace the most recently used page (2).
    • Reference: 3
    • Frames: [7, 0, 3]
    • Page Faults: 10

Here’s a table summarising the example:

Advantages and Potential Issues with MRU

Advantages:

• Simple to implement.
• Suitable for specific use cases.

Potential Issues:

• Can lead to poor performance in many scenarios.
• Opposite of the principle of temporal locality.

Last in First Out (LIFO) Page Replacement Algorithm

Concept Behind LIFO Algorithm

The LIFO algorithm replaces the most recently loaded page. This is the opposite of FIFO. It assumes that the most recently added page is less likely to be used soon. This method is straightforward but often not practical.

Example to Understand LIFO

Consider the same reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3. We have three frames.

1. Initial State: All frames are empty.
   • Reference: 7
   • Frames: [7, -, -]
   • Page Faults: 1
2. Reference 0: Load page 0.
   • Reference: 0
   • Frames: [7, 0, -]
   • Page Faults: 2
3. Reference 1: Load page 1.
   • Reference: 1
   • Frames: [7, 0, 1]
   • Page Faults: 3
4. Reference 2: Replace the last loaded page (1).
   • Reference: 2
   • Frames: [7, 0, 2]
   • Page Faults: 4
5. Reference 0: Page 0 is already in memory.
   • Reference: 0
   • Frames: [7, 0, 2]
   • Page Faults: 4
6. Reference 3: Replace the last loaded page (2).
   • Reference: 3
   • Frames: [7, 0, 3]
   • Page Faults: 5
7. Reference 0: Page 0 is already in memory.
   • Reference: 0
   • Frames: [7, 0, 3]
   • Page Faults: 5
8. Reference 4: Replace the last loaded page (3).
   • Reference: 4
   • Frames: [7, 0, 4]
   • Page Faults: 6
9. Reference 2: Replace the last loaded page (4).
   • Reference: 2
   • Frames: [7, 0, 2]
   • Page Faults: 7
10. Reference 3: Replace the last loaded page (2).
    • Reference: 3
    • Frames: [7, 0, 3]
    • Page Faults: 8
11. Reference 0: Page 0 is already in memory.
    • Reference: 0
    • Frames: [7, 0, 3]
    • Page Faults: 8
12. Reference 3: Page 3 is already in memory.
    • Reference: 3
    • Frames: [7, 0, 3]
    • Page Faults: 8
13. Reference 2: Replace the last loaded page (3).
    • Reference: 2
    • Frames: [7, 0, 2]
    • Page Faults: 9
14. Reference 3: Replace the last loaded page (2).
    • Reference: 3
    • Frames: [7, 0, 3]
    • Page Faults: 10

Here’s a table summarising the example:

Strengths and Weaknesses of LIFO

Strengths:

• Simple to understand and implement.
• No complex data structures required.

Weaknesses:

• Often impractical and inefficient.
• Ignores the principle of temporal locality.

Random Page Replacement Algorithm Explained

Working Principle of Random Algorithm

The Random page replacement algorithm replaces any page in memory randomly. It does not follow a specific pattern or rule. This makes it easy to implement but unpredictable. The main idea is to choose a page to replace without considering the order or frequency of page accesses.

Example Demonstrating Random Replacement

Consider a page reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3. We have three frames available. Let’s see how Random replacement works.

1. Initial State: All frames are empty.
   • Reference: 7
   • Frames: [7, -, -]
   • Page Faults: 1
2. Reference 0: Load page 0.
   • Reference: 0
   • Frames: [7, 0, -]
   • Page Faults: 2
3. Reference 1: Load page 1.
   • Reference: 1
   • Frames: [7, 0, 1]
   • Page Faults: 3
4. Reference 2: Randomly replace one page (let’s say page 0).
   • Reference: 2
   • Frames: [7, 2, 1]
   • Page Faults: 4
5. Reference 0: Randomly replace one page (let’s say page 7).
   • Reference: 0
   • Frames: [0, 2, 1]
   • Page Faults: 5
6. Reference 3: Randomly replace one page (let’s say page 1).
   • Reference: 3
   • Frames: [0, 2, 3]
   • Page Faults: 6
7. Reference 0: Page 0 is already in memory.
   • Reference: 0
   • Frames: [0, 2, 3]
   • Page Faults: 6
8. Reference 4: Randomly replace one page (let’s say page 2).
   • Reference: 4
   • Frames: [0, 4, 3]
   • Page Faults: 7
9. Reference 2: Randomly replace one page (let’s say page 0).
   • Reference: 2
   • Frames: [2, 4, 3]
   • Page Faults: 8
10. Reference 3: Page 3 is already in memory.
    • Reference: 3
    • Frames: [2, 4, 3]
    • Page Faults: 8
11. Reference 0: Randomly replace one page (let’s say page 4).
    • Reference: 0
    • Frames: [2, 0, 3]
    • Page Faults: 9
12. Reference 3: Page 3 is already in memory.
    • Reference: 3
    • Frames: [2, 0, 3]
    • Page Faults: 9
13. Reference 2: Page 2 is already in memory.
    • Reference: 2
    • Frames: [2, 0, 3]
    • Page Faults: 9
14. Reference 3: Page 3 is already in memory.
    • Reference: 3
    • Frames: [2, 0, 3]
    • Page Faults: 9

Here’s a table summarising the example:

Pros and Cons of Random Replacement

Pros:

• Simple to implement.
• No overhead for tracking pages.

Cons:

• Unpredictable performance.
• Can lead to suboptimal page replacement decisions.

Additional Concepts: Frame Allocation in Virtual Memory

Equal Frame Allocation Algorithms

Equal frame allocation divides the total number of frames equally among all processes. This is simple but may not be efficient for processes with different memory needs.

Proportionate Frame Allocation Algorithms

Proportionate frame allocation assigns frames based on the size of each process. Larger processes get more frames, while smaller ones get fewer. This method aims to use memory more efficiently.

Priority Frame Allocation Algorithms

Priority frame allocation assigns frames based on the priority of processes. Higher-priority processes receive more frames, ensuring they run more efficiently. Lower-priority processes get fewer frames, possibly leading to more page faults.

Comparison of Various Page Replacement Algorithms

Summary of Key Features

• FIFO: Replaces the oldest page in memory.
• Optimal: Replace the page not used for the longest time in the future.
• LRU: Replaces the page that has not been used for the longest time.
• MRU: Replaces the most recently used page.
• LIFO: Replaces the most recently loaded page.
• Random: Replaces a random page.

Performance Comparison in Different Scenarios

Each algorithm performs differently depending on the workload. For example:

• FIFO may lead to Belady’s anomaly.
• Optimal offers the best performance but is impractical.
• LRU and MRU provide good performance but require tracking usage.
• LIFO and Random are simple but often inefficient.

Practical Considerations for Implementation

When choosing page replacement algorithms in OS, consider the system’s workload, memory size, and required performance. Algorithms like LRU and Optimal are better for critical applications, while FIFO and Random might suffice for less demanding tasks.

Also Read- Major Types of Operating Systems with their Functions

Conclusion

Page replacement algorithms in OS are vital for effective memory management in operating systems. We explored several algorithms, including FIFO, Optimal, LRU, MRU, LIFO, and Random. Each algorithm has unique strengths and weaknesses. FIFO is simple but can suffer from Belady’s anomaly. Optimal offers the fewest page faults but is impractical due to its need for future knowledge.

LRU and MRU perform well but require tracking of page usage. LIFO and Random are easy to implement but can lead to inefficient memory use. By understanding these algorithms, we can make informed decisions to optimise memory performance and reduce page faults in various computing environments. This knowledge is essential for developers and system administrators aiming to enhance system efficiency and reliability.