Why doesn\'t this solution(in pseudo code) works for the 2 process mutual exclus

Question

Why doesn't this solution(in pseudo code) works for the 2 process mutual exclusion problem(before Peterson's algorithm)? Provide a detailed counter example showing where this algorithm fails.

Shared Data: blocked: array [0..1] of Boolean; turn: 0..1; blocked [0]blocked[1]false; turn = 0; Local Data: ID: 0..1; /* (identifies the process; set to 0 for one process, 1 for the other/ Code for each of the two processes: repeat blocked [ID] true ; while(turn ID) do while (blocked [1-ID]) do nothing; turn = D; end loop; blocked[ID] -false normal work >> forever;

Explanation / Answer

The solution posses some problem
The process when tries to enter in critical section, it first make itelf blocked and then cheks the turn variable, If it is turn for the other process, then this process keeps waiting..
ONce it gets its turn, it checks if the other process is blocked or not.. If the other process is blocked, this process will keep waiting till other process unblocks itself and then this process enters into critical section.. ONce completed, it unblocks itself and exits.

Now think of the scenrio where P1 and P2 both have executed just their first line of blocked[ID] = true;
SO after this line,
blocked[0] = blocked[1] = true
turn = 0;

Now first process checks if it is its turn, and finds turn to be 0.. Hence first process passes first while loop, while the second process waits because it is not its turn.
First process reaches to line while(blocked[1-0]) do nothing;
Here, it sees that blocked[1] = true, and hence it keeps waiting...

So we see that first process thinks process2 is blocking and hence it keeps waiting.. while the second process thinks it is turn of first process and thus that waits too...

This is a situation of deadlock, where none of the processes can proceed further, as they are blocking each other.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.