Page faults: LRU, FIFO, Optimum

Page fault

A page fault is a trap raised when a process refers to a page that is not in main memory. The OS reads the page from disk into a free frame (using a replacement algorithm if no frame is free) and restarts the instruction.

Simulation

Reference string: 1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6 (20 references). The number of frames is not stated; three frames are assumed (all initially empty). * = fault.

LRU

ref  1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
F1   1 1 1 4 4 4 5 5 5 1 1 1 7 7 7 2 2 2 2 2
F2   - 2 2 2 2 2 2 6 6 6 6 3 3 3 3 3 3 3 3 3
F3   - - 3 3 3 1 1 1 2 2 2 2 2 6 6 6 1 1 1 6
     * * * *   * * * * *   * * *   * *     *

Faults = 15.

FIFO

ref  1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
F1   1 1 1 4 4 4 4 6 6 6 6 3 3 3 3 2 2 2 2 6
F2   - 2 2 2 2 1 1 1 2 2 2 2 7 7 7 7 1 1 1 1
F3   - - 3 3 3 3 5 5 5 1 1 1 1 6 6 6 6 6 3 3
     * * * *   * * * * *   * * *   * *   * *

Faults = 16.

Optimum

ref  1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
F1   1 1 1 1 1 1 1 1 1 1 1 3 3 3 3 3 3 3 3 6
F2   - 2 2 2 2 2 2 2 2 2 2 2 7 7 7 2 2 2 2 2
F3   - - 3 4 4 4 5 6 6 6 6 6 6 6 6 6 1 1 1 1
     * * * *     * *       * *     * *     *

Faults = 11.

Result

Answer (3 frames): LRU = 15, FIFO = 16, Optimum = 11 page faults. Optimum is always the lowest; with more frames faults reduce.