CSE Roadmap

Core tier · about 6 hours · 7 parts

Part 7 of 7 · 3 min read

Exercises

Easy

Easy 1: FIFO by hand (20 minutes)

Trace FIFO with 3 frames on the string 1 2 3 1 4 2. Count the faults.

Done when: 4 faults, on 1, 2, 3 and 4.

Hint

The queue order is the order of arrival, and a hit does not change it.

Easy 2: LRU by hand (20 minutes)

Trace LRU with 3 frames on the string of Easy 1.

Done when: 5 faults: 1, 2, 3, then 4 (2 leaves) and 2 (3 leaves).

Hint

On a hit, move the page to the "most recent" end.

Easy 3: Why OPT is a yardstick (20 minutes)

Explain in two sentences why OPT cannot be used in a real kernel, and what it is still good for.

Done when: the answer says that the kernel cannot know future references, and that OPT sets the lowest possible fault count for comparing real rules.

Hint

Think about what "farthest next use" needs to know.

Medium

Medium 1: Four rules on one string (45 minutes)

Trace FIFO, LRU, OPT and the clock with 3 frames on the string 2 3 2 1 5 2 4 5 3 2 5 2. Give the fault count of each.

Done when: FIFO 9, LRU 7, OPT 6 and the clock 8, with all four traces shown.

Hint

Draw the frames after each reference, and mark each fault.

Medium 2: Belady with LRU and OPT (45 minutes)

Trace LRU and OPT on the string 6 2 1 1 3 6 2 4 6 4 2 5 1 4 with 3 and with 4 frames.

Done when: LRU 10 and 7, OPT 7 and 6, so neither rule shows the anomaly.

Hint

For OPT, look at the rest of the string at each fault.

Medium 3: A simulator (60 minutes)

Write a program that reads a frame count and a reference string, and prints the faults for FIFO, LRU and OPT. Test it on S with 3 frames.

Done when: the program prints 12, 10 and 7 for S, and gives 9 and 10 for FIFO on the string of section 2 with 3 and 4 frames.

Hint

Keep a list for the frames, and for OPT search the rest of the string for each page.

Hard

Hard 1: Curves with locality (90 minutes)

Generate a string of 2,000 references over 50 pages in which 80% of the references go to 10 hot pages chosen at random. Plot or tabulate the faults for FIFO, LRU and OPT with 5 to 50 frames.

Done when: a table in which OPT is lowest in every row, the LRU and OPT counts never rise as frames grow, and a sentence on how the gap between LRU and FIFO changes.

Hint

Use a fixed random seed so that the runs can be repeated.

Hard 2: Who wins, FIFO or LRU? (90 minutes)

Use the simulator on S with 2 to 6 frames. State for which frame counts each rule wins.

Done when: LRU wins at 3 frames (10 and 12), FIFO wins at 4 and 5 frames (7 and 8, 6 and 7), and they tie at 2 and 6, with a sentence on why one string cannot settle the question.

Hint

Reuse the counts from section 5 to check the program.

Hard 3: Add the dirty bit (90 minutes)

Mark some references as writes. Extend the simulator so that LRU counts a disk write for each dirty victim, and add a variant that removes the least recently used clean page when one exists among the frames.

Done when: a table of faults and disk writes for both variants on one string, and a note on the trade-off between a few more faults and fewer writes.

Hint

A write marks the page dirty, and a page that is removed becomes clean when it is loaded again.