Local-spin group mutual exclusion algorithms

<br><br>
Robert Danek and Vassos Hadzilacos

<br><br>
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.