# LRU replacement

178 views

" In the case of LRU, ( and particularly the stack implementation thereof ), the top N pages of the stack will be the same for all frame set sizes of N or anything larger."

Can somebody please explain what this means?

Theoretically, It means, If u r having a stack of Size N, then it will contain N most recently used page entries. Consider the same set of Entries, but this time use stack of N+1 size. If you compare, top N entries of both stack, they will be Same.

Consider this Example:-

String: 4 7 0 7 1 0 1 2 3

Stack 1 of size 4 -> 3, 2, 1, 0 (They are the most recently used, 3 is at top of stack because it arrived that, means most recent)

stack 2 of size 5 ->  3, 2, 1,0,7 (Here 7 is there but at the last entry)

Let's implement this Stack,

Initially Empty:

Stack-> 4

Stack-> 7 4

Stack -> 0 7 4

Stack -> 7 0 7 4 (Remove duplicate from bottom) => 7 0 4

Stack -> 1 7 0 4

Stack -> 0 1 7 4 (You know what happened here)

Read 1 -> 1 0 7 4

read 2 -> 2 1 0 7

read 3 -> 3 2 1 0 (Final State)

For Stack of size 5, final value will be -> 3 2 1 0 7

Now compare top 4 entries of both stack:- they are same ie., 3 2 1 0

## Related questions

1
164 views
Self doubt: What is the rule or keyb point we should keep in mind while solving problems on LRU page replacement algorithm? Please explain with examples.
1 vote
Give a simple example of a page reference sequence where the first page selected for replacement will be different for the clock and $LRU$ page replacement algorithms. Assume that a process is allocated $3=\text{three}$ frames, and the reference string contains page numbers from the set $0, 1, 2, 3.$