Context switching

Why it exists

One CPU can run only one process at a time, yet the operating system keeps several programs in progress. It does so by giving the CPU to a process for a while, then taking it away and giving it to another, and later giving it back to the first so that it continues exactly where it stopped. For that to work the system must save everything the process needs to continue and load the same for the next one. This is the context switch. It is the basic mechanism of multiprogramming and time sharing, and, since it does no useful work for any program, its cost sets the limit on how short a time slice can be. GATE asks for the steps, the triggers, the information saved and the CPU efficiency of a scheduler with a switching cost.

Prerequisites

You need the PCB and the process states from the process model; a context switch is the move between the Running and Ready states described there.

Precise definitions

Context. All the state of a process that must be restored for it to continue: the program counter, the processor status register, the general registers (and floating-point registers), the stack pointer, the memory-management state (the page table base register or the base and limit registers) and the kernel's record of it, which is the PCB.

Context switch. Saving the context of the running process in its PCB and loading the context of the next process from its PCB. It happens in kernel mode.

Steps (the animation follows exactly these):

1. An interrupt or system call enters the kernel; the hardware saves the PC (and status) of the old process on the kernel stack.
2. The kernel saves the old process's registers and other state in its PCB and changes its state (to Ready if preempted, to Waiting if it blocked, to Terminated if it ended).
3. The scheduler chooses the next process.
4. The kernel restores the new process: it loads its page table base (changing the address space) and its registers from its PCB, and sets its state to Running.
5. A return from the interrupt resumes the new process at the saved program counter.

What triggers a context switch.

• The timer interrupt ends the time slice (preemptive round robin, and generally preemptive scheduling).
• The running process blocks (an I/O request, waiting for a lock, wait).
• A higher-priority process becomes ready, for example when its I/O completes (preemptive priority scheduling).
• The process yields the CPU voluntarily or terminates.

Dispatcher and scheduler. The scheduler decides which process runs next (a policy). The dispatcher is the part of the kernel that actually gives the CPU to that process: it does the context switch, switches to user mode and jumps to the right location. The time it takes from stopping one process to starting another is the dispatch latency.

Overhead. A context switch is pure overhead: no user program makes progress during it. Its time depends on the number of registers to save, the memory-management work (loading the page table pointer), and the indirect costs: cached translations and cache contents of the old process become useless for the new one. If the TLB is not tagged with a process id, it must be flushed at each switch and the new process starts with a cold TLB (TLB). Some hardware reduces the cost with several register sets, so that a switch only changes which set is current.

Mode switch versus context switch; process switch versus thread switch. A system call or an interrupt changes the mode but need not change the process. Switching between two threads of the same process leaves the address space unchanged, so no page-table change and no TLB flush is needed, which makes it cheaper than a switch between processes.

Efficiency with a time slice. If a round-robin system gives each process a time quantum $q$ and a context switch costs $s$ (and nothing else is lost), then

$\text{useful fraction} = \frac{q}{q + s}, \qquad \text{overhead fraction} = \frac{s}{q + s}.$

A very small quantum makes the system responsive but spends most of the time switching; a very large one is efficient but approaches first-come first-served.

How it works

The first animation switches the CPU from process A to process B. Follow the PCBs (memory rows 100 to 105 for A and 200 to 205 for B): A's registers are copied out into its PCB one by one, A becomes Ready and B Running, the page table base register changes to B's page table, then B's saved registers are loaded and the return from interrupt starts B at its own saved PC.

The second animation is a switch between two threads of the same process. Only the PC, SP and R0 are exchanged. The page table base register stays at 7000 throughout: that is why a thread switch is cheaper.

Worked examples

#include <stdio.h>
 
int main(void) {
    /* round robin with a context switch costing s ms after every quantum of q ms */
    double s = 1;
    double qs[4] = {1, 4, 10, 100};
    for (int i = 0; i < 4; i++) {
        double q = qs[i];
        printf("q = %5.0f ms, switch %.0f ms: %5.1f%% of the CPU time is useful, %5.1f%% is overhead\n", q, s, 100 * q / (q + s), 100 * s / (q + s));
    }
    /* a process needing 50 ms of CPU, quantum 10 ms: 5 quanta, the last one ends the process */
    int need = 50, q = 10;
    int slices = (need + q - 1) / q;
    printf("a %d ms burst with q = %d ms needs %d slices\n", need, q, slices);
    return 0;
}

q =     1 ms, switch 1 ms:  50.0% of the CPU time is useful,  50.0% is overhead
q =     4 ms, switch 1 ms:  80.0% of the CPU time is useful,  20.0% is overhead
q =    10 ms, switch 1 ms:  90.9% of the CPU time is useful,   9.1% is overhead
q =   100 ms, switch 1 ms:  99.0% of the CPU time is useful,   1.0% is overhead
a 50 ms burst with q = 10 ms needs 5 slices

Cheat box

Traps and GATE patterns

Connections

The PCB and states being switched are in the process model and process states. The choice of who runs next is the round-robin and priority scheduler. A system call is a mode switch; a thread switch avoids the address-space change; the cost of the translation cache after a switch is the topic of the TLB.

PYQs

Consider a process P running on a CPU. Which one
or more of the following events will always trigger a
context switch by the OS that results in process P
moving to a non-running state (e.g., ready, blocked)?

Which one or more of the following need to be
saved on a context switch from one thread (T1) of
a process to another thread (T2) of the same process
?

Consider four processes P, Q, R, and S scheduled
on a CPU as per round robin algorithm with a time
quantum of 4 units. The processes arrive in the
order P, Q, R, S, all at time t = 0. There is exactly
one context switch from S to Q, exactly one context
switch from R to Q, and exactly two context
switches from Q to R. There is no context switch
from S to P. Switching to a ready process after the
termination of another process is also considered a
context switch. Which one of the following is NOT
possible as CPU  burst time (in time units) of these
processes?

Let the time taken to switch between user and
kernel modes of execution be t1 while the time
taken to switch between two processes be t2. Which
of the following is TRUE?

Consider three CPU-intensive processes, which
require 10, 20 and 30 time units and arrive at times
0, 2 and 6, respectively. How many context
switches are needed if the operating system
implements a Shortest Remaining Time First
(SRTF) scheduling algorithm?

Do not count the context switches at time zero and
at the end.

Self-check

Revision card

References