search
Log In
0 votes
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?

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

in Operating System 178 views

1 Answer

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
1 answer
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.
asked Jan 18, 2018 in Operating System Sona Barman 164 views
1 vote
0 answers
2
175 views
if you have 10 Frames and using LRU how many page fault will be there in both below: for (int j = 0; j < 100; j++) for (int i = 0; i < 100; i++) A[i][j] = A[i][j] + A[j][i]; for (int i = 0; i < 100; i++) for (int j = 0; j < 100; j++) A[i][j] = A[i][j] + A[j][i];
asked Nov 13, 2017 in Operating System ashu0316 175 views
0 votes
1 answer
3
242 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 implement? Why?
asked Jan 11, 2016 in Revision Arjun 242 views
0 votes
0 answers
4
49 views
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.$
asked Oct 26, 2019 in Operating System Lakshman Patel RJIT 49 views
...