Page Replacement Algorithms

Page replacement algorithm We have seen in the concept of paging that by dividing the processes in pages we put them in the frames of main memory, what does the concept of virtual memory say? That we never bring the entire process inside the main memory and not all the pages of a process at the same time we try to keep in the main memory no, Here we provide the reason to the programmer through virtual memory that all the processes you have. We can accommodate the maximum number of processes inside the main memory. but actually how it is done If we will keep the entire process in the main memory So it may be that our main memory is completely finite., so my main memory will get filled with one or two processes. So what do we do instead? Virtual memory one or two pages, Each process brings one or two pages into the main memory. which have demand. When their need runs out, we swipe out those pages and then swipe in fresh pages. So this swipe in and swipe out funda we saw in virtual memory. Now which page do we have to bring inside the main memory? And when that page will come inside main memory it is possible that the main memory is already filled, all the frames are already filled in it. So if I want to bring the new page inside the main memory and get it accommodated, So for that one page from the main memory will have to be taken out from there So that I can clear a frame over there So what is my concept here? of page replacement, Means I am bringing a page to the main memory If my main memory is full, then I will remove the old page from there by swiping out and make space on it and place the new page in that place. So how to replace these pages? There are three methods, first is the first in first out, optimal page replacement and least recently used. These three algorithms which are common and most of the time are used to replace the page. If there is a space in the main memory then there is no problem Then you can put the new page on that empty space. But the problem is that the size of the processes are very big, and the number of processes are very high but the size of main memory is limited and it is finite. So in order to bring more and more processes What I have to do? I have to remove old pages and replace them with new pages So how do we replace it? let's start with first of all first in first out, here I have one string this is what? It is called a reference reference string reference string means the CPU is demanding pages Let's say the CPU is executing a process. Executing any process and we have divided that process into different pages Now the CPU has sent a demand that first I want page number 7 then one then 0, then 1, then 2 and again 0, this is the sequence, means this is the reference, it is in sequence it is already in the order, here I have taken this sequence now whenever the CPU is demanding, for what? that is page number 7 then 0, then 1, then 2 and this is how it moves and here I have three frames of the main memory Means in this process, its pages out of these three frames can appear anywhere Now if we see this in real time, then in real time pages of a process we do not give the 5th number of frames Meaning the number of frames can be more or less. But Just for Solving the Example or Numerical So that we can understand these three concepts very well. So I fixed here that for this process, for the pages of this process three frames have been given in the main memory Frame 1, Frame 2, Frame 3 Now let's start with solving how first-in-first-out works? So here's what the CPU has demanded first that is of page No.7 Means the CPU is saying that the byte because the CPU does not even know that we have used any paging concept, then the byte that the CPU has demanded the byte that it is demanding, Where is that byte? on page No. 7, We converted the logical address and found out that it is demanding for page number 7 When I saw page number 7 in the main memory, it is neither in frame one nor in two nor in three, that is, that page is not present anywhere So if that page is nowhere then what do we call? Page fault We have already discussed this whenever the CPU is looking for a page and that page is absent in main memory we call it page fault. So whenever a page fault happens, we service it. Means we bring it from the hard disk and keep it in the main memory. Although it is very time consuming And one of the motives of the page replacement algorithm is to minimize page faults. Because whenever a page fault happens My time is wasted because the hard disk gets involved. and where hard disk is involved, definitely hard disk is very slow so obviously my time will increase and performance will decrease. So for this we would like to minimize the page fault. but that is just numerical so we check how many page faults occur in it. Or how many page hits occur, when page number 7 comes, page number 7 is not here. So that means what happened here fault happened, then we called page number 7 from the hard disk and let's say we put it in frame number 1. Along with this, you should also mention here's what it actually is, a page fault because the page you were looking for was not there now it has arrived, now that page has arrived Now page No. 0 Second of CPU is saying that I have demand for page number zero. But even if you look carefully for zero, it is not there. Zero also have to be brought that is also called a page fault. So here too there is a page fault because zero page is also not present in main memory so I will bring page number 0 from the hard disk and place it in frame 2 of main memory. Now there is no need to replace do not replace this 7 because you already have vacant space. So when the space is empty, fill that space first. Why are you replacing it? The point of replacement will come when the entire space is filled. But still the slot was empty, so I put this 0 here, You can start from the top also, it is our own way of practice I was used to practice this from beginning I used to solve like this I first placed 7 here then 0 in the second now next frame came 1 sorry next is page number 1, Now if you look carefully So page number one is also not there So here again page fault is occurring so I will bring page number one from the hard disk and put it in the main memory. So the three frames here are all filled up and all of these three are page faults. Next frame No. 2 Page No. 2 there is demand for page number 2 whether I have page number 2 first you have to check that. That if page number 2 is there it is a hit, isn't it? The page got hit, but if you look carefully, the CPU is demanding page number 2, but page number two is not here. and here the space also ran out Means we have three frames saved and all are full then what will I do an old page will have to be replaced. So what does FIFO do? First in first out, means the frame which was filled first empty that frame first Means what will I fill here in place of 7, 2 and rest as it is rest as it is, means means we brought 2 in place of 7, and 0 and 1 as it is, So what is this? This is also a page fault. Because the page you were asking for is not present. After that, if you look carefully, Whose demand has come next? page number zero, So is my page number zero present here? You have to check here recently as this is an updated report. You have to check it in the updated Is page number zero there? Yes, my page number zero is present. So if page number zero is present then what is it called? Page hit, Hit means? The thing you were asking for is already present in main memory. So we copy the hit case as it is. Means copy it here as it is if hit occurs I also note here, Let me write, that is called a hit because the page you were demanding was found. Next 3 Check if 3 is there or not? No, 3 is not there, So I'll have to replace it. Which frame was the first to be replaced according to First In First Out? Which frame did we change? In frame one, now which one has to be changed? frame 2, means you have to remove frames one by one. Will send this zero out of the frame. and we'll bring 3 in place of that zero. Means we will replace this zero with 3 keep the rest as it is. And what is this too? Page fault because the number three page was not present We have brought it now. Next 0, Zero, page No. 0 Is page no. 0 there? No it's not there. Now again we have to do replacement with whom we will replace now? with frame No. 3 first of all frame No. 1 then replaced in 2 now in 3, you have to replace line-wise so in frame no. 3 we replaced 1 with 0 we are in this frame on this page No. 3, 2 and what is this? This is miss or page fault. because the page you were having demand for is not there. after that we come on page No. 4 Is page No. 4 present there? No, it is not Page No. 4 is not present, so what will we replace? Frame 1, Why? because first we replaced frame 1, then 2 then 3 now we have come back on frame No. 1 so we will replace 2 with 4 and rest write as it is and this is also page fault, because because page No. 4 was also not present Next is 2, Is 2 present? No, 2 is not present as 2 is not present so we will replace 3 with 2 and rest 2, 0, 4 because after frame 1, replacement will be in frame 2 Next 3, Now we are on this page No. Is page No. 3 there? No, it is not. So again page fault occur here What we will replace? Frame No .3 You just have to replace line-wise After this comes page No. 0, Page No. 0 Is Page No. 0 present? No it is not. So we are again on frame No. 1 We replaced 4 with 0 2, 3 Again what I am having here? Miss then after 0, I am having 3 Page No. 3 Is page No. 3 present? Yes page No. 3 is already there. So the page which CPU is demanding is present in main memory This we call hit. So when there is hit you don't have to do any changes just copy previous one as it is. and write here that it is a hit then, page No. 1 Is page No. 1 present here? No, page No. 1 is not present. So, what will we replace? this one, because we have already replaced frame No.1 now it's turn of frame 2 So in frame 2 we replace 2 with 1 and keep rest as it is. that is again called a miss. or page fault after that Page No. 2 Is page No. 2 present? No Page No. 2 is not present So what do we replace now 3rd frame, replaced 3rd frame put 2 in its place and rest as it is. That is again called a page fault. After that came page No. 0, Is page No. 0 present? Yes page No. 0 is present. So when it is present we call it hit, So you copy it as it is. That is called a hit. So this is how we have to follow. No matter how big this referencing is you will not face any problem because you have to follow a simple method that you have to replace frame wise first you have to replace frame 1 then 2, then 3 then again 1, 2 and 3 again 1, 2, 3 but when? when frames are already full means all slots are filled and the page which CPU is making demand is not there. means there is page fault. So now you can check here how much hit I am having? and how many page fault or miss are there. We can call this page fault or page miss. and this is page hit. So how many page hit came 1, 2, 3 That is called page hit. and how many page fault came? 1, 2, 3, 4, 5, 6, 7 8, 9, 10, 11, 12 So 12 No. of page faults. and how many hits 3 Many times you can be asked What is the... all this question is given at last it is asked what is the hit ratio? or what is the miss ratio? So if you want to find hit ratio or miss ratio first of all find number of hits and number of miss now I know if I have to find hit ratio How will you find hit ratio? number of hits divided by total number of references so the number of hits I am having is 3 number of hits are 3, and the number of references 1, 2, 3 15 So 3 divided by 15 multiplied by 100 and what is the miss ratio or page fault ratio? 12 divide by 15 multiplied by 100 So this is the way how we can solve. Solve it further So 20% is the hit ratio and if you solve this definitely it will come 80 % If hit ratio is 20 % so what would be 100 - 20% that would be miss 80% This is how we can solve the question of FIFO first in first out, in which you have to go frame wise just frame wise don't worry about how reference came just go on replacing frames one by one in sequence So this is all about first in first out Thank You.

