Part 7 of 7 · 3 min read
Exercises
Easy
Easy 1: Utilisation (20 minutes)
Tasks (C, T): (1, 4), (2, 8), (3, 12). Give the total utilisation.
Done when: 0.25 + 0.25 + 0.25 = 0.75.
Hint
Add C ÷ T for each task.
Easy 2: RM bound (20 minutes)
Compute n × (2^(1/n) − 1) for n = 2 and 4.
Done when: 0.828 and 0.757.
Hint
2^(1/2) = 1.414 and 2^(1/4) = 1.189.
Easy 3: Which queue design? (20 minutes)
A machine has 64 processors. Which ready-queue design suits it, and why?
Done when: one queue per processor with load balancing, because one shared lock would become a bottleneck.
Hint
Think about who touches the shared list.
Medium
Medium 1: Balance the load (30 minutes)
Jobs 6, 5, 4, 3, 2, 2 (total 22) on two processors, all in the queue of processor 0 at the start. Move jobs to give the best end time and report it.
Done when: a split into 6 + 5 + 2 = 13 and 4 + 3 + 2 = 9, or a better one such as 6 + 5 = 11 and 4 + 3 + 2 + 2 = 11, ending at 11.
Hint
The ideal is half of 22.
Medium 2: Trace RM (30 minutes)
Tasks (C, T): A (1, 3) and B (2, 5). Draw the RM timeline for 15 units and say whether all deadlines are met.
Done when: A 0, 3, 6, 9, 12; B uses the free units; the utilisation 0.733 is under the bound of 0.828, so all deadlines are met.
Hint
B has the lower priority, so it fills the gaps.
Medium 3: Trace EDF (30 minutes)
For the tasks of Medium 2, draw the EDF timeline for 15 units and compare it with RM.
Done when: a timeline with all deadlines met, and a note that on this set it is the same as the RM timeline.
Hint
At each release, compare absolute deadlines.
Hard
Hard 1: Count your migrations (60 minutes)
Run 1, 2, 3 and 4 spinning loops on your machine for 10 seconds, and read se.nr_migrations and se.sum_exec_runtime for each. Explain the pattern in a short paragraph.
Done when: a table with migrations near 0 when loops do not exceed the processors, and more when they do.
Hint
Read the files after the loops have run a few seconds.
Hard 2: Real-time simulator (90 minutes)
Write a simulator that takes periodic tasks (C, T) and a policy (RM or EDF), runs them for one hyperperiod (the least common multiple of the periods), and reports missed deadlines. Check it against the examples of sections 4 and 5.
Done when: RM misses a deadline for (2, 5) and (4, 7), and EDF misses none.
Hint
The hyperperiod of 5 and 7 is 35.
Hard 3: Overload (60 minutes)
Run your simulator on tasks (2, 4), (2, 6) and (3, 8), whose utilisation is above 1. Report which tasks miss deadlines under RM and under EDF, and discuss which behaviour is better for a system with one critical task.
Done when: a table of misses for both policies, with the critical task named, and a reasoned choice.
Hint
Total utilisation is 0.5 + 0.33 + 0.375 = 1.21.