High‐contention mutual exclusion by elevator algorithms
- 17 May 2018
- journal article
- research article
- Published by Wiley in Concurrency and Computation: Practice and Experience
- Vol. 30 (18)
Abstract
Summary: 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 new algorithms are between −5% to 50% slower for maximal contention than the starvation‐free first‐come first‐served hardware‐assisted MCS algorithm, which uses two atomic instructions (fetch‐store and CAS); they are between 10% to 50% slower than MCS for minimal contention.Keywords
Funding Information
- Natural Sciences and Engineering Research Council of Canada
This publication has 17 references indexed in Scilit:
- Progress under bounded fairnessDistributed Computing, 1999
- Shared memory consistency models: a tutorialComputer, 1996
- A first-come-first-served mutual-exclusion algorithm with small communication variablesACM Transactions on Programming Languages and Systems, 1991
- Algorithms for scalable synchronization on shared-memory multiprocessorsACM Transactions on Computer Systems, 1991
- The performance of spin lock alternatives for shared-memory multiprocessorsIEEE Transactions on Parallel and Distributed Systems, 1990
- A method for solving synchronization problemsScience of Computer Programming, 1989
- A fast mutual exclusion algorithmACM Transactions on Computer Systems, 1987
- The mutual exclusion problemJournal of the ACM, 1986
- The mutual exclusion problemJournal of the ACM, 1986
- Solution of a problem in concurrent programming controlCommunications of the ACM, 1965