Peterson's Solution

This solution is for 2 processes to enter into critical section. This solution works for only 2 processes.

Properties:

We have following properties of this solution:
Following are some properties of this method:
  1. This solution is developed in user mode.
  2. This is a software mechanism.
  3. This is a busy waiting solution.
  4. It used both TURN and INTERESTED variable.

The below pseudo code will give you an idea about this solution:


1. #define N 2
2. #define TRUE 1
3. #define FALSE 0
4. int INTERESTED[N] = FALSE
5. int TURN;
6. void Entry_Section(int process)
7. {
8.  int other;
9.  other = 1 – process;
10.     INTERESTED[process] = TRUE;
11.     TURN  = process;
12.     while(INTERESTED[other] == TRUE && TURN = process)
13. }
14. void Exit_Section(int process)
15. {
16.     INTERESTED[process] = FALSE;
17. }

Explanation:

Let’s say P0 starts first then entry section function for P0 will be called and values will be:
other = 1 – 0 = 1
INTERESTED[0] = TRUE
TURN = 0
while(INTERESTED[1] == TRUE && TURN = 0) // this while condition will be false
as INTERESTED[1] = F and TURN is 0 And process will enter into critical section.
Now let’s say process P1 will come and entry section function will be called for it also:
other = 1 -1 = 0 // this variable will tell process id of other process
INTERESTED[1] = T // it means the process is interested to get into critical section
while(INTERESTED[0] == TRUE && TURN = 1) // this while condition will be true and process will be
       
//in while loop, doing busy waiting .
So now process P0 will come out of the critical section and will call exit section function and will made
INTERESTED[0] = False
So if process P1 will come in scheduling then while loop condition will become false and then P1 will go
into critical section. Condition will false because:
while(INTERESTED[0] == TRUE && TURN = 1) // INTERESTED[0] is false now && TURN = 1 which is false after AND operation.
So that’s how this solutions is working and the mutual exclusion condition is explained.


Execution Sequence:

Entry section function is called for P0
P0 : 8, 9, 10 | P1: 8, 9, 10, 11, 12(here loop) // numbers are line numbers from above code.
     // “|” this means process got preempted
So after the above sequence process P1 will wait in the while loop
You will be thinking that whichever process will execute line number 10, will get the critical section.
Again the sequencing continues;
P0: 11 , 12 (while loop) // it got stuck into the loop because INTERESTED[1] is True and TURN = 0 , so loop will continue
After P0, P1 will come
So line number 12 will now break because TURN is 0 [because of process P0] and the condition TURN = 1
will become false and process P1 will go into critical section.
Note: So whichever process make TURN first will go into critical section first.


Properties followed by this solution:

  1. Mutual Exclusion: This condition is followed, explained in above example.
  2. Progress: It is definitely followed as whichever process needs critical section, will make the INTERESTED value as true.
  3. Bounded Waiting: This property is also followed as whichever process can make the TURN variable first, will get into critical section.
  4. Platform Neutrality: yes because the solution is in user mode.

Disadvantage:
  1. This solution works for 2 processes, but this solution is best scheme in user mode for critical section.
  2. This is also a busy waiting solution so CPU time is wasted. And because of that “SPIN LOCK” problem can come. And this problem can come in any of the busy waiting solution.





Quantitative Aptitude
Reasoning
Programming
Interview