19 March

The quiz this week will be only on page replacement strategies such as FIFO and LRU. Here are some sample problems with solutions.

Suppose we have a virtual memory system with a logical address space of 5 pages, but a physical memory of just 3 frames. (For this problem, it does not matter how big the pages are.) A process needs to access the following sequence of pages:

0 1 2 3 2 0 2 3 1 4 2 0 2 1 0 2 1

1. How many page faults occur in this sequence using the LRU (least recently used) page replacement policy? Show your work.

       x x x x   x     x x x x   x          10 page faults
       0 1 2 3 2 0 2 3 1 4 2 0 2 1 0 2 1
      -----------------------------------
      .0 0 0.3   3     3 3.2 2   2          The dots show which
       _.1 1 1  .0    .1 1 1.0   0          page was replaced.
       _ _.2 2   2     2.4 4 4  .1

2. Suppose that you expand your physical memory, so that it now contains 4 frames. Still using LRU page replacement, how many page faults occur now?

       x x x x           x   x               6 page faults
       0 1 2 3 2 0 2 3 1 4 2 0 2 1 0 2 1
      -----------------------------------
      .0 0 0 0          .4   2
       _.1 1 1           1   1
       _ _.2 2           2   4
       _ _ 3.3           3  .0

3. Even with expanded memory, the LRU algorithm made one or two bad decisions. How many page faults would occur with 4 frames using an optimal page replacement policy (one that can see into the future)?

       x x x x           x                  5 page faults
       0 1 2 3 2 0 2 3 1 4 2 0 2 1 0 2 1
      -----------------------------------
      .0 0 0 0           0                Looking into future,
       _.1 1 1           1                you see you won't use
       _ _.2 2           2                page 3 again, so
       _ _ 3.3          .4                replace IT with 4.