Mutual Exclusion

Declare Intent

Declare Intent is a two-thread mutex attempt where each thread publishes a flag (WantIn/DontWantIn) and spins while the other wants in. It breaks rule 4 (liveness) — two threads that both WantIn will deadlock.

Why is this the classic deadlock example?

Because intent is declared before checking — both threads can simultaneously set WantIn, then each sits in its while(you == WantIn){} loop forever. The fix in Retract Intent is: back off and re-declare. The fix in Dekker is: use a tiebreaker (Last).

Code

enum Intent { WantIn, DontWantIn };
_Task DeclIntent {
    Intent & me, & you;
    void main() {
        for ( int i = 1; i <= 1000; i += 1 ) {
            me = WantIn;                      // entry protocol
            while ( you == WantIn ) {}        // spin
            CriticalSection();
            me = DontWantIn;                  // exit protocol
        }
    }
public:
    DeclIntent( Intent & me, Intent & you ) : me( me ), you( you ) {}
};
int main() {
    Intent me = DontWantIn, you = DontWantIn;
    DeclIntent t0( me, you ), t1( you, me );
}

Why it fails

T0 sets me = WantIn; context-switch; T1 sets me = WantIn. Both loop forever on you == WantIn. Deadlock.

Related

• Retract Intent
• Mutual Exclusion Game
• Peterson’s Algorithm