Hagit Attiya
Danny Hendler
ABSTRACT
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.
- S. V. Adve and K. Gharachorloo. Shared memory consistency models: A tutorial. IEEE Computer, 29(12):66--76, 1996. Google Scholar
Digital Library
- J. H. Anderson and Y.-J. Kim. Adaptive mutual exclusion with local spinning. In DISC, pages 29--43, 2000. Google ScholarDigital Library
- H. Attiya, R. Guerraoui, D. Hendler, P. Kuznetsov, M. M. Michael, and M. T. Vechev. Laws of order: expensive synchronization in concurrent algorithms cannot be eliminated. In POPL, pages 487--498, 2011. Google ScholarDigital Library
- H. Attiya, D. Hendler, and P. Woelfel. Tight RMR lower bounds for mutual exclusion and other problems. In STOC, pages 217--226, 2008. Google ScholarDigital Library
- T. Craig. Building FIFO and priority-queuing spin locks from atomic swap. Technical report, 1993.Google Scholar
- R. Danek and W. M. Golab. Closing the complexity gap between FCFS mutual exclusion and mutual exclusion. In DISC, pages 93--108, 2008. Google ScholarDigital Library
- D. Dice. personal communication, May 2013.Google Scholar
- W. M. Golab, V. Hadzilacos, D. Hendler, and P. Woelfel. RMR-efficient implementations of comparison primitives using read and write operations. Distributed Computing, 25(2):109--162, 2012.Google ScholarCross Ref
- W. M. Golab, D. Hendler, and P. Woelfel. An O(1) rmrs leader election algorithm. SIAM J. Comput., 39(7):2726--2760, 2010. Google ScholarDigital Library
- D. Hendler and P. Woelfel. Randomized mutual exclusion with sub-logarithmic rmr-complexity. Distributed Computing, 24(1):3--19, 2011.Google ScholarDigital Library
- M. P. Herlihy and J. M. Wing. Linearizability: a correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems, 12(3):463--492, 1990. Google ScholarDigital Library
- Intel Corporation. Intel® 64 and IA-32 Architectures Software Developer's Manual. Number 253669-033US. December 2009.Google Scholar
- P. Jayanti. Adaptive and efficient abortable mutual exclusion. In PODC, pages 295--304, 2003. Google ScholarDigital Library
- P. Jayanti, S. Petrovic, and N. Narula. Read/write based fast-path transformation for FCFS mutual exclusion. In SOFSEM, pages 209--218, 2005. Google ScholarDigital Library
- Y.-J. Kim and J. Anderson. A time complexity bound for adaptive mutual exclusion. In DISC, pages 1--15, 2001. Google ScholarDigital Library
- M. Kuperstein, M. Vechev, and E. Yahav. Automatic inference of memory fences. In FMCAD, pages 111--119, 2010. Google ScholarDigital Library
- L. Lamport. A new solution of dijkstra's concurrent programming problem. Commun. ACM, 17(8):453--455, 1974. Google ScholarDigital Library
- L. Lamport. How to make a correct multiprocess program execute correctly on a multiprocessor. IEEE Trans. Computers, 46(7):779--782, 1997. Google ScholarDigital Library
- D. L.Weaver and T. Germond, editors. The SPARC Architecture Manual. Prentice Hall, 1994. Google ScholarDigital Library
- P. Magnusson, A. Landin, and E. Hagersten. Queue locks on cache coherent multiprocessors. In IPPS, pages 165--171, 1994. Google ScholarDigital Library
- J. M. Mellor-Crummey and M. L. Scott. Algorithms for scalable synchronization on shared-memory multiprocessors. ACM Trans. Comput. Syst., 9(1):21--65, 1991. Google ScholarDigital Library
- S. Owens, S. Sarkar, and P. Sewell. A better x86 memory model: x86-tso. In Theorem Proving in Higher Order Logics, pages 391--407, 2009. Google ScholarDigital Library
- S. Park and D. Dill. An executable specification and verifier for relaxed memory order. Computers, IEEE Transactions on, 48(2):227--235, 1999. Google ScholarDigital Library
- G. L. Peterson. Myths about the mutual exclusion problem. Inf. Process. Lett., 12(3):115--116, 1981.Google ScholarCross Ref
- P. Sewell, S. Sarkar, S. Owens, F. Z. Nardelli, and M. O. Myreen. x86-tso: a rigorous and usable programmer's model for x86 multiprocessors. Commun. ACM, 53(7):89--97, 2010. Google ScholarDigital Library
- J.-H. Yang and J. Anderson. A fast, scalable mutual exclusion algorithm. Distributed Computing, 9(1):51--60, 1995.Google ScholarDigital Library
Index Terms
- An O(1)-barriers optimal RMRs mutual exclusion algorithm: extended abstract
Recommendations
A Simple Local-Spin Group Mutual Exclusion Algorithm
This paper presents a new solution to the group mutual exclusion problem recently posed by Joung. In this problem, processes repeatedly request access to various sessions. It is required that distinct processes are not in different sessions concurrently,...
An O(1) RMRs leader election algorithm
PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computingThe leader election problem is a fundamental distributed coordination problem. We present leader election algorithms for the cache-coherent (CC) and distributed shared memory (DSM) models using reads and writes only, for which the number of remote ...
Randomized mutual exclusion in O(log N / log log N) RMRs
PODC '09: Proceedings of the 28th ACM symposium on Principles of distributed computingMutual exclusion is a fundamental distributed coordination problem. Shared-memory mutual exclusion research focuses on local-spin algorithms and uses the remote memory references (RMRs) metric. A recent proof [9] established an Ω(log N) lower bound on ...
Comments