388 views
0 votes
0 votes

" 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?

Please refer : https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/9_VirtualMemory.html

1 Answer

0 votes
0 votes
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:

read 4

Stack-> 4

reading 7

Stack-> 7 4

Read 0

Stack -> 0 7 4

Read 7

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

Read 1

Stack -> 1 7 0 4

Read 0

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

3 votes
3 votes
1 answer
1
Sona Barman asked Jan 18, 2018
458 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 votes
1 votes
0 answers
2
0 votes
0 votes
1 answer
3
Arjun asked Jan 11, 2016
592 views
In LRU policy for cache replacement. the least recently used block is replaced. So, what happens when all the slots are empty at beginning?Is LRU or MRU easier to impleme...
9 votes
9 votes
3 answers
4