The Gateway to Computer Science Excellence
0 votes
151 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 by Active (3.3k points) | 151 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
by (51 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,741 questions
57,251 answers
198,057 comments
104,685 users