Page replacement algorithm We have seen in the concept of paging 
that by dividing the processes in pages we put them in the frames of main memory, what does the concept of
virtual memory say? That we never bring the entire
 process inside the main memory  and not all the pages of a process at the same time we try to keep in the
 main memory no, Here we provide the reason to the
programmer through virtual memory that all the processes you have. We can accommodate the maximum number of
 processes inside the main memory. but actually how it is done If we will keep the entire process
in the main memory So it may be that our main memory is
 completely finite., so my main memory will get filled with
one or two processes. So what do we do instead?  Virtual memory one or two pages,  Each process brings
one or two pages into the main memory. which have demand. When their need runs out,
we swipe out those pages and then swipe in fresh pages. So this swipe in and swipe out funda
 we saw in virtual memory. Now which page do we have to bring
 inside the main memory? And when that page will come
 inside main memory it is possible that the main
 memory is already filled, all the frames are already filled in it. So if I want to bring the new page
 inside the main memory and get it accommodated, So for that one page from the main memory will have to be taken out from there So that I can clear a frame over there So what is my concept here? of page replacement,
Means I am bringing a page to the main memory If my main memory is full, then I will remove the old page from there
by swiping out and make space on it and place the new
 page in that place. So how to replace these pages? There are three methods, first is the first in first out, optimal page replacement and least recently used. These three algorithms which are common
