Table of

1. Introduction............................................................................1
1.1 Backgroung

1.2 Objective of the Study

2. History of Page Replacement.................................................2

2.1 Evolution of Memory Management
2.2 Emergence of Virtual Memory
2.3 Introduction of Page Replacement Algrithms

3. Page Replacement : Concepts and Definations......................4

3.1 Page Fault
3.2 Page Frame
3.3 Need for Page Replacement

4. FIFO (First-In-First-Out) Algorithm..........................................5

4.1 Description
4.2 Example
4.3 Belady's Anomaly
4.4 Example of Belady’s Anomaly
4.5 Advantages
4.6 Disadvantages

5. LRU (Least-Recently-Used) Algorithm....................................9

5.1 Description
5.2 Example
5.3 Advantages
5.4 Disadvantages

6. MRU (Most-Recently-Used) Algorithm..................................11

6.1 Description
6.2 Example
6.3 Advantages
6.4 Disadvantages
7. Optimal Page Replacement Algorithm.................................13
5.1 Description
5.2 Example
5.3 Advantages
5.4 Disadvantages

8. Comparison of Algorithms....................................................15

9. Conclusion............................................................................16

10. References......................................................................... 16

11. The Website / Simulation of Page Replacement Algorithms17

11.1 User Interface
11.2 Belady's Anomaly
11.3 Incorrect Input Check
11.4 Description of Algorithms
1. Introduction
1.1 Background

Modern operating systems manage memory to ensure that multiple processes can execute
efficiently and simultaneously. One of the key components of memory management is virtual
memory, which creates an abstraction of main memory by using both RAM and disk storage.
Virtual memory is divided into blocks known as pages, and only the necessary pages are loaded into
RAM as needed. When a required page is not in memory, a page fault occurs, and the operating
system must load the page from the disk. If memory is already full, this results in a page
replacement.

 Virtual memory improves multitasking.

 It separates logical and physical memory.
 Page replacement is necessary when memory is full.
 Efficiency depends on the chosen replacement strategy.

1.2 Objective of the Study

This report aims to provide a comprehensive analysis of page replacement algorithms used in
operating systems. We will delve into how these algorithms function, compare their performance,
and highlight their advantages and disadvantages.

 Study core page replacement algorithms.

 Understand their mechanisms and logic.
 Analyze performance and efficiency.
 Evaluate practicality and suitability.

1
2. History of Page Replacement
2.1 Evolution of Memory Management

Memory management has undergone a tremendous transformation since the earliest days of
computing. Initially, operating systems used simple memory allocation schemes such as fixed
partitioning, where memory was divided into static partitions and assigned to processes. This
approach was rigid and inefficient, especially as programs grew larger and more complex.

The need to support multiprogramming and multitasking environments led to the introduction of
dynamic memory allocation techniques, including paging and segmentation. These methods
allowed programs to be broken into pages or segments and loaded into memory as needed, rather
than all at once.

 Fixed and variable partitions were early memory management schemes.

 Paging and segmentation offered flexibility and better memory utilization.
 Swapping techniques helped accommodate more programs in limited memory.
 Internal and external fragmentation issues prompted innovation in memory design.

2.2 Emergence of Virtual Memory

The concept of virtual memory was first introduced in the 1960s as part of the Multics project. It
marked a revolutionary shift in how operating systems managed memory by decoupling logical
memory from physical memory. Virtual memory allows systems to run larger programs than the
available RAM by using disk space as an extension of main memory.

 Multics (Multiplexed Information and Computing Service) was among the first systems
to implement virtual memory.
 Virtual memory enabled programs to exceed physical memory limits.
 It provided memory isolation, improving system stability and security.
 Memory paging became central to virtual memory, dividing memory into equal-sized
blocks.

This advancement paved the way for more efficient multitasking, as the operating system could
swap pages in and out of physical memory, keeping only the necessary parts of each program in
RAM. The use of page tables, TLB

2.3 Introduction of Page Replacement Algorithms

As virtual memory became more prevalent, the issue of page faults became critical. When all
memory frames are occupied, and a new page is needed, the system must decide which page to
remove—this is where page replacement algorithms come into play. The first algorithms were
2
designed with simplicity in mind, such as FIFO (First-In-First-Out), which replaced the oldest
loaded page regardless of usage.

