Data Requirements for Implementation of N -Process Mutual Exclusion Using a Single Shared Variable
James E. Burns, Paul B. Jackson, Nancy Ann Lynch, Michael J. Fischer, Gary L. Peterson · Journal of the ACM · 1982
An analysis is made of the shared memory requirements for implementing mutual excluslon of N asynchronous parallel processes m a model where the only primitive communication mechamsm is a general test-and-set operation on a single shared variable.While two variable values suffice to tmplement simple mutual exclusion without deadlock, it is shown that any solution whJch avoids possJble lockout of processes requires at least 2~ + ½ values A technical restnctmn on the model increases this requtrement to N/2 values, while achieving a fixed bound on wamng further increases the reqmrement to N + 1 values.These bounds are shown to be nearly optimal, for algorithms are exhibited for the last two cases which use [N/2J + 9 and N + 3 values, respectively All of the lower bounds apply afortiori to the space requirements for weaker primitives, such as P and V, using busy waiting Categones and Subject Descnptors D 4 1 [Operating Systems]" Process Management--mutual exclusion; D 4 2 [Operating Systems]' Storage Management F ! ![Computation by Abstract Devices]: Models of Computation, F !.2 [Computation by Abstract Devices]" Modes ofComputaUon--parallehsm, F 2 [Theory of Computation] Analysis of Algorithms and Problem Complexity General Terms Algonthms, Performance, Theory