LEAST RECENTLY USED LRU)ALGORITHM o Reference string:1,2,3,4,1,2,5,1,2,3,4,5 2 3 5 4 3 3 3 o Counter implementation Every page entry has a counter;every time page is referenced through this entry,copy the clock into the counter When a page needs to be changed,look at the counters to determine which are to change
LEAST RECENTLY USED (LRU) ALGORITHM Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 Counter implementation Every page entry has a counter; every time page is referenced through this entry, copy the clock into the counter When a page needs to be changed, look at the counters to determine which are to change 5 2 4 3 1 2 3 4 1 2 5 4 1 2 5 3 1 2 4 3
LRU PAGE REPLACEMENT reference string 7012030423032120170 2 2 4 4 4 0 1 1 1 0 0 0 0 0 0 3 3 3 0 0 3 3 2 2 2 2 2 7 page frames
LRU PAGE REPLACEMENT
LRU ALGORITHM (CONT.) oStack implementation-keep a stack of page numbers in a double link form: ·Page referenced: omove it to the top orequires 6 pointers to be changed No search for replacement
LRU ALGORITHM (CONT.) Stack implementation – keep a stack of page numbers in a double link form: Page referenced: move it to the top requires 6 pointers to be changed No search for replacement
USE OF A STACK TO RECORD THE MOST RECENT PAGE REFERENCES reference string 47 07101 21 2 7 1 2 2 7 a 1 2 0 1 7 0 4 4 stack stack before after a b
USE OF A STACK TO RECORD THE MOST RECENT PAGE REFERENCES
LRU APPROXIMATION ALGORITHMS o Reference bit With each page associate a bit,initially =0 When page is referenced bit set to 1 Replace the one which is 0(if one exists) o We do not know the order,however o Second chance ·Need reference bit ·Clock replacement If page to be replaced (in clock order)has reference bit 1 then: o set reference bit 0 o leave page in memory o replace next page (in clock order),subject to same rules
LRU APPROXIMATION ALGORITHMS Reference bit With each page associate a bit, initially = 0 When page is referenced bit set to 1 Replace the one which is 0 (if one exists) We do not know the order, however Second chance Need reference bit Clock replacement If page to be replaced (in clock order) has reference bit = 1 then: set reference bit 0 leave page in memory replace next page (in clock order), subject to same rules