Arbiter

Create full-time arbitrator task to control entry to critical section. N-Thread Mutual Exclusion

the N-threads communicate with an arbiter to know when to enter the critical section.

In essence

the mutual exclusion problem among N-threads is converted into a synchronization problem between the N-threads and the arbiter.

• In the entry protocol, a thread indicates its intent to enter and waits until the arbiter indicates the start of this thread’s turn.
• The exit protocol retracts intent after exiting the critical section and waits until the arbiter indicates the finish of the thread’s turn.
• The arbiter cycles around the N intent-flags looking for a thread wanting to enter. Once one is found, the arbiter indicates the start of that thread’s turn, and waits for the thread to retract its intent indicating it has exited the critical section.
• The arbiter then indicates the finish of the thread’s turn. Because there are no simultaneous assignments to shared data among the arbiter and N threads, atomic assignment is not required.

Impractical solution

Because the arbiter is continuously busy waiting checking the intent flags even when there is no contention for a critical section.

For $M$ critical sections, there are $M$ arbiters spinning constantly, which can consume a substantial amount of the CPU resource. Any attempt to reduce the arbiter spinning, correspondingly slows entry into the critical section.