10 - Mutual Exclusion Flashcards
What is mutual exclusion?
The problem of granting some exclusive privilege of a recourse to a process through the exchange of messages.
What are the requirements for a mutual exclusion solution?
- Safety: exclusive access
- liveness: no deadlock or starvation
- fairness: requests granted in some time order
What are the three classes of mutex algorithms?
- election based
- token based
- permission based
What class of mutex algorithm is Lamport’s?
Permission based
What type of timestamps does lamport’s mutex algorithm use?
Every message carries a scalar logical timestamp
What is the major assumption for lamports mutex algorithm?
Channels are FIFO
In mutex algorithms, what is the abreviation CS?
Critical section: The data area one tries to access using mutex.
What two requirements need to be met in order for process P to own a mutex?
- It has received a reply from every process
- its own request is at the head of its own request queue
Decribe the pseudo code for lamports mutex alg.
# Requesting CS in Pi: broadcast(REQUEST,ts,i) to all processes Receiving request,ts,j: send(REPLY, ts') to Pj enter (ts,j) into the request queue #Releasing the mutex of Pi: send(RELEASE,i) to all processes #Receiving a RELASE,j: remove (ts,j) from the request queue
Explain Lompart’s mutex message complexity.
It requires (n-1) REQUESTS, REPLIES and RELEASES. So complexity of 3(n-1)
What improvement does Ricart’s and Agrawala’s algorithm propose? and on what algorithm?
Improvement on lamport’s algorithm:
If Pi receives a REQUEST for CS of PJ that is lower priority than Pi’s own request to access Pj, then it will wait with sending a REPLY untill Pi has released it.
It allows any process to access a CS as often as it likes. (capped to complexity: fi. if all other processes also request access)
It is implied here that because Pi’s request is of higher priority, it will be granted access earlier. And that by REPLYing only after mutex is released, it acts as a release of sorts.
What is the complexity of Ricart-Agrawala’s mutex algorithm?
(n-1) Requests and (n-1) Replies = 2(n-1)
What class of mutex algrotihm is Ricart-Agrawala’s?
Permission based
What class of mutex algorithm is Maekawa’s?
Permission based.
Explain the main idea of Maekawa’s mutex algorithm.
every process has a request set of processes to which it sends its REQUESTs and from whom it needs REPLYs (better load distribution)
What are the Requirements and Desirable features of the request sets in Maekawa’s mutex algorithm?
Requirement:
* any two request sets have a non-empty intersection
Desirable features:
* every process is in its own request set
* all request sets have the same size
* every process is contained in the same number of request sets
In Maekawa’s mutex algorithm, what is the mininum size of the request set?
in the order of sqrt( N )
Explain what a deadlock is, and how it can occur.
A deadlock is an event in the system where multiple processes are actively waiting for eachothers response, whilst no responses can be generated. This can for instance occur in asynchronous systems if mutliple requests happen simultaneously.
How does Maekawa’s mutex algorithm handle deadlocks (incl. signals)?
Whenever process Pi has GRANTED access to Pj’s request of k, but later receives an other request for k from a different process (with higher priority), it will retract its original permission to j with an INQUIRE, which is confirmed by j with a RELINQUISH message.
However, if Pi receives a request for k that has lower priority (and it already granted k to pj), then it sends a POSTPONED
What is Meakawa’s mutex algorithm message complexity under low load?
if K is the request set size.
Then k-1 Requests, k-1 Grants and k-1 Release= 3(k-1)
What is Meakawa’s mutex algorithm message complexity under heavy load?
if K is the request set size.
Then k-1 Requests, k-1 Grants, k-1 Releases and k-1 Postponed= 4(k-1)
What is Meakawa’s mutex algorithm message complexity for old request?
if K is the request set size.
Then k-1 Requests, k-1 Grants, k-1 Replies, k-1 inquires and k-1 relinquish= 5(k-1)
In meakawa’s algorithm, what happens after Pi receives a POSTPONED from Pj?
Pi will then wait untill Pj has received a RELEASE from an external process. Then Pj will send a GRANT to Pi, allowing Pi to own the mutex.
What class of mutex alg. is the generalized mutex algorithm?
Permission based
Explain the main idea of generalized mutex algorithm.
Every process maintains three sets:
1. request set: to which Pi requests and obtains grants
2. inform set: notify processes of requests and releases
3. status set: contains infromation about the processes to which a GRANT was sent.
In A generalized mutex algorithm, what is the relation between the inform and status set?
Pj is in the inform set of Pi iff Pi is in the status set of Pj
In the generalized mutex algorithm, what is the relation between the information set and the request sst?
The information set is a subset of the request set.
In generalized mutex algorithm, when are two processes regarded related?
Either they are in eachother’s request sets (Ricart-agrawala), or the intersection of the inform set is not empty (meakawa)
In the generalized mutex algorithm, what is the condition for Pi to enter a CS?
If it has received a GRANT from all pocesses in Ri (request set)
For generalized mutex algorithm, explain the psuedo code for Releasing. (send and receive)
Releasing the CS in Pi:
~~~
send(RELEASE) to processes in information set.
~~~
Receiving a release:
~~~
CSSTAT = NULL
until request_queue == empty or CSSTAT != NULL:
Pj = popped head of request queue
send(GRANT) to Pj
if Pj in Si: (status set)
CSSTAT = j
~~~
For generalized mutex algorithm, explain the psuedo code for Requesting. (send and receive)
Requesting the CS in Pi:
~~~
send(REQUEST) to all processes in request set.
~~~
Receiving a request from Pj:
~~~
if CSSTAT == NULL:
send(GRANT) to Pj
if Pj in Si: (status set)
CSSTAT = j
else:
enter(ts,j) into request queue
~~~
Explain how the request, informatoin and status set are constructed to produce Ricarts-Agrawala algorithm from the generalized mutex alg.
Ri = {0, 1, … , n-1} (all process send request to all processes)
Ii = {i} (processes do not send releases)
Si = {i} (processes only keep track of own status)
Explain how the request, informatoin and status set are constructed to produce Maekawa’s algorithm from the generalized mutex alg.
Ri = set[k] (request set is subset of size k inlcuding i)
Ii = Ri (send releases to processes in your request set)
Si = {i} (processes keep track of own status)
What class is Suzuki-Kasami’s mutex algorithm?
Token based
Explain how Suzuki-Kasami’s mutex algorithm works. What data structuresa are needed?
A process can exclusively access an CS when it has hold of the token.
Every process maintains an array N, that tracks the last request of each process. When a process wants access to the token, it broadcasts an value that is updated in N by every process.
The token also contains such an array, TN, that maintains the values of all the processes since its last visit to them. Whenever it leaves a process, it’s value of that process is updated.
Explain how the order of the token is decided in Suzuki-Kasami’s mutex algorithm, and wheter this is fair.
When a process wants to release the token, it evaluates for which next process it satisfies N[i] > TN[i]. (Meaning that Process Pj has received an request by Pi and the token has not been there yet)
If there is no difference between N and TN, the token stays put untill request arrives.
This is fair because the evaluation starts at Process ID. All processes will get access in due time.
Explain the variation of Suzuki-Kasami’s mutex algorithm.
The token also maintains queue Q, that holds all the processes that have an active request for that token. Q is updated when the token leaves a process. (and the token is send to the head of Q).
What is the message complexity of Suzuki-Kasami’s mutex algorithm?
n-1 token requests + 1 token transfer = n messages
What is the main idea behind singhal’s mutex algorithm?
If the processes and token keep track of the status of each process (e.g. if they have requested the token). Then a process’ own token request only has to be send to processes who might have the token. This reduces message complexity even more.
What is the initial values for the state array for Singhal’s mutex algorithm?
P 1: H O O O … O O
P 2: R O O O … O O
P 3: R R O O … O O
…
P N: R R R R … R O
H: holds, R: requests, O: other - the token
Explain the psuedo code for receiving a request in Singhal’s mutex alg. (for each state)
Upon receiving request;j,r
N[j] = r case S[i]: E or O: S[j] = R R: if S[j] != R: S[j] = R send(request,i,N[i]) to Pj # Pj did not receive update before H: S[i] = R; S[i] = O TS[j] = R; TN[j] = r send(token) to Pj
r is the request count of process j
Explain the psuedo code for receiving a token in Singhal’s mutex alg. (for each state)
Upon receiving request;j,r
S[i] = E
Critical Section
S[i] = O; TS[i] = O
for j in range(n):
if N[j] > TN[j] then:
TN[j] = N[j] ; TS[j] = S[j]
else:
N[j] = TN[j] ; T[j] = TS[j]
if S[j] for all j in n:
S[i] = H
else:
send(token) to Pj
r is the request count of process j
What is the message complexity of Singhal’s mutex algorithm (low contention)?
on average, n/2 messages per CS
What is the message complexity of Singhal’s mutex algorithm (high contention)?
on average, n messages per CS
Explain the main idea of Raymonds algorithm.
It operates on a binary spanning tree. By default the root holds the token. A request can be made through the spanning tree to obtain the token. When a (intermediate) node gets the token, it becomes the new root. A node only forwards a request using its own ID (only tree neighbours are known). If a node receives multiple requests (f.i. from both childs), it puts them in the request_queue. Then when it has sent a token to one child, it also requests it back in order to send it to the other child.
Explain why, in Raymonds mutex algorithm, token requests are always send upwards?
A node only knows its own ID and it’s parents. Furthermore, the root changes with the holder of the token. Hence, when you want the token you can request your parent. The parent either holds the token (and therefor is root) or he can request his parent (etc.)
What is the message complexity for raymonds mutex algorithm in worst case low contention?
2(D-1) with D the diamter of the tree.
D = N for linear tree
D= log N for random trees
Diameter of tree is longest path between any two nodes.
What is the message complexity for raymonds mutex algorithm in high contention?
In high contention, a node always requests its token back. Meaning a request and token transfer in both ways = 4 messages on average