However, as workloads became more complex, new algorithms were introduced to improve
performance. LRU (Least Recently Used) and MRU (Most Recently Used) attempted to consider
usage history. Meanwhile, the Optimal algorithm, although theoretical, was introduced as a
benchmark to evaluate others.

 Page replacement algorithms emerged to handle memory overflow.

 Early algorithms prioritized simplicity over efficiency.
 Real-world usage led to more intelligent strategies based on recency and frequency.
 Research and simulation tools helped evaluate and refine these algorithms.
 Modern systems may use hybrid techniques, combining multiple strategies to optimize
performance.

The evolution of these algorithms reflects the broader development of operating systems—balancing
efficiency, accuracy, and resource management. Today, advanced OS like Linux, Windows, and
macOS use adaptive and dynamic page replacement techniques, often supported by hardware-level
assistance.

3
3. Page Replacement : Concepts and Definations
Page Replacement Algorithms are techniques used by operating systems to decide which memory
pages to swap out when a page fault occurs and the memory is already full. These algorithms aim to
minimize the number of page faults and improve memory efficiency.

3.1 Page Fault

A page fault occurs when a process accesses a page not present in main memory. The operating
system halts the process, fetches the required page from disk, and resumes execution.

 Slows down performance temporarily.

 Can be handled by OS interrupt service.
 Frequent faults indicate inefficient page management.

3.2 Page Frame

Page frames are blocks of physical memory where pages are loaded. The number of frames
determines how many pages a process can hold in memory at once.

 Physical memory is divided into frames.

 Page and frame sizes are equal.
 Frames are allocated to processes dynamically.

3.3 Need for Page Replacement

When no free frames are available during a page fault, the system must replace a page. A page
replacement algorithm determines which page to evict.

 Occurs during full memory.

 Selection affects system efficiency.
 Choice of algorithm influences performance.

4
4. FIFO (First-In-First-Out) Algorithm

4.1 Description

FIFO is one of the simplest and earliest page replacement algorithms. It operates using a queue
structure to maintain the order of pages that entered the memory. When a page must be replaced due
to a page fault and no empty frame is available, the page that has been in memory the longest (i.e., at
the front of the queue) is removed regardless of its usage frequency or recency.

This method is simple to implement and has low overhead but may result in inefficient performance
due to its ignorance of actual access patterns. It often removes pages that are still in frequent use,
which can lead to an increased number of page faults—a phenomenon known as Belady's anomaly.

 Maintains insertion order.

 Replaces the oldest loaded page.
 Does not consider how recently or frequently a page was accessed.

4.2 Example

Reference String: 7, 0, 1, 2, 0, 3, 0, 4 (3 frames)

1. Insert 7 → Page fault

2. Insert 0 → Page fault

3. Insert 1 → Page fault

4. Insert 2 → Replace 7 → Page fault

5. 0 already present → No page fault

6. Insert 3 → Replace 0 → Page fault

7. Insert 0 → Replace 1 → Page fault

8. Insert 4 → Replace 2 → Page fault

 Total Page Faults: 6

 Simple, but inefficient in some scenarios.

5
4.3 Belady’s Anomaly

Belady’s Anomaly refers to a counterintuitive situation in which increasing the number of page
frames results in an increase in the number of page faults. This anomaly is most commonly
observed in FIFO. The anomaly occurs because FIFO uses a fixed ordering of arrival and does not
account for access patterns, often leading to the premature removal of frequently used pages.

 Occurs mainly in FIFO.

 Adding memory can lead to more page faults.
 Shows limitations of simple replacement policies.

4.5 Example of Belady’s Anomaly

Reference String: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 (3 frames)

1. Insert 1 → Page fault

2. Insert 2 → Page fault

3. Insert 3 → Page fault

4. Insert 4 → Replace 1 → Page fault

5. Insert 1 → Replace 2 → Page fault

6. Insert 2 → Replace 3 → Page fault

7. Insert 5 → Replace 4 → Page fault

8. 1 already present → No Page fault

9. 2 already present → No Page fault

10. Insert 3 → Replace 1 → Page fault

11. Insert 4 → Replace 2 → Page fault

12. 5 already present → No Page fault

 Total Page Faults: 9

6
Now, increase the number of frames to 4 and repeat the process:

Reference String: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 (4 frames)

1. Insert 1 → Page fault

2. Insert 2 → Page fault

3. Insert 3 → Page fault

