Mutual Exclusion

Retract Intent

Retract Intent fixes Declare Intent’s deadlock by having a thread temporarily retract its WantIn if it sees the other also wants in. Still breaks rule 4 — now both threads can livelock by retracting in lockstep.

Why doesn't retracting solve it?

Because both threads can play the same symmetric strategy: set WantIn → see conflict → set DontWantIn → wait until the other backs off → try again. If they stay in phase, neither makes progress. Deadlock turned into livelock. The fix is to prioritize who retracts — see Prioritized Retract Intent and eventually Dekker.

Code

enum Intent { WantIn, DontWantIn };
_Task RetractIntent {
    Intent & me, & you;
    void main() {
        for ( int i = 1; i <= 1000; i += 1 ) {
            for ( ;; ) {                      // entry protocol
                me = WantIn;
                if ( you == DontWantIn ) break;   // got in
                me = DontWantIn;              // retract
                while ( you == WantIn ) {}    // wait for other to finish
            }
            CriticalSection();
            me = DontWantIn;
        }
    }
};

Failure mode

Two perfectly-symmetric threads retract and re-declare in sync forever. Making progress requires that somebody commits — which is what priority-based solutions do.

Related

• Declare Intent
• Prioritized Retract Intent
• Dekker’s Algorithm
• Livelock