We present a generic fetch-and-/spl phi/-based local-spin mutual exclusion algorithm with O(1) time complexity under the RMR (remote-memory-reference) measure. This algorithm is "generic" in the sense that it can be implemented using any fetch-and-/spl phi/ primitive of rank 2N, where N is the number of processes. The rank of a fetch-and-/spl phi/ primitive expresses the extent to which processes may "order themselves" using that primitive. By using an arbitration tree, a /spl otimes/(log/sub r/ N) algorithm can be constructed using any primitive of rank r, where 2 /spl les/ r < N. For primitives that meet a certain additional condition, we present a O(log N/log log N) algorithm, which is time-optimal for certain primitives of constant rank.

We present an N-process local-spin mutual exclusion algorithm, based on nonatomic reads and writes, in which each process performs Θ(log N) remote memory references to enter and exit its critical section. No atomic read/write algorithm with better asymptotic worst-case time complexity is currently known. This suggests that atomic memory is not fundamentally required if one is interested in worst-case time complexity. The same cannot be said if one is interested in fast-path or adaptive algorithms. We show that such algorithms fundamentally require memory accesses to be atomic. In particular, we show that for any N-process nonatomic algorithm, there exists a single-process execution in which the lone competing process executes Ω(log N/log log N) remote operations to enter its critical section. Moreover, these operations must access Ω(√log N/log log N) distinct variables.

We establish a lower bound of 23 N= log log N) remote memory references for N-process mutual exclusion algorithms based on reads, writes, or comparison primitives such as test-and-set and compareand -swap. Our bound improves an earlier lower bound of 34 log N= log log log N) established by Cypher. Our lower bound is of importance for two reasons. First, it almost matches the (log N) time complexity of the best known algorithms based on reads, writes, or comparison primitives. Second, our lower bound suggests that it is likely that, from an asymptotic standpoint, comparison primitives are no better than reads and writes when implementing local-spin mutual exclusion algorithms. Thus, comparison primitives may not be the best choice to provide in hardware if one is interested in scalable synchronization.