Question

Two processes A and B are being executed concurrently, and they share several resources during execution, such as memory, processor time, and input output devices. Explain how the mutual exclusion approach can be used by A and B to avoid collision when both processes wish to use a certain shared resource

Answer 1

"Peterson's Algorithm"

• "a simple algorithm that can be run by two processes to ensure mutual exclusion for one resource (say one variable or data structure)"
• "does not require any special hardware"
• "it uses busy waiting (a spinlock)"

Peterson's Algorithm
"Shared variables are created and initialized before either process starts. The shared variables flag[0] and flag[1] are initialized to FALSE because neither process is yet interested in the critical section. The shared variable turn is set to either 0 or 1 randomly (or it can always be set to say 0)."

var flag: array [0..1] of boolean;
turn: 0..1;
flag[k] means that process[k] is interested in the critical section
flag[0] := FALSE;
flag[1] := FALSE;
turn := random(0..1)

After initialization, each process, which is called process i in the code (the other process is process j), runs the following code:

repeat
flag[i] := TRUE;
turn := j;
while (flag[j] and turn=j) do no-op;
CRITICAL SECTION
flag[i] := FALSE;
REMAINDER SECTION
until FALSE;

Information common to both processes:
turn = 0
flag[0] = FALSE
flag[1] = FALSE

EXAMPLE 1
Process 0	Process 1
i = 0, j = 1	i = 1, j = 0
flag[0] := TRUE turn := 1 check (flag[1] = TRUE and turn = 1) -  Condition is false because flag[1] = FALSE - Since condition is false, no waiting in while loop -  Enter the critical section -  Process 0 happens to lose the processor
	flag[1] := TRUE turn := 0 check (flag[0] = TRUE and turn = 0) - Since condition is true, it keeps busy waiting until it loses the processor
- Process 0 resumes and continues until it finishes in the critical section - Leave critical section flag[0] := FALSE - Start executing the remainder (anything else a process does besides using the critical section) - Process 0 happens to lose the processor
	check (flag[0] = TRUE and turn = 0) - This condition fails because flag[0] = FALSE - No more busy waiting - Enter the critical section

EXAMPLE 2
Process 0	Process 1
i=0, j=1	i=1, j=0
flag[0] = TRUE turn = 1 - Lose processor here
	flag[1] := TRUE turn := 0 check (flag[0] = TRUE and turn = 0) - Condition is true so Process 1 busy waits until it loses the processor
check (flag[1] = TRUE and turn = 1) -  This condition is false because turn = 0 - No waiting in loop - Enters critical section

EXAMPLE 3
Process 0	Process 1
i=0, j=1	i=1, j=0
flag[0] = TRUE - Lose processor here
	flag[1] = TRUE turn = 0 check (flag[0] = TRUE and turn = 0) - Condition is true so, Process 1 busy waits until it loses the processor
turn := 1 check (flag[1] = TRUE and turn = 1) - Condition is true so Process 0 busy waits until it loses the processor
	check (flag[0] = TRUE and turn = 0) - The condition is false so, Process 1 enters the critical section