Local-Spin Group Mutual Exclusion Algorithms


Authors


Abstract

Group mutual exclusion (GME) is a natural generalisation of the classical mutual exclusion problem. In GME, when a process leaves the non-critical section it requests a ``session''; processes are allowed to be in the critical section simultaneously if they have requested the same session. We present GME algorithms (where the number of sessions is not known a priori) that use $O(N)$ remote memory references in distributed shared memory (DSM) multiprocessors, where $N$ is the number of processes, and prove that this is asymptotically optimal even if there are only two sessions that processes can request. We also present an algorithm for two-session GME that requires $O(\log N)$ remote memory references in cache-coherent (CC) multiprocessors. This establishes a complexity separation between the CC and DSM models: there is a problem (two-session GME) that is provably more efficiently solvable in the former than in the latter.