Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I was going through page replacement algorithms from Galvin's Operating System book. I encountered this line about LRU:
A stack algorithm is one in which the pages kept in memory for a frame set of size N will always be a subset of the pages kept for a frame size of N + 1.
And it states that stack based algorithm does not suffer from Belady's anomaly. Can anyone explain how it avoids Belady's anomaly?
Stack based algorithms implies that a set of n pages will be a subset of n+1 pages. Why?
In LRU every time a page is referenced it is moved at the top of the stack, therefore the top n pages of the stack are the n most recently used pages. Furthermore, since in LRU the near future is an approximation of recent past, we effectively will reduce the page faults if we increase n.
That is, if number of frames are now made n + 1, top of the stack will have n+1 most recently used pages. Hence, set of n pages are a subset of n+1 pages and as page faults are directly proportional to n (due to the LRU assumption) increasing n will never increase page faults.
An intuitive case(special case) is to think that the LRU stack uses n = number of total pages required by the process. There will be no page faults. And if n=1, there will be page faults equal to total pages required by the process.
