L-5.25: Least Recently Used Page Replacement Algorithm | Operating System

In LRU we replace the page which is least
recently used in the past means we replace that page which was used
firstly in the past
means we replace that page which was used
firstly in the past let's solve it with the example
let's solve it with the example this is the reference stream given to us
this is the reference stream given to us and four number of frames are there
and four number of frames are there whenever there is a demand of first page
that is page number 7
whenever there is a demand of first page
that is page number 7 initially all the frames are empty
initially all the frames are empty so we service the page number 7
and we call it in the main memory
so we service the page number 7
and we call it in the main memory that is called a page fault
that is called a page fault after that we checked for page number 0,
that is there page number?
after that we checked for page number 0,
that is there page number? page number 0 is also not there,
serviced the page number 0
page number 0 is also not there,
serviced the page number 0 means called from the hard disk
means called from the hard disk and this also we call as page fault
and this also we call as page fault after that page number 1 comes
after that page number 1 comes so page number 1 was also absent
so page number 1 was also absent so that also we called to main memory from
hard disk, that is also called a page fault
so that also we called to main memory from
hard disk, that is also called a page fault then page number 2
then page number 2 so that is also a page fault because
it was also initially absent
so that is also a page fault because
it was also initially absent now next is page number 0
now next is page number 0 when page number 0 came,
is my page number 0 present or absent?
when page number 0 came,
is my page number 0 present or absent? so page number 0 is already present,
so that is called a page hit
so page number 0 is already present,
so that is called a page hit so we can write it a page hit
so we can write it a page hit next is page number 3
next is page number 3 page number 3 came so,
is my page number 3 present?
page number 3 came so,
is my page number 3 present? page number 3 is not present
page number 3 is not present so now here LRU will start, what LRU will
do?
so now here LRU will start, what LRU will
do? so on which frame are we standing
on page number 3 we are standing
so on which frame are we standing
on page number 3 we are standing this is the page that i have to put in the
main memory
this is the page that i have to put in the
main memory so to put this page i will have to replace
any of the page
so to put this page i will have to replace
any of the page so which page will we replace?
so which page will we replace? in LRU we check the past,
means previously used pages
in LRU we check the past,
means previously used pages so in previously used pages
so in previously used pages which page is there among these 4
which was used at first?
which page is there among these 4
which was used at first? which was called at first
which was called at first means whose demand was least
means whose demand was earliest
means whose demand was least
means whose demand was earliest so if we see here, 3 , 7, 0, 1, 2
so if we see here, 3 , 7, 0, 1, 2 so 0 has come here, 2 here, 1 here and
7 here
so 0 has come here, 2 here, 1 here and
7 here so if we see carefully, 7's demand was at
first among these four
so if we see carefully, 7's demand was at
first among these four you just have to compare these four
you just have to compare these four standing at this point we have to compare
these four
standing at this point we have to compare
these four that in past which one came at first
that in past which one came at first whose demand was at first
whose demand was at first so if you see carefully 7's demand was at
first
so if you see carefully 7's demand was at
first among these four
among these four so after sending 7 outside,
we brought 3 inside
so after sending 7 outside,
we brought 3 inside so we entered 3 in,
and write rest of these as it is
so we entered 3 in,
and write rest of these as it is that is called a page fault because
3 was absent
that is called a page fault because
3 was absent now next pagenumber is 0,
is page number 0 present?
now next page number is 0,
is page number 0 present? yes it is present?
yes it is present? so directly copy over here
so directly copy over here we copied and
below that we wrote hit.
we copied and
below that we wrote hit.

Then page number 4
then page number 4 so page number 4 came
so page number 4 came so when page number 4 will come, we will
have to check, is page number 4 present?
so when page number 4 will come, we will
have to check, is page number 4 present? no page number 4 is not present
no page number 4 is not present so now here, from 4
so now here, from 4 towards back means in past i will check,
these 4 should be compared
towards back means in past i will check,
these 4 should be compared among 2,1,0,3 which one was used at first
among 2,1,0,3 which one was used at first so 4, 0 came here itself, 3 came here
so 4, 0 came here itself, 3 came here 2 came here, 1 came here, so if you see
carefully, 1 is used at first among these 4
2 came here, 1 came here, so if you see
carefully, 1 is used at first among these 4 so we will replace 1 with 4
so we will replace 1 with 4 rest of these write as it is
rest of these write as it is and this also we will call as page fault
because this page number 4 was absent
and this also we will call as page fault
because this page number 4 was absent now we have put after service
now we have put after service next is page number 2,
so is page number 2 present?
next is page number 2,
so is page number 2 present? yes it is already present
so we can call this as hit
yes it is already present
so we can call this as hit next comes page number 3
next comes page number 3 just put a mark, so that you don't try any
page again.
just put a mark, so that you don't try any
page again.

So 3, is my 3 present over here?
yes 3 is already present.
so 3, is my 3 present over here?
yes 3 is already present. so that is again called a hit
so that is again called a hit so next is page number 0, is page number 0
present? .. yes it is already present
so next is page number 0, is page number 0
present? .. yes it is already present that is called a hit
that is called a hit so next is page number 3, is page number 0
present? .. yes it is already present
so next is page number 3, is page number 0
present? .. yes it is already present that is called a hit
that is called a hit next is page number 2, is page number 2
present? .. yes it is already present
next is page number 2, is page number 2
present? .. yes it is already present this also i will write as it is, that is
again called a hit
this also i will write as it is, that is
again called a hit after that comes page number 1
after that comes page number 1 is page number 1 present?..no
page number 1 is absent
is page number 1 present?..no
page number 1 is absent so from here onward i have to check back in
past
so from here onward i have to check back in
past among 4,3,0 which one came first
among 4,3,0 which one came first 2 came here, 3 came here, 2 here
4, among these four 4 came first in past
2 came here, 3 came here, 2 here
4, among these four 4 came first in past so we will replace 4 with 1
so we will replace 4 with 1 4,3, rest all write as it is,
and what is it? …

A page fault
4,3, rest all write as it is,
and what is it? … a page fault because this was absent
because this was absent next comes page number 2, is page number 2
present? yes it is already present
next comes page number 2, is page number 2
present? yes it is already present that is called a hit
that is called a hit next comes page number 0, is page number 0
present? yes it is already present
next comes page number 0, is page number 0
present? yes it is already present that is again called a hit
that is again called a hit next comes page number 1, is page number 1
present? yes it is already present
next comes page number 1, is page number 1
present? yes it is already present that is again called a hit
so we write it as it is
that is again called a hit
so we write it as it is 2, 1, 0, 3 that is again called a hit
2, 1, 0, 3 that is again called a hit next comes page number 7, is page number 7
present? no page number 7 is not present
next comes page number 7, is page number 7
present? no page number 7 is not present so again i will check in the past, among
1,2,0,3 which one came first
so again i will check in the past, among
1,2,0,3 which one came first 1 came here
1 came here 0 came here, 2 came here
3, 3 came here first amon these in past
0 came here, 2 came here
3, 3 came here first among these in past i replace 3 with 7, rest all as it is
that is called a page fault
i replace 3 with 7, rest all as it is
that is called a page fault next comes page number 0, is page number 0
present? yes it is already present
next comes page number 0, is page number 0
present? yes it is already present this also we will call as a page hit
this also we will call as a page hit after that page number 1 came
after that page number 1 came page number 1 is already present
that is again called a hit
page number 1 is already present
that is again called a hit so this way, we can replace pages through
LRU
so this way, we can replace pages through
LRU so there is only one simple formula for
LRU
so there is only one simple formula for
LRU that we replace the page who demand in past
was at first
that we replace the page who demand in past
was at first so what i mean to say
so what i mean to say means the page which was called in past
a long time ago,
means the page which was called in past
a long time ago, there is no need of that page over here
there is no need of that page over here so there that page we will replace by
sending in hard disk
so there that page we will replace by
sending in hard disk and will bring any fresh page in the main
memory
and will bring any fresh page in the main
memory so you can simply count number of page
fault..

One two three four five six
so you can simply count number of page
fault.. one two three four five six seven eight
seven eight so number of page faults are…eight
so number of page faults are…eight in maximum questions they will ask you
what is total numbe of page faults
in maximum questions they will ask you
what is total number of page faults and
what is total numbe of page hits
and
what is total numbe of page hits so you can also calculate page hits
so you can also calculate page hits so one two three four five six seven eight
nine ten eleven twelve
so one two three four five six seven eight
nine ten eleven twelve so 12 number of hits are there
so 12 number of hits are there so that is how LRU works
so that is how LRU works although it is given less number of page
faults..

As compared to Fifo
although it is given less number of page
faults.. as compared to Fifo but what is the problem with it?…
performance ..speed
but what is the problem with it?…
performance ..speed because, this always, if you have checked
carefully
because, this always, if you have checked
carefully so this always search in past which one
was farthest in past
so this always search in past which one
was farthest in past so over here searching algorithm
is being used
so over here searching algorithm
is being used so due to that if i compare it with Fifo
so due to that if i compare it with Fifo over here that, speed factor
over here that, speed factor LRU.. it's speed is less,
so at somepoint it is taking more time
LRU.. it's speed is less,
so at some point it is taking more time as compared to fee fo
1
00:00:00,603 –> 00:00:05,158
In LRU we replace the page which is least
recently used in the past
as compared to Fifo but yes it is performing better
than that in terms of page performance
but yes it is performing better
than that in terms of page performace so this is all about the LN
Thank you
so this is all about the LN
Thank you