Scheduling and waiting

In outline SlopOS shares CPUs the way Linux does: a timer takes the CPU back from a thread that has had its turn, each CPU keeps its own run queue, and idle CPUs take work from busy ones. A thread waiting in the kernel for a keypress, a packet, a child process or a lock uses no CPU, can't miss the wakeup it is waiting for, and stops waiting if it is killed. What you don't get is fine control over who goes first: there are a few fixed priority levels, ordinary programs can choose between two of them, and nice values are recorded but have no effect yet.

Waiting follows the check-then-sleep order of the Linux kernel's wait_event. The rest of the page covers how threads take turns, how a thread waits without missing what it waits for, and what happens when a waiting thread is killed.

Sharing the CPUs

The scheduler works with tasks, the kernel's name for threads (see Processes and signals). A task is running on a CPU, ready and waiting for a turn, or blocked until something happens.

Time slices and preemption

A timer interrupts each CPU every 10 milliseconds. On each of these ticks the kernel counts down the running task's time slice, which is ten ticks by default. When the slice runs out and another task is ready, the kernel saves the running task's registers, puts it back in line and switches to the next one, whether or not the task ever makes a system call.

Most tasks give the CPU up long before their slice ends because they have to wait for something, and a woken task with a higher priority than the running one takes the CPU at once.

One queue per CPU

Each CPU keeps its own queue of ready tasks, so CPUs don't contend for one shared list every time they switch. The cost is that the queues can get out of balance, which SlopOS corrects in three places. A new process or thread starts on whichever CPU has the least to do. A task that wakes up goes back to the CPU it last ran on, because that CPU's caches probably still hold its data. And a CPU with nothing to run takes a waiting task from any CPU that has at least two more than it does, while every few ticks a busy CPU checks whether it should hand work to a quieter one.

Priorities

Each task belongs to one of five tiers, and a CPU always runs a task from the highest tier that has one ready:

A program picks Normal or Low when it starts another one through spawn, and any other tier is refused. A High task that looped forever would starve everything below it, so the kernel grants High per program, through the same table that grants special permissions. nice and setpriority succeed, but the scheduler ignores the value.

Strict priority on its own would let a busy Normal task keep a Low task from ever running. So the scheduler counts how often each tier has been passed over while it had work waiting, and gives it one turn once that count reaches a small limit. The rule doesn't apply to High or Kernel I/O, because other work depends on them: a background job run ahead of the thread that delivers network packets would stall the network.

How a task waits without using a CPU

Most tasks spend most of their time waiting: a shell for a keypress, a server for a connection, make for its children. Checking over and over (busy-waiting) would burn a CPU on nothing, so a waiting task tells the kernel what it is waiting for and stops running until it happens.

Wait queues

The kernel keeps a wait queue for each thing that can be waited for: data arriving in a pipe, a child exiting, a lock coming free. A task that needs to wait adds itself to the right queue, marks itself blocked and gives up its CPU. Whatever makes the thing happen, such as a writer putting data into the pipe, then wakes the queue, which makes every task on it ready to run again. A woken task checks that what it waited for is there, and waits again if not.

Why a wakeup can get lost

Written in the obvious order, this has a gap. The reader checks the pipe, finds it empty and goes to sleep, but those are two steps, and on a machine with several CPUs, or with preemption, the writer can run between them:

Reader (waits for data)

Writer (provides it)

1

Is there data in the pipe?

No.

2

Write data into the pipe

3

Wake everyone waiting on the pipe

Nobody is waiting yet.

4

Join the wait queue and sleep

The waiter sleeps with data waiting for it, and nothing will wake it.

The writer woke the queue while it was still empty, so the reader sleeps with data sitting in the pipe until something else wakes it, which may be never. This is the lost wakeup, the classic bug in sleeping and waking, and it is hard to find because it needs exactly the wrong timing.

How SlopOS closes the gap

SlopOS reverses the order. The reader joins the queue and marks itself blocked first, then checks the pipe one last time, and only then gives up its CPU.

Reader (waits for data)

Writer (provides it)

1

Is there data in the pipe?

No.

2

Join the wait queue, mark myself asleep

3

Check again

Still no data.

4

Write data into the pipe

5

Wake everyone waiting on the pipe

