Abstract
The problem of the mutual exclusion of several independent processes from simultaneous access to a “critical section” is discussed for the case where there are two distinct classes of processes known as “readers” and “writers.” The “readers” may share the section with each other, but the “writers” must have exclusive access. Two solutions are presented: one for the case where we wish minimum delay for the readers; the other for the case where we wish writing to take place as early as possible.
- 1 Dijkstra, E.W. Solution of a problem in concurrent programming control. Comm. ACM 8, 9 (Sept. 1965), 569. Google ScholarDigital Library
- 2 Knuth, D.W. Additional comments on a problem in concurrent programming control. Comm. ACM 9, 5 (May 1966), 321-322. Google ScholarDigital Library
- 3 de Bruijn, N.G. Additional comments on a problem in concurrent programming control. Comm. ACM 10, 3 (Mar. 1967), 137-138. Google ScholarDigital Library
- 4 Dijkstra, E.W. The structure of the "THE"-multiprogramming system. Comm. ACM11, 5 (May 1968), 341-346. Google ScholarDigital Library
Recommendations
On the family of critical section problems
A unified framework is proposed for mutual exclusion, mutual inclusion and such what we call critical section problem.Critical section problem is characterized by a pair of integers.The family of critical section problems is closed under complement ...
Word-Size RMR Tradeoffs for Recoverable Mutual Exclusion
PODC '23: Proceedings of the 2023 ACM Symposium on Principles of Distributed ComputingWe present tradeoffs between RMR complexity and memory word size for recoverable mutual exclusion (RME) algorithms using arbitrary synchronization primitives. Assuming that each memory location stores w bits, we show that n-process mutual exclusion ...
A mutual exclusion algorithm with optimally bounded bypasses
Peterson's algorithm [G.L. Peterson, Myths about the mutual exclusion problem, Inform. Process. Lett. 12 (3) (1981) 115-116] for mutual exclusion has been widely studied for its elegance and simplicity. In Peterson's algorithm, each process has to cross ...
Comments