Mutual exclusion as a matter of priority
| Autor: | Yoram Moses, Katia Patkin |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Correctness
Theoretical computer science General Computer Science Relation (database) Lamport's bakery algorithm Computer science Process (computing) 020207 software engineering 0102 computer and information sciences 02 engineering and technology 01 natural sciences Blocking (computing) Theoretical Computer Science Priority inheritance 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Mutual exclusion Algorithm Block (data storage) |
| Zdroj: | Theoretical Computer Science. 751:46-60 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2016.12.015 |
| Popis: | A new approach to the study and analysis of Mutual Exclusion (ME) algorithms is presented, based on identifying the priority relation that the ME algorithm constructs. It is argued that by analyzing how a process detects that it has priority over all other processes, ME algorithms can be better understood and improved. The approach is illustrated by applying it to Lamport's celebrated Bakery algorithm in the safe register SWMR model. By analyzing how Bakery established and detects priority, cases in which the Bakery algorithm causes processes to block unnecessarily are identified. Namely, a process that already knows that it has priority over another process is made to perform reads and wait on registers of the other process. An optimized version of the Bakery algorithm, called Boulangerie, is proposed, and is shown to be free of any unnecessary blocking. A second contribution of the approach is obtaining a clear explanation for how the Bakery algorithm uses reads from safe registers to detect that a process has priority. Our analysis provides more insight into the workings of the Bakery algorithm than is obtained by other proofs of its correctness. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect