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

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