Scheduler Policy, Timers, and Blocking

By the end of this lesson, you will be able to...

• Compare run-to-completion and round-robin scheduling for a small set of runnable tasks.

• Trace a task through running, blocking, wakeup, and runnable states.

• Explain why checking a condition and going to sleep must form one protected transition.

Idea in one sentence: The scheduler is policy layered over context switching: it chooses only runnable work, while timers and wakeups decide when work becomes eligible again.

calc wants all the CPU it can get. shell needs to respond quickly after each typed character. A third task, reader, is waiting for bytes from a pipe. One CPU cannot run all three at once, so the kernel must make a choice each time the current task yields, blocks, or a timer tick arrives.

The previous lesson made a switch safe. It did not say when to switch, who should run next, or how a task that has nothing useful to do stops consuming CPU time. Those are scheduler design questions. A bad answer can make the shell feel frozen, spin a core while a reader waits for input, or lose a wakeup so a task sleeps forever despite work being ready.

Core Insight

Scheduling has two separate responsibilities:

1. Mechanism: preserve one thread's context and restore another's.
2. Policy: decide which eligible thread receives the CPU and how long it may keep it.

A scheduler normally chooses only from the runnable set. A task that is running already owns the CPU. A task that is sleeping or blocked is waiting for a condition, device completion, or timer; running it would not make its required event happen sooner.

Plain meaning:

The runnable queue is the line for the CPU. A timer asks, “should we give the next person a turn?” A blocked task is not standing in the line; it is waiting for a specific door to open.

In this scenario:

calc and shell can both be runnable. reader is not runnable while the pipe is empty. When a writer supplies bytes, the pipe's wakeup path moves reader back into the runnable set.

Technical name:

The timer interval given to a task is a time slice or quantum. A policy that rotates runnable tasks after each quantum is round robin. A deliberate wait for an event is blocking.

The Naive Policy: Let the Current Task Run Until It Stops

The simplest scheduler runs a task until it yields, blocks, or exits. That works for a batch job with one task. Add calc, however, and a problem appears: it is CPU-bound and may never voluntarily yield. shell has input ready but cannot run. The system is correct in the narrow sense that calc continues, yet it is unusable for an interactive user.

A periodic timer interrupt gives the kernel a preemption point. At each tick, the running task enters the trap path. The kernel may leave it running, or change it to RUNNABLE and select another task. The timer provides an opportunity; policy decides what to do with it.

Round robin is a good first policy because its rule is visible:

keep a queue of runnable tasks
run the next task for one quantum
if it remains runnable, append it to the tail
repeat

This does not promise that every job finishes quickly. It promises that a runnable task is not ignored forever while other runnable tasks take turns, assuming the queue and wakeup rules are correct. More advanced policies may favor latency, deadlines, priorities, or throughput. Their complexity must still preserve the same basic state invariants.

A Task Must Block Instead of Spinning

Suppose reader executes read(pipe, buffer, 16) while the pipe is empty. A naive loop is:

while pipe_is_empty:
    keep checking

This is spinning. It consumes a time slice to discover the same empty state again and again. It also competes with the writer that might make the pipe non-empty.

Blocking changes the arrangement:

acquire pipe state protection
while pipe is empty:
    mark reader SLEEPING on this pipe's wait channel
    release protection and switch away as one operation
when woken:
    re-acquire protection and re-check pipe state
remove bytes
release protection

The while, not an if, is important. A wakeup means “the condition may have changed; check again.” Another reader may consume the bytes first, a timeout may wake the task, or an implementation may permit spurious wakeups. The condition is the truth; the wakeup is only a prompt to inspect it.

Worked Trace: A Reader Blocks, a Timer Preempts, and Data Wakes It

Assume a one-core kernel using round robin with a short quantum. At the start, reader runs, calc and shell are runnable, and the pipe is empty.

Input state:

1. reader observes the empty condition and blocks

While holding the pipe's state protection, reader sees no data. It records itself as waiting on that pipe, changes from RUNNING to SLEEPING, and hands control to the scheduler without leaving a gap where a writer can miss its wait registration.

Intermediate state: reader is absent from the runnable queue. It has a valid saved context from lesson 006, but that context is intentionally ineligible until a pipe event changes its state.

The scheduler now sees a queue like:

runnable: [calc, shell]
sleeping on pipe P: [reader]

2. The scheduler chooses calc, then the timer creates a policy point

Round robin selects calc. It runs until a timer tick traps into the kernel. calc remains runnable, so the kernel saves its context, changes it from RUNNING to RUNNABLE, and places it at the tail of the runnable queue.

The queue becomes:

before tick: [shell]
after returning calc to tail: [shell, calc]

The scheduler selects shell. Notice what did not happen: reader was not chosen merely because it has been waiting a long time. It still lacks pipe data, so its blocking contract says it remains asleep.

3. A writer changes the condition and wakes reader

While shell runs, some producer writes bytes into pipe P. Under the same protection used for the pipe condition, the kernel inserts bytes and identifies tasks waiting on P. It changes reader from SLEEPING to RUNNABLE and enqueues it once.

Now the state is:

runnable: [calc, reader]
running:  shell
pipe P:   non-empty

The wakeup does not resume reader in the middle of the writer. It makes reader eligible. This distinction keeps the writer's shared data consistent and lets the scheduler choose a safe boundary for the actual context switch.

