Fast mutual exclusion by the Triangle algorithm

다국어 초록 (Multilingual 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 and four read operations to enter and leave the critical section; to the best of our knowledge, this is optimal. For algorithms with starvation, five write and two read read operations are 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.