and most of the time are used to replace the page. If there is a space in the main memory then there is no problem Then you can put the new page
on that empty space. But the problem is that the size of
the processes are very big, and the number of processes are very high but the size of main memory is limited
and it is finite. So in order to bring more
 and more processes What I have to do? I have to remove old pages and replace them with new pages So how do we replace it? let&#39;s start with first of all
 first in first out, here I have one string this is what? It is called a reference reference string reference string means the CPU is demanding pages Let&#39;s say the CPU is executing a process. Executing any process and we have divided that process
into different pages Now the CPU has sent a demand that first I want page number 7 then one then 0, then 1, then 2
 and again 0, this is the sequence,
 means this is the reference, it is
in sequence it is already in the order, here I have
taken this sequence now whenever the CPU is
demanding, for what? that is page number 7 then 0, then 1, then 2 and this is how it moves and here I have three frames of
 the main memory Means in this process, its pages out of these three frames can appear anywhere Now if we see this in real time, then in real time pages of a process we do not give the 5th number of frames Meaning the number of frames
can be more or less. But Just for Solving the Example
or Numerical So that we can understand these
three concepts very well. So I fixed here that for this process, for the pages of this process three frames have been given
in the main memory Frame 1, Frame 2, Frame 3 Now let&#39;s start with solving how first-in-first-out works? So here&#39;s what the CPU has demanded first that is of page No.7 Means the CPU is saying that the byte because the CPU does not even know
 that we have used any paging concept, then the byte that the CPU has demanded the byte that it is demanding,
