Implementing multiple locks using Lamport's mutual exclusion algorithm

Autor:	Alan J. Demers, Hans-J. Boehm, Chris Uhler
Rok vydání:	1993
Předmět:	Critical section Record locking Lamport timestamps Lamport's bakery algorithm Computer science Multiprocessing General Medicine Parallel computing symbols.namesake Constant (computer programming) Logical clock symbols Mutual exclusion Algorithm
Zdroj:	ACM Letters on Programming Languages and Systems. 2:46-58
ISSN:	1557-7384 1057-4514
DOI:	10.1145/176454.176479
Popis:	We describe an approach for implementing higher-level mutual-exclusion constructs using Lamport's algorithm. A straightforward implementation of, for example, monitor locks based on Lamport's algorithm requires O( n ) space per monitor lock if there are n processes that may share the lock. It has occasionally been claimed that this makes the algorithm undesirable in practice. The insight presented here is that we only need a (small) constant amount of space per lock, plus O( n ) space shared by all locks in the system. For some common applications, this adds no memory references to the implementation of the algorithm. Fully general spin-lock acquisition and release can usually be implemented with the addition of one memory reference to Lamport's algorithm. On particularly unfavorable hardware, three additional memory references may be required in the contention-free case.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::1eda817515c1dd16a6b011c2977c7491 https://doi.org/10.1145/176454.176479 Zobrazit plný text záznamu