Run queues, priorities, and CPU placement ========================================= Runnable work and queue state ----------------------------- A run queue contains threads eligible to execute. Its priority-indexed queues help an implementation choose among them, but a queue is only one part of thread state. The implementation must also coordinate the current thread, accounting, affinity restrictions, and transitions into or out of blocked states. The common primitives are in ``kern_switch.c`` and ``runq.h``. Kernel priority ranges are defined in ``priority.h``; lower numeric values represent higher scheduling priority. Interrupt, realtime, timeshare, and idle treatment must be understood in terms of those ranges and the active scheduler. ULE's per-CPU queues -------------------- Each ULE CPU has a ``tdq`` containing a run queue, a queue lock, load information, a current-thread pointer, and queue-selection state. In this checkout, the single ``tdq_runq`` contains distinct priority ranges used by the realtime, timeshare, and idle selection policies. The source's field annotations distinguish state protected by ``tdq_lock`` from CPU-local state and values that support lockless loads. Those annotations matter when interpreting a load snapshot from another CPU. ULE uses recent sleeping and execution behavior to classify timeshare threads and calculate priorities. Nice values influence non-interactive priority ranges. Timeshare insertion/dequeue offsets and time-slice state control how eligible work rotates through those ranges. Interactive classification and priority inheritance are separate mechanisms. CPU selection combines eligibility and policy: * A thread's cpuset restricts the CPUs on which it can execute. * Bound and pinned state constrain movement for different reasons. * Recent execution, CPU topology, and load influence placement. * Balancing and stealing can transfer eligible work between CPUs. Follow ``sched_pickcpu()``, ``sched_setcpu()``, the ``tdq`` helpers, and the balancing routines together. Queue transfer includes lock and thread-state work; it is not just a change to a CPU-number field. 4BSD's queues and accounting ---------------------------- ``sched_4bsd.c`` maintains ``runq_global`` and, for SMP, per-CPU run queues and associated lengths. Its ``td_sched`` state records estimated CPU use, recent CPU ticks, sleeping time, and remaining slice information. Priority recalculation and decay of CPU-use estimates implement a different timeshare policy from ULE's interactive classification. The shared run-queue primitives do not imply identical placement, fairness, or slice behavior between the implementations. Investigating scheduling behavior --------------------------------- First distinguish a thread that is blocked from one that is runnable but waiting for a CPU. For runnable work, identify the scheduler, scheduling class, effective priority, cpuset, bound/pinned state, and relevant queue. Then compare those observations with the implementation's placement and preemption paths. The ``kern.sched`` controls and the ``sched`` tracing probes are useful entry points. Clock-derived slice values and tunables should be read from the current implementation rather than inferred from a fixed historical quantum. A workload's throughput, wakeup latency, and migration rate measure different aspects of scheduling behavior.