Where is that byte? on page No. 7, We converted the logical address and
found out that it is demanding for page number 7 When I saw page number 7 in
the main memory, it is neither in frame one nor
in two nor in three, that is, that page is not present anywhere So if that page is nowhere
then what do we call? Page fault We have already discussed this whenever the CPU is looking for a page and that page is absent in main memory we call it page fault. So whenever a page fault happens,
 we service it. Means we bring it from the hard disk and keep it in the main memory. Although it is very time consuming And one of the motives of the page
replacement algorithm is to minimize page faults. Because whenever a page fault happens My time is wasted because the
hard disk gets involved. and where hard disk is involved, definitely hard disk is very slow so obviously my time will increase and performance will decrease. So for this we would like to minimize
the page fault. but that is just numerical so we check
 how many page faults occur in it. Or how many page hits occur, when page number 7 comes, page number 7
 is not here. So that means what happened here fault happened, then we called page
number 7 from the hard disk and let&#39;s say we put it in frame number 1. Along with this, you should also mention
  here&#39;s what it actually is, a page fault because the page you were
looking for was not there now it has arrived, now that
page has arrived Now page No. 0 Second of CPU is saying that I have
 demand for page number zero. But even if you look carefully for zero,
 it is not there. Zero also have to be brought that is also called a page fault. So here too there is a page fault because zero page is also not present
 in main memory so I will bring page number 0 from
the hard disk and place it in frame 2 of main memory. Now there is no need to replace do not replace this 7 because you
already have vacant space. So when the space is empty,
fill that space first. Why are you replacing it? The point of
replacement will come when the entire space is filled. But still the slot was empty,
so I put this 0 here, You can start from the top also, it is our own way of practice I was used to practice this from beginning I used to solve like this I first placed 7 here then 0 in the second now next frame came 1 sorry next is page number 1, Now if you look carefully So page number
one is also not there So here again page fault is occurring so I will bring page number one
from the hard disk and put it in the main memory. So the three frames here are all filled up and all of these three are page faults. Next frame No. 2 Page No. 2 there is demand for page number 2 whether I have page number 2 first you
have to check that. That if page number 2 is there
it is a hit, isn&#39;t it? The page got hit,
but if you look carefully, the CPU is demanding page number 2, but page number two is not here. and here the space also ran out Means we have three frames saved
and all are full then what will I do an old page will
have to be replaced. So what does FIFO do? First in first out,
means the frame which was filled first empty that frame first Means what will I fill here in
place of 7, 2 and rest as it is rest as it is, means means we brought 2 in place of 7, and 0 and 1 as it is, So what is this? This is also a page fault. Because the page you were asking
for is not present. After that, if you look carefully, Whose demand has come next?
page number zero, So is my page number zero present here? You have to check here recently as this is an updated report.
You have to check it in the updated Is page number zero there? Yes, my page number zero is present. So if page number zero is present then
what is it called?  Page hit, Hit means? The thing you were asking for is already
present in main memory. So we copy the hit case as it is. Means copy it here as it is if hit occurs I also note here, Let me write, that is called a hit because the page you were
demanding was found. Next 3 Check if 3 is there or not?
No, 3 is not there, So I&#39;ll have to replace it. Which frame was the first to be replaced
according  to First In First Out? Which frame did we change?
In frame one, now which one has to be changed? frame 2, means you have to remove
frames one by one. Will send this zero out of the frame. and we&#39;ll bring 3 in place of that zero. Means we will replace this zero with 3 keep the rest as it is. And what is this too?
Page fault because the number three page
was not present We have brought it now. Next 0, Zero, page No. 0 Is page no. 0 there? No it&#39;s not there. Now again we have to do replacement with whom we will replace now? with frame No. 3 first of all frame No. 1 then replaced in 2 now in 3, you have to replace line-wise so in frame no. 3 we replaced 1 with 0 we are in this frame on this page No. 3, 2 and what is this? This is miss or page fault. because the page you were having
 demand for is not there. after that we come on page No. 4 Is page No. 4 present there?
