Assignment # 03
Muskaan Batool BS-CS-R-002
Group Member: 02
Muzzlfa Saif BS-CS-R-042
Subject: Operating System
Instructor: Ms. Quratulain
Topic: Page replacement & Page Demand
3/25/2024
Govt. College Women University Sialkot
Paging
Paging in Operating Systems (OS):
Paging is a storage mechanism. Paging is used to retrieve processes from secondary
memory to primary memory. The main memory is divided into small blocks called pages. Now,
each of the pages contains the process which is retrieved into main memory and it is stored in
one frame of memory.
Page Replacement Algorithms:
There are three types of Page Replacement Algorithms. They are:
Optimal Page Replacement Algorithm
First In First Out Page Replacement Algorithm
Least Recently Used (LRU) Page Replacement Algorithm
First in First out Page Replacement Algorithm:
This is the first basic algorithm of Page Replacement Algorithms. This algorithm is
basically dependent on the number of frames used. Then each frame takes up the certain page
and tries to access it. When the frames are filled then the actual problem starts. The fixed
number of frames is filled up with the help of first frames present. This concept is fulfilled with
the help of Demand Paging. After filling up of the frames, the next page in the waiting queue
tries to enter the frame. If the frame is present then, no problem is occurred. Because of the
page which is to be searched is already present in the allocated frames. If the page to be
searched is found among the frames then, this process is known as Page Hit. If the page to be
searched is not found among the frames then, this process is known as Page Fault. When Page
Fault occurs this problem arises, then the First In First Out Page Replacement Algorithm comes
into picture. The First In First Out (FIFO) Page Replacement Algorithm removes the Page in the
frame which is allotted long back. This means the useless page which is in the frame for a
longer time is removed and the new page which is in the ready queue and is ready to occupy the
frame is allowed by the First In First Out Page Replacement. Let us understand this First In
First Out Page Replacement Algorithm working with the help of an example.
Example: Consider the reference string 6, 1, 1, 2, 0, 3, 4, 6, 0, 2, 1, 2, 1, 2, 0, 3, 2, 1, 2, 0 for a
memory with three frames and calculate number of page faults by using FIFO (First In First
Out) Page replacement algorithms.
Points to Remember
Page Not Found - - - > Page Fault
Page Found - - - > Page Hit
Reference String:
Number of Page Hits = 8
Number of Page Faults = 12
The Ratio of Page Hit to the Page Fault = 8 : 12 - - - > 2 : 3 - - - > 0.66
The Page Hit Percentage = 8 *100 / 20 = 40%
The Page Fault Percentage = 100 - Page Hit Percentage = 100 - 40 = 60%
Explanation:
First, fill the frames with the initial pages. Then, after the frames are filled we need to
create a space in the frames for the new page to occupy. So, with the help of First in First Out
Page Replacement Algorithm we remove the frame which contains the page is older among the
pages. By removing the older page we give access for the new frame to occupy the empty space
created by the First in First out Page Replacement Algorithm.
OPTIMAL Page Replacement Algorithm: This is the second basic algorithm of
Page Replacement Algorithms. This algorithm is basically dependent on the number of
frames used. Then each frame takes up the certain page and tries to access it. When the
frames are filled then the actual problem starts. The fixed number of frames is filled up with
the help of first frames present. This concept is fulfilled with the help of Demand Paging.
After filling up of the frames, the next page in the waiting queue tries to enter the frame. If
the frame is present then, no problem is occurred. Because of the page which is to be
searched is already present in the allocated frames. If the page to be searched is found
among the frames then, this process is known as Page Hit. If the page to be searched is not
found among the frames then, this process is known as Page Fault. When Page Fault occurs
this problem arises, then the OPTIMAL Page Replacement Algorithm comes into picture.
The OPTIMAL Page Replacement Algorithms works on a certain principle. The principle is:
Replace the Page which is not used in the Longest Dimension of time in future This
principle means that after all the frames are filled then, see the future pages which are to
occupy the frames. Go on checking for the pages which are already available in the frames.
Choose the page which is at last.
Example:
Consider the reference string 6, 1, 1, 2, 0, 3, 4, 6, 0, 2, 1, 2, 1, 2, 0, 3, 2, 1, 4, 0 for a
memory with three frames and calculate number of page faults by using OPTIMAL Page
replacement algorithms.
Points to Remember
Page Not Found - - - > Page Fault
Page Found - - - > Page Hit
Reference String:
Number of Page Hits = 8
Number of Page Faults = 12
The Ratio of Page Hit to the Page Fault = 8 : 12 - - - > 2 : 3 - - - > 0.66
The Page Hit Percentage = 8 *100 / 20 = 40%
The Page Fault Percentage = 100 - Page Hit Percentage = 100 - 40 = 60%
Explanation:
First, fill the frames with the initial pages. Then, after the frames are filled we need to
create a space in the frames for the new page to occupy. Here, we would fill the empty spaces
with the pages we and the empty frames we have. The problem occurs when there is no space
for occupying of pages. We have already known that we would replace the Page which is not
used in the Longest Dimension of time in future.
Least Recently Used (LRU) Replacement Algorithm:
This is the last basic algorithm of Page Replacement Algorithms. This algorithm is
basically dependent on the number of frames used. Then each frame takes up the certain page
and tries to access it. When the frames are filled then the actual problem starts. The fixed
number of frames is filled up with the help of first frames present. This concept is fulfilled with
the help of Demand Paging. After filling up of the frames, the next page in the waiting queue
tries to enter the frame. If the frame is present then, no problem is occurred. Because of the
page which is to be searched is already present in the allocated frames. If the page to be
searched is found among the frames then, this process is known as Page Hit. If the page to be
searched is not found among the frames then, this process is known as Page Fault. When Page
Fault occurs this problem arises, then the Least Recently Used (LRU) Page Replacement
Algorithm comes into picture. The Least Recently Used (LRU) Page Replacement Algorithms
works on a certain principle. The principle is: Replace the page with the page which is less
dimension of time recently used page in the past.
Example:
Consider the reference string 6, 1, 1, 2, 0, 3, 4, 6, 0, 2, 1, 2, 1, 2, 0, 3, 2, 1, 2, 0 for a
memory with three frames and calculate number of page faults by using Least Recently Used
(LRU) Page replacement algorithms.
Points to Remember
Page Not Found - - - > Page Fault
Page Found - - - > Page Hit
Reference String:
Number of Page Hits = 7
Number of Page Faults = 13
The Ratio of Page Hit to the Page Fault = 7 : 12 - - - > 0.5833 : 1
The Page Hit Percentage = 7 * 100 / 20 = 35%
The Page Fault Percentage = 100 - Page Hit Percentage = 100 - 35 = 65%
Explanation:
First, fill the frames with the initial pages. Then, after the frames are filled we need to
create a space in the frames for the new page to [Link], we would fill the empty spaces
with the pages we and the empty frames we have. The problem occurs when there is no space
for occupying of pages. We have already known that we would replace the Page which is not
used in the Longest Dimension of time in past or can be said as the Page which is very far away
in the past.
Demand Paging:
According to the concept of Virtual Memory, in order to execute some process, only a
part of the process needs to be present in the main memory which means that only a few pages
will only be present in the main memory at any time.
However, deciding, which pages need to be kept in the main memory and which need to
be kept in the secondary memory, is going to be difficult because we cannot say in advance that
a process will require a particular page at particular time.
Therefore, to overcome this problem, there is a concept called Demand Paging is
introduced. It suggests keeping all pages of the frames in the secondary memory until they are
required. In other words, it says that do not load any page in the main memory until it is
[Link] any page is referred for the first time in the main memory, then that page
will be found in the secondary [Link] that, it may or may not be present in the main
memory depending upon the page replacement algorithm.