Finds the waiter, marks it ready.

6

Go to sleep

Already marked ready: carry on instead.

Wherever the write lands, one side sees the other: either the second check finds the data, or the wake finds the waiter.

If the writer adds the data before that last check, the check finds it and the reader cancels its sleep. If the writer adds it after, the reader is already on the queue and marked blocked, so the wake marks it ready, and when the reader then tries to give up its CPU, the scheduler sees that and lets it carry on.

That last step relies on how the kernel stores a task's state. The status (running, ready, blocked) and the reason for blocking share one word of memory, which is only ever changed in a single indivisible step (an atomic compare-and-swap), together with a counter that goes up on every change. So a wake never sees half of a change, and a CPU acting on a stale value finds the counter has moved and reads it again. All blocking in the kernel goes through the same few wait functions, so this order is written once.

When a wait ends early: kills, signals and timeouts

A wait can end without the thing happening, and each place that waits chooses which of these reasons apply:

• The task was killed. Almost every wait ends at once on a kill, which is what lets kill -9 stop a program blocked in a system call.
• A signal arrived. Waits inside a slow system call, such as reading from an empty pipe, also end when a signal arrives that the program handles. The call fails with EINTR, or is restarted if the handler was installed with SA_RESTART (see Processes and signals).
• Time ran out. A wait can have a deadline, as poll with a timeout does.

The kernel's wait functions return either what was waited for or the reason for giving up, and the compiler makes every caller handle both.

One kind of wait ignores kills: waiting for a disk request the device is still working on. Abandoning it could let that old write reach the disk after a newer write to the same place. That wait still has a deadline of a few seconds, so it can delay a kill but not prevent it.

Waiting on many things at once

poll, select and SlopRing wait on many file descriptors at once, which reopens the gap: a wake can arrive after the task has joined one descriptor's queue but while it is still checking the others. So poll first sets a marker in the task's state word. A wake that finds the marker leaves a note there instead of waking a task that is still running, and the task sees the note when it tries to sleep and carries on. The marker carries a short generation number, so a late wake from one poll can't be taken for a wake belonging to the next.

Locks that sleep

Kernel code that holds a lock for a long time, for example across a disk read, uses a lock that sleeps (a Mutex) instead of one that spins. A task that finds it taken spins briefly first, because most locks are released sooner than a sleep and wake would take, and then joins the lock's wait queue. A kill can end that wait but a signal can't, so Ctrl-C never makes a filesystem operation give up half done.

Waiting in user programs: futexes

Threads in a program wait for each other too, and calling the kernel for every lock operation would be slow. So the C library's locks are built on a futex ("fast user-space mutex"): a word of ordinary memory that threads update themselves while nobody has to wait. A thread that does have to wait calls futex(FUTEX_WAIT), meaning "put me to sleep if this word still holds this value". The kernel checks the word and queues the thread under one lock, so the lost-wakeup gap can't open, and FUTEX_WAKE wakes it.

SlopOS supports wait, wake, the bitset variants and requeue, but not the priority-inheritance operations. Futexes work in memory shared between processes even when each maps it at a different address, as PTHREAD_PROCESS_SHARED mutexes and shared semaphores need.

Killing a task that is waiting

Another CPU never tears a task down. Killing a task sets a flag on it and wakes it, in one operation, and the task ends itself: it sees the flag in whatever wait it was in, returns from that wait with "killed", and unwinds its own stack, releasing each lock and buffer on the way. SlopOS used to stop tasks from outside, but from outside nobody knows which locks the task held or what change it was halfway through. When the task unwinds itself, the code that took a lock is the code that releases it. The flag is kept apart from the task's signals, so no signal mask can hide it.

A killed task that is running its own code rather than waiting acts on the flag the next time it passes from the kernel back to that code, at the latest on the next timer tick. A kernel loop that never reaches a wait can't be stopped this way; a forced termination from outside exists only as a last resort at shutdown.

What this means for programs

• Don't busy-wait. A thread blocked in read, poll, futex, waitpid or pthread_cond_wait costs no CPU.
• Expect EINTR from slow calls such as read on a pipe or terminal if you install signal handlers without SA_RESTART.
• Start background jobs at the Low tier with spawn; nice has no effect yet.
• Killing always works, even on a program blocked in the kernel or stuck in a loop: within a tick, or a few seconds for a disk request in flight.

