Fast mutual exclusion by the Triangle algorithm

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