N-Thread Prioritized Entry
N-thread prioritized entry is a Lamport-style software mutual-exclusion algorithm that extends declare-intent to arbitrary N tasks using a fixed priority ordering. Each task has a priority and checks higher-priority intents before entering, then waits for lower-priority tasks already past their check. It uses only N bits of shared state, one per task.
Why prioritization rather than tickets?
Bakery tickets (the FIFO N-thread solution) need unbounded counters and tie-breaking by task id. Prioritized entry uses a fixed priority order, which compresses state to N bits total. The trade-off: it breaks rule 5 (bounded waiting). High-priority tasks can starve low-priority ones indefinitely.
Algorithm
enum Intent { WantIn, DontWantIn };
_Task NTask { // Lamport, simpler version of Burns-Lynch
Intent * intents;
int N, priority;
void main() {
for ( int i = 1; i <= 1000; i += 1 ) {
// step 1: wait for tasks with higher priority
do {
intents[priority] = WantIn;
for ( int j = priority - 1; j >= 0; j -= 1 ) {
if ( intents[j] == WantIn ) {
intents[priority] = DontWantIn;
while ( intents[j] == WantIn ) {} // back off
break;
}
}
} while ( intents[priority] == DontWantIn );
// step 2: wait for already-declared lower-priority tasks
for ( int j = priority + 1; j < N; j += 1 ) {
while ( intents[j] == WantIn ) {}
}
CriticalSection();
intents[priority] = DontWantIn; // exit protocol
}
}
};Two-step logic
- Step 1 retracts intent if any higher-priority task also wants in, and waits for that task to finish. Then it re-declares intent and re-checks, until no higher-priority task is competing.
- Step 2 waits out any lower-priority task that declared before this one. This prevents a strictly-lower-priority task that already passed its own step 1 from being overtaken.
Properties
- N bits of shared state total, one per task.
- Breaks rule 5: a stream of higher-priority contenders starves lower ones.
- No known N-thread solution satisfies all 5 rules using only N bits. Best known: 3-bit read/write-unsafe, 4-bit read/write-safe.