Prepare for this assignment by reading
Consider the page reference string:
start with 20 repetitions of the pattern 1
followed by 5 repetitions of the pattern 2 3 4 5 6
followed by 30 repetitions of the pattern 6
followed by 5 repetitions of the pattern 6 5 4 3 2
This string models a four-phase program with three locality sets, {1}, {6} and {2,3,4,5,6}; two of the sets overlap. We are interested in the fault functions F(m), the number of page faults when memory size is (or averages) m, for various memory policies.
|
(1) Find the FIFO fault function, F(m), for m=1,...,6. (2) Find the LRU fault function, F(m), for m=1,...,6. (Use the stack analysis method to calculate the stack distance histogram in one pass. Do not do separate simulations for each memory size.) (3) Does this reference string have any anomalies for FIFO and LRU? Explain carefully. (4) Find the MIN fault function, F(m), for m=1,...,6. (Use the stack analysis method, not separate simulations.) (5) Find the WS fault function, F(T), for T=1,2,...,30 where T is the window size. (Use the stack analysis method for working sets). (6) Find the mean WS size, m(T), for T=2 and T=5. (7) Plot the fault functions for FIFO, LRU, and MIN on the same graph. Show also the two WS operating points, (m(T), F(T)), for T=2 and T=5. (8) You may find that the working-set operating point for T=5 has fewer faults than MIN. Explain how this can be so. (9) Imagine an ideal memory policy, the locality policy. It loads pages on demand. At the end of each phase, it flushes from memory all pages that are not in the next phases's locality set. If we could build a locality policy, how many faults would it produce and what would be its average memory? (10) Compare the locality policy and the WS policy with T=5. |