Data Requirements for Implementation of N -Process Mutual Exclusion Using a Single Shared Variable

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;