דניאל הנדלר

Mutual exclusion is a fundamental coordination problem. Over the last 20 years, shared-memory mutual exclusion research focuses on local-spin algorithms and uses the remote memory references (RMRs) metric. To ensure the correctness of concurrent algorithms in general, and mutual exclusion algorithms in particular, it is often required to prohibit certain re-orderings of memory instructions that may compromise correctness, by inserting memory barrier instructions. Memory barriers incur non-negligible overhead and may significantly increase the algorithm's time complexity. This paper presents the first read/write mutual exclusion algorithm with asymptotically optimal complexity under both the RMRs and barriers metrics: each passage through the critical section incurs O(log n) RMRs and a constant number of barriers. The algorithm works in the popular Total Store Ordering model.