Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Fast Local-Spin Abortable Mutual Exclusion with Bounded Space
verfasst von : Hyonho Lee
Erschienen in: Principles of Distributed Systems
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abortable mutual exclusion is a variant of mutual exclusion, where processes are allowed to abort their invocations while waiting to enter the critical section. In this paper, we present an FCFS abortable mutual exclusion algorithm with bounded time and space, in which each invocation performs
O
(
k
2
) RMAs if at most
k
processes abort. We define an object type,
S-HAD
, from which it is easy to construct local-spin abortable mutual exclusion algorithms. Our main contribution is a wait-free implementation of an S-HAD object. We also develop a new, wait-free memory reclamation method, which generalizes reference counting, to achieve bounded space. The resulting algorithm uses
O
(
N
2
) shared variables, each with
O
(log
N
) bits, where
N
is the number of processes.