Transportation Model
Least Cost Method (LCM)
Vogel’s Approximation Method (VAM)
Page Replacement Algorithms in Operating Systems
In an 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. in this article, we will discuss different types of page
replacement algorithms.
Page Replacement Algorithms
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.
If no page frame is free, the virtual memory manager performs a page
replacement operation to replace one of the pages existing in memory with the page
whose reference caused the page fault. It is performed as follows: The virtual memory
manager uses a page replacement algorithm to select one of the pages currently in
memory for replacement, accesses the page table entry of the selected page to mark it
as “not present” in memory, and initiates a page-out operation for it if the modified bit of
its page table entry indicates that it is a dirty page.
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 using FIFO Page Replacement Algorithm.
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.
Prerequisite : Page Replacement Algorithms In operating systems that use paging for
memory management, page replacement algorithm are needed to decide which page
needed to be replaced when new page comes in. Whenever a new page is referred and
not present in memory, page fault occurs and Operating System replaces one of the
existing pages with newly needed page. Different page replacement algorithms suggest
different ways to decide which page to replace. The target for all algorithms is to reduce
number of page faults.
First In First Out (FIFO) page replacement algorithm –
This is the simplest page replacement algorithm. In this algorithm, operating system
keeps track of all pages in the memory in a queue, 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 and 3 page slots. 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. —>1Page Fault.
Finally 6 comes, it is also not available in memory so it replaces the oldest page slot i.e 3
—>6 Page Fault.
So total page faults = 5.
Example -2. Consider the following reference string: 0, 2, 1, 6, 4, 0, 1, 0, 3, 1, 2, 1.
Using FIFO page replacement algorithm –
So, total number of page faults = 9. Given memory capacity (as number of pages it can
hold) and a string representing pages to be referred, write a function to find number of
page faults.
Implementation – Let capacity be the number of pages that memory can hold. Let set
be the current set of pages in memory.
Note – We can also find the number of
page hits. Just have to maintain a
separate count. If the current page is
already in the memory then that must be
count as Page-hit.
Time Complexity: O(n), where n is the
number of pages.
Space Complexity: O(capacity)
Belady’s anomaly:
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 string 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.
Least Recently Used
In this algorithm, page will be replaced which is least recently used.
Example Consider the page reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3 with 4-
page frames. Find number of page faults using LRU Page Replacement Algorithm.
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.
Prerequisite: Page Replacement Algorithms
In operating systems that use paging for memory management, page replacement
algorithm are needed to decide which page needed to be replaced when new page
comes in. Whenever a new page is referred and not present in memory, page fault
occurs and Operating System replaces one of the existing pages with newly needed
page. Different page replacement algorithms suggest different ways to decide which
page to replace. The target for all algorithms is to reduce number of page faults.
In Least Recently Used (LRU) algorithm is a Greedy algorithm where the page to be
replaced is least recently used. The idea is based on locality of reference, the least
recently used page is not likely
Let say the page reference string 7 0 1 2 0 3 0 4 2 3 0 3 2 . Initially we have 4 page slots
empty.
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.
Given memory capacity (as
number of pages it can hold) and
a string representing pages to be
referred, write a function to find
number of page faults.
Complexity Analysis :
Time Complexity : average time complexity of set and map operations is O(1)
and the worst-case time complexity is O(n) but O(n) is the dominant term.
Space Complexity : O(capacity) which is a constant and depends on the size of
the input array and the size of the memory buffer.
Another approach: (Without using HashMap)
Following are the steps to solve this problem :
1. Using a deque data structure, the program implements the page replacement
algorithm.
2. A predetermined number of pages are kept in memory by the algorithm, and they
are replaced as new pages are requested.
3. Using an integer array to stimulate page requests, the code keeps track the
number of page faults that occur throughout the simulation.
4. The deque data structure, which is built using STL in C++, is used to maintain the
pages in memory.
5. The total number of page faults that occurred throughout the simulation is given as
output by the code.
Complexity Analysis :
Time Complexity : O(n), as it performs a constant amount of work for each page
request.
Space Complexity : O(n+4), where n is the size of the input array and 4 is the
size of the memory buffer.
Note : We can also find the number of page hits. Just have to maintain a separate count.
If the current page is already in the memory then that must be count as Page-hit.
We will discuss other Page-replacement Algorithms in further sets.