Yield Points and What Makes a Task Cooperatively Schedulable

A cooperative scheduler runs a task until the task gives up control. There is no timer, no signal, and no instruction counter the runtime can inspect to decide that a task has had enough. Control returns only when the running code explicitly transfers it, and the places where that transfer is legal are fixed when the program is compiled.

That is a weaker guarantee than a preemptive scheduler provides, and it is easy to describe as a limitation. The useful framing is the other way round: the set of yield points defines the runtime’s latency model, and a program’s worst-case response time is decided not by how fast the scheduler is but by how long the longest uninterruptible stretch of code runs.

The three things a yield point must do

A yield point is a program location where the runtime may save the current task’s state, choose another task, and resume it later. For that to be sound, three conditions must hold at the location.

First, the live state must be describable. If the task is stackless, the compiler has already partitioned the function into states and knows exactly which locals are live at each suspend point; the yield point is a numbered resume label. If the task is stackful, the state is the stack, and any point is describable as long as the runtime can unwind and later rewind it, which is why stackful runtimes can yield inside arbitrary calls.

Second, the runtime must be at a consistent point with respect to its own bookkeeping. If the task holds a lock the runtime needs, or sits in the middle of a heap operation, yielding there would let another task observe a half-updated structure. Runtimes handle this either by deferring the switch until the critical section exits or by making the critical sections non-yielding by construction.

Third, the switch must not surprise code that assumed it would not happen. If a task yields while holding a user-visible mutex, another task that takes the same mutex will run and block, which is correct but means a cooperative lock is not a spinlock and cannot be held across a suspension unless the runtime supports it.

The third condition is where most of the practical design lives. A cooperative mutex in a task-based runtime must either record the owning task and suspend the waiter without blocking a carrier thread, or refuse to be held across a yield point at all.

Where checkpoints get placed

The simplest placement is the explicit call. A function named yield, sleep, or await transfers control; nothing else does. This gives the programmer full control and the runtime nothing to verify. It also means a single forgotten call in a library routine turns a task into a monopolist.

The next step is to place an implicit checkpoint at every call that the compiler can see might suspend. In a stackless runtime this is automatic: a function is either suspendable or not, and the type system tracks which is which. Calling a suspendable function from a non-suspendable one is a compile error, so the compiler knows every point where a task can leave.

The strongest placement, and the one used by runtimes that want preemption-like properties without signals, is a check on every loop back-edge and every function entry. The check is a load of a flag and a conditional branch: two instructions on x86-64, and predictable enough that the branch predictor absorbs it in steady state. When the flag says the task’s budget is exhausted, the check calls into the scheduler.

/* A cooperative checkpoint on every loop iteration: one load, one test. */
for (size_t i = 0; i < n; i++) {
    if (__builtin_expect(rt_should_yield(), 0)) {
        rt_yield();                 /* save state, pick next task, return here */
    }
    work(i);
}

The cost of that check is small per iteration and adds up over a tight loop. Runtimes that care about numeric throughput either omit the check from leaf loops the compiler can prove terminate, or make the flag a thread-local that the scheduler writes once per timeslice so the load hits L1.

Latency is the longest run between checkpoints

With checkpoints in place, the scheduler’s response time is bounded by the longest stretch between two of them. That stretch is a property of the code, not the runtime. A task that copies a gigabyte in a loop with a checkpoint per iteration yields often; a task that calls into a C library that sorts an array of ten million elements yields once, at the end, because the library was compiled without checkpoints.

This is the cooperative model’s characteristic failure. The runtime’s scheduling policy can be perfectly fair among tasks that yield and cannot touch a task that does not. With M carrier threads, M non-yielding tasks stop all progress in the runtime, and there is no timeout that helps because the runtime is not running to enforce it.

The mitigations are worth naming because they shape real runtimes. One is to keep the number of carriers above the number of cores so that a pinned carrier does not consume all parallelism; this wastes memory and does not bound latency, only prevents total deadlock. Another is to run suspicious work on a separate thread pool and never on the scheduler’s carriers, which is what an async runtime’s blocking pool does. The third is asynchronous preemption by signal, which converts the model back into a preemptive one at the cost of a signal handler and a delicate resumption protocol.

Fairness among tasks that do yield

Given that every task yields, the scheduler still has to choose. A single ready queue with FIFO order gives round-robin behaviour and O(1) selection, but it makes a task that yields after one unit of work and a task that yields after a thousand units indistinguishable. Measuring work per timeslice requires the runtime to count something, whether instructions retired, allocation events, or checkpoint hits, and to charge each task against a budget.

Charging by checkpoint count is the cheapest and the least accurate: a task that yields inside a loop over a million elements is charged a million times, while a task that calls one function which internally loops without checkpoints is charged once for unbounded work. Charging by wall-clock time requires reading a clock at each checkpoint, which on x86-64 is a rdtsc instruction and costs on the order of tens of cycles; at a checkpoint per iteration that dominates the work being measured.

A workable compromise is a hybrid: count checkpoints, but also read the clock every so often, so that a task which is charged cheaply but runs long is still caught. The design question is what the scheduler does when a task exceeds its budget. Suspending it mid-timeslice requires the state to be savable at the checkpoint, which it is by construction. Simply refusing to run it again until others have had a turn is the weaker option, because it does not help a task that never yields.

The reentrancy hazard

A yield point in the middle of a runtime operation is a reentrancy hazard even when the runtime’s own structures are protected, because user code can observe the interleaving. Consider a task that removes an element from a shared queue, yields, and only then processes it. Another task sees the queue as empty and concludes there is no work, even though an element is in flight. The program is correct in the sense that no memory is corrupted, and wrong in the sense that its liveness assumption was violated.

The standard discipline is that a task must not yield between taking an item and marking it taken. Runtimes enforce this for their own queues by making the dequeue non-yielding; libraries enforce it by documentation. Where the discipline is violated the symptom is not a crash but a stall, and the diagnostic is usually a scheduler trace showing every task waiting on a condition that no task will ever signal.

The same hazard appears in a coarser form at the level of the whole program. A cooperative runtime gives no guarantee that a task runs at all while another is inside a long computation, so a program that depends on a background task to replenish a buffer will eventually find the buffer empty. Bounding that requires either preemption or a discipline of inserting checkpoints into long loops, which is exactly the choice that blocking calls inside an asynchronous runtime faces when a library cannot be changed.

Choosing the model

Cooperative scheduling is worth its constraints when the tasks are numerous and short, when the runtime already controls compilation, and when the code that runs on it is written against the runtime’s rules. It is a poor fit when the workload includes large opaque library calls, when response time must be bounded independently of what any task does, or when third-party code must run on the scheduler’s threads without modification.

The event loop in readiness notification and the single-threaded event loop is the purest instance of the model: every handler yields by returning, and the constraint is stated as a rule rather than enforced. The task scheduler in green threads and user-space switching is the same model with more machinery, and its need for a preemption fallback is the price of admitting arbitrary code.