park and unpark: building a blocking primitive by hand

Pass a baton around a ring of threads and record the route.

pub fn relay(rounds: usize, threads: usize) -> Vec<usize>

Thread i hands off to thread (i + 1) % threads. Thread 0 starts. Every time a thread receives the baton it appends its own id to a shared log. After rounds * threads hops everyone stops and you return the log.

relay(3, 2) -> [0, 1, 0, 1, 0, 1]
relay(2, 4) -> [0, 1, 2, 3, 0, 1, 2, 3]
relay(3, 1) -> [0, 0, 0]
relay(0, 4) -> []

The output is deterministic by construction of the ring, not by luck: only one thread can act at a time, and which one is fully determined.

No Condvar. Use thread::park and Thread::unpark directly, plus a Mutex for the shared state. And no spinning — a while !my_turn {} loop burns a core and may never make progress on an oversubscribed machine.

Why build this by hand

park/unpark is the layer underneath Condvar, underneath Mutex contention handling, and underneath every async executor’s blocking fallback. Writing a handoff with it is the shortest route to understanding why a future needs a Waker: a Waker is an unpark for a task instead of a thread, and “poll me again” is “your token is available”.

The token model — this is the whole API

Every thread has one boolean token.

• thread::park() — if the token is available, consume it and return immediately. Otherwise block until someone makes it available.
• Thread::unpark() — make that thread’s token available. If it is parked, it wakes.

Three consequences, and each one matters here:

Unpark-before-park is remembered. If you unpark a thread that has not parked yet, the token is stored, and its next park() returns at once. This is why the race between “I decided to sleep” and “you told me to wake up” is not a lost wakeup. It is the single most important property of the API.

There is at most one token. Two unparks do not queue up two wakeups. If your design needs to count wakeups, this is not the primitive.

park() may return spuriously. With no unpark from anyone. So you must loop and re-check the real condition, exactly as with Condvar — the state is the truth, the wakeup is a hint.

It does carry ordering: unpark has release semantics and park acquire, so everything you wrote before unparking is visible to the thread after it wakes.

The starter’s bug

It parks while holding the mutex guard:

let mut g = state.lock().unwrap();
if g.holder != me {
    thread::park();     // asleep, still holding the lock
}

Compiles. Passes clippy. Wedges instantly. The thread falls asleep holding the lock, and the only code that could ever wake it — the current baton holder, who must update the shared state to hand over — needs that same lock first.

This is the guard-lifetime lesson from earlier in this track in its sharpest form. Drop the guard, then park. And notice what that creates: a window between unlocking and parking in which the predecessor may unpark you. Under any other design that would be a lost wakeup; here the stored token makes it safe. That is not an accident of the implementation, it is the reason the API is shaped this way.

The documented rule you must not break

From the std docs, and it is worth quoting because it is unusually strict:

…ensure that a thread is about to park through shared state before unparking it, and do not call unknown code between establishing that state and parking.

Both halves bite. The first means the token is not a message queue — you must be able to tell, from the shared state, whose turn it is; an unpark alone proves nothing. The second is the same rule as “never call unknown code while holding a lock”, for the same reason: something in that call might park internally and eat your token, and then you park forever.

Getting hold of the neighbour’s handle

You need a std::thread::Thread to call unpark on. Two ways:

• thread::current() inside the thread, published into shared state;
• JoinHandle::thread() from the parent, which is easier — spawn everyone, collect the handles, publish them.

Either way there is a publish-before-unpark ordering problem: thread 0 must not start relaying before the handles are visible. A started flag in the same shared state, set by the parent after publishing and followed by an unpark of everyone, is enough. Getting that startup fence right is most of the difficulty of this problem.

If it hangs

A missed handoff blocks forever. Check three things: is the guard dropped before every park()? Does the state say whose turn it is, rather than relying on the unpark alone? And can every thread still see the terminating condition — including the ones asleep when the last hop happened?