CSE 120 Spring 2002
Principles of Computer Operating Systems

Stack Page Replacement Policies

A stack page replacement policy is a policy that assigns a priority to a page that is independent of the number of page frames. Examples of such policies are Optimal, LRU and LFU. Such policies don't suffer from Belady's anomaly, and have a nice property for simulation: the miss (or hit) ratio can be computed for any number of page frames with a single pass through the reference string.

The priority of a page is relative to other pages: given two pages a and b, which page should be retained over the other? For example, in LRU it is that page that was more recently referenced, for Optimal it is the one that will be referenced first in the future, and for LFU it is the one that has been referenced more often in the past. Note that all of these priorities are independent of the number of page frames. FIFO also has such a priority--a < b if b came into physical memory before a did--but the priority is not independent of the number of page frames and hence FIFO is not a stack page replacement policy.

Is LIFO a stack page replacement policy?
Pages can have the same priority. I'll indicate priority by <: a < b means that b has priority over a, and a = b means that a and b have the same priority.

The state of physical memory is represented by a column, where the first m rows represent the contents of physical memory containing m page frames. Clearly, when a page is referenced it must be in the first row (otherwise, it would not be paged into a physical memory containing only one page frame).

The stack is easy to maintain. There are two cases to consider: a reference to a page that is already in the stack and a reference to a page that is not in the stack. For the first case, consider the following stack. Assume that page r is referenced in this state.
 

a
d
y
n
a
m
i
c
r
s
t
a
t
i
c

The next state of the stack will have r on top, and a will move somewhere in the part of the stack marked dynamic. Other pages as well in dynamic may move down, but no page will move up (except for the page r, of course).

Let r be in row R. For values of m less than R page r is paged in, and for values of m greater than or equal to R there is no page fault. No page below r will move in the stack. Suppose otherwise: Let page s in row S move. If page s moves up, then for m = S - 1 page s is paged in without being referenced. And, if page s moves down then it would indicate for m = S page s was discarded even when there was no page fault.

Specifically, page a moves down the stack as long as the page b below it is in the dynamic range and  a < b. Once a b is found such that b <= a, then a replaces b in the stack. Page b then moves down the stack until a page c is found such that c <= b is satisfied. Page b replaces c, and the procedure continues until the row vacated by r is encountered. The page that is currently moving down the stack goes in this row, completing the update of the stack.

You might have noticed that I'm breaking a nondeterministic
choice in a systematic manner. One could instead move a down
until a b is found for which b < a holds (rather than until a b is
found such that b <= a holds). Is it important to be systematic?
The second case, in which the referenced page is not in the stack, is handled just like the first case. There is no static part of the stack, however; the procedure continues until a page becomes the last page of the stack.

Here's an example of using the stack for both LRU and Optimal. The first reference to a pages is indicated in fushia, and page that is referenced in the next step is in green. Thus, the pages below green comprise the static part. The blue column on the right counts the number of page faults for the number of page frames indicated by that row (the first row is for one frame, the second for two frames, etc.) The number of page faults is computed by counting the fushia numbers above the row and the number of green numbers below the row.

The reference string:
1 2 3 2 4 3 5 1 3 2 3 5

LRU:
1 2 3 2 4 3 5 1 3 2 3 5 12
1 2 3 2 4 3 5 1 3 2 3 10
1 1 3 2 4 3 5 1 1 2 8
1 1 2 4 4 5 5 1 7
1 2 2 4 4 4 5

Optimal: The most interesting case is the first reference to page 5. Page 5 displaced page 3 from the top. Page 4 doesn't have priority over page 3, and so 3 displaced 4. Pages 1 and 2 have priority over page 4, and so page 4 becomes the last page in the stack.
1 2 3 2 4 3 5 1 3 2 3 5 12
1 2 3 3 4 3 3 1 3 2 2 8
1 1 1 1 1 5 5 5 5 3 6
2 2 2 2 2 1 1 1 5
4 4 4 4 4 4 5

Give it a try for LFU. Once you have tried it, you can compare your result with the solution. (Try to work it out first before looking, though! Most people find applying the stack algorithm more subtle than it first appeared.)