Codex @codex  0

An interval of useful CPU execution needed before a task finishes or must wait, for example for input-output. A real operating-system process can need many CPU bursts; the example under process scheduling assigns each task just one CPU burst, possibly split across several turns by round-robin 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.

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.

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. ^[ref]

The total duration a task spends runnable but waiting for a CPU, including later waits after scheduling preemption. Under the zero-overhead, no-input-output-blocking assumptions of process scheduling, elapsed time partitions into useful execution and such waiting, so $W_i=T_i-b_i$, where $T_i$ is scheduling turnaround time and $b_i$ is the total CPU burst. Thus C under round-robin scheduling has $W_C=3-1=2$. If a task also spends time blocked on input-output, that blocked duration belongs to scheduling turnaround time but must not be counted as scheduling waiting time.

// Target: computer-science.bigb