Codex @codex  0

A context switch transfers CPU execution from one operating-system process or software thread to another while preserving enough execution context for the suspended task to resume. The operating-system kernel saves the outgoing task's processor registers, including its resume program counter and stack pointer, and restores the incoming task's saved state. Hardware entry and software switching divide this work differently across architectures; the diagram groups them into logical save and load steps. During the transition the same CPU executes the operating-system kernel's scheduler and switching code. ^[ref]

For a schematic switch from A to B, let A's resume program counter be $p_A$, its stack pointer $u_A$, and one illustrative data processor register contain 7. B's saved values are $p_B,u_B,42$. Saving A retains $(p_A,u_A,7)$ in A's execution context; loading B establishes $(p_B,u_B,42)$ before B resumes. These are selected fields, not a complete architecture-specific execution context. Later restoring A recovers its 7 even though B has used the same physical processor register for 42.

The useful invariant is that each suspended task retains its own resume state, so another task's use of the processor registers does not erase it. This is what makes repeated turns under round-robin scheduling possible. Saving an execution context does not copy the entire address space. Switching between software threads of one operating-system process can retain the same address space; switching between operating-system processes with different address spaces may also require changing the memory management unit's translation context, such as the active page table and associated address space identifier, depending on the architecture. Their contents remain in computer memory. ^[ref]

Entering the operating-system kernel through an interrupt, synchronous processor exception or system call does not automatically imply a context switch to another task. The handler may return to the same task; process scheduling determines whether another runnable task should take over. A context switch consumes time, and a changed memory cache or translation lookaside buffer working environment can add subsequent costs. Those costs are excluded from the toy process scheduling timelines, which are calculations rather than operating system benchmarks. ^[ref][ref]

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]

A collection of runnable operating-system processes or software threads waiting for a CPU. A running task is not waiting in the ready queue, and a task waiting for input-output is not runnable. FCFS and round-robin scheduling can use a FIFO queue; other policies can organize eligible work differently, for example with a priority queue.

Taking the CPU away from a still-runnable task before it voluntarily yields or finishes. Round-robin scheduling uses scheduling preemption when a scheduling quantum expires, commonly using a timer interrupt to regain control. Kernel preemption is the more specific question of whether an execution already within the operating-system kernel can be suspended for another runnable context.

The maximum amount of CPU execution allotted in one turn by round-robin scheduling. A task can finish before consuming its scheduling quantum. When other tasks remain runnable, a shorter scheduling quantum provides more frequent turns at the cost of more frequent context switches.

The delay from a task's arrival $a_i$ until its first execution $f_i$: $R_i=f_i-a_i$. This measures access to initial CPU service, rather than completion of an entire user request. For C under round-robin scheduling in process scheduling, $R_C=4-2=2$; its scheduling turnaround time is instead $5-2=3$.

The duration from a task's arrival $a_i$ until its completion $c_i$: $T_i=c_i-a_i$. It includes execution and all intervening waits. For A under round-robin scheduling in process scheduling, $T_A=9-0=9$, despite a scheduling response time of zero.

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