4. Insert 4 → Page fault

5. 1 already present → No Page fault

6. 2 already present → No Page fault

7. Insert 5 → Replace 1 → Page fault

8. Insert 1 → Replace 2 → Page fault

9. Insert 2 → Replace 3 → Page fault

10. Insert 3 → Replace 4 → Page fault

11. Insert 4 → Replace 5 → Page fault

12. Insert 5 → Replace 1 → Page fault

Total Page Faults with 4 Frames: 10

This example demonstrates how adding frames lead to more faults in FIFO. But this anomaly only
occurs in some cases only.

4.4 Advantages

 Easy to implement.
 No overhead of tracking access.
 Predictable behavior.
 Good for simple embedded systems.
 Minimal computational cost.

4.5 Disadvantages

 May replace frequently used pages.

 Suffers from Belady’s anomaly.

7
 Ignores page usage patterns.
 Poor for workloads with high locality.
 Suboptimal for modern multitasking systems.

8
5. LRU (Least-Recently-Used) Algorithm

5.1 Description

LRU is a smarter replacement policy compared to FIFO. It keeps track of the usage history of pages
and always removes the page that has not been accessed for the longest time. This method is based
on the principle of temporal locality, which states that recently accessed pages are more likely to be
accessed again in the near future.

Implementing LRU requires maintaining access timestamps or a stack to determine the order of
recent accesses. Though it generally results in fewer page faults than FIFO, it also introduces
complexity in terms of bookkeeping and processing time, especially in systems without hardware
support.

 Uses historical access data.

 Removes the least recently accessed page.
 Respects locality of reference.

5.2 Example

Reference String: 7, 0, 1, 2, 0, 3, 0, 4 (3 frames)

1. Insert 7 → Page fault

2. Insert 0 → Page fault

3. Insert 1 → Page fault

4. Insert 2 → Replace 7 (least recently used) → Page fault

5. 0 present → No page fault

6. Insert 3 → Replace 1 → Page fault

7. 0 present → No page fault

8. Insert 4 → Replace 2 → Page fault

 Total Page Faults: 6

 Requires tracking recent access order.

9
5.3 Advantages

 Better performance than FIFO.

 Avoids replacing frequently accessed pages.
 Supports temporal locality.
 Commonly used in real systems.
 Less susceptible to anomalies.

5.4 Disadvantages

 Complex to implement.
 Needs tracking structures (stack/timestamp).
 Higher overhead.
 Can be inaccurate under bursty access.
 Requires more memory for tracking.

6. MRU (Most-Recently-Used) Algorithm

10
6.1 Description

MRU is essentially the opposite of LRU. It removes the page that was most recently accessed,
assuming that if a page was used very recently, it is less likely to be used again soon. This behavior
fits specific access patterns such as stack-like operations or certain database workloads, where data
is loaded and discarded in bursts.

Though it can outperform LRU in certain scenarios, MRU often performs poorly in typical
applications where the same data is frequently reused. It is rarely used in general-purpose operating
systems but can be found in specialized environments.

 Removes the most recently accessed page.

 Assumes recent access implies short-term use.
 Best suited for bursty, stack-like data access.

6.2 Example

Reference String: 7, 0, 1, 2, 0, 3, 0, 4 (3 frames)

1. Insert 7 → Page fault

2. Insert 0 → Page fault

3. Insert 1 → Page fault

4. Insert 2 → Replace 1 (most recent) → Page fault

5. 0 present → No page fault

6. Insert 3 → Replace 0 → Page fault

7. Insert 0 → Replace 3 → Page fault

8. Insert 4 → Replace 0 → Page fault

 Total Page Faults: 7

 Depends on access burst patterns.

6.3 Advantages

 Works well in some DBMS scenarios.

11
  Can outperform LRU in specific patterns.
 Simple to manage.
 Less tracking than LRU.
 Low memory overhead.

6.4 Disadvantages

 Poor performance in general use.

 Removes pages that might be needed soon.
 Not suitable for temporal locality.
 Inconsistent results across workloads.
 Rarely used in OS-level memory management.

7. Optimal Page Replacement Algorithm

7.1 Description

12
The Optimal algorithm offers the best possible performance in terms of minimizing page faults. It
works by replacing the page that will not be used for the longest time in the future. This requires
knowledge of the future page reference string, making it impractical for real-time systems.

