Consider the mutex algorithm of Ricart and Agrawala. Recall the assumptions: 1.
ID: 3813287 • Letter: C
Question
Consider the mutex algorithm of Ricart and Agrawala. Recall the assumptions:
1. Each thread executes at non-zero speed.
2. Communication lines and input ports are non-FIFO (“non” here means “not necessarily”).
3. Each thread can receive its input messages independently, without synchronization issues with other threads’ inputs.
In each question, a modification to the code is suggested.
Will the new code work? (YES or No).
If Yes, give an explanation, in less than 50 words.
If No, give a counter example. In this example, assume we have EXACTLY TWO processes P0 and P1 in the system.
Q1.
In the thread receiving Request messages, the assignment to Defer_it it replaced by:
Defer_it := (Requesting_Critical_Section AND j>me)
Explanation / Answer
Algorithm by Ricart and Agrawala
1)based on multicast
2)process requesting access multicasts request to all other processes
3)process may only enter critical section if all other processes return
4)positive acknowledgment messages
assumptions
all processes have communication channels to all other processes
all processes have distinct numeric ID and maintain logical clocks
On initialization
state := RELEASED;
To enter the section
state := WANTED;
Multicast request to all processes; processing of incoming requests
T := request’s timestamp; deferred here
Wait until (number of replies received = (N – 1));
state := HELD;
On receipt of a request <Ti, pi> at pj (i j)
if (state = HELD or (state = WANTED and (T, pj) < (Ti, pi)))
then
queue request from pi without replying;
else
reply immediately to pi;
end if
To exit the critical section
state := RELEASED;
reply to any queued requests;
2.Algorithm by Ricart and Agrawala
if request is broadcast and state of all other processes is RELEASED, then
all processes will reply immediately and requester will obtain entry
if at least one process is in state HELD, that process will not reply until it has
left critical section, hence mutual exclusion
if two or more processes request at the same time, whichever process'
request bears lower timestamp will be the first to get N1 replies
in case of equal timestamps, process with lower ID wins
p1 p3
p2
Algorithm by Ricart and Agrawala
p3 not attempting to enter, p1 and p2 request entry simultaneously
p3 replies immediately
p2 receives request from p1, timestamp(p2) < timestamp(p1), therefore p2 does not reply p1
sees its timestamp to be larger than that of the request from p2, hence it
replies immediately and p2 is granted access p2will reply to p1’s request after exiting the critical section
3.Algorithm by Ricart and Agrawala
p3 not attempting to enter, p1 and p2 request entry simultaneously
p3 replies immediately p2 receives request from p1, timestamp(p2) < timestamp(p1), therefore p2 does not reply p1
sees its timestamp to be larger than that of the request from p2
, hence it
replies immediately and p2 is granted access
p2
will reply to p1
’s request after exiting the critical section
On initialization
state := RELEASED;
To enter the section
state := WANTED;
Multicast request to all processes; processing of incoming requests
T := request’s timestamp; deferred here
Wait until (number of replies received = (N – 1));
state := HELD;
On receipt of a request <Ti, pi> at pj (i j)
if (state = HELD or (state = WANTED and (T, pj) < (Ti, pi)))
then
queue request from pi without replying;
else
reply immediately to pi;
end if
To exit the critical section
state := RELEASED;
reply to any queued requests;
4.Algorithm by Ricart and Agrawala
algorithms satisfies ME1
two processes pi
and pj
can only access critical section at the same time
in case they would have replied to each other
since pairs <Ti
, pi> are totally ordered, this cannot happen
algorithms also satisfies ME2 and ME3
On initialization
state := RELEASED;
To enter the section
state := WANTED;
Multicast request to all processes; processing of incoming requests
T := request’s timestamp; deferred here
Wait until (number of replies received = (N – 1));
state := HELD;
On receipt of a request <Ti, pi> at pj (i j)
if (state = HELD or (state = WANTED and (T, pj) < (Ti, pi)))
then
queue request from pi without replying;
else
reply immediately to pi;
end if
To exit the critical section
state := RELEASED;
reply to any queued requests;