How it is tested

Kernel tests in sched/src/sched_tests.rs cover waits that time out, waits ended by a kill, and the disk wait that must outlast one. Tests in core/src/syscall/tests.rs check that the poll marker refuses a late wake from an old generation, and sched/src/fair.rs has host tests for the aging rule. In userland, spin_signal_test kills a program spinning in a loop and ctrlc_flood_test interrupts a job blocked in a write. just check-sched-spread boots the system and fails if any online CPU can't run tasks.

For contributors

The state word. TaskState (slopos-ostd/src/task/state.rs) is one AtomicU64. Every transition is a compare-and-swap on the whole word, gated on status, and bumps the epoch. A terminal status never moves back to a live one.

Ready means placed. A non-idle Ready task must be somewhere the scheduler will find it: owned by a CPU, in one ready queue, in one remote wake inbox, held by a wake publisher, or in a migration handoff. The idle loop's rescue sweep re-enqueues a stranded task and logs it, but that is a diagnostic backstop; a stranded task is a bug.

The wait order. WaitQueue::wait_core links its node and commits Running -> Blocked under the queue lock, drops the lock, issues a SeqCst fence, then re-checks the condition and the abort probe outside the lock and cancels the block if either holds or the node was already woken. Never evaluate the condition under the queue lock: the condition's own locks would nest inside it and deadlock against a producer that wakes while holding them. Producers publish their state, then take the queue lock and wake. Timed waits sleep in chunks of at most 500 ms and re-check, so a lost wake costs bounded delay.

Wait results. Blocking primitives return WaitResult<R> = Result<R, WaitAbort> (Killed, Interrupted, Timeout, NoRuntime). wait_event_uninterruptible_timeout_until ignores kills and is capped at UNINTERRUPTIBLE_MAX_MS; its one caller is the block engine, and a new caller needs a reason of the same kind. Mutex::lock is killable but not interruptible, and must never be taken from an interrupt handler.

The kill flag. task_kill_and_wake (slopos-ostd/src/task/ops.rs) is the only writer of killed. The syscall exit and every interrupt exit share one delivery point that checks it.

Wake placement and preemption. A wake for another CPU goes into that CPU's remote wake inbox, followed by a reschedule IPI. A woken task preempts the running one if its tier is strictly higher. A wake from an interrupt (a device completing, a sleep expiring) also preempts at equal tier, but a task-to-task wake doesn't, so a futex handoff doesn't bounce two threads on one CPU. CPUs switch straight from task to task without passing through the idle task; Task lifetimes explains why that is safe.

Deferred work and RCU. Work that can't run where it is triggered (destroying a dead task, RCU callbacks) runs at the bottom-half point (slopos-ostd/src/sync/bh.rs): with interrupts on, holding no tracked lock, pinned to its CPU, and never blocking. RCU read-side sections hold a preemption guard. A CPU that never reaches a quiescent state gets a stall warning and is waited for; nothing declares a stalled grace period complete.

Further reading

• Scheduling: Introduction, Multi-level Feedback and Multiprocessor Scheduling, chapters 7, 8 and 10 of Operating Systems: Three Easy Pieces. Start here. Time slices, priorities and starvation (the "boost" there resembles the aging rule here), then per-CPU queues and work stealing.
• Condition Variables, chapter 30 of the same book. The lost wakeup seen from user space, and why a waiter must re-check its condition.
• Kernel Korner: Sleeping in the Kernel by Kedar Sovani, Linux Journal (2005). Linux's wait queues and the order of operations that prevents a lost wakeup.
• Futexes Are Tricky by Ulrich Drepper. How locks are built on futexes and the mistakes that are easy to make doing it. The futex(2) man page is the reference.
• What is RCU? "Read, Copy, Update" in the Linux kernel documentation, for the RCU mentioned under For contributors.
• EEVDF Scheduler, for comparison. Linux's current scheduler weighs tasks against each other instead of using strict tiers; the comment at the top of sched/src/fair.rs says why SlopOS doesn't.

In the source

Task lifetimes covers how run queues and wait queues own the tasks they hold.