The Optimal algorithm is used primarily for benchmarking and comparing the efficiency of other,
practical algorithms. It helps identify how close a given strategy is to the theoretical best-case
scenario.

 Replaces the page used farthest in the future.

 Cannot be implemented without future knowledge.
 Used for evaluating algorithm effectiveness.

7.2 Example

Reference String: 7, 0, 1, 2, 0, 3, 0, 4 (3 frames)

1. Insert 7 → Page fault

2. Insert 0 → Page fault

3. Insert 1 → Page fault

4. Insert 2 → Replace 7 (not used again) → Page fault

5. 0 present → No page fault

6. Insert 3 → Replace 1 → Page fault

7. 0 present → No page fault

8. Insert 4 → Replace 2 → Page fault

 Total Page Faults: 6

 Produces best possible result.

7.3 Advantages

 Produces minimum page faults.

13
  Ideal for performance evaluation.
 Helps compare real-world algorithms.
 Useful in simulations.
 Provides optimal fault rate.

7.4 Disadvantages

 Not implementable in practice.

 Requires future access prediction.
 Only used for theoretical comparison.
 Computationally demanding in analysis.
 Cannot adapt dynamically.

14
8. Comparison of Algorithms

Criteria FIFO LRU MRU Optimal

First-In-First- Least Recently Most Recently Optimal Page
Full Form
Out Used Used Replacement

Removes the Removes the Removes the

Working Removes the
least recently most recently page used
Principle oldest page
used page used page farthest ahead

Reference
Data
Stack/Map with sequence
Structure Queue Stack/List
timestamps (future
Used
knowledge)

Implementati Moderate Impractical in

Very simple Simple
on complexity real-time

Page Fault Moderate to Minimum

High Variable
Rate low possible
Yes (Belady's
Anomaly No No No
Anomaly)
Better due to
Poor in modern Depends on
Performance temporal Ideal
scenarios workload
locality
Memory High (tracking
Low Low High
Overhead needed)
Widely used in
Niche (DBMS, Only
Practical Use Limited real-world
stack-based) theoretical
systems
Systems with
Simple Burst-access Benchmarking
Best For frequent reuse
systems patterns algorithms
of data

15
9. Conclusion
In modern computing systems, efficient memory management is critical to performance and user
experience. At the heart of this management lies the decision of which memory pages to keep and
which to replace—a responsibility handled by page replacement algorithms.

This report explored and analyzed four major algorithms:

 FIFO, the simplest to implement, which unfortunately can perform poorly and suffers from
Belady's anomaly.
 LRU, which improves performance by using access history, though it requires additional
memory and tracking.
 MRU, effective in special cases like databases but not ideal for most workloads.
 Optimal, which offers a theoretical best-case scenario but is impossible to use in practice.

Each algorithm has distinct strengths and weaknesses. The right choice depends on the system’s
workload, application type, and memory constraints. In practice, operating systems may implement
approximate or hybrid models that balance complexity and performance—often inspired by LRU
or FIFO.

Future advancements in artificial intelligence and hardware-assisted memory tracking might give
rise to adaptive, self-learning page replacement mechanisms that dynamically choose the best
strategy.

Thus, while the underlying concepts remain rooted in the past, page replacement algorithms
continue to evolve, remaining a vital area of research and optimization in modern operating system
design.

Page replacement plays a vital role in memory management by determining which pages to evict
during a page fault. This report has analyzed four major algorithms, each with its strengths and
weaknesses. FIFO is simple but inefficient, LRU balances performance with complexity, MRU is
useful in specific cases, and the Optimal algorithm, while theoretical, sets a performance
benchmark.

10. References
 Silberschatz, A., Galvin, P. B., & Gagne, G. (Operating System Concepts)
 William Stallings, Operating Systems: Internals and Design Principles
 Andrew S. Tanenbaum, Modern Operating Systems
 Research papers on memory management and paging algorithm

16
11. The Website / Simulation of Page Replacement
Algorithms

11.1 User Interface

17
11.2 Belady’s Anomaly

1. 3 Frames

18
19
2. 4 Frames

20
11.3 Incorrect Input Check

21
11.4 Description of Algorithms
1. FIFO (First-In-First-Out)

2. LRU (Least-Recently-Used)

22
3. Optimal Page Replacement

4. MRU (Most-Recently-Used)

23