No, it is not Page No. 4 is not present,
 so what will we replace? Frame 1,
Why? because first we replaced frame 1,
 then 2 then 3 now we have come back on frame No. 1 so we will replace 2 with 4 and rest write as it is and this is also page fault, because because page No. 4 was also not present Next is 2, Is 2 present? No, 2 is not present as 2 is not present so we will
replace 3 with 2 and rest 2, 0, 4 because after frame 1, replacement
will be in frame 2 Next 3, Now we are on this page No. Is page No. 3 there?
No, it is not. So again page fault occur here What we will replace?
Frame No .3 You just have to replace line-wise After this comes page No. 0, Page No. 0 Is Page No. 0 present?
No it is not. So we are again on frame No. 1 We replaced 4 with 0 2, 3 Again what I am having here? Miss then after 0, I am having 3 Page No. 3 Is page No. 3 present? Yes page No. 3 is already there. So the page which CPU is demanding is
present in main memory This we call hit. So when there is hit you don&#39;t
have to do any changes just copy previous one as it is. and write here that it is a hit then, page No. 1 Is page No. 1 present here? No, page No. 1 is not present. So, what will we replace? this one, because we have already
replaced frame No.1 now it&#39;s turn of frame 2 So in frame 2 we replace 2 with 1 and keep rest as it is. that is again called a miss. or page fault after that Page No. 2 Is page No. 2 present? No
Page No. 2 is not present So what do we replace now 3rd frame, replaced 3rd frame put 2 in its place and rest as it is. That is again called a page fault. After that came page No. 0, Is page No. 0 present? Yes page No. 0 is present. So when it is present we call it hit, So you copy it as it is. That is called a hit. So this is how we have to follow. No matter how big this referencing is you will not face any problem because you have to follow a simple method that you have to replace frame wise first you have to replace frame 1 then 2, then 3 then again 1, 2 and 3 again 1, 2, 3 but when? when frames are already full means all slots are filled and the page which CPU is making demand is not there. means there is page fault. So now you can check here how
much hit I am having? and how many page fault or miss are there. We can call this page fault or page miss. and this is page hit. So how many page hit came 1, 2, 3 That is called page hit. and how many page fault came? 1, 2, 3, 4, 5, 6, 7 8, 9, 10, 11, 12 So 12 No. of page faults. and how many hits 3 Many times you can be  asked What is the... all this question is given at last it is asked what is the hit ratio? or what is the miss ratio? So if you want to find hit ratio or
miss ratio first of all find number of hits and number of miss now I know if I have to find hit ratio How will you find hit ratio? number of hits divided by total number of references so the number of hits I am having is 3 number of hits are 3, and the number of references 1, 2, 3 15 So 3 divided by 15 multiplied by 100 and what is the miss ratio or
page fault ratio? 12 divide by 15 multiplied by 100 So this is the way how we can solve. Solve it further So 20% is the hit ratio and if you solve this definitely it will come 80 % If hit ratio is 20 % so what would be 100 - 20% that would be miss 80% This is how we can solve the question of FIFO first in first out, in which you have to go frame wise just frame wise don&#39;t worry about how reference came just go on replacing frames one by one in sequence So this is all about first in first out Thank You.

Transcript for:Page Replacement Algorithms

Transcript for:
Page Replacement Algorithms