1. Consider an algorithm for twoprocess with the exit section the same as in the
ID: 3617069 • Letter: 1
Question
1. Consider an algorithm for twoprocess with the exit section the same as in theDekker's
algorithm for ME, and with thefollowing entry section, where either i = 0 or i = 1:
entry region for processi :
raise the ag up ;
while the ag of the process 1 - i is up do
begin
if itis process (1 - i)'s turn then lower the ag down ;
repeat x<------ Turnuntil x= i;
raise the ag up again;
end
Does this algorithm providemutual exclusion? If you believe that this is the case,
then does it provide deadlockfreedom? If you believe that the two above questions
are answered in the armative, then does itprevent lockout to occur?
Explanation / Answer
Mutual Exclusion:
This given the same guarantee of Mutual Exclusion as Dekker'salgorithm does.
One process i is in the critical region
Flag = up
Other process 1-i keeps checking on flag of i, and each time itfinds the flag raised up, it executes the inner block ofinstructions, but does not enter.
When the critical region is empty one process wants to enter thecritical region then raises the flag up, checks on the other flagto see that it is down, and enters.
Suppose two processes want to enter and their flags have alreadybeen raised up when each of them enabled checking on the otherflag.
Let it be the turn of process i. Then process i keeps iteratingreading, first the flag of 1i and then Turn. Eventuallyprocess 1i checks on the flag of process i and on Turn.Since it is not it's turn, it lowers the flag, and enters a loop.It will be raised up again, if at all, not earlier than after Turnhas been flipped. Process i eventually is able to read the flag ofprocess 1i and see that it is down, which makes process ienter. By symmetry, if it is process 1-i's turn, it will be the oneto enter.
I hope it will helps you!!!!!!!!!!!!!
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.