Split Binary Semaphore
A split binary semaphore (SBS) is a collection of binary semaphores whose summed value is always ≤ 1. At most one semaphore in the collection is ever 1, so at most one task is ever unblocked from the group. Splitting one binary semaphore into many lets you segregate waiters by kind — readers on one, writers on another — while keeping mutual exclusion.
Why split if only one task enters at a time anyway?
Because you get to pick which kind of waiter to release. A single binary semaphore queues FIFO across all kinds; SBS lets the exit protocol say “if writers are waiting, release a writer; else release all readers.” That’s what makes Reader-Writers priority variants possible.
Invariant
∑ semᵢ.value ≤ 1 (always)
Maintain it by construction: every path from P on one sem to V on another sem either stays inside the critical section or passes the baton (see Baton Passing).
Typical skeleton
uSemaphore entry(1), readerQ(0), writerQ(0);
int readers = 0, writersWaiting = 0;
// reader entry
entry.P(); // take the one baton
if ( writer_active || writersWaiting > 0 ) {
// defer — V entry via baton-passing path
readerQ.P(); // blocks; baton arrives here
}
readers += 1;
// pass baton to next reader (cascade) or V(entry)
...When to use
- Any problem with multiple kinds of blocked tasks: writers, full/empty buffers, priority classes.
- Combine with baton passing to prevent barging and enforce priorities.