4. The next policy point selects reader

At the next quantum boundary, shell goes to the queue tail if it remains runnable. With round robin, calc and then reader receive turns in queue order. When reader restores its context, it reacquires pipe protection, rechecks that data is available, removes bytes, and returns from read.

Output: reader used no CPU while the pipe was empty, shell received a responsive turn despite calc being CPU-bound, and reader became runnable exactly when its condition changed.

Naive failure contrast: If reader checked the pipe, released protection, and only later marked itself sleeping, a writer could add bytes and look for waiters in that gap. The writer would find none; reader would then sleep even though data is ready. This is a missed wakeup. The condition check and sleep publication must be one protected transition.

Check: A timer tick occurs while reader is sleeping on an empty pipe. Should round robin move it to the runnable queue so every task receives a fair turn?

Think first, then reveal.

Answer: No. Fairness is among runnable work. reader is waiting for a condition, not waiting its turn. Making it runnable would waste CPU and break the meaning of blocking.

Compare Two Policies Under the Same Workload

The context-switch mechanism and state machine can support more than one policy. Compare them with the same calc, shell, and reader workload.

There is no universally fair choice without stating the metric. Round robin treats each runnable task similarly. Strict priority treats importance differently. A throughput-oriented policy may prefer a cache-warm task. A real-time policy may care about deadlines. The design requirement is to name the promise and test the states that can violate it.

The trade-off in quantum length is especially concrete. A shorter quantum improves response time for shell and reduces the longest wait before another runnable task is considered. It also increases trap and context-switch overhead and can reduce cache locality. A longer quantum improves useful work per switch but makes interactive tasks wait longer behind calc. Timers turn this trade-off into an adjustable policy parameter.

Blocking Has a Wakeup Contract

The scheduler owns runnable selection, but the subsystem that knows an event occurred owns the wakeup signal. A pipe write wakes pipe readers; a timer expiration wakes a timed sleep; device completion wakes the request's waiter. The wakeup contract needs at least these rules:

1. A task publishes its wait channel and SLEEPING state while the condition is protected.
2. The event path changes the condition and finds waiting tasks under compatible protection.
3. A wakeup moves a matching sleeper to RUNNABLE at most once.
4. The resumed task rechecks the condition before acting.

These rules prevent missed wakeups, duplicate queue entries, and a task continuing after a condition has been consumed by another task. The implementation needs locks or another synchronization mechanism to enforce them; lesson 009 examines those internal-kernel coordination details. Here, the design boundary is enough: sleeping is state plus a condition, not merely “do not schedule me.”

Common Confusions

Confusion: A timer interrupt always forces a context switch

Why it is tempting:

The timer is introduced as the source of preemption.

Better model:

The timer creates a safe decision point. The scheduler may continue the current task if no other task is runnable or if its policy says to do so.

Confusion: Waking a task means it runs immediately

Why it is tempting:

The event made the task ready, so immediate execution sounds natural.

Better model:

Wakeup changes SLEEPING to RUNNABLE. The scheduler selects when that runnable task receives the CPU, subject to policy and current critical sections.

Confusion: Blocking is just a slower form of spinning

Why it is tempting:

Both wait for a condition to become true.

Better model:

Spinning consumes CPU while checking. Blocking removes the task from the runnable set and requires an event path to restore it, preserving CPU time for useful work.

Practice: Review a Missed-Wakeup Design

Consider this proposed empty-pipe read path:

if pipe_empty(P):
    release(P.lock)
    set current.state = SLEEPING
    schedule()

Write the smallest correction. A strong answer keeps the condition check, wait-channel publication, and transition to SLEEPING coordinated with P.lock (or an equivalent scheduler/condition protocol). The writer must add data and perform wakeup with compatible protection. When the reader resumes, it must re-acquire the lock and check the pipe again in a loop.

Then predict the effect of changing the quantum from 10 ms to 100 ms while calc remains CPU-bound and shell is interactive. The expected answer is not “better” or “worse”: shell can wait longer for a turn, while the kernel performs fewer switches and may retain more cache locality.

Check: The pipe writer wakes reader twice by mistake. What scheduler data-structure failure should the design prevent?

Think first, then reveal.

Answer: reader must not appear twice in the runnable queue. A state transition from SLEEPING to RUNNABLE should be accepted once; a second wakeup must see that it is already runnable or running and avoid creating a duplicate execution claim.

Resources

• [BOOK] xv6 RISC-V textbook — Focus: scheduler state, timer-driven yielding, sleep, wakeup, and the scheduler loop.
• [COURSE] MIT 6.1810 scheduling homework — Focus: yield, sched, scheduler, and the state protected during thread switching.
• [COURSE] MIT xv6 thread-switching lab — Focus: saved contexts and why a runnable task needs a complete continuation.

Key Takeaways

• Context switching is mechanism; selecting among runnable tasks is scheduling policy.
• Timers create preemption points, while blocking removes work that cannot make progress from the runnable set.
• Round robin gives runnable tasks turns, trading response time against switch and locality costs through the quantum length.
• A wakeup makes a task runnable; it does not require immediate execution.
• Condition check, sleep publication, wakeup, and recheck must form a compatible protocol to prevent missed or duplicate wakeups.