10 - Mutual Exclusion

Question 1

What is mutual exclusion?

Answer 1

The problem of granting some exclusive privilege of a recourse to a process through the exchange of messages.

Question 2

What are the requirements for a mutual exclusion solution?

Answer 2

1. Safety: exclusive access
2. liveness: no deadlock or starvation
3. fairness: requests granted in some time order

Question 3

What are the three classes of mutex algorithms?

Answer 3

• election based
• token based
• permission based

Question 4

What class of mutex algorithm is Lamport’s?

Answer 4

Permission based

Question 5

What type of timestamps does lamport’s mutex algorithm use?

Answer 5

Every message carries a scalar logical timestamp

Question 6

What is the major assumption for lamports mutex algorithm?

Answer 6

Channels are FIFO

Question 7

In mutex algorithms, what is the abreviation CS?

Answer 7

Critical section: The data area one tries to access using mutex.

Question 8

What two requirements need to be met in order for process P to own a mutex?

Answer 8

1. It has received a reply from every process
2. its own request is at the head of its own request queue

Question 9

Decribe the pseudo code for lamports mutex alg.

Answer 9

# 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

Question 10

Explain Lompart’s mutex message complexity.

Answer 10

It requires (n-1) REQUESTS, REPLIES and RELEASES. So complexity of 3(n-1)

Question 11

What improvement does Ricart’s and Agrawala’s algorithm propose? and on what algorithm?

Answer 11

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.

Question 12

What is the complexity of Ricart-Agrawala’s mutex algorithm?

Answer 12

(n-1) Requests and (n-1) Replies = 2(n-1)

Question 13

What class of mutex algrotihm is Ricart-Agrawala’s?

Answer 13

Permission based

Question 14

What class of mutex algorithm is Maekawa’s?

Answer 14

Permission based.

Question 15

Explain the main idea of Maekawa’s mutex algorithm.

Answer 15

every process has a request set of processes to which it sends its REQUESTs and from whom it needs REPLYs (better load distribution)

Question 16

What are the Requirements and Desirable features of the request sets in Maekawa’s mutex algorithm?

Answer 16

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

Question 17

In Maekawa’s mutex algorithm, what is the mininum size of the request set?

Answer 17

in the order of sqrt( N )

Question 18

Explain what a deadlock is, and how it can occur.

Answer 18

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.

Question 19

How does Maekawa’s mutex algorithm handle deadlocks (incl. signals)?

Answer 19

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

Question 20

What is Meakawa’s mutex algorithm message complexity under low load?

Answer 20

if K is the request set size.
Then k-1 Requests, k-1 Grants and k-1 Release= 3(k-1)

Question 21

What is Meakawa’s mutex algorithm message complexity under heavy load?

Answer 21

if K is the request set size.
Then k-1 Requests, k-1 Grants, k-1 Releases and k-1 Postponed= 4(k-1)

Question 22

What is Meakawa’s mutex algorithm message complexity for old request?

Answer 22

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)

Question 23

In meakawa’s algorithm, what happens after Pi receives a POSTPONED from Pj?

Answer 23

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.

Question 24

What class of mutex alg. is the generalized mutex algorithm?

Answer 24

Permission based

Question 25

Explain the main idea of generalized mutex algorithm.

Answer 25

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.

Question 26

In A generalized mutex algorithm, what is the relation between the inform and status set?

Answer 26

Pj is in the inform set of Pi iff Pi is in the status set of Pj

Question 27

In the generalized mutex algorithm, what is the relation between the information set and the request sst?

Answer 27

The information set is a subset of the request set.

Question 28

In generalized mutex algorithm, when are two processes regarded related?

Answer 28

Either they are in eachother’s request sets (Ricart-agrawala), or the intersection of the inform set is not empty (meakawa)

Question 29

In the generalized mutex algorithm, what is the condition for Pi to enter a CS?

Answer 29

If it has received a GRANT from all pocesses in Ri (request set)

Question 30

For generalized mutex algorithm, explain the psuedo code for Releasing. (send and receive)

Answer 30

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
~~~

Question 31

For generalized mutex algorithm, explain the psuedo code for Requesting. (send and receive)

Answer 31

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
~~~

Question 32

Explain how the request, informatoin and status set are constructed to produce Ricarts-Agrawala algorithm from the generalized mutex alg.

Answer 32

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)

Question 33

Explain how the request, informatoin and status set are constructed to produce Maekawa’s algorithm from the generalized mutex alg.

Answer 33

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)

Question 34

What class is Suzuki-Kasami’s mutex algorithm?

Answer 34

Token based

Question 35

Explain how Suzuki-Kasami’s mutex algorithm works. What data structuresa are needed?

Answer 35

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.

Question 36

Explain how the order of the token is decided in Suzuki-Kasami’s mutex algorithm, and wheter this is fair.

Answer 36

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.

Question 37

Explain the variation of Suzuki-Kasami’s mutex algorithm.

Answer 37

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).

Question 38

What is the message complexity of Suzuki-Kasami’s mutex algorithm?

Answer 38

n-1 token requests + 1 token transfer = n messages

Question 39

What is the main idea behind singhal’s mutex algorithm?

Answer 39

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.

Question 40

What is the initial values for the state array for Singhal’s mutex algorithm?

Answer 40

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

Question 41

Explain the psuedo code for receiving a request in Singhal’s mutex alg. (for each state)

Answer 41

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

Question 42

Explain the psuedo code for receiving a token in Singhal’s mutex alg. (for each state)

Answer 42

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

Question 43

What is the message complexity of Singhal’s mutex algorithm (low contention)?

Answer 43

on average, n/2 messages per CS

Question 44

What is the message complexity of Singhal’s mutex algorithm (high contention)?

Answer 44

on average, n messages per CS

Question 45

Explain the main idea of Raymonds algorithm.

Answer 45

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.

Question 46

Explain why, in Raymonds mutex algorithm, token requests are always send upwards?

Answer 46

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.)

Question 47

What is the message complexity for raymonds mutex algorithm in worst case low contention?

Answer 47

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.

Question 48

What is the message complexity for raymonds mutex algorithm in high contention?

Answer 48

In high contention, a node always requests its token back. Meaning a request and token transfer in both ways = 4 messages on average