§28.12–28.14Too Much Spinning: What Now? … Using Queues: Sleeping Instead Of Spinning

Hardware bought correctness (TAS) and even fairness (tickets) — but every design so far spins, and spinning has a worst case the OS must rescue us from.

28.12 Too Much Spinning: What Now?

Two threads, one CPU: the holder is preempted mid-critical-section; the other thread spins its entire time slice checking a flag that cannot change — the holder isn’t running. With N threads, N−1 time slices can burn this way per incident.

Hardware support alone cannot solve this. We’ll need the OS.

28.13 A Simple Approach: Just Yield, Baby

First idea: when you would spin, yield yield A system call that does nothing but hand the CPU to the OS — the cooperative approach's way to share. defined in ch. 6 — open in glossary instead (Figure 28.8):

void lock() {
    while (TestAndSet(&flag, 1) == 1)
        yield(); // give up the CPU
}

yield() deschedules the caller — running → ready — promoting someone else. For two threads on one CPU it works nicely: the waiter steps aside, the holder finishes. But scale to 100 contending threads: one holder preempted, and the other 99 each run, find the lock held, and yield — 99 context switches per incident, cheaper than 99 slices but far from free. Worse: starvation is untouched — a thread can be caught in an endless run-and-yield loop while others slip through the lock repeatedly. Too much is still left to chance.

28.14 Using Queues: Sleeping Instead Of Spinning

The real problem: the scheduler keeps choosing who tries next. To control succession explicitly we need a queue of waiters, and OS primitives to sleep and wake precisely: park() park Solaris's sleep-a-thread primitive (with unpark(tid) to wake one): the OS support that turns spinning locks into sleeping ones — enqueue yourself, park; the releaser unparks the next waiter, passing the lock DIRECTLY (flag never resets in between). setpark() closes the wakeup/waiting race. defined in ch. 28 — open in glossary (sleep the caller) and unpark(threadID) (wake that one), per Solaris. The lock (Figure 28.9):

typedef struct __lock_t {
    int flag;
    int guard;
    queue_t *q;
} lock_t;

void lock(lock_t *m) {
    while (TestAndSet(&m->guard, 1) == 1)
        ; // acquire guard lock by spinning
    if (m->flag == 0) {
        m->flag = 1; // lock is acquired
        m->guard = 0;
    } else {
        queue_add(m->q, gettid());
        m->guard = 0;
        park();
    }
}

void unlock(lock_t *m) {
    while (TestAndSet(&m->guard, 1) == 1)
        ; // acquire guard lock by spinning
    if (queue_empty(m->q))
        m->flag = 0; // let go of lock; no one wants it
    else
        unpark(queue_remove(m->q)); // hold lock
                                    // (for next thread!)
    m->guard = 0;
}

Step through its three defining moments — including the race that almost breaks it:

Three subtleties, restated. The guard means spinning isn’t gone, just bounded — a few bookkeeping instructions, not a user-defined critical section. The direct handoff (flag never returns to 0 between holder and successor) is a necessity: the woken thread can’t safely re-acquire anything at its wake point. And the wakeup/waiting race — unparked before you park, then sleeping forever — is closed by setpark():

queue_add(m->q, gettid());
setpark(); // new code
m->guard = 0;

(An alternative passes the guard into the kernel, which can then atomically release it and dequeue the sleeper.)