FOR FREE CONTENT

Stack Property

 

To achieve the desirable page fault i.e. page fault decreases as the number of frames increase (inversely proportionate), a page replacement algorithm must follow the stack property (also called the inclusion property).

 

So, if any page replacement algorithm does not follow stack property, then Belady’s anomaly occurs. 

 

As we see in the previous chapter: Belady's Anomaly only the FIFO policy of page replacement suffering from Belady’s anomaly.

 

Stack property:

 

 

This stack property means that at a certain time instant, page references present at n frames, is a subset of the number of page references present at frames such that n < m

 

Now to clear it the better way we see how to stack properly ensures the desirable page fault characteristic and why only FIFO facing Belady’s anomaly. 

 

For example 

Now we take two page replacement algorithms LRU and FIFO to see how LRU follows stack property and FIFO unable to follow stack property.

 

LRU:

Page references5, 4, 3, 2, 1, 4, 3, 5, 4, 3, 2, 1, 5 and number of frame = 3 and 4t1t2 … measures the time instance.

 

 

From the above figure, it is clear that when we increase the frame from 3 to 4, then in every instance of time t, the page references present in 3 frames, it also present at 4 frames, so LRU follows stack property,

 

For example, at time instance t7, first frame 3 contains pages 3, 1, 4 which is also present at frame 4.

And it happens in every case. 

 

Same way optimal, MRU and all page replacement algorithms except FIFO follow stack property.

 

FIFO:

Page references5, 4, 3, 2, 1, 4, 3, 5, 4, 3, 2, 1, 5 and number of frame = 3 and 4.

 

 

From the above figure, it is clear that FIFO unable to holds stack property because if we see time instance t8, first frame 3 contains pages 3, 5, 4 but at frame 4, page 4 is not present but as per stack property 3, 5, 4 all pages which loaded at frame 3, should also present at frame 4.

 

This is also true for time instance t9 and t12.

 

So, the FIFO page replacement policy does not hold stack property.