§6.3Problem #2: Switching Between Processes

The trap machinery of the previous section has one hole: it only gives the OS control when the process asks (a system call) or slips (an exception). If a process is running, then — by definition — the OS is not. And if the OS is not running, it can do exactly nothing. Almost philosophical, and very real:

A cooperative approach: wait for system calls

Some early systems (old Macintosh OS, the Xerox Alto) simply trusted processes: run for a while, then be a good citizen and give the CPU back. Most processes hand over control frequently anyway — every system call does it — and such systems often add an explicit yield() yield A system call that does nothing but hand the CPU to the OS — the cooperative approach's way to share. defined in ch. 6 — open in glossary call whose only job is to transfer control to the OS. Misbehavior also helps: divide by zero or touch bad memory, and the resulting trap gives the OS the CPU (and a process to terminate).

The flaw is easy to spot. What if a process — buggy or malicious — lands in an infinite loop and never traps? In a cooperative world the OS has exactly one recourse, the age-old fix for everything:

A non-cooperative approach: the OS takes control

The answer, discovered decades ago, is beautifully simple: a timer interrupt timer interrupt A hardware timer raising an interrupt every few milliseconds, halting the running process and running an OS handler — how the OS regains control without cooperation. defined in ch. 6 — open in glossary . A timer device raises an interrupt every so many milliseconds; when it fires, the running process is halted by the hardware, and a pre-configured OS handler runs. The OS has the CPU back — free to stop the current process and start another. At boot, the OS registers the timer handler (alongside the syscall handler) and starts the timer — both privileged, naturally. From then on the OS runs user programs with total confidence: control returns within X milliseconds, no cooperation required. (The hardware saves the interrupted program’s state just as it does for a trap — enough that a later return-from-trap resumes it perfectly.)

Saving and restoring context

Control regained (politely via trap, or forcibly via timer), the scheduler scheduler The OS component whose policy decides which ready process runs next, using history, workload knowledge, and metrics. defined in ch. 4 — open in glossary makes its decision: keep running the current process, or switch. If it says switch, the OS runs the context switch context switch The mechanism that stops one program and starts another on a CPU by saving and restoring register state. defined in ch. 4 — open in glossary — conceptually simple: save a few registers of the outgoing process, restore those of the incoming one, so that the eventual return-from-trap lands in the other program. Step through the full protocol:

The subtlest point deserves its own picture: two different register save/restores happen, by two different actors, into two different places —

And because a picture of assembly is worth a thousand words of it, here is the real thing — xv6’s context switch (Figure 6.4). By switching stacks mid-routine, swtch is entered in the context of one process and returns in the context of another:

# void swtch(struct context **old, struct context *new);
#
# Save current register context in old
# and then load register context from new.
.globl swtch
swtch:
  # Save old registers
  movl 4(%esp), %eax # put old ptr into eax
  popl 0(%eax)        # save the old IP
  movl %esp, 4(%eax) # and stack
  movl %ebx, 8(%eax) # and other registers
  movl %ecx, 12(%eax)
  movl %edx, 16(%eax)
  movl %esi, 20(%eax)
  movl %edi, 24(%eax)
  movl %ebp, 28(%eax)

  # Load new registers
  movl 4(%esp), %eax # put new ptr into eax
  movl 28(%eax), %ebp # restore other registers
  movl 24(%eax), %edi
  movl 20(%eax), %esi
  movl 16(%eax), %edx
  movl 12(%eax), %ecx
  movl 8(%eax), %ebx
  movl 4(%eax), %esp # stack is switched here
  pushl 0(%eax)       # return addr put in place
  ret                 # finally return into new ctxt

Figure 6.4: The xv6 Context Switch Code — the old and new context structures live in the two processes’ process structures (the struct context you met in chapter 4).