Local-spin mutual exclusion using fetch-and-Φ primitives

Abstract

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.