Recoverable Mutual Exclusion
| Autor: | Wojciech Golab, Aditya Ramaraju |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Critical section
Computer science Readers–writers problem Distributed computing Concurrency Liveness 0102 computer and information sciences 02 engineering and technology 01 natural sciences 010201 computation theory & mathematics Monitor 020204 information systems Reentrant mutex 0202 electrical engineering electronic engineering information engineering Mutual exclusion Semaphore |
| Zdroj: | PODC |
| DOI: | 10.1145/2933057.2933087 |
| Popis: | Mutex locks have traditionally been the most common mechanism for protecting shared data structures in parallel programs. However, the robustness of such locks against process failures has not been studied thoroughly. Most (user-level) mutex algorithms are designed around the assumption that processes are reliable, meaning that a process may not fail while executing the lock acquisition and release code, or while inside the critical section.If such a failure does occur, then the liveness properties of a conventional mutex lock may cease to hold until the application or operating system intervenes by cleaning up the internal structure of the lock. For example, a process that is attempting to acquire an otherwise starvation-free mutex may be blocked forever waiting for a failed process to release the critical section. Adding to the difficulty, if the failed process recovers and attempts to acquire the same mutex again without appropriate cleanup, then the mutex may become corrupted to the point where it loses safety, notably the mutual exclusion property. We address this challenge by formalizing the problem of recoverable mutual exclusion, and proposing several solutions that vary both in their assumptions regarding hardware support for synchronization, and in their time complexity. Compared to known solutions, our algorithms are more robust as they do not restrict where or when a process may crash, and provide stricter guarantees in terms of time complexity, which we define in terms of remote memory references. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|