Split Binary Semaphore

Baton Passing

Baton passing is a discipline on top of a split binary semaphore that makes entry/exit protocols atomic without a monitor. Intuition: exactly one baton circulates through the system; you can only read or write shared state while holding it, and you “pass” it to the next eligible task by V-ing the semaphore they are blocked on.

Why need a discipline on top of SBS?

Because SBS alone doesn’t prevent barging — a newly arriving task can race past a task being released. Baton passing says: the releaser doesn’t V(entry), they V directly on the waiting task’s queue. The arriving task can’t barge because entry.P() is held by whoever just became ready.

Three rules

1. Exactly one baton. ∑ sem.value ≤ 1. The sum is 1 iff some task is currently at the top of an entry/exit protocol; otherwise 0 (a task is in the CS).
2. Nobody moves without the baton. In entry/exit protocol you must have just completed a P (picked up the baton) or be about to complete a V (pass it).
3. Release before leaving. After V (passing the baton) you cannot read or write any of the entry/exit-protocol variables — the baton is gone.

Canonical example, BinSem via spin lock (Buhr §6.4)

Buhr’s archetype: a binary semaphore whose internal spin-lock is the baton. P picks it up by acquiring the spin-lock; V either releases the spin-lock (drops the baton) or passes it straight to an unblocked task without ever releasing.

class BinSem {
    queue<Task> blocked;
    bool avail;
    SpinLock lock;
  public:
    BinSem( bool start = true ) : avail( start ) {}
    void P() {
        lock.acquire();                     // PICKUP BATON, access state
        if ( ! avail ) {
            // add self to lock's blocked list
            yieldNoSchedule( lock );        // PUT DOWN BATON while yielding
            // unblocks WITH the spin-lock still acquired
            // PASSED BATON, access state
        }
        avail = false;
        lock.release();                     // PUT DOWN BATON
    }
    void V() {
        lock.acquire();                     // PICKUP BATON
        if ( ! blocked.empty() ) {
            // remove task from blocked list, mark ready
            // PASS BATON, do NOT release spin-lock
        } else {
            avail = true;
            lock.release();                 // PUT DOWN BATON
        }
    }
};

The unblocked task in P wakes already holding the spin-lock, so no arriver can barge between the V’s decision and the unblocked task’s continuation.

Why mutex/condition locks can't baton-pass

If the signalled task must re-acquire the mutex lock before continuing, the signaller has to release it first, which opens a race between the signalled task and any new caller, exactly the barging baton passing is meant to prevent.

Canonical cascade (readers)

// exit protocol — I'm the last reader leaving
readers -= 1;
if ( readers == 0 && writersWaiting > 0 ) writerQ.V();  // pass baton to a writer
else                                       entry.V();   // pass baton back to entry

Why this works

• The if/else is executed with the baton in hand (we just did a P), so no one else is reading shared state.
• Exactly one V fires ⇒ exactly one task is unblocked ⇒ SBS invariant preserved.
• The unblocked task, the moment it wakes, has the baton — it’s the only one allowed to touch entry/exit vars.

Related

• Split Binary Semaphore
• Semaphore
• Reader-Writers Problem