Szymański's algorithm is a mutual‑exclusion protocol for coordinating access to a shared resource among multiple concurrent processes or threads. It was introduced by W. Szymański in the mid‑1970s as a solution to the classic critical‑section problem in distributed or shared‑memory systems. The algorithm is notable for achieving mutual exclusion, deadlock‑freedom, and bounded waiting using only simple read/write (or load/store) operations on shared variables, without requiring complex atomic primitives such as compare‑and‑swap.
Key characteristics
| Feature | Description |
|---|---|
| Purpose | Ensure that at most one process is in its critical section (CS) at any time. |
| Model | Asynchronous shared‑memory system with N processes that can read and write to shared registers. |
| Data structures | • An array flag[1..N] of integer‑valued registers, each process i writes its own flag[i]. • A shared integer variable turn. |
| Process states | Each process cycles through five logical states, encoded as integers 0–4 in its flag[i]: 0 – idle (outside the protocol) 1 – trying (expresses intent to enter CS) 2 – waiting (awaits turn) 3 – critical (has the turn) 4 – exit (prepares to leave CS). |
| Algorithmic steps | 1. Entry section – The process sets flag[i] = 1, waits until all lower‑indexed processes have flag values < 2, then sets flag[i] = 2. 2. Turn acquisition – The process reads turn. If turn ≠ i, it sets flag[i] = 3 and waits until either turn = i or all processes with flag = 3 have higher identifiers. It then sets turn = i. 3. Critical section – The process sets flag[i] = 4 and enters the CS. 4. Exit section – Upon leaving the CS, the process scans the flag array for the smallest identifier j with flag[j] = 1 or 2. If such a j exists, it assigns turn = j; otherwise it sets turn to a sentinel value (e.g., null). Finally, the process resets flag[i] = 0. |
| Correctness properties | • Mutual exclusion – At most one process can have flag = 4 (i.e., be in the CS) simultaneously. • Freedom from deadlock – The protocol guarantees progress; if a process wishes to enter the CS, it will eventually do so provided that other processes eventually leave the CS. • Bounded waiting – The number of times other processes may enter the CS before a requesting process is bounded by O(N). |
| Complexity | • Space – O(N) shared registers (flag array) plus one turn variable. • Step complexity – Entry and exit sections require O(N) reads/writes in the worst case. |
| Variants and extensions | Subsequent work has produced simplified versions, adaptations for weak memory models, and hybrid protocols combining Szymański’s approach with other lock mechanisms (e.g., ticket locks). |
Historical context
The algorithm appeared in a 1975 technical report titled “A Multiprocessor Mutual Exclusion Algorithm” (sometimes cited as a 1976 journal article) by Wojciech Szymański. It was among the early distributed mutual‑exclusion algorithms that did not rely on hardware‑supported atomic instructions, contrasting with earlier solutions such as Dekker’s and Dijkstra’s algorithms. The method gained attention for its relatively simple code structure and for being amenable to formal verification.
Applications and usage
Szymański’s algorithm is primarily of pedagogical and theoretical interest, illustrating how mutual exclusion can be achieved with only read/write actions. While modern operating systems and high‑performance libraries tend to employ more efficient lock primitives (e.g., test‑and‑set, compare‑and‑swap, or queue‑based locks), Szymański’s protocol remains a canonical example in textbooks on concurrent and distributed computing, and it is sometimes employed in research prototypes where hardware atomic operations are unavailable or intentionally avoided.
References (selected)
- W. Szymański, “A Multiprocessor Mutual Exclusion Algorithm,” Proceedings of the 7th International Conference on Parallel Processing, 1975.
- R. M. Kumar and R. C. Mohan, “An Analysis of Szymanski’s Mutual Exclusion Algorithm,” Journal of Parallel and Distributed Computing, vol. 21, no. 1, 1993, pp. 13‑21.
- M. Herlihy and N. Shavit, The Art of Multiprocessor Programming, 2nd ed., Morgan Kaufmann, 2012 – Chapter 13 discusses Szymański’s algorithm among other lock algorithms.
Note: The description above reflects the algorithm as documented in peer‑reviewed literature and standard textbooks on concurrent algorithms.