least recently used lru | optimal | fifo page replacement algorithm

Today I am going to explain about page replacement algorithm in the operating system, in the operating system that uses paging for the virtual memory management, page replacement algorithm are needed to decide which page needed to be replaced when the new page comes in. Page replacement happens when a requested page is not found in memory called as page fault and Operating System replaces one of the existing pages with a newly needed page with the help of the various algorithm to decide which page is going to replace.least recently used lru | optimal page replacement | fifo page replacement

page replacement algorithm

Page Replacement Algorithm are:-

  1. FIFO (First in First Out) fifo page replacement
  2. Optimal page replacement
  3. Least Frequently used

fifo page replacement

1. First in First Out (FIFO):-

it is a simplest page-replacement algorithm. the FIrst in First out page replacement algorithm keeps track of all the pages in memory in a queue with the oldest arrival at the front and the new arrival at the back. the page that is in the front is selected whenever a page needs to be replaced.

in other words, the page in the frame that has been in memory the longest is replaced.

let us take one example:-

Reference string:- 1,2,3,4,,2,5

total frame:- 3

step:-

the frame is empty so 1,2,3 will fix in frame                         page fault:- 3

4 is not in the frame so it will replace 1                                page fault:- 4

2 is in the frame so there is no page replacement                page fault:- 4

5 is not in the frame so it replace 2                                       page fault:- 5

fifo page replacement

total page fault:- 5

Belady Anomaly:-

more frames more page fault

2. optimal page replacement

in this algorithm that pages are replaced which are not used for the longest duration of time in the future.

lets us take one example

Reference string:- 1,2,3,4,1,2,5,1,2,3,4,5

total frame:- 4

step:

first frame is empty so 1,2,3,4 will fix in frame page                     page fault:- 4

1,2 is in frame so no page replacement                                        page fault:-4+0

5 will replace 4 because 1,2,3 will be used in future                     page fault:-4+1=5

1,2,3 is in frame so no page replacement                                     page fault:-5+0

4 will replace 1                                                                               page fault:- 5+1=6

5 is in the frame so no page replacement                                         page fault:-6+0

total page fault:- 6

optimal page replacement

3.least recently used lru

The least recently used lru page replacement algorithm keeps track of page usage over a short period of time. LRU replaced a page which is least recently used. its uses a counter implement.

a counter is applied to each frame start from 1 and when a page is not in the frame its replace the page that has lowest no of the counter value. and if the page is available in frame its change the counter value of that page and increment by 1.

Reference string:- 7,0,1,2,0,3

total frame:- 3

step:-

7(1),0(2),1(3) will fix in frame where 1,2,3 is a counter value                       page fault-3

2 is not in the frame so it replace lowest counter value(0) of 7 and

increment counter now 2(4),0(2),1(3)                                                            page fault:-3+1

0 is in frame so no page placement now 2(4),0(5),1(3)                                 page fault: 4+0

3 is not in frame so it replace lowest counter value (3) of 1

2(4),0(5),3(6)                                                                                                   page fault: 4+0

 

total page fault:- 4

 

least recently used lru

 

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *