2026-07-21T12:47:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8652 2024-03-06T10:42:12Z ddc:004 open_access

Mutual Exclusion Algorithms with Constant RMR Complexity and Wait-Free Exit Code Dvir, Rotem Taubenfeld, Gadi Mutual exclusion locks local-spinning cache coherent distributed shared memory RMR complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rotem Dvir and Gadi Taubenfeld 2018 Is Part Of LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2017.17 urn:nbn:de:0030-drops-86523 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.17 eng https://creativecommons.org/licenses/by/3.0/legalcode