A kernel saves every user register before preemption, chooses another process, and restores that process’s user registers. It still crashes. The missing state is the suspended kernel call chain: stack pointer, return address, and preserved registers needed to resume inside the first process’s trap handler. A user trapframe answers “how does this thread return to user code?” A scheduler context answers “how does this kernel thread resume its suspended C execution?” Neither subsumes the other.
Prediction — two continuations
Process enters the kernel on a timer interrupt and calls the scheduler, which runs Name the exact continuation that must be stored for each arrow:
A user → A kernel → per-CPU scheduler → B kernel → B user
HintExpandCollapse
A privilege return and a C return consume different saved program counters.
Worked solutionExpandCollapse
A user → A kernel stores A’s user PC in trap state/trapframe and all user-visible registers in A’s trapframe. A kernel → scheduler stores the return address into the suspended kernel call chain plus A’s kernel SP and callee-saved registers in A’s scheduler context. scheduler → B kernel restores B’s kernel SP/return path, resuming where B last yielded or at its first-run trampoline. B kernel → B user restores B’s trapframe and uses sret. If the answer names one generic PC, it misses two independently nested stacks and return mechanisms.
Ownership model: process is not thread
A useful decomposition is:
| Entity | Owns or denotes | Shared by threads in one process? | Required to resume one thread? |
|---|---|---|---|
| Process | resource container: address space, descriptor table, credentials, limits, process relationships | yes | identity only |
| Thread | one flow of control and scheduling state | no | yes |
| Address space | virtual-to-physical mappings and permissions | normally yes | select or confirm translation context |
| Protection domain | authority boundary enforced by hardware/software | normally yes | identify access rights |
| User stack | user call chain and automatic storage for one thread | no | yes, via saved user SP |
| Kernel stack | privileged call chain while servicing one thread | no | yes, via saved kernel SP |
| Trapframe | full user architectural state at a controlled entry | no | yes for kernel-to-user return |
| Scheduler context | kernel callee-saved continuation across swtch | no | yes for scheduler-to-kernel return |
POSIX defines threads in one process as separate flows of control with per-thread scheduling attributes while memory reachable by address is accessible to all live threads in that process. Thus threads provide concurrency, not mutual protection. A process may contain one thread; the concepts remain distinct because resource and execution lifetimes differ.
Retrieval — classify state after a thread switch
Threads and belong to one process. The kernel switches from to on the same CPU. Classify each item as necessarily changed, possibly changed, or normally shared: page-table root, user SP, kernel SP, descriptor table, signal mask, CPU register file, current-working directory.
Worked solutionExpandCollapse
User SP, kernel SP, and the active CPU register file necessarily change because they encode each thread’s continuation. The page-table root normally remains shared, though an implementation may reload it or use thread-specific mappings. Descriptor table and current-working directory are normally process resources. A POSIX signal mask is per-thread, so it may change. The diagnostic mistake is using “context switch” as shorthand for “replace every process resource.”
Context Switch Save Sets Classification Matrix
Evaluate each statement regarding the differences between the user trapframe and the kernel scheduler context in RISC-V:
Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.
Process state is a global invariant
Xv6 rev5 uses UNUSED, USED, SLEEPING, RUNNABLE, RUNNING, and ZOMBIE. These names encode both lifetime and scheduling eligibility.
Three invariants constrain every transition:
- Exclusive execution: a process is
RUNNINGon at most one CPU, and that CPU’s current-process pointer names it. - Continuation ownership: a non-running process has a saved kernel context sufficient for its next scheduler entry; a running process’s live registers/stack are owned by its CPU.
- Queue/state agreement: every selection data structure agrees with the process state; a sleeping or zombie process is not selectable.
xv6 protects process state and context with p->lock. The scheduler acquires that lock before observing RUNNABLE, changes the state to RUNNING, installs c->proc, and switches while the lock remains part of the handoff protocol. This unusual lock transfer prevents another CPU from selecting the same process during the interval when its execution ownership is moving.
Application — the double-run interleaving
Two CPUs scan the process table. Rewrite the following broken selection as a minimal interleaving that runs process twice:
if (p->state == RUNNABLE) {
p->state = RUNNING;
switch_to(p);
}
Then state the linearization point in a repaired design.
Worked solutionExpandCollapse
CPU 0 reads RUNNABLE; CPU 1 reads RUNNABLE; CPU 0 writes RUNNING; CPU 1 writes RUNNING; both install and restore P’s context. Concurrent stacks/registers then corrupt one logical continuation. In the repaired xv6-style design, acquisition of p->lock serializes the check-and-transition; the successful write RUNNABLE → RUNNING while holding the lock is the selection linearization point. An atomic state compare-and-swap could serialize that field, but it would still need a protocol for context and CPU-pointer ownership.
Why there are two save sets
At user trap entry, arbitrary user code can have live values in every allocatable register. The kernel did not call that code under a C ABI that permits clobbering caller-saved registers. Entry assembly therefore saves the complete user register state needed for transparent resumption.
At swtch(old, new), the compiler emitted an ordinary function call. Under the RISC-V calling convention, s0–s11 and sp must be preserved across calls; the return address determines where the suspended call resumes. Caller-saved temporaries and argument registers need not be saved by swtch: if the C caller needs one after the call, the compiler has already preserved it according to the ABI, often on the kernel stack. Xv6 rev5 stores:
context = { ra, sp, s0, s1, ..., s11 }
swtch has no privileged instruction. It stores the old set through a0, loads the new set through a1, then executes ret. Because ra came from the new context, ret continues the other kernel thread.
Register audit — kill two plausible bugs
For each mutation, predict the earliest reliable failure mechanism rather than a single output string.
- omit
s3from both save and restore; - save
racorrectly but restorespfrom the old context rather than the new.
Worked solutionExpandCollapse
- A suspended C function with a live value allocated to
s3resumes with the next thread’s value. The symptom depends on compiler allocation; force it with assembly or a function that keeps distinct sentinel values live across repeated yields. The failure is an ABI-preservation violation. - Control returns to the new thread’s
rawhile using the old thread’s kernel stack. Returns, spills, and local accesses combine two call chains, quickly corrupting frames or returning through attacker/unrelated data. A test must give stacks distinct canaries and alternate contexts; merely checking that a switch occurred may pass once.
Worked trace: timer preemption of process A
Assumptions: one hart; is in user mode; is RUNNABLE; the timer event is recognized; scheduling policy selects
| Cut | Active execution | Durable user state | Durable kernel continuation | Process state |
|---|---|---|---|---|
| 0 | user registers/stack | none required yet | none; not in kernel | RUNNING, RUNNABLE |
| 1 | trap-entry assembly | trapframe being filled | kernel stack selected | unchanged |
| 2 | timer handler | complete trapframe | live on kernel stack | unchanged |
| 3 | yield() | complete | handler call chain + swtch caller live | RUNNING→RUNNABLE under lock |
| 4 | per-hart scheduler | complete | context now stores SP/RA/s-registers | runnable; CPU owns scheduler context |
| 5 | kernel continuation | trapframe | context restored; kernel stack active | RUNNABLE→RUNNING |
| 6 | user continuation | registers/stack restored | kernel continuation remains latent | running in user mode |
There is no direct swtch(A, B) in xv6. switches to the per-CPU scheduler context; the scheduler later switches to This coroutine structure centralizes policy and maintains a scheduler stack not owned by either process.
Trace calculation — count transitions, not names
Starting at cut 0, count (a) privilege transitions, (b) swtch calls, and (c) address-space changes needed before reaches user mode in xv6 rev5. State assumptions.
HintExpandCollapse
A context switch and a privilege transition are independent events.
Worked solutionExpandCollapse
There is one U-to-S transition on A’s timer trap and one S-to-U transition on B’s eventual sret: two privilege transitions. There are two swtch executions: A-to-scheduler and scheduler-to-B. xv6’s user trap entry switches from A’s user page table to the kernel page table, and B’s return switches from the kernel page table to B’s user page table: two satp installations, with required fences in the trampoline. A path that resumes B already inside the kernel still needs only the first page-table switch until B returns. The count depends on the explicit starting/ending cuts and xv6’s mapping design.
Worked trace: blocking read and wakeup
Assumptions: calls a pipe read when the pipe is empty but still has a writer; later writes data.
- holds
pi->lockand observesnread == nwrite && writeopenin rev5piperead. - calls the combined
sleep(&pi->nread, &pi->lock). Insidesleep(chan, lk), it acquires A’sp->lockbefore releasingpi->lock, then recordschanand changesRUNNING→SLEEPING. A writer cannot complete a matchingwakeupthrough the gap: after acquiringpi->lock, it must also acquire A’sp->lockbefore changing A’s state. sleepcallssched()while holding A’sp->lock. The user trapframe remains unchanged; the saved kernel context now resumes after thatsched()call.- acquires
pi->lock, writes bytes, and callswakeup(&pi->nread).wakeupacquires A’sp->lock, changesSLEEPING→RUNNABLE, and releases it. Wakeup establishes eligibility; it does not run A. - A scheduler eventually selects
swtchreturns insidesleep; A clearschan, releases itsp->lock, reacquirespi->lock, returns topiperead, and reevaluates thewhilepredicate. - The read copies available bytes through rev5’s checked
copyout, releases the pipe lock, and the trap-return path resumes A after the system call.
The context switch preserves control; the predicate protocol preserves meaning. A perfect register save cannot repair a lost wakeup.
Transfer — wakeup is not execution
Why is changing SLEEPING → RUNNING in wakeup() unsafe on a multicore kernel, even if an idle CPU exists?
Worked solutionExpandCollapse
RUNNING asserts ownership by one CPU and requires a restored live context and consistent per-CPU current pointer. wakeup() only establishes eligibility; it has not selected a CPU, acquired a scheduler context, or performed a switch. The correct transition is to RUNNABLE, after which the scheduler’s serialized selection establishes execution ownership. Direct dispatch is possible in another design, but it must perform the full ownership protocol rather than relabel state.
Boundary cases that expose false equivalences
| Claim | Counterexample | Correct distinction |
|---|---|---|
| “Every system call context-switches.” | A fast getpid can enter and return to the same thread without scheduling another. | mode switch is not scheduling switch |
| “Every context switch changes processes.” | Two threads in one process share its address space/resources. | thread switch need not replace process state |
| “Every process switch flushes all translation state.” | Tagged TLBs/ASIDs can retain entries; kernel designs differ. | logical address-space switch is not necessarily a full hardware flush |
| “A blocked thread consumes no resources.” | It retains stacks, descriptors, mappings, and wait metadata. | not running is not nonexistent |
| “A zombie is still schedulable because it has a process slot.” | A zombie retains exit status for its parent but has no executable continuation. | lifetime state is not eligibility |
Counterexample — copying a process structure
A kernel implements fork by byte-copying its entire process structure, including the spinlock, kernel stack pointer, and scheduler context. Explain at least three independent failures.
Worked solutionExpandCollapse
The copied lock may appear held by a nonexistent owner or duplicate internal wait state. The kernel-stack pointer aliases the parent’s stack, so parent and child corrupt one call chain. The scheduler context resumes at the parent’s suspended kernel PC with parent-specific stack/register assumptions rather than a controlled child-first-return path. Descriptor objects also need reference-counted duplication rather than arbitrary pointer ownership. Correct creation copies selected semantics and constructs fresh synchronization/execution state.
Deep Practice
Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.
Exercise 2.1.1: Classifying Thread-Private Continuations vs Process-Shared Resources
In a multi-threaded Unix environment, classify which architectural and operating-system resources must be swapped during a thread switch within the same process versus a full process context switch across distinct address spaces.
HintExpandCollapse
Determine which registers and memory structures define an execution continuation versus an address space.
Worked solutionExpandCollapse
During a thread switch within the same process, the kernel swaps only thread-private execution state: the kernel stack pointer (sp), user stack pointer, architectural CPU register file (callee-saved registers in cooperative switches, or full trapframe in preemptive switches), thread-local storage base pointers, and thread-specific signal masks. The virtual address space (satp root page table), open file descriptor table, current working directory, and shared memory segments remain unchanged. During a full process context switch, the kernel additionally reloads satp (flushing or tagging TLBs with ASIDs), switches process credential contexts, and points to a distinct descriptor table.
Exercise 2.1.2: C ABI Invariants in Context Switching vs Asynchronous Traps
Explain why the kernel swtch(&old->context, &new->context) assembly routine on RISC-V saves only callee-saved registers (ra, sp, s0..s11), whereas the user-to-kernel trapframe must save all 31 general-purpose registers.
HintExpandCollapse
Contrast the caller/callee contract of a standard C function call with an arbitrary asynchronous interrupt.
Worked solutionExpandCollapse
The swtch() routine is invoked as a standard C function call by the kernel scheduler. According to the RISC-V calling convention (ABI), the compiler automatically generates code to spill any caller-saved temporary registers (t0..t6, a0..a7) that contain live values across the call onto the thread kernel stack. Thus, swtch() only needs to preserve callee-saved registers to restore the C execution context. In contrast, an asynchronous user trap (such as a timer interrupt) can strike at any arbitrary instruction boundary where any or all of the 31 user registers hold live values; the kernel has no compiler guarantees and must save every user register to preserve transparency.
Exercise 2.1.3: Multicore Mutual Exclusion and Double-Execution Prevention
Consider a multicore system where two idle CPU cores run scheduler() loops concurrently. State the exact locking invariant and state transition linearization point that prevents both cores from selecting the same RUNNABLE process and executing it simultaneously on two CPUs.
HintExpandCollapse
Analyze the atomic state check and lock acquisition in xv6 proc.c scheduler loop.
Worked solutionExpandCollapse
The invariant is: No process struct can have state RUNNING on more than one CPU, and a thread kernel stack can be active on at most one CPU core simultaneously. To linearize selection, the scheduler on each CPU acquires the candidate process lock (acquire(&p->lock)), checks if (p->state == RUNNABLE), updates p->state = RUNNING, and calls swtch() while still holding p->lock. The newly scheduled process releases p->lock only after running on the new CPU core. Any competing CPU scheduler attempting to acquire p->lock spins until the state transition to RUNNING is complete, whereupon it observes p->state != RUNNABLE and skips it.
Exercise 2.1.4: Execution Trace of Blocking Pipe Read and Waiter Wakeup
Trace the process state transitions, queue manipulations, and context switches when Process blocks reading an empty pipe, Process writes data to the pipe, and Process is subsequently scheduled and completes its read.
HintExpandCollapse
Trace the lock handoff between pipe lock and process lock during sleep() and wakeup().
Worked solutionExpandCollapse
- Process acquires the pipe lock, discovers the pipe buffer is empty, and calls
sleep(&pipe->nread, &pipe->lock). - Inside
sleep(), acquiresa->lock, releasespipe->lock, updatesa->state = SLEEPING, records the channela->chan = &pipe->nread, and callssched()to switch context to the per-CPU scheduler. - The CPU scheduler releases
a->lockand schedules another process. - Process runs, acquires
pipe->lock, copies bytes into the pipe buffer, and callswakeup(&pipe->nread). wakeup()scans the process table, acquiresp->lockfor each sleeping process, and upon matchingp->chan == &pipe->nread, updatesp->state = RUNNABLEand releasesp->lock.- Later, an idle CPU scheduler acquires
a->lock, observesa->state == RUNNABLE, setsa->state = RUNNING, and switches context to - resumes inside
sleep(), re-acquirespipe->lock, releasesa->lock, reads the newly written bytes from the buffer, releasespipe->lock, and returns to user space.
Exercise 2.1.5: Failure Modes of Direct Struct Byte-Copying in Fork Implementation
A junior operating systems engineer attempts to optimize fork() by executing a raw memory copy (memcpy(child_proc, parent_proc, sizeof(struct proc))). Detail three catastrophic failure modes that manifest during execution.
HintExpandCollapse
Identify synchronization objects, stack pointers, and kernel continuations that cannot be aliased.
Worked solutionExpandCollapse
- Lock corruption and deadlock: The copied spinlock (
child->lock) inherits the locked/unlocked state and holder ID of the parent. If copied while held or contended, the child lock is poisoned, leading to deadlocks or assertion panics in the scheduler. - Kernel stack aliasing: The child struct inherits the parent kernel stack pointer (
sp). When the child runs, its push and pop operations overwrite active stack frames of the parent, resulting in immediate kernel call chain corruption. - Scheduler continuation aliasing: The child inherits the parent scheduler context (
context.raandcontext.sp). Rather than returning through the dedicatedforkretentry point that prepares a fresh user trapframe return, the child resumes at the parent suspended kernel continuation with parent-specific local variables.
Exercise 2.1.6: Designing Context Switching for Multi-Threaded Processes with Migration
Design the context switch protocol for a multi-threaded kernel supporting multiple kernel threads per address space and core migration. Detail when satp must be reloaded, how thread-local register state is managed, and how migration across cores preserves cache and TLB consistency.
HintExpandCollapse
Check whether incoming and outgoing threads share the same page table root to optimize MMU reloads.
Worked solutionExpandCollapse
- Address space check: The context switch routine inspects
prev->proc == next->proc. If both threads belong to the same process, reloadingsatpand issuingsfence.vmais bypassed, eliminating unnecessary TLB invalidation overhead. If switching across distinct processes,satpis updated tonext->proc->pagetableand an address-space-tagged TLB sync is executed. - Thread-local state: The user thread-pointer register (
tpor thread-local base CSR) is restored fromnext->trapframe->tp. - Migration safety: If a thread migrates from CPU to CPU CPU acquires
thread->lockbefore switching. The release fence in the lock ensures all stores from CPU are visible to CPU Lazy floating-point/vector registers must be explicitly saved from CPU hardware registers before allowing CPU to activate the thread.
References & Further Reading
- MIT PDOS, xv6: a simple, Unix-like teaching operating system, Chapter 7.
- MIT PDOS, xv6 rev5
kernel/proc.h,kernel/proc.ccombined sleep/wakeup path,kernel/pipe.cread path,kernel/swtch.S, andkernel/trap.c. - RISC-V International, RISC-V ABIs Specification, integer register convention (CC BY 4.0).
- The Open Group, POSIX.1-2024 Base Definitions, definition of a live thread.
- The Open Group, POSIX.1-2024
read(), empty-pipe blocking and EOF behavior.