High-contention mutual exclusion by elevator algorithms

Peter A. Buhr, Dave Dice, Wim H. Hesselink

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)

Abstract

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.

Original languageEnglish
Article number4475
Number of pages29
JournalConcurrency and Computation
Volume30
Issue number18
Early online dateMay-2018
DOIs
Publication statusPublished - 25-Sep-2018

Keywords

  • concurrency
  • mutual exclusion
  • performance experiment
  • software solutions
  • SYNCHRONIZATION
  • COMMUNICATION
  • COMPLEXITY

Cite this