We have already used 3 methods to solve the problem of Critical section. This is the fourth method. Peterson Solution combines the logic of turn variables as well as flag variables. I will show you step by step how Peterson Solution solves the problem of criticals ection. So, let's start, shall we?
Peterson Solution
In the peterson solution we will consider 2 process P0 and P1, Turn variable whose value can be either 0 or 1 and a flag boolean array whose value is initialised to F for both slots initially.
The mistake that we were making in turn variable was that we were never asking the process if it wants to enter into the critical section or not. That's why it did not show Progress.
In flag variable the mistake we committed was that if both the process makes the value of flag T then the system was trapped in deadlock. Hence use of flag variable too did not showed us Progress.
Now let's trace the above code and prove if it holds good for all criterias of critical section or not.
1. Suppose P0 wants to enter critical section so flag[0] is set T and turn is set 1. Now while loop will be executed. It says turn == 1 which is true and flag[1]==T which is false because P1 is not interested in entering into critical section till this time. So, overall while condition will not execute because true && false = false and P0 will enter into critical section.
2. Now let say P1 wants to enter into critical section too. So, flag[1] is set T and turn is set 0. Now while loop will be executed. It says turn == 0 which is true and flag[0]==T which is true because P0 is already in the critical section. So, overall the while condition will execute because true && true = true and P1 will be trapped in the while loop.
3. Now let say P0 comes out of critical section and it sets flag[0] to F. So, now P1 can enter into critical section because flag[0] is F so while loop condition will be false.
4. Now let say P0 again wants to enter into critical section so it sets flag[0]=T and turn=1. Now while loop will be executed. It says turn == 1 which is true and flag[1]==T which is also true because P1 is in the critical section. So, overall while condition will not be execute because true && true = false and P0 will be trapped in the while loop.
5. Now, we say see that at a time only 1 process can enter critical section so Mutual Exclusion holds good for this solution.
6. Now let's see if it shows progress also or not. Assume the flag variable is set to F again for both the processes.
7. Suppose P0 wants to enter critical section so flag[0] is set T and turn is set 1. Now while loop will be executed. It says turn == 1 which is true and flag[1]==T which is false because P1 is not interested in entering into critical section till this time. So, overall while condition will not execute because true && false = false and P0 will enter into critical section.
8. Now let say P0 comes out of critical section and it sets flag[0]=F.
9. P1 is not interested to enter into critical section till this time.
10. Now let say P0 again wants to enter into critical section. So flag[0] is set T and turn is set 1. Now while loop will be executed. It says turn == 1 which is true and flag[1]==T which is false because P1 is not interested in entering into critical section . So, overall while condition will not execute because true && false = false and P0 will enter into critical section again.
11. So we can observe that a process can access critical section multiple time. But when we were discussing the Flag variable solution for critical section then we observed that due to strict alternation between P0 and P1 the processes went into Deadlock. Now, let's see if this occurs in this solution or not.
12. Assume the flag variable is set to F again for both the processes.
13. Suppose P1 wants to enter critical section so flag[1] is set T and turn is set 0. Since we want to check if the processes goes into deadlock so we context switch before executing while loop.
14. Now P0 enters into critical section so flag[0] is set T and turn is set 1. Now while loop will be executed. It says turn == 1 which is true and flag[1]==T which is true as well because P1 was context switched after initialising flag[1] to T. So, overall while condition will execute because true && true = true and P0 will not enter into critical section.
14. Now context switch will occur and control comes to P1 again and while loop will be executed. It says turn == 0 which is false and flag[0]==T which is true because P0 has been initialised flag[0] to T. So, overall while condition will not execute because false && true = false and P1 will enter into critical section.
15. So, you can see that it is possible that both the processes are interested in entering into the critical section at a time but turn variable can have either 0 or 1 value so only either P0 or P1 will enter into critical section.
16. So this solution holds good for Progress as well.
17. Now lets see if it holds good for Bounded Wait or not. Assume flag is initialised to F for both processes again.
18. Suppose P0 wants to enter critical section so flag[0] is set T and turn is set 1. Now while loop will be executed. It says turn == 1 which is true and flag[1]==T which is false because P1 is not interested in entering into critical section till this time. So, overall while condition will not execute because true && false = false and P0 will enter into critical section.
19. Now let say P1 wants to enter into critical section too. So, flag[1] is set T and turn is set 0. Now while loop will be executed. It says turn == 0 which is true and flag[0]==T which is true because P0 is already in the critical section. So, overall the while condition will execute because true && true = true and P1 will be trapped in the while loop.
20. Now let say P0 comes out of critical section and it sets flag[0] to F. So, now P1 can enter into critical section because flag[0] is F so while loop condition will be false.
21. Now let say P0 again wants to enter into critical section so it sets flag[0]=T and turn=1. Now while loop will be executed. It says turn == 1 which is true and flag[1]==T which is also true because P1 is in the critical section. So, overall while condition will not be execute because true && true = false and P0 will be trapped in the while loop.
22. So, we can say that we have to wait for 1 round for execution of a process. Thus, This solution holds good for Bounded Waiting also.
Conclusion
Peterson solution satisfies all three criterias of critical section.