Principle of mutual exclusion of processes

Idle admission: when the critical area is idle, a process should be allowed to access it.

Wait when busy: when the critical area is being accessed, other processes trying to access need to wait.

Limited waiting: to enter the critical area within a limited time, the packaging will not be hungry.

Let the right wait: for processes that cannot enter the critical area, release the processor to prevent busy, etc

Single sign method

Algorithmic thought

After accessing the critical area, two processes will give the permission to use the critical area to another process. In other words, the permission of each process to enter the critical zone can only be given by another process.

int turn = 0; // turn indicates the process number currently allowed to enter the critical area

P0 process:
while(turn != 0);  1 //Entry area
critical section;  2 //Critical zone
turn =  1;         3 //Exit zone
remainder section  4 //Residual area

P1 process:
while(turn != 1);    5 //Entry area
critical section;    6 //Critical zone
turn = 0;            7 //Exit zone
remainder section;   8 //Residual area

The initial value of turn is 0, that is, only process 0 is allowed to enter the critical area at the beginning.

If P1 runs on the processor first, it will always be stuck at 5. Until the time slice of P1 runs out, scheduling occurs, and the processing operation on P0 is switched.

Code 1 will not block P0. P0 can normally access the critical area. Even if P1 is switched back during P0 accessing the critical area, P1 will still be stuck at 5.

Therefore, the algorithm can realize that "at most one process is allowed to access the critical area at the same time".

Turn indicates the process number currently allowed to enter the critical area. Only the process currently allowed to enter the critical area will modify the value of turn after accessing the critical area. In other words, for the access to the critical area, press P0 ➡️ P1 ➡️ P0 ➡️ P1 ➡️...... So take turns visiting.

The problem with this "alternate access" is that if the process allowed to enter the critical area is P0, and P0 does not access the critical area all the time, P1 is not allowed to access although the critical area is idle at this time.

Therefore, the main problem of the single sign method is that it violates the principle of "free concession".

Double sign first check method

Algorithmic thought

Set a Boolean array flag [], and each element in the array is used to mark the meaning that each process wants to enter the critical area. For example, "flag[0]=true" means that process 0 P0 now wants to enter the critical area. Before entering the critical area, each process first checks whether there are other processes that want to enter the critical area. If not, set its corresponding flag[i] to true, and then start accessing the critical area.

bool flag[2];    // An array representing the willingness to enter the critical zone
flag[0] = false;
flag[1] = false; // At first, it was set that neither process wanted to enter the critical zone

P0 Process:
while(flag[1]);    1 // If P1 has entered the critical zone, P0 keeps waiting
flag[0] = true;    2 // The process marked P0 wants to enter the critical zone
critical section;  3 // Access critical area
flag[0] = false;   4 // After accessing the critical area, modify the mark P0 and do not want to use the critical area
remainder section; 

P0 Process:
while(flag[0]);    1 // If P0 has entered the critical zone, P1 keeps waiting
flag[1] = true;    2 // The process marked P1 wants to enter the critical zone
critical section;  3 // Access critical area
flag[1] = false;   4 // After accessing the critical area, modify the mark P1 and do not want to use the critical area
remainder section; 

If it is executed in the order of 1, 5, 2, 6, 3, 7,..., P0 and P1 will access the critical area at the same time.

Therefore, the main problem of the double sign first inspection method is that it violates the principle of "busy, wait".

The reason is that process switching may occur before and after "check" and "lock" in the entry area.

Double mark post inspection method

Algorithmic thought

Double sign first check the revision of the method. The problem of the former algorithm is to "check" and then "lock", but these two operations can not be completed at one time, which leads to the problem that the two processes enter the critical zone at the same time. Therefore, people think of the method of "locking" before "checking" to avoid the above problems.

bool flag[2];        //An array representing the willingness to enter the critical zone
flag[0] = false;    
flag[1] = false;     //At first, it was set that neither process wanted to enter the critical zone

P0 Process:
flag[0] = true;    1
while(flag[1]);    2
critical section;  3
flag[0] = false;   4
remainder section;

P1 Process:
flag[1] = true;    5 //The process marked P1 wants to enter the critical zone
while(flag[0]);    6 //If P0 also wants to enter the critical zone, P1 cycles and waits
critical section;  7 //Access critical area
flag[1] = false;   8 //After accessing the critical area, modify the mark as P1 and do not want to use the critical area
remainder section;

If the sequence of 1, 5, 2, 6... Is followed, P0 and P1 will not enter the critical zone.

Therefore, although the double flag post inspection method solves the problem of "busy waiting", it also violates the principles of "idle letting in" and "limited waiting", and will produce the phenomenon of "hunger" because all processes are unable to access critical resources for a long time.

Peterson algorithm

Algorithmic thought

In the double sign post inspection method, both processes strive to enter the critical area, but no one will let anyone, and finally no one can enter the critical area. Gary L.Peterson came up with a method. If both sides are trying to enter the critical area, they can try "Kong Rong let the pear" and take the initiative to let the other party use the critical area first.

bool flag[2];    //An array indicating the willingness to enter the critical area. The initial values are false
int turn = 0;    //turn indicates which process is allowed to enter the critical area first

P0 process
flag[0] = true;                1
turn = 1;                      2
while(flag[1] && turn == 1);   3
critical section;              4
flag[0] = fales;               5
remainder section;

P10 process
flag[1] = true;                6   //Say you want to enter the critical zone
turn = 0;                      7   //The priority person can enter the critical area
while(flag[0] && turn == 0);   8   //If the other party wants to enter, and the last time is to "let the pear", then he will wait in a circle
critical section;              9
flag[1] = fales;               10  //After accessing the critical area, it means that you no longer want to access the critical area
remainder section;

Access area:

1. Actively strive for
2. Active humility
3. Check whether the other party also wants to use it, and whether he said "polite words" the last time

Peterson algorithm solves the process mutual exclusion problem with software method, and abides by the three principles of idle admission, busy waiting and limited waiting, but it still abides by the principle of concession waiting.