Petersons's Solution
Peterson's Solution
Next, we illustrate a classic software-based solution to the critical-section problem known as Peterson's solution. Because of the way modern computer architectures perform basic machine-language instructions, such as load and store, there are no guarantees that Peterson's solution will work correctly on such architectures. However, we present the solution because it provides a good algorithmic description of solving the critical-section problem and illustrates some of the complexities involved in designing software that addresses the requirements of mutual exclusion, progress, and bounded waiting requirements. Peterson's solution is restricted to two processes that alternate execution between their critical sections and remainder sections. The processes are numbered Po and Pi. For convenience, when presenting P,-, we use Pj to denote the other process; that is, j equals 1 — i. Peterson's solution requires two data items to be shared between the two processes:
int turn;
boolean flag [2]
• The variable turn indicates whose turn it is to enter its critical section. That is, if turn == i, then process P; is allowed to execute in its critical section. The flag array is used to indicate if a process is ready to enter its critical section. For example, if f lag[i] is true, this value indicates that P; is ready to enter its critical section. With an explanation of these data structures complete, we are now ready to describe the algorithm shown in Figure 6,2.
These Topics Are Also In Your Syllabus | ||
---|---|---|
1 | Process Concept | link |
2 | Operating System Operations- Dual-Mode Operation, Timer | link |
You May Find Something Very Interesting Here. | link | |
3 | Operations on Process | link |
4 | Threads overview | link |
5 | Multithreading Models | link |
To enter the critical section, process P, first sets flag[i] to be true and then sets turn to the value j, thereby asserting that if the other process wishes to enter the critical section, it can do so. If both processes try to enter at the same time, turn will be set to both i and j at roughly the same time. Only one of these assignments will last; the other will occur but will be overwritten immediately. The eventual value of turn decides which of the two processes is allowed to enter its critical section first. We now prove that this solution is correct. We need to show that:
1. Mutual exclusion is preserved.
2. The progress requirement is satisfied.
3. The bounded-waiting requirement is met.
These Topics Are Also In Your Syllabus | ||
---|---|---|
1 | Deadlock prevention | link |
2 | Deadlock Avoidance | link |
You May Find Something Very Interesting Here. | link | |
3 | Deadlock Recovery | link |
4 | Stable Storage Implementation | link |
5 | File System Mounting | link |
To prove property 1, we note that each P; enters its critical section only if either flag[j] == false or turn -- i. Also note that, if both processes can be executing in their critical sections at the same time, then flag [0] == flag [1] == true. These two observations imply that Po and Pi could not have successfully executed their while statements at about the same time, since the value of turn can be either 0 or 1 but cannot be both. Hence, one of the processes —say Pj—must have successfully executed the while statement, whereas P, had to execute at least one additional statement ("turn == j"). However, since, at that time, f lag[j] == true, and turn == j, and this condition will persist as long as Pj is in its critical section, the result follows: Mutual exclusion is preserved.
To prove properties 2 and 3, we note that a process P, can be prevented from entering the critical section only if it is stuck in the while loop with the condition flag [j] == true and turn == j; this loop is the only one possible. If P; is not ready to enter the critical section, then flag [j] == false, and P; can enter its critical section. If Pj has set flag [j ] to true and is also executing in its while statement, then either turn == i or turn == j . If turn == i, then P, will enter the critical section. If turn == j, then Pj will enter the critical section. However, once P; exits its critical section, it will reset f lag[j] to false, allowing P, to enter its critical section. If Pj resets flag [j ] to true, it must also set turn to i. Thus, since P, does not change the value of the variable turn while executing the while statement, P,- will enter the critical section (progress) after at most one entry by P/ (bounded waiting).