Mutual Exclusion

Arbiter

Arbiter is an N-thread mutex built from a full-time arbitrator task that polls client intent flags and hands out permission. Mutual exclusion reduces to synchronization between arbiter and clients.

Why spend an entire thread on this?

Because it sidesteps the software-only mutex difficulties. The arbiter never enters the critical section, so there’s no indefinite postponement. It cycles through clients, so no starvation. The downside: it’s a dedicated thread doing continuous busy-waiting — wasted CPU. Good for teaching the pattern (central coordinator), bad as a practical lock.

Code

bool intents[N], serving[N];    // initialize to false
 
_Task Client {
    int me;
    void main() {
        for ( int i = 0; i < 100; i += 1 ) {
            intents[me] = true;                 // entry protocol
            while ( ! serving[me] ) {}          // busy wait
            CriticalSection();
            serving[me] = false;                // exit protocol
        }
    }
};
 
_Task Arbiter {
    void main() {
        int i = N;
        for ( ;; ) {
            do {
                i = (i + 1) % N;                // circular search — no starvation
            } while ( ! intents[i] );           // advance to next wanting client
            intents[i] = false;                 // retract intent on behalf of client
            serving[i] = true;                  // grant entry
            while ( serving[i] ) {}             // busy wait until client exits
        }
    }
};

Properties

• No indefinite postponement — arbiter never uses the critical section.
• No starvation — arbiter cycles through waiting clients (not FCFS — round-robin).
• RW-unsafe due to read flicker.
• Cost — creation, management, and continuous busy-waiting of the arbiter task.

Related

• Mutual Exclusion
• Monitor (a lighter-weight central-coordinator pattern)
• Administrator (task-level arbiter)