High-contention mutual exclusion by elevator algorithms

This paper presents new starvation-free hardware-assisted and software-only algorithms for the N-thread mutual-exclusion problem. The hardware-assisted versions use a single atomic-CAS instruction and no fences. The software-only algorithms simulate the CAS instruction using a variation of Burns-Lamport (1 fence) or Lamport's fast algorithm (3 fences). The algorithms are based on Attiya et al, where every thread in the critical section chooses its successor (if one is available). While Attiya et al use a binary tree for this purpose, it can also be done with a linear search. Surprisingly, all software-only algorithms perform equally well under maximal contention on three different computer architectures; the hardware-assisted versions perform better under minimal contention. The newalgorithms are between-5% to50% slower for maximal contention than the starvation-free first-come first-served hardware-assistedMCSalgorithm, which uses two atomic instructions (fetch-store and CAS); they are between 10% to 50% slower than MCS for minimal contention.