Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Digital systems, linear algebra, introduction to formal proof / 2

An input-output-bound process spends much of its time waiting for input-output, often with short CPU bursts between waits. A CPU-bound process spends most of its time doing useful CPU computation, with comparatively little blocking. These descriptions concern the bottleneck in the workload; an I/O-bound process still needs CPU time.

With nonpreemptive scheduling, a running process retains the processor until it finishes its current CPU burst, blocks or voluntarily yields. With preemptive scheduling, the operating system may suspend a runnable process and select another one.

Time-slice preemption needs a hardware timer delivering an interrupt after bounded execution time, so control returns to the scheduler even if the running program never yields. Saving and restoring the execution context then lets the interrupted process resume later. The timer mechanism should remain under operating-system control.

Assume both processes are available at time zero and run the listed order, A followed by B, with no overlap even during input-output. A takes $12+4=16$ ms; B then takes $3+4=7$ ms. ThusThe scheduling turnaround time includes the time waiting before a process first runs. Reversing the serial order would leave the total at 23 ms but change completion times to 7 and 23 ms, with mean 15 ms. If arrivals were instead delayed until each serial launch, that would define a different turnaround measurement; the simultaneous-arrival convention is used for comparing the schedulers below.

With the given ready-order rule and A first, the CPU timeline in milliseconds isA performs input-output during $[4,6)$ and $[10,12)$; B does so during $[5,7)$ and $[11,13)$. In particular, B becoming ready at time 7 does not interrupt A's ongoing nonpreemptive burst. The completion times are $C_A=16$ and $C_B=17$, givingThere are 15 ms of useful CPU execution and 2 ms of idle time on this particular timeline.

Use round-robin scheduling with scheduling quantum 2 ms. A's first burst is split by B, and A's second burst is also interrupted once. The resulting CPU intervals areA blocks for input-output during $[5,7)$ and $[12,14)$; B blocks during $[3,5)$ and $[6,8)$. At time 8, B joins the ready queue while A uses the remainder of its current quantum; B runs at time 9. No other process is runnable during A's final four milliseconds, so A can continue across the time-16 quantum boundary. Consequently

The preemptive policy improves B's scheduling turnaround time from 17 to 10 ms and the mean from 16.5 to 14 ms. A finishes later, at 18 rather than 16 ms, and the total completion time rises from 17 to 18 ms. Thus preemption improves mean turnaround here; nonpreemption gives the shorter makespan here.

The result illustrates different scheduling objectives, not a universal winner. These calculations assume negligible context switch overhead; charging for the additional switches could change the comparison. Both policies perform the same 15 ms of useful CPU work.