CSE Roadmap

Core tier · about 6 hours · 7 parts

Part 3 of 7 · 3 min read

FIFO

In plain words: The simplest rule is first in, first out (FIFO). The kernel keeps the pages in the order in which they arrived, and the victim is the oldest. It is like a queue at a counter: the person who came first leaves first, whatever they are doing there. The rule needs a queue and nothing else. The weakness is that age says nothing about use. A page loaded long ago may be the most used page of all.

The trace below uses S with 3 frames. Each cell lists the frames from the oldest page to the newest. A star marks a fault.

Ref FIFO frames, oldest first
5 5 *
2 5 2 *
4 5 2 4 *
5 5 2 4 (hit)
6 2 4 6 * (5 leaves)
4 2 4 6
6 2 4 6
5 4 6 5 * (2 leaves)
3 6 5 3 * (4 leaves)
6 6 5 3
4 5 3 4 * (6 leaves, though it was just used)
6 3 4 6 *
1 4 6 1 *
1 4 6 1
2 6 1 2 *
3 1 2 3 *
6 2 3 6 *
2 2 3 6

FIFO causes 12 faults in 18 references. The line for the 4 in the middle shows the weakness: page 6 was used in the previous step and was removed because it was the oldest.

A natural hope is that more frames never make things worse. For FIFO the hope is false. Belady's anomaly is the case in which a rule causes more faults with more frames. The string 6 2 1 1 3 6 2 4 6 4 2 5 1 4 shows it:

Frames FIFO faults on 6 2 1 1 3 6 2 4 6 4 2 5 1 4
3 9
4 10

Trace of 3 frames, oldest first, with a star on each fault: 6*, 6 2*, 6 2 1*, hit, 2 1 3*, 1 3 6*, 3 6 2*, 6 2 4*, then hits on 6, 4 and 2 for three references, 2 4 5*, 4 5 1*, and a hit on 4. That is 9 faults. With 4 frames, the faults fall on 6, 2, 1, 3, then 4, 6, 2, 5, 1, 4: ten in all, with hits only on the second 1, on the 6 and 2 that follow the 3, and on the second 4. The extra frame lets old pages stay longer, and that changes which page is the oldest at each step in an unlucky way.

Belady's anomaly

Belady's anomaly is the effect that a page replacement rule causes more page faults when it is given more frames, which FIFO can show and which rules such as LRU and the optimal rule can never show.

Example: on the string 6 2 1 1 3 6 2 4 6 4 2 5 1 4, FIFO causes 9 faults with 3 frames and 10 faults with 4 frames.

Check yourself: 1. Which page does FIFO remove? 2. Why can the page that FIFO removes be one that is used often? 3. How many faults does FIFO cause on the string above with 3 frames?