#OS doubt

Question

State True/False:-

A Page replacement algorithm suffers from Belody's anomoly when it is not a stack algorithm.

how to identify a stack algorithm? Is LRU stack algorithm? Is FIFO stack algorithm?

Comments

Stack property : Some number of pages in the main memory with 'm' frames and when I increase the number of frame by 1 , then the same pages which were present when we had 'm' frames should also be present when I have 'm+1' frames that's is what stack property

P(m) $\subseteq$ P(m+1)

In belody's anomoly it's seen that the increasing the number of page frames results in an increase in the number of page faults for a given memory access pattern

 belody's anomoly  is commonly experienced when using the FIFO

both LRU and Optimal is under the stack algorithm

---

Yes, ur statement is True!!!

optimal and LRU page replacement algorithm follows the stack property. Therefore we used to call them stack algorithm.

stack property: It is a property which says that the number of pages present in main memory with m frames is a subset of the number of pages present in the main memory with m+1 frames for the same reference string.

It is mathematically proven(proof is very hectic and not required for GATE exam) that optimal and LRU follows the stack property and therefore we call them stack algorithm

FIFO does not follow stack property and we say that it suffers from Beldays Anomaly and So it is not a stack algorithm.

---

a rather simple way to check for whether a given page replacement algorithm is stack algorithm or not is to check how the replacement is taking place? if it is on the base of aging criteria, it can't be stack. if it is on the base of recent(past or future) access criteria, it is stack.

---

thank u @Magma @akash.dinkar12 @aambazinga