Premium
High‐contention mutual exclusion by elevator algorithms
Author(s) -
Buhr Peter A.,
Dice David,
Hesselink Wim H.
Publication year - 2018
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.4475
Subject(s) - mutual exclusion , computer science , thread (computing) , algorithm , critical section , software , parallel computing , concurrency , theoretical computer science , operating system
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.