GATE: 1992, Q: 12
Let the page reference and the working set window be c c d b c e c e a d and 4, respectively. The initial working set at time t = 0 contains the pages {a,d,e}, where a was referenced at time t = 0, d was referenced at time t = −1, and e was referenced at time t = −2. Determine the total number of page faults and the average number of page frames used by computing the working set at each reference.
Prerequisite:
Before seeing the solution please follow the previous chapter: Working Set Model
Solutions:
The window size of working set = 4
Initial pages in the working set window = {e, d, a}
Page requested | Time | Working set window | Page fault (Hit/Miss) | Current windows |
e | -2 | {e} | ----- | Preloaded |
d | -1 | {d, e} | ----- | Preloaded |
a | 0 | {a, d, e} | ----- | Preloaded |
c | 1 | {c, a, d, e} | Page fault | 4 |
c | 2 | {c, a, d} | No page fault | 3 |
d | 3 | {d, c, a} | No page fault | 3 |
b | 4 | {b, d, c} | Page fault | 3 |
c | 5 | {b, d, c} | No page fault | 3 |
e | 6 | {e, c, b, d} | Page fault | 4 |
c | 7 | {c, e, b} | No page fault | 3 |
e | 8 | {e, c} | No page fault | 2 |
a | 9 | {a, e, c} | Page fault | 3 |
d | 10 | {d, a, e, c} | Page fault | 4 |
Number of page faults = 5
Now, we are calculating the average frame requirement