Mutual Exclusion
Revision as of 10:59, 10 October 2022 by Admin (talk | contribs) (Created page with "== Problem Description== Mutual exclusion is a property of process synchronization which states that “no two processes can exist in the critical section at any given point of time”. The term was first coined by Djikstra. == Bounds Chart == 1050px == Step Chart == 1050px == Improvement Table == {| class="wikitable" style="text-align:center;" width="100%" !width="20%" | Complexity Clas...")
Problem Description
Mutual exclusion is a property of process synchronization which states that “no two processes can exist in the critical section at any given point of time”. The term was first coined by Djikstra.
Bounds Chart
Step Chart
Improvement Table
| Complexity Classes | Algorithm Paper Links | Lower Bounds Paper Links |
|---|---|---|
| Exp/Factorial | ||
| Polynomial > 3 | ||
| Cubic | ||
| Quadratic | ||
| nlogn | ||
| Linear | [- Dekker's algorithm (1963)]
Lamport's bakery algorithm (1974) Taubenfeld's black-white bakery algorithm (2004) [ Raymond's algorithm (1997)] |
|
| logn | Naimi-Trehel's algorithm (1996) |