Prioritized Retract Intent
Prioritized Retract Intent fixes Retract Intent’s livelock by asymmetry — only the low-priority thread retracts. Now somebody commits, so the two threads can’t synchronize forever. But rule 5 is broken: the low-priority thread can starve if the high-priority thread keeps re-entering.
Why is priority the right fix — and also not enough?
Priority breaks symmetry, which cures livelock. But fixed priority creates starvation: the high-priority thread can loop through “exit → re-enter” without ever giving the low-priority thread a turn. Dekker fixes this by dynamically swapping who’s the “loser” via
Last.
Code
enum Intent { WantIn, DontWantIn }; enum Priority { HIGH, low };
_Task PriorityEntry {
Intent & me, & you;
Priority priority;
void main() {
for ( int i = 1; i <= 1000; i += 1 ) {
for ( ;; ) { // entry protocol
me = WantIn;
if ( you == DontWantIn ) break;
if ( priority == low ) { // only low-priority retracts
me = DontWantIn;
while ( you == WantIn ) {} // busy wait
}
// HIGH priority does not retract — it waits with WantIn
}
CriticalSection();
me = DontWantIn;
}
}
};Starvation path
HIGH always has me = WantIn while looping. If HIGH finishes its critical section and immediately re-enters, low never sees you == DontWantIn long enough to commit. Rule 5 broken.