Present by:
Muhammad Talha (23-UON-0446)
Nahah Butt (23-UON-0338)
page 01
1
In Virtual memory operating system that uses
paging for memory management, a page
replacement algorithm is needed to decide which
page needs to be replaced when a new page
comes in. Page replacement becomes necessary
when a page fault occurs and no free page frames
are in memory.
2
Page replacement algorithms are techniques
used in operating systems to manage memory
efficiently when the physical memory is full.
When a new page needs to be loaded into
physical memory, and there is no free space,
these algorithms determine which existing
page to replace.
3
Page replacement algorithms are essential in virtual
memory systems to manage limited physical
memory efficiently.
Physical (main) memory has a limited number of
frames.
When all frames are full and a new page is needed
(due to a page fault), the system must free up a
frame by removing an existing page.
A page replacement algorithm determines which
page to replace.
4
In page replacement, frame locking is a restriction where
certain frames in main memory are not allowed to be
replaced. These locked frames contain critical
components like:
OS kernel
Control structures
I/O buffers
Time-sensitive data
Locking is managed using a lock bit associated with each
frame, stored in the frame table and possibly the page
table. This ensures that essential pages stay in memory
and are protected from being swapped out during page
replacement.
5
Regardless of the resident set management strategy there
are certain basic algorithms that are used for the selection
of a page to replace.
Optimal Page Replacement (OPT)
Least recently used (LRU)
First-in-first-out (FIFO)
6
Optimal Page replacement algorithm
(OPT)
Replaces the page not needed for the longest time in the
future.
Gives the fewest page faults, but is impractical since future
references are unknown.
Used as a theoretical bench mark so that other replacement
algorithms can be analyzed against it.
7
The steps for optimal Page replacement
algorithm are as follows :
8
Example
Input: Number of frames = 3, Reference String = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3}
Page-by-page analysis:
7, 0, 1, 2: First four pages fill the frames → Misses = 4
0: Already in the frame → Hit
3: Replaces 7 (not used for the longest) → Miss
0: Already in the frame → Hit
4: Replaces 1 → Miss
2, 3: All already in frames → Hits = 2
optimal2n
Final Tally:
Hits = 4
Misses = 6
9
Least Recently Used Algorithm (LRU)
Replaces the page that hasn’t been used for the longest time.
Based on the principle of locality, performs close to optimal.
Difficult to implement due to high overhead (needs timestamping or stack).
10
Steps for LRU page replacement algorithm are as
follows :
11
Example
Consider the page reference string {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3, with 4-page
frames.
Analysis :
Initially, all slots are empty, so when 7 0 1 2 are allocated to the empty slots ---> 4
Page faults
0 is already there so ---> 0 Page fault.when 3 came it will take the place of 7 because
it is least recently used ---> 1 Page fault
0 is already in memory so ---> 0 Page fault.
4 will takes place of 1 ---> 1 Page Fault
Now for the further page reference string ---> 0 Page fault because they are already
available in the memory.
12
FIFO Algorithm
FIFO is one of the simplest and most basic page
replacement algorithms. It replaces the oldest page in
memory — the one that has been there the longest.
Pages are stored in a queue in the order they are loaded
into memory.
When a new page needs to be loaded and memory is full,
the page at the front of the queue (oldest) is removed and
the new page is added to the rear.
13
Steps for FIFO page replacement algorithm are as
follows :
14
Example
Consider page reference string {1, 3, 0, 3, 5, 6, 3} with 3-page frames.
Analysis :
Initially, all slots are empty, so when 1, 3, 0 came they are allocated to the
empty slots ---> 3 Page Faults.
when 3 comes, it is already in memory so ---> 0 Page Faults. Then 5 comes,
it is not available in memory, so it replaces the oldest page slot i.e
1. ---> 1 Page Fault. 6 comes, it is also not available in memory, so it replaces
the oldest page slot i.e 3 ---> 1 Page Fault. Finally, when 3 come it is not
available, so it replaces 0 1-page fault.
15
Comparison of Algorithms
Optimality: OPT > LRU > FIFO
Complexity: FIFO< LRU < OPT
Performance: OPT > LRU > FIFO
16
Real-World Usage
Page replacement algorithms are used in:
Operating Systems (Windows, Linux, macOS)
Database Management Systems (buffer pools)
Web Servers (caching)
Embedded Systems (smartphones, IoT devices)
Virtualization (virtual machines)
These algorithms optimize memory usage, reduce
page faults, and improve performance.
17
Conclusion
The page replacement algorithm efficiently manages memory by
identifying and replacing pages that are least likely to be needed soon,
minimizing page faults and optimizing system performance. Its three-
sweep approach ensures a balanced trade-off between page replacement
and performance.
First sweep: Finds an unmodified page that hasn't been accessed recently.
Second sweep: Finds a modified page that hasn't been accessed recently.
Third sweep: Marks all frames as not accessed recently and replaces a
page.
18
Thank You!
19
