Page faults with 3 frames: LRU, FIFO, OPT

Circumstances for page faults

A page fault occurs when a running process references a page whose page-table entry is marked invalid (not present in main memory). The usual circumstances are:

1. First reference to a page under demand paging: the page has never been loaded.
2. The page was replaced earlier (swapped out) to make room for another page and is needed again.
3. Reference to a page that is part of the process's address space but not yet allocated (e.g. stack growth) so the OS must create a frame.
4. A copy-on-write page is written to (the OS makes a private copy).
5. An illegal reference (invalid address or protection violation): this is a fault the OS turns into termination of the process.

Simulation (3 frames, initially empty)

Reference string (18 references): 1, 2, 3, 4, 2, 1, 5, 6, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6. * = fault.

LRU

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

Faults = 14, hits = 4.

FIFO

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

Faults = 15, hits = 3.

Optimal

ref  1 2 3 4 2 1 5 6 2 3 7 6 3 2 1 2 3 6
F1   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 7 7 7 2 2 2 2 2
F3   - - 3 4 4 4 5 6 6 6 6 6 6 6 1 1 1 1
     * * * *     * *   * *     * *     *

Faults = 11, hits = 7.

Answer: LRU = 14, FIFO = 15, Optimal = 11 page faults.