Part 7 of 7 · 3 min read
Exercises
Easy
Easy 1: Proportional shares (20 minutes)
Share 90 frames among processes of 30, 60 and 210 pages in proportion to their size.
Done when: 9, 18 and 63 frames, with the sum 90.
Hint
Each share is 90 × pages / 300.
Easy 2: Working set by hand (20 minutes)
For the string 3 1 3 2 3 1 4 4 4 1 and Δ = 3, give the working set after the 6th, the 9th and the 10th references.
Done when: {1, 2, 3} (size 3), {4} (size 1) and {1, 4} (size 2).
Hint
Take the last three references up to the time asked, and remove the repeats.
Easy 3: CPU utilisation (20 minutes)
Use the model of section 2 with a fault time of 200 and a fault rate of 0.02. Find the utilisation for 1, 3 and 5 processes.
Done when: 0.20, 0.60 and 1.00, with the last one capped at 1.
Hint
Utilisation is n / (1 + 200 × 0.02), and it cannot exceed 1.
Medium
Medium 1: Decide whether to suspend (45 minutes)
Four processes have working set sizes of 12, 20, 9 and 14 pages, and the machine has 50 frames. Compute D. Say whether a process must be suspended, and show which single suspensions are enough.
Done when: D = 55 is above 50, so one process must be suspended, and suspending any one of the four gives D between 35 and 46.
Hint
Add the four sizes, and subtract one at a time.
Medium 2: PFF decisions (45 minutes)
With bounds of 0.01 and 0.05, say what PFF does for processes with fault rates of 0.08, 0.02 and 0.004.
Done when: give a frame, keep, and take a frame.
Hint
Compare each rate with the two bounds.
Medium 3: Read the counters (60 minutes)
Write a script that reads pgfault, pgmajfault, pswpin and pswpout from /proc/vmstat, waits 5 seconds while you start a large program, reads them again, and prints the rate per second of each.
Done when: a table of four rates, and a sentence on whether the activity was mostly minor faults.
Hint
Use time.sleep(5) in Python, and subtract the first reading from the second.
Hard
Hard 1: Reproduce the collapse (90 minutes)
Write the simulation of section 2. Generate a string with a locality of 20 pages that changes every 3,000 references, and run it with LRU for 100 frames shared by 1 to 10 processes. Print the table of CPU utilisation.
Done when: a table that rises to 1.00 for a few processes and then falls sharply once the frames per process fall below 20, with a sentence that names the cause.
Hint
Use a fixed seed, and average the fault rate over a few seeds.
Hard 2: Working set curve (90 minutes)
On the string of Hard 1, compute the average working set size for Δ = 10, 100, 1,000 and 10,000.
Done when: a table with values near 8, 20, 26 and 80 pages (yours will differ a little), and a sentence on why the size reaches the locality size of 20 at Δ = 100 but climbs again at Δ = 10,000, where the window spans several phases, and how that guides the choice of Δ.
Hint
A set of the last Δ references is enough; a long string may need a sliding counter for speed.
Hard 3: Add load control (90 minutes)
Add the rule of section 3 to the simulation of Hard 1: run only as many processes as fit when each has its working set (20 frames), and keep the rest suspended. Compare the utilisation with 10 processes with and without the rule.
Done when: utilisation near 1.00 with the rule (5 processes run) against about 0.10 without it, and a note on what the suspended processes lose.
Hint
With 100 frames and 20 pages for each process, 5 processes fit.