Part 6 of 6 · 3 min read
Exercises
Easy
Easy 1: Waits between turns (20 minutes)
Eight ready processes and a quantum of 5 ms. Give the longest wait between two turns of one process.
Done when: 35 ms.
Hint
Wait = (n − 1) × q.
Easy 2: Useful fraction (20 minutes)
Compute q ÷ (q + s) for a quantum of 2 ms and a switch of 4 µs.
Done when: 2 ÷ 2.004 = 0.998.
Hint
Convert the switch to ms first: 4 µs = 0.004 ms.
Easy 3: Infinite quantum (20 minutes)
What policy results when the quantum is longer than every burst? Check with the table of section 2.
Done when: FCFS, with the quantum-8 row equal to the FCFS figures.
Hint
Compare the quantum-8 row with page 1.
Medium
Medium 1: Trace round robin (30 minutes)
Processes P (arrival 0, CPU 5), Q (arrival 1, CPU 3), R (arrival 2, CPU 1) and a quantum of 2. Give the timeline and the three averages. Use the rule that a new arrival enters the queue before a process whose quantum has just ended.
Done when: timeline P 0 to 2, Q 2 to 4, R 4 to 5, P 5 to 7, Q 7 to 8, P 8 to 9; turnaround 9, 7, 3; waiting 4, 4, 2; response 0, 1, 2.
Hint
At time 2, Q has arrived at 1 and R arrives at 2, so the queue is Q, R, then P.
Medium 2: Count the switches (30 minutes)
For the timeline of Medium 1, count the context switches, and compute the end time if each switch costs 0.25 time units.
Done when: 5 switches and an end time of 9 + 1.25 = 10.25.
Hint
Count the changes of the running process.
Medium 3: Pick the quantum (30 minutes)
A system needs a response of at most 50 ms with 20 ready processes, and wants overhead below 1 per cent with a 20 µs switch. Give the range of quanta that meets both.
Done when: a quantum of at least 2 ms (overhead) and at most 2.6 ms (response, 19 × q ≤ 50 ms), so about 2 to 2.6 ms.
Hint
Overhead = s ÷ (q + s) below 0.01 gives q above about 1.98 ms.
Hard
Hard 1: Measure your slice (60 minutes)
Write the gap-counting program of section 4 and run it with 0, 1 and 3 competitors on one processor (use taskset -c 0). Report the on-CPU run and off-CPU gap for each.
Done when: a table of three rows in which the gap grows about with the number of competitors.
Hint
Use clock_gettime and pin with sched_setaffinity or taskset.
Hard 2: Write a round robin simulator (60 minutes)
Write a program that reads processes (name, arrival, CPU time) and a quantum, and prints the timeline and the three averages. Test it on the workload of section 1.
Done when: averages 10.50, 6.00 and 3.00 for a quantum of 3.
Hint
Keep the queue as an array and add arrivals before re-adding the running process.
Hard 3: Best quantum for turnaround (60 minutes)
Run your simulator on the workload for quanta 1 to 10. Plot or tabulate the average turnaround and response time. Explain why no single quantum minimises both.
Done when: a table for 10 quanta, and a paragraph saying response time rises with the quantum while turnaround does not move steadily.
Hint
Response grows because new processes wait up to one turn of each earlier process.