Choosing the Next Thread: Policies for Interleaving Exploration
Once SECT can isolate a test domain and ask which eligible task should run next, the scheduler needs a policy for making that choice. This chapter compares the four strategies implemented in SECT—Random Walk, Random Priority, Partial Order Sampling, and Probabilistic Concurrency Testing—by what information each uses and what behavior it induces. The practical question is not which policy is universally best. It is what each policy is willing to remember, what kind of unfairness it accepts, and how those choices change the schedules a kernel campaign can afford to explore.
Four ways to spend a scheduling decision
A scheduling policy is a weight-assignment rule called at the points where SECT regains control. The common machinery supplies the runnable candidates and dispatches the winner; the policy decides how those candidates are ranked. This separation matters because “randomized scheduling” is too broad a description to predict behavior. Two policies can both use random numbers while remembering different histories, responding to different events, and imposing different costs on the tasks that happen not to win.
Random Walk is the simplest baseline. At each scheduling point, it selects the next task uniformly from the enqueued candidates, assigning them equal weight. If there are many candidates, the next choice is likely to differ from the current task, so the policy creates frequent context switches. Its virtue is that it does not permanently privilege a task: over repeated choices, a runnable task is unlikely to be delayed for an extended period. That gives Random Walk a form of probabilistic fairness and makes it a useful default when the framework needs broad variation without a detailed semantic model of the program.
Uniform choice is not the same as useful exploration. A task may be selected repeatedly even when its next event cannot interact with the state changed by another task. Conversely, the one task whose event would expose a bug may be selected too rarely at the critical moment. Random Walk spends decisions without distinguishing those cases. It is therefore easy to extend and relatively easy to reason about, but it treats all runnable candidates as equally informative. Its many switches can also consume execution time that might otherwise be spent generating new inputs.
Random Priority keeps more history. At each scheduling point, it assigns a priority to the most recently executed task and then selects the runnable task with the highest weight. The important difference from Random Walk is that weights for most tasks persist across decisions. A task that receives a low weight can remain disadvantaged for subsequent choices, rather than returning immediately to the same odds as every other candidate. That persistence can create longer, more structured schedules, but it also creates a starvation risk: the policy may keep selecting a subset of tasks while a low-weight task waits.
Persistent weights are useful when exploration benefits from continuity. Repeatedly running a task can carry a state transition farther before another task intervenes, and deprioritizing a task can create a deliberately sparse interference pattern. But persistence also means that the policy’s history becomes a source of bias. If an early choice assigns a task a weight that is unhelpful for the current execution, later scheduling events may inherit the mistake. The policy gains memory without gaining a semantic understanding of whether the remembered preference is still relevant.