Mutual Exclusion: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 27: | Line 27: | ||
|- | |- | ||
| [[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] | ||
| Line 36: | Line 38: | ||
|} | |} | ||
== Time Complexity | == Time Complexity Graph == | ||
[[File:Mutual Exclusion - Time.png|1000px]] | [[File:Mutual Exclusion - Time.png|1000px]] | ||
== Space Complexity | == Space Complexity Graph == | ||
[[File:Mutual Exclusion - Space.png|1000px]] | [[File:Mutual Exclusion - Space.png|1000px]] | ||
== Pareto | == Pareto Frontier Improvements Graph == | ||
[[File:Mutual Exclusion - Pareto Frontier.png|1000px]] | [[File:Mutual Exclusion - Pareto Frontier.png|1000px]] | ||
Revision as of 13:04, 15 February 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(logn)$? (originally this had $O(n)$) | $O({1})$ per process, $O(n)$ total? | Exact | Deterministic | 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(logn)$ | $O({1})$ per process, $O(n)$ total? | Exact | Deterministic | Time |
| Chan-Singhal-Liu | 1990 | $O(logn)$ | $O({1})$ per process, $O(n)$ total? | Exact | Deterministic | Time |
Time Complexity Graph
Space Complexity Graph
Pareto Frontier Improvements Graph
