Mutual Exclusion: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| (5 intermediate revisions by the same user not shown) | |||
| Line 6: | Line 6: | ||
== Parameters == | == Parameters == | ||
$n$: number of processors | |||
== Table of Algorithms == | == Table of Algorithms == | ||
| Line 24: | Line 24: | ||
| [[Maekawa's algorithm ( Mutual Exclusion)|Maekawa's algorithm]] || 1985 || $O(n^{0.5})$ || $O({1})$ per process, $O(n)$ total? || Exact || Deterministic || [https://cseweb.ucsd.edu/classes/wi09/cse223a/p145-maekawa.pdf Time] & [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.135.825&rep=rep1&type=pdf Space] | | [[Maekawa's algorithm ( Mutual Exclusion)|Maekawa's algorithm]] || 1985 || $O(n^{0.5})$ || $O({1})$ per process, $O(n)$ total? || Exact || Deterministic || [https://cseweb.ucsd.edu/classes/wi09/cse223a/p145-maekawa.pdf Time] & [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.135.825&rep=rep1&type=pdf Space] | ||
|- | |- | ||
| [[Raymond's algorithm ( Mutual Exclusion)|Raymond's algorithm]] || 1997 || $O( | | [[Raymond's algorithm ( Mutual Exclusion)|Raymond's algorithm]] || 1997 || $O(\log n)$? (originally this had $O(n)$) || $O({1})$ per process, $O(n)$ total? || Exact || Deterministic || [https://dl.acm.org/doi/abs/10.1145/58564.59295 Time] & [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.135.825&rep=rep1&type=pdf Space] | ||
|- | |- | ||
| [[Suzuki-Kasami's algorithm ( Mutual Exclusion)|Suzuki-Kasami's algorithm]] || 1985 || $O(n)$? (originally this had $O(logn)$) || $O({1})$ per process, $O(n)$ total? || Exact || Deterministic || [https://cse.iitkgp.ac.in/~agupta/distsys/Mutex-SuzukiKasami.pdf Time] & [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.135.825&rep=rep1&type=pdf Space] | | [[Suzuki-Kasami's algorithm ( Mutual Exclusion)|Suzuki-Kasami's algorithm]] || 1985 || $O(n)$? (originally this had $O(logn)$) || $O({1})$ per process, $O(n)$ total? || Exact || Deterministic || [https://cse.iitkgp.ac.in/~agupta/distsys/Mutex-SuzukiKasami.pdf Time] & [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.135.825&rep=rep1&type=pdf Space] | ||
|- | |||
| [[Dekker's algorithm (2-thread Mutual Exclusion Mutual Exclusion)|Dekker's algorithm]] || 1963 || $O(n)$ || || Exact || Deterministic || | |||
|- | |- | ||
| [[Peterson's algorithm ( Mutual Exclusion)|Peterson's algorithm]] || 1981 || $O(n)$ || $O(n)$ total || Exact || Deterministic || [https://zoo.cs.yale.edu/classes/cs323/doc/Peterson.pdf Time] | | [[Peterson's algorithm ( Mutual Exclusion)|Peterson's algorithm]] || 1981 || $O(n)$ || $O(n)$ total || Exact || Deterministic || [https://zoo.cs.yale.edu/classes/cs323/doc/Peterson.pdf Time] | ||
|- | |- | ||
| [[Naimi-Trehel's algorithm ( Mutual Exclusion)|Naimi-Trehel's algorithm]] || 1996 || $O( | | [[Naimi-Trehel's algorithm ( Mutual Exclusion)|Naimi-Trehel's algorithm]] || 1996 || $O(\log n)$ || $O({1})$ per process, $O(n)$ total? || Exact || Deterministic || [https://www.sciencedirect.com/science/article/abs/pii/S0743731596900416 Time] | ||
|- | |- | ||
| [[Chan-Singhal-Liu ( Mutual Exclusion)|Chan-Singhal-Liu]] || 1990 || $O( | | [[Chan-Singhal-Liu ( Mutual Exclusion)|Chan-Singhal-Liu]] || 1990 || $O(\log n)$ || $O({1})$ per process, $O(n)$ total? || Exact || Deterministic || [https://ieeexplore.ieee.org/document/113817 Time] | ||
|- | |- | ||
|} | |} | ||
== Time Complexity | == Time Complexity Graph == | ||
[[File:Mutual Exclusion - Time.png|1000px]] | [[File:Mutual Exclusion - Time.png|1000px]] | ||
Latest revision as of 09:07, 28 April 2023
Description
Mutual exclusion is a property of concurrency control; which is instituted for the purpose of preventing race conditions.
Parameters
$n$: number of processors
Table of Algorithms
| Name | Year | Time | Space | Approximation Factor | Model | Reference |
|---|---|---|---|---|---|---|
| Lamport's bakery algorithm | 1974 | $O(n)$ | $O({1})$ per process, $O(n)$ total? | Exact | Deterministic | Time & Space |
| Szymanski's algorithm | 1988 | $O(n)$ | $O({1})$ per process, $O(n)$ total? | Exact | Deterministic | Time & Space |
| Taubenfeld's black-white bakery algorithm | 2004 | $O(n)$ | $O({1})$ per process, $O(n)$ total? | Exact | Deterministic | Time & Space |
| Maekawa's algorithm | 1985 | $O(n^{0.5})$ | $O({1})$ per process, $O(n)$ total? | Exact | Deterministic | Time & Space |
| Raymond's algorithm | 1997 | $O(\log n)$? (originally this had $O(n)$) | $O({1})$ per process, $O(n)$ total? | Exact | Deterministic | Time & Space |
| Suzuki-Kasami's algorithm | 1985 | $O(n)$? (originally this had $O(logn)$) | $O({1})$ per process, $O(n)$ total? | Exact | Deterministic | Time & Space |
| Dekker's algorithm | 1963 | $O(n)$ | Exact | Deterministic | ||
| Peterson's algorithm | 1981 | $O(n)$ | $O(n)$ total | Exact | Deterministic | Time |
| Naimi-Trehel's algorithm | 1996 | $O(\log n)$ | $O({1})$ per process, $O(n)$ total? | Exact | Deterministic | Time |
| Chan-Singhal-Liu | 1990 | $O(\log n)$ | $O({1})$ per process, $O(n)$ total? | Exact | Deterministic | Time |
Time Complexity Graph
