馃攳
L-5.22: Page Replacement Introduction | FIFO Page Replacement algorithm | Operating System - YouTube
Channel: Gate Smashers
[0]
Page replacement algorithm
[2]
We have seen in the concept of paging
that by dividing the processes in pages
[7]
we put them in the frames of main memory,
[9]
what does the concept of
virtual memory say?
[12]
That we never bring the entire
process inside the main memory
[17]
and not all the pages of a process
[20]
at the same time we try to keep in the
main memory
[24]
no, Here we provide the reason to the
programmer through virtual memory
[28]
that all the processes you have.
[31]
We can accommodate the maximum number of
processes inside the main memory.
[36]
but actually how it is done
[38]
If we will keep the entire process
in the main memory
[41]
So it may be that our main memory is
completely finite.,
[44]
so my main memory will get filled with
one or two processes.
[47]
So what do we do instead? Virtual memory
[50]
one or two pages, Each process brings
one or two pages into the main memory.
[56]
which have demand.
[58]
When their need runs out,
we swipe out those pages
[61]
and then swipe in fresh pages.
[64]
So this swipe in and swipe out funda
we saw in virtual memory.
[68]
Now which page do we have to bring
inside the main memory?
[73]
And when that page will come
inside main memory
[76]
it is possible that the main
memory is already filled,
[79]
all the frames are already filled in it.
[82]
So if I want to bring the new page
inside the main memory
[86]
and get it accommodated,
[88]
So for that one page from the main memory
[91]
will have to be taken out from there
[94]
So that I can clear a frame over there
[97]
So what is my concept here?
[99]
of page replacement,
Means
[101]
I am bringing a page to the main memory
[105]
If my main memory is full,
[107]
then I will remove the old page from there
by swiping out
[111]
and make space on it and place the new
page in that place.
[115]
So how to replace these pages?
[118]
There are three methods,
[119]
first is the first in first out,
[123]
optimal page replacement
[125]
and least recently used.
[127]
These three algorithms which are common
and most of the time are used
[131]
to replace the page.
[133]
If there is a space in the main memory
[135]
then there is no problem
[137]
Then you can put the new page
on that empty space.
[140]
But the problem is that the size of
the processes are very big,
[144]
and the number of processes are very high
[146]
but the size of main memory is limited
and it is finite.
[150]
So in order to bring more
and more processes
[153]
What I have to do?
[155]
I have to remove old pages
[158]
and replace them with new pages
[160]
So how do we replace it?
[162]
let's start with first of all
first in first out,
[166]
here I have one string
[169]
this is what? It is called a reference
[173]
reference string
[175]
reference string means
[177]
the CPU is demanding pages
[179]
Let's say the CPU is executing a process.
[182]
Executing any process
[184]
and we have divided that process
into different pages
[188]
Now the CPU has sent a demand
[191]
that first I want page number 7
[194]
then one then 0, then 1, then 2
and again 0,
[197]
this is the sequence,
means
[200]
this is the reference, it is
in sequence
[202]
it is already in the order, here I have
taken this sequence
[207]
now whenever the CPU is
demanding, for what?
[210]
that is page number 7
[212]
then 0, then 1, then 2
[214]
and this is how it moves
[216]
and here I have three frames of
the main memory
[219]
Means in this process, its pages
[223]
out of these three frames
[226]
can appear anywhere
[228]
Now if we see this in real time,
[230]
then in real time
[231]
pages of a process
[234]
we do not give the 5th number of frames
[236]
Meaning the number of frames
can be more or less.
[240]
But Just for Solving the Example
or Numerical
[244]
So that we can understand these
three concepts very well.
[247]
So I fixed here
[249]
that for this process,
[250]
for the pages of this process
[252]
three frames have been given
in the main memory
[255]
Frame 1, Frame 2, Frame 3
[261]
Now let's start with solving
[263]
how first-in-first-out works?
[266]
So here's what the CPU has demanded first
[268]
that is of page No.7
[270]
Means the CPU is saying that the byte
[273]
because the CPU does not even know
that we have used any paging concept,
[277]
then the byte that the CPU has demanded
[280]
the byte that it is demanding,
Where is that byte?
[283]
on page No. 7,
[285]
We converted the logical address and
found out
[288]
that it is demanding for page number 7
[291]
When I saw page number 7 in
the main memory,
[294]
it is neither in frame one nor
in two nor in three,
[297]
that is, that page is not present anywhere
[299]
So if that page is nowhere
then what do we call?
[302]
Page fault
[303]
We have already discussed this
[306]
whenever the CPU is looking for a page
[308]
and that page is absent in main memory
[311]
we call it page fault.
[314]
So whenever a page fault happens,
we service it.
[317]
Means we bring it from the hard disk
[319]
and keep it in the main memory.
[322]
Although it is very time consuming
[324]
And one of the motives of the page
replacement algorithm is
[329]
to minimize page faults.
[332]
Because whenever a page fault happens
[334]
My time is wasted because the
hard disk gets involved.
[338]
and where hard disk is involved,
[340]
definitely hard disk is very slow
[343]
so obviously my time will increase
[345]
and performance will decrease.
[347]
So for this we would like to minimize
the page fault.
[353]
but that is just numerical so we check
how many page faults occur in it.
[358]
Or how many page hits occur,
[360]
when page number 7 comes, page number 7
is not here.
[364]
So that means what happened here
[367]
fault happened, then we called page
number 7 from the hard disk
[371]
and let's say we put it in frame number 1.
[374]
Along with this, you should also mention
here's what it actually is,
[379]
a page fault because the page you were
looking for was not there
[383]
now it has arrived, now that
page has arrived
[386]
Now page No. 0
[388]
Second of CPU is saying that I have
demand for page number zero.
[391]
But even if you look carefully for zero,
it is not there.
[394]
Zero also have to be brought
[396]
that is also called a page fault.
[398]
So here too there is a page fault
[400]
because zero page is also not present
in main memory
[405]
so I will bring page number 0 from
the hard disk
[408]
and place it in frame 2 of main memory.
[412]
Now there is no need to replace
[414]
do not replace this 7 because you
already have vacant space.
[417]
So when the space is empty,
fill that space first.
[421]
Why are you replacing it? The point of
replacement will come
[425]
when the entire space is filled.
[426]
But still the slot was empty,
so I put this 0 here,
[430]
You can start from the top also,
[432]
it is our own way of practice
[434]
I was used to practice this from beginning
[436]
I used to solve like this
[439]
I first placed 7 here then 0 in the second
[441]
now next frame came 1
[444]
sorry next is page number 1,
[446]
Now if you look carefully So page number
one is also not there
[449]
So here again page fault is occurring
[451]
so I will bring page number one
from the hard disk
[455]
and put it in the main memory.
[457]
So the three frames here are all filled up
[460]
and all of these three are page faults.
[463]
Next frame No. 2
[466]
Page No. 2
[467]
there is demand for page number 2
[469]
whether I have page number 2 first you
have to check that.
[472]
That if page number 2 is there
it is a hit, isn't it?
[475]
The page got hit,
but if you look carefully,
[478]
the CPU is demanding page number 2,
[480]
but page number two is not here.
[483]
and here the space also ran out
[485]
Means we have three frames saved
and all are full
[488]
then what will I do an old page will
have to be replaced.
[492]
So what does FIFO do?
[494]
First in first out,
means
[496]
the frame which was filled first
[501]
empty that frame first
[505]
Means what will I fill here in
place of 7, 2
[508]
and rest as it is
[510]
rest as it is, means
[513]
means we brought 2 in place of 7,
[515]
and 0 and 1 as it is,
[517]
So what is this? This is also a page fault.
[519]
Because the page you were asking
for is not present.
[524]
After that, if you look carefully,
[526]
Whose demand has come next?
page number zero,
[529]
So is my page number zero present here?
[533]
You have to check here recently
[535]
as this is an updated report.
You have to check it in the updated
[538]
Is page number zero there?
[540]
Yes, my page number zero is present.
[543]
So if page number zero is present then
what is it called? Page hit,
[547]
Hit means?
[548]
The thing you were asking for is already
present in main memory.
[552]
So we copy the hit case as it is.
[555]
Means copy it here as it is
[558]
if hit occurs
[560]
I also note here, Let me write,
[562]
that is called a hit
[563]
because the page you were
demanding was found.
[567]
Next 3
[568]
Check if 3 is there or not?
No, 3 is not there,
[572]
So I'll have to replace it.
[573]
Which frame was the first to be replaced
according to First In First Out?
[577]
Which frame did we change?
In frame one,
[580]
now which one has to be changed?
[581]
frame 2, means you have to remove
frames one by one.
[585]
Will send this zero out of the frame.
[587]
and we'll bring 3 in place of that zero.
[590]
Means we will replace this zero with 3
[592]
keep the rest as it is.
[594]
And what is this too?
Page fault
[597]
because the number three page
was not present
[599]
We have brought it now.
[601]
Next 0,
[603]
Zero, page No. 0
[605]
Is page no. 0 there?
[607]
No it's not there.
[608]
Now again we have to do replacement
[610]
with whom we will replace now?
[611]
with frame No. 3
[612]
first of all frame No. 1
[614]
then replaced in 2
[616]
now in 3, you have to replace line-wise
[619]
so in frame no. 3 we replaced 1 with 0
[622]
we are in this frame
[623]
on this page No.
[625]
3, 2
[626]
and what is this?
[629]
This is miss or page fault.
[631]
because the page you were having
demand for is not there.
[634]
after that we come on page No. 4
[636]
Is page No. 4 present there?
No, it is not
[639]
Page No. 4 is not present,
so what will we replace?
[642]
Frame 1,
Why?
[644]
because first we replaced frame 1,
then 2 then 3
[647]
now we have come back on frame No. 1
[651]
so we will replace 2 with 4
[654]
and rest write as it is
[656]
and this is also page fault, because
[658]
because page No. 4 was also not present
[661]
Next is 2,
[663]
Is 2 present?
[665]
No, 2 is not present
[667]
as 2 is not present so we will
replace 3 with 2
[670]
and rest 2, 0, 4
[673]
because after frame 1, replacement
will be in frame 2
[676]
Next 3,
[678]
Now we are on this page No.
[680]
Is page No. 3 there?
No, it is not.
[682]
So again page fault occur here
[685]
What we will replace?
Frame No .3
[687]
You just have to replace line-wise
[692]
After this comes page No. 0,
[696]
Page No. 0
[697]
Is Page No. 0 present?
No it is not.
[700]
So we are again on frame No. 1
[703]
We replaced 4 with 0
[706]
2, 3
[707]
Again what I am having here? Miss
[711]
then after 0, I am having 3
[715]
Page No. 3
[717]
Is page No. 3 present?
[719]
Yes page No. 3 is already there.
[721]
So the page which CPU is demanding is
present in main memory
[726]
This we call hit.
[728]
So when there is hit you don't
have to do any changes
[731]
just copy previous one as it is.
[734]
and write here that it is a hit
[738]
then, page No. 1
[741]
Is page No. 1 present here?
[743]
No, page No. 1 is not present.
[745]
So, what will we replace?
[748]
this one, because we have already
replaced frame No.1
[751]
now it's turn of frame 2
[753]
So in frame 2 we replace 2 with 1 and
[758]
keep rest as it is.
[760]
that is again called a miss.
[762]
or page fault
[764]
after that Page No. 2
[768]
Is page No. 2 present? No
Page No. 2 is not present
[771]
So what do we replace now
[773]
3rd frame, replaced 3rd frame
[776]
put 2 in its place
[778]
and rest as it is.
[779]
That is again called a page fault.
[782]
After that came page No. 0,
[785]
Is page No. 0 present?
[787]
Yes page No. 0 is present.
[789]
So when it is present we call it hit,
[792]
So you copy it as it is.
[796]
That is called a hit.
[798]
So this is how we have to follow.
[800]
No matter how big this referencing is
[803]
you will not face any problem
[805]
because you have to follow a simple method
[808]
that you have to replace frame wise
[810]
first you have to replace frame 1
[812]
then 2, then 3
[815]
then again 1, 2 and 3
[816]
again 1, 2, 3
[817]
but when? when frames are already full
[821]
means all slots are filled
[823]
and the page which CPU is making demand
[825]
is not there.
[827]
means there is page fault.
[829]
So now you can check here how
much hit I am having?
[832]
and how many page fault or miss are there.
[835]
We can call this page fault
[839]
or page miss.
[843]
and this is page hit.
[846]
So how many page hit came
[848]
1, 2, 3
[851]
That is called page hit.
[852]
and how many page fault came?
[854]
1, 2, 3, 4, 5, 6, 7
[857]
8, 9, 10, 11, 12
[863]
So 12 No. of page faults.
[867]
and how many hits 3
[869]
Many times you can be asked
[871]
What is the... all this question is given
[874]
at last it is asked what is the hit ratio?
[877]
or what is the miss ratio?
[879]
So if you want to find hit ratio or
miss ratio first of all
[882]
find number of hits and number of miss
[885]
now I know if I have to find hit ratio
[889]
How will you find hit ratio?
[891]
number of hits divided by
[895]
total number of references
[899]
so the number of hits I am having is 3
[902]
number of hits are 3,
[904]
and the number of references 1, 2, 3
[909]
15
[911]
So 3 divided by 15
[913]
multiplied by 100
[916]
and what is the miss ratio or
page fault ratio?
[920]
12 divide by 15
[921]
multiplied by 100
[923]
So this is the way how we can solve.
[926]
Solve it further
[932]
So 20% is the hit ratio
[936]
and if you solve this
[938]
definitely it will come 80 %
[940]
If hit ratio is 20 %
[942]
so what would be 100 - 20%
[945]
that would be miss 80%
[947]
This is how we can solve the question of
[951]
FIFO
[952]
first in first out, in which you
[954]
have to go frame wise just frame wise
[956]
don't worry about how reference came
[959]
just go on replacing frames one by one
[961]
in sequence
[963]
So this is all about first in first out
[965]
Thank You.
Most Recent Videos:
You can go back to the homepage right here: Homepage