Mutual Exclusion Problem.pdf

The mutual exclusion problem for two processes requires finding sections of code (trying protocol, exit protocol) to preserve mutual exclusion and prevent deadlock or lockout. A simple solution is presented:

Trying Protocol for P1
1. Q1 := true
2. TURN := 1
3. Wait until not Q2 or TURN = 2
4. Critical Section

Exit Protocol for P1
1. Q1 := false

Trying Protocol for P2
1. Q2 := true
2. TURN := 2
3. Wait until not Q1 or TURN = 1
4. Critical Section

Exit Protocol for P2
1. Q2 := false

This solution has a simple structure, making it easy to prove correct. It ensures mutual exclusion and prevents deadlock or lockout.

Proof of Correctness

1. Neither process can be locked out.
2. Mutual exclusion is preserved, as both processes cannot be in their critical sections at the same time.

Generalization to n Processes

A simple n-process solution is presented, using the two-process solution repeatedly in n-1 levels to eliminate at least one process per level until only one remains.

Protocols for Pi
1. For j := 1 to n-1 do
a. Q[i] := j
b. TURN[j] := i
c. Wait until (Vk # i, Q[k] < j) or TURN[j] # i
2. Critical Section
3. Q[i] := 0

This solution requires 2n-1 shared variables of size n. Other algorithms may require fewer variables while satisfying more constraints.