Fast mutual exclusion by the Triangle algorithm

Willem Hesselink, Peter Buhr, David Dice

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)

Abstract

This paper presents a new starvation-free software algorithm for the N-thread mutual-exclusion problem. In the absence of contention, the algorithm requires only eight write operations and four read operations to enter and leave the critical section; to the best of our knowledge, this is optimal. For algorithms with starvation, seven read and write operations is optimal. In the presence of contention, the algorithm has excellent performance comparable to the best-known software solutions using only atomic load and store, and to a hardware-assisted lock (MCS) using stronger atomic primitives and used within the Linux kernel. It is rare for software-only algorithms for mutual exclusion to perform well for both minimal and maximal contention workloads, making the new algorithm largely self-tuning when exposed to swings in access patterns.
Original languageEnglish
Article numbere4183
Number of pages28
JournalConcurrency and Computation
Volume30
Issue number4
DOIs
Publication statusPublished - 25-Feb-2018

Keywords

  • CONCURRENT PROGRAMMING CONTROL
  • performance experiment
  • software solutions
  • concurrency
  • mutual exclusion

Cite this