Categorical Mutual Exclusion
A bathroom can hold N people of the same category but never mix categories. People of category A enter while bathroom is empty or only A's are inside; same for B's. Generalizes Readers-Writers, readers and writers are categories, with N=1 for writers.
The setup
The classic teaching example is a single-category bathroom: a room that can be used by either men or women, but not by both at once. The rules:
- If the bathroom is empty, the first person walks in and "claims" the category. Now it's a "men only" or "women only" room until everyone leaves.
- If somebody of the same category is already inside, you walk straight in. Multiple same-category people can be inside at the same time — there's no per-category capacity here.
- If somebody of the other category is inside, you wait outside until the room empties.
- The room "switches" only after going through empty.
The challenge: write enter(category) and exit() so people of the same category enter freely, people of opposite categories never overlap inside, and nobody busy-waits.
A picture of the lock states
The room is always in exactly one of three states. Same-category arrivals are absorbed in place; cross-category arrivals can only enter from the empty state.
The two important invariants:
- A and B are never inside at the same time. The state machine has no
A_AND_Bstate; the only path betweenA_ONLYandB_ONLYgoes throughEMPTY. - Same-category arrivals never wait if it's already their turn. They self-loop on the active-category state.
The pattern in primitives
Implementing this in code means three pieces:
- A lock to protect the shared state (current category + count).
- A condition variable that waiting threads block on.
- A small predicate evaluated inside the lock: "can I enter? Either the room is empty, or the active category is mine."
When exit() is called and the count drops to zero, the room transitions to EMPTY and the condition variable signals (broadcasts) to all waiters. Waiters re-check the predicate; whichever category gets in first claims the room and wakes up; the other category goes back to waiting.
What this generalizes
Same shape as Readers-Writers — but symmetric Readers-Writers is asymmetric: readers are unlimited; writers are exclusive (capacity 1). Categorical mutex is symmetric: both categories allow many concurrent users, neither has special status. Same lock + condition variable + state machine; one is just a degenerate case of the other.
Generalizes further to N categories, per-category capacity limits, and priority schemes — all with the same primitive structure. Update the predicate, leave the synchronization shape alone.
Where this maps to real systems
- Concurrent garbage collection phases — mutator threads vs. collector threads cannot overlap in stop-the-world or some incremental collectors.
- Database schema migrations — many concurrent readers OR one schema-altering writer, but never both.
- Network virtualization with VLAN isolation — only one tenant's traffic on a shared path at a time.
- A/B test bucket exclusivity — when buckets run different code paths and a single user must not see both.
In every one of these, the design question is the same: what's the "category", and what's the predicate that lets you in?
The starvation gap
Fair-mode is a separate decision The straight implementation above can starve one category. If A's keep arriving faster than they leave, the count never reaches zero, and B's wait forever.
Standard fix: add a "transition pending" flag. Once any B arrives while A's are inside, no new A's may enter — existing A's drain to zero, then the B's go. Trades a bit of throughput for fairness. Exactly the fix that Readers-Writers fair-mode uses.
Why this pattern is worth knowing
The decomposition — state machine + condition-variable signaling on transitions — is the right shape for almost every "modal exclusion" problem. Once you recognize it, you see it everywhere: HTTP/2 stream prioritization, mode-switching display drivers, database isolation-level transitions, JVM safepoint coordination.
Implementations
Track current category and count. New entrant of same category increments count; cross-category entrant waits until count hits 0.
1 import java.util.concurrent.locks.*;
2
3 class CategoricalMutex {
4 private final ReentrantLock lock = new ReentrantLock();
5 private final Condition cond = lock.newCondition();
6 private String current = null; // "A", "B", or null
7 private int count = 0;
8
9 public void enter(String category) throws InterruptedException {
10 lock.lock();
11 try {
12 while (current != null && !current.equals(category)) {
13 cond.await();
14 }
15 current = category;
16 count++;
17 } finally { lock.unlock(); }
18 }
19
20 public void exit() {
21 lock.lock();
22 try {
23 count--;
24 if (count == 0) {
25 current = null;
26 cond.signalAll();
27 }
28 } finally { lock.unlock(); }
29 }
30 }Key points
- •Two states: 'A only', 'B only', or empty
- •Same-category entry is unrestricted (up to capacity if any)
- •Cross-category entry must wait until current category empties
- •Generalization of Readers-Writers, same problem, more symmetric
- •Risk: starvation, if one category keeps arriving, the other never enters