2
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ stack-based meaning LIFO as opposed to FIFO? $\endgroup$ – Purag Jun 7 '16 at 8:16
  • $\begingroup$ What have you tried? Have you worked through some examples, to see if you can construct an example of Belady's anomaly? Have you tried proving that it is not subject to Belady's anomaly? $\endgroup$ – D.W.♦ Jun 7 '16 at 15:26
  • $\begingroup$ stackoverflow.com/q/5263988/781723 $\endgroup$ – D.W.♦ Jun 7 '16 at 15:28
  • $\begingroup$ I have gone through FIFO examples having some page references resulting in Belady's anomaly but I am unable to relate it with this line. $\endgroup$ – Maharaj Jun 8 '16 at 6:00
2
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.