Publication

Fast mutual exclusion by the Triangle algorithm

Hesselink, W., Buhr, P. & Dice, D. 25-Apr-2017 (Accepted/In press) In : Concurrency and Computation. 28 p.

Research output: Scientific - peer-reviewArticle

Copy link to clipboard

Documents

  • Fast mutual exclusion by the Triangle Algorithm

    Proof, 497 KB, PDF-document

DOI

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
Number of pages28
JournalConcurrency and Computation
StateAccepted/In press - 25-Apr-2017

View graph of relations

ID: 48357390