License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2017.17
URN: urn:nbn:de:0030-drops-86523
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8652/
Dvir, Rotem ;
Taubenfeld, Gadi
Mutual Exclusion Algorithms with Constant RMR Complexity and Wait-Free Exit Code
Abstract
Two local-spinning queue-based mutual exclusion algorithms are presented that have several de- sired properties: (1) their exit codes are wait-free, (2) they satisfy FIFO fairness, (3) they have constant RMR complexity in both the CC and the DSM models, (4) it is not assumed that the number of processes, n, is a priori known, that is, processes may appear or disappear intermit- tently, (5) they use only O(n) shared memory locations, and (6) they make no assumptions on what and how memory is allocated.
The algorithms are inspired by J. M. Mellor-Crummey and M. L. Scott famous MCS queue- based algorithm [13] which, except for not having a wait-free exit code, satisfies similar properties. A drawback of the MCS algorithm is that executing the exit code (i.e., releasing a lock) requires spinning – a process executing its exit code may need to wait for the process that is behind it in the queue to take a step before it can proceed. The two new algorithms overcome this drawback while preserving the simplicity and elegance of the original algorithm.
Our algorithms use exactly the same atomic instruction set as the original MCS algorithm, namely: read, write, fetch-and-store and compare-and-swap. In our second algorithm it is possible to recycle memory locations so that if there are L mutual exclusion locks, and each process accesses at most one lock at a time, then the algorithm needs only O(L + n) space, as compared to O(Ln) needed by our first algorithm.
BibTeX - Entry
@InProceedings{dvir_et_al:LIPIcs:2018:8652,
author = {Rotem Dvir and Gadi Taubenfeld},
title = {{Mutual Exclusion Algorithms with Constant RMR Complexity and Wait-Free Exit Code}},
booktitle = {21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
pages = {17:1--17:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-061-3},
ISSN = {1868-8969},
year = {2018},
volume = {95},
editor = {James Aspnes and Alysson Bessani and Pascal Felber and Jo{\~a}o Leit{\~a}o},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8652},
URN = {urn:nbn:de:0030-drops-86523},
doi = {10.4230/LIPIcs.OPODIS.2017.17},
annote = {Keywords: Mutual exclusion, locks, local-spinning, cache coherent, distributed shared memory, RMR complexity}
}
|
Keywords: |
|
Mutual exclusion, locks, local-spinning, cache coherent, distributed shared memory, RMR complexity |
|
Collection: |
|
21st International Conference on Principles of Distributed Systems (OPODIS 2017) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
28.03.2018 |
