Hey guys, In this tutorial I am going to talk
about Least Frequently Used page replacement algorithm it is also called as not frequently used this algorithm replaces the page that has
the smallest frequency so i’ll explain this algorithm using an example.
This is the page frame buffer these are the page requests.. and these are
the frequencies by default they are set to 0 because currently
the page frame buffer is empty now the first page is 7 so we’ll add 7 here because the page frame buffer is empty and when the page which is requested by the
program is not present in the RAM it is called as page fault so here page fault will occur so the frequency of 7 will increase by 1 so
it’ll become 1 the next page is 0.. so 7 will remain there
and 0 will get added here again there will be a page fault because it
wasn’t present in the page frame buffer and now again 0’s frequency will increase the next page is 1..so there is one more space
left for it to get added so 7 and 0 will remain there and 1 will get
added.. there will be a page fault and 1’s frequency will increase by 1. Now
the page frame buffer is full and the next page is 2 which is not present in the page
frame buffer. So we’ll have to decide which page to remove. Now we’ll check the frequencies
of these 3 pages… 7,0 and 1. All the frequencies are equal so we’ll apply FIFO here. So what
FIFO does is.. you just have to look from left to right which page came first. So 7
came first, 7 will get removed and 2 will get added here and there will be a page fault
because it wasn’t present already. and 0 and 1 will remain there. Now 2’s frequency will
increase. Since we removed 7, the frequency of 7 will reset. So it’ll become 0 again and
we’ll put a cross over here so we know that it is removed. You’ll know why we are doing
this later. Now the next page is 0 which is already present in the page frame buffer.
So 2,0,1 will remain there and this will be a PAGE HIT. The page which is requested by
the program is present in the RAM hence, it is a page hit. and the frequency of 0 will
increase, so it’ll become 2. The next page is 3 so we’ll have to decide which page to
remove. Now we’ll see 2,0,1..2,1 and 1. So, which page has the least frequency.. 1 & 2
have same frequencies so we’ll see between 1& 2 which page came first. That is we are
applying FIFO here. So, 1 came first.. from left to right we have to check. So, 1 came
first, so we’ll remove 1 and add 3 here. So, 2 and 0 will remain there, 3 will get added
here and there will be a page fault. Now we’ll increase the frequency of 3 and we’ll reset
the frequency of 1 and we’ll also put a cross over here so that we know 1 is removed. Now
the next page is 0 which is already present.. so 2,0,3 will remain there and there will
be a page hit and also 0’s frequency will get increased by 1.The next page is 4. So
we’ll check 2,0,3..0’s frequency is 3 which is the highest and 2 and 3’s frequencies are
equal which is 1. So we’ll check which page came first from left to right.. 2 came first.
So, we’ll remove 2 and add 4 here. So 4 will get added here, there will be a page fault
and 0 and 3 will remain there. and 4’s frequency will increase, 2’s frequency will reset and
we’ll put a cross over here. The next page is 2, so we’ll see the frequencies of 4,0,3…0’s
frequency is highest. So 4 and 3 have the same frequency.. so we’ll see from left to
right which page came first. 3 came first so we’ll remove 3 and add 2 there. So 4 and
0 will remain here and 2 will get added here, there will be a page fault.. and we’ll increase
the frequency of 2.. and 3’s frequency will reset and we’ll also put a cross over here.
The next page is 3. So we’ll check 4,0,2’s frequencies. 0 has the highest frequency..4
and 2 have same frequency so again left to right. 2 came first but we can’t consider
this page because it is removed. So that’s why we have put a cross over here so that
we know that we don’t need to consider these pages now. So just move your cursor from left
to right and see which page came first. 4 came first. So we’ll remove 4 and add 3 there.
So 3 will get added here, there will be a page fault and 0 and 2 will remain there..
and 3’s frequency will increase.. 4’s frequency will be reset and we’ll put a cross over here.
The next page is 0. So 3,0,2 will remain there and 0’s frequency will get increased. This
is a page hit.The next page is 3 which is already present again there will be a page
hit and 3’s frequency will increase. Again 2 is already present so there will be a page
hit and 2’s frequency will be increased. The next page is 1 which is not present in the
page frame. So we’ll see 3,0,2’s frequencies. So 0 has the highest frequency that is 4 and
2 and 3 both have frequency 2. So we’ll check which page came first. From left to right,
2 came first. So we’ll remove 2 and add 1 here. So 0 and 3 will remain there and 1 will
get added here and there will be a page fault. 1’s frequency will be increased, 2’s frequency
will get reset and we’ll put a cross over here. Just make sure that you are putting
cross over here so that you are tracing it correctly. The next page is 2 which is not
present in the page frame. So we’ll check 3,0 and 1’s frequencies. 0 has the highest
frequency.. so 3 and 1.. between 3 and 1, 1 has the least frequency so we’ll remove
1 and add 2 there. So 0 and 3 will remain there, 2 will get added here, there will be
a page fault, 2’s frequency will get increased, 1’s frequency will reset and we’ll put a cross
over here. So this is how least frequently used or not
frequently used page replacement algorithm works. The difference between LFU and LRU
is requires a shorter history. So that’s it for today. I hope you understood what is LFU
and how it works. Thank you for watching this video. Make sure to subscribe to my channel
and if you like this video, make sure to hit the like button. Bye.