= Process scheduling
<Process scheduling> chooses which runnable <operating-system process> or <software thread> uses a <CPU> next, and when it gives up that <CPU>. Runnable means able to execute now; work waiting for an <input-output> operation is not eligible until that wait ends. A <ready queue> records eligible work. The policy chooses a recipient; a <context switch> supplies the mechanism for transferring execution. Sharing a single <CPU> lets a long calculation and an interactive program both make progress, although only one execution stream runs on that <CPU> at an instant.
Consider three single-<software thread> <operating-system processes> on one <CPU>, with abstract time units, zero <context switch> or scheduler overhead, and no <input-output> blocking. Their arrival times and <CPU bursts> are $(a_A,b_A)=(0,5)$, $(a_B,b_B)=(1,3)$ and $(a_C,b_C)=(2,1)$. Each <CPU burst> is all the execution that its task needs. With <FCFS>, the current task runs to completion: A occupies $[0,5)$, B $[5,8)$ and C $[8,9)$. With <round-robin scheduling> and <scheduling quantum> $q=2$, the intervals are A $[0,2)$, B $[2,4)$, C $[4,5)$, A $[5,7)$, B $[7,8)$ and A $[8,9)$. At a boundary, arrivals join the <ready queue> before the unfinished task whose <scheduling quantum> has expired; this fixes the otherwise ambiguous ordering at time 2.
\Image[/scheduling-fcfs-versus-round-robin.png]
{title=<FCFS> and <round-robin scheduling> share the same nine units of useful <CPU> work differently}
The following triples always list A, B, C. Completion is an absolute time; <scheduling turnaround time>, <scheduling waiting time> and <scheduling response time> are durations measured from the relevant events.
|| Policy
|| Completion times
|| <Scheduling turnaround times>
|| <Scheduling waiting times>
|| <Scheduling response times>
| <FCFS>
| $(5,8,9)$
| $(5,7,7)$
| $(0,4,6)$
| $(0,4,6)$
| <Round-robin scheduling>, $q=2$
| $(9,8,5)$
| $(9,7,3)$
| $(4,4,2)$
| $(0,1,2)$
For example, B first runs at time 2 under <round-robin scheduling>, so its <scheduling response time> is $2-1=1$. It finishes at time 8, giving <scheduling turnaround time> $8-1=7$ and <scheduling waiting time> $7-3=4$. Under <FCFS>, C waits $8-2=6$ before its sole execution interval. Under <round-robin scheduling>, A waits during $[2,5)$ and $[7,8)$, totaling $3+1=4$. Both timelines do exactly $5+3+1=9$ units of useful <CPU> work; changing the order changes who benefits first.
The appeal is that shared progress can improve responsiveness: B and C get their first <CPU> service sooner under <round-robin scheduling>, while A completes later. The <arithmetic mean> of the <scheduling response times> falls from $10/3$ to $1$; the <arithmetic mean> of the <scheduling turnaround times> is $19/3$ for both policies in this particular example. These are different goals, and this workload establishes no universal ranking. Giving each continuously runnable task repeated turns is a practical form of fairness. A smaller <scheduling quantum> can shorten waits between turns, but makes <context switches> more frequent when competitors remain runnable. If each full slice performs $q$ units of useful work and incurs a fixed switching cost $s$, the overhead fraction in that simplified repeated cycle is $s/(q+s)$. Real costs and workloads determine the choice. https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf[Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau, Operating Systems: Three Easy Pieces, chapter 7, sections 7.2–7.3 and 7.6–7.7: metrics, FCFS and round robin]{ref}
Back to article page
