Mutual Exclusion: Difference between revisions
Jump to navigation
Jump to search
(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...") |
No edit summary |
||
| Line 1: | Line 1: | ||
== | {{DISPLAYTITLE:Mutual Exclusion (Mutual Exclusion)}} | ||
== Description == | |||
Mutual exclusion is a property of concurrency control; which is instituted for the purpose of preventing race conditions. | |||
== | == Parameters == | ||
<pre>n: number of processors?</pre> | |||
== Table of Algorithms == | |||
{| class="wikitable sortable" style="text-align:center;" width="100%" | |||
! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference | |||
|- | |- | ||
| | |||
| | | [[Lamport's bakery algorithm ( Mutual Exclusion)|Lamport's bakery algorithm]] || 1974 || $O(n)$ || $O({1})$ per process, $O(n)$ total? || Exact || Deterministic || [http://lamport.azurewebsites.net/pubs/bakery.pdf Time] & [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.135.825&rep=rep1&type=pdf Space] | ||
| | |||
|- | |- | ||
| | | [[Szymanski's algorithm ( Mutual Exclusion)|Szymanski's algorithm]] || 1988 || $O(n)$ || $O({1})$ per process, $O(n)$ total? || Exact || Deterministic || [https://www.researchgate.net/publication/221235887_A_simple_solution_to_Lamport's_concurrent_programming_problem_with_linear_wait Time] & [http://cs.rpi.edu/~szymansk/papers/jerus.93.pdf Space] | ||
| | |||
| | |||
|- | |- | ||
| | | [[Taubenfeld's black-white bakery algorithm ( Mutual Exclusion)|Taubenfeld's black-white bakery algorithm]] || 2004 || $O(n)$ || $O({1})$ per process, $O(n)$ total? || Exact || Deterministic || [https://link-springer-com.ezproxy.canberra.edu.au/chapter/10.1007/978-3-540-30186-8_5 Time] & [https://link-springer-com.ezproxy.canberra.edu.au/content/pdf/10.1007/b101206.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(logn)$? (originally this had $O(n)$) || $O({1})$ per process, $O(n)$ total? || Exact || Deterministic || [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] | |||
[https://zoo.cs.yale.edu/classes/cs323/doc/Peterson.pdf | |- | ||
| [[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(logn)$ || $O({1})$ per process, $O(n)$ total? || Exact || Deterministic || [https://www-sciencedirect-com.ezproxy.canberra.edu.au/science/article/abs/pii/S0743731596900416 Time] | |||
|- | |||
| [[Chan-Singhal-Liu ( Mutual Exclusion)|Chan-Singhal-Liu]] || 1990 || $O(logn)$ || $O({1})$ per process, $O(n)$ total? || Exact || Deterministic || [https://ieeexplore-ieee-org.ezproxy.canberra.edu.au/document/113817 Time] | |||
|- | |||
|} | |||
== Time Complexity graph == | |||
[ | [[File:Mutual Exclusion - Time.png|1000px]] | ||
== Space Complexity graph == | |||
[ | [[File:Mutual Exclusion - Space.png|1000px]] | ||
[ | |||
== Pareto Decades graph == | |||
[ | [[File:Mutual Exclusion - Pareto Frontier.png|1000px]] | ||
Revision as of 10:20, 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 |
| 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
Error creating thumbnail: Unable to save thumbnail to destination
Space Complexity graph
Error creating thumbnail: Unable to save thumbnail to destination
Pareto Decades graph
Error creating thumbnail: Unable to save thumbnail to destination