8 Process Synchronization – Solutions I

Mary Anitha Rajam

11.1  Introduction

When two or more concurrent processes communicate among themselves, they share data when they access common variables and data structures. Hence, there is a need for synchronization between the processes. The portion of code in each of the processes where they access the common data structures or variables is called their respective critical sections of code. If there is no proper synchronization between the processes when they access their critical sections of code, inconsistency of data may result. Hence, any solution to the critical section problem should satisfy the mutual exclusion, progress and bounded waiting conditions. In the previous module (Module 10), we learnt a solution to the critical section problem, which provided a solution when only two processes were involved. This module is a continuation of the previous module and describes different other solutions to the critical-section problem and explains how the solutions satisfy mutual exclusion, progress and bounded waiting requirements.

11.2  Solution 2

In the solution to the critical section problem that we learnt in the previous module, we learnt a solution when only two processes were involved. That solution made use of a variable called ‘turn’ to provide synchronization. But that solution satisfied only the mutual exclusion requirement.

In this second solution, a Boolean array called ‘flag’ is used to provide synchronization. This is also a solution when only two processes are involved. The solution is given below:

Shared variables

boolean flag[2];           /* initially flag [0] = flag [1] = false*/

flag [i] = true                /* Pi ready to enter its critical section*/

Process Pi:

do {

flag[i] := true;

while (flag[j]) ;

,

critical section

flag [i] = false;

remainder section

} while (1);

Here, the array flag is common to both the processes which use this algorithm to solve the critical section problem. The array has two elements flag[0] and flag[1]. Initially, both of the elements are initialized to false.

Suppose Pi and Pj are the two processes that want to synchronize. If process (Pi) wants to enter the critical section, Pi sets the value of flag[i] to true. Pi then checks if flag[j] is true or false. If the other process, Pj is currently in its critical section, flag[j] is true. As long as Pj is in its critical section, Pi is stuck in the while loop. When Pj comes out of its critical section, flag[j] is made false. Pi, which is now executing while (flag[j]); comes out of the while loop and enters its critical section. After executing the critical section and after coming out of the critical section, process Pi executes the exit section. In the exit section, Pi changes back the value of flag[i] to false (flag[i] was changed to true by Pi in its entry section).

We now see whether all the three conditions—mutual exclusion, progress and bounded waiting—are satisfied by this algorithm. Let P0 and P1 be the two processes that are to be synchronized. To show that the algorithm in solution 2 satisfies mutual exclusion, one possible sequence of execution of the two processes is given below:

Algorithm 2 – Mutual Exclusion

According to the mutual exclusion requirement, when process P0 is in its critical section, process P1 should wait and vice versa.

Here, initially, both flag[0] and flag[1] are false. When process P0  wants to enter its critical section, P0 changes flag[0] to true. P0 then checks the value of flag[1]. Since P1 is still not competing to enter the critical section, flag[1] is false. Since the value of flag[1] is false, in process P0, the condition inside the while loop becomes false (while(flag[1])) and process P0 comes out of the while loop. P0 now enters its critical section. Now, when P0 is in the critical section, if P1 wants to enter its critical section, P1 changes the value of flag[1] to true and checks the value of flag[0] inside the while loop. Since the value of flag[0] is true, the condition inside the while loop remains true. Therefore, P1 continues to execute inside the while loop. When P0 comes out of its critical section, P0 changes the value of flag[0] to false. That is, process P1 waits till process P0 comes out of its critical section. Thus, it is seen that, when process P0 is in its critical section, process P1 is not allowed to enter its critical section. Therefore, mutual exclusion is satisfied.

Let us see how the algorithm satisfies the progress requirement.

Algorithm 2–Progress

Progress is not satisfied

According to the progress requirement, when two processes are competing to enter the critical section, the decision as to which process will enter the critical section first, should not be postponed indefinitely. In the example shown above, both the processes P0 and P1 want to enter the critical section at the same time. P0 sets the value of flag[0] to true. Suppose, there is a context switch, P1 is assigned the CPU and P1 also sets the value of flag[1] to true. Now both the processes continue to wait in their respective while loops. Both the processes are unable to proceed further. Thus, the progress requirement is not satisfied.

We will now see another solution to the critical section problem. This solution combines the features used in solutions 1 and 2 to provide a solution to the critical section problem.

11.3  Solution 3 

Similar to the previous two solutions, this is also a solution when only two processes compete to execute their respective critical sections of code. This solution makes use of the variable turn and the flag array used in solution 1 and solution 2 respectively. The solution is given below:

In this solution, a variable turn and a Boolean array flag are used to provide a solution to the critical section problem. Let Pi and Pj be the two processes competing to enter the critical section. Initially, the values of flag[i] and flag [j] are set to false. The initial value of turn can be either i or j. If process Pi wants to enter its critical section, Pi sets the value of flag[i] to true and changes the value of turn to j. Now Pi checks if the value of flag[j] is true and the value of turn is j. If process Pj is not competing to enter the critical section and hence is not yet in the entry section, the value of flag[j] would not have been modified. It would still remain as false. Since flag[j] is false, the condition in the while loop for process Pi (flag[j] && turn) becomes false and process Pi enters the critical section.

Now, when process Pi is in its critical section, let us see what happens if Pj wants to enter its critical section. Pj sets flag[j] to true and changes turn to i. Pj checks the condition in the while loop (flag [i] && turn == i). Since flag[i] is true and turn is equal to i, Pj waits in the while loop. Pj continues to wait in the while loop as long as Pi is in its critical section. When Pi comes out of its critical section, Pi changes the value of flag[i] to false in its exit section. When flag[i] becomes false, the condition (flag [i] && turn == i) in the while loop becomes false for process Pj. Hence, Pj comes out of the while loop and enters its critical section.

We now see whether all the three conditions—mutual exclusion, progress and bounded waiting—are satisfied by this algorithm. Let P0 and P1 be the two processes that are competing to enter the critical section.

The above scenario shows how mutual exclusion is satisfied. Initially, flag[0] and flag[1] are false. Let the value of turn be 0. If process P0 wants to enter its critical section, it changes the value of flag[0] to true and the value of turn to 1. Process P1 is not yet competing to enter its critical section. P0 checks the value of flag[1] and the value of turn in the while loop. As flag[1] is false and turn = 1, the condition (flag[1] && turn==j) becomes false. That is, even though the value of turn==j is true (here, j=1, since P0 is executing), the value of flag[1] is false. Therefore, the process P0 comes out of the while loop and enters its critical section.

When P0 is in the critical section, let P1 want to enter its critical section. P1 changes flag[1] to true and changes turn to 0. In the condition inside the while loop, P1 checks (flag[0] && turn=0). Since flag[0] is true and turn is 0, both the checks are true and the condition remains true. P1 continues to wait in the while loop. When P0 comes out of critical section, it changes flag[0] to false. Now the condition (flag[0] && turn=0), which is being checked by P1 becomes false. P1 now enters its critical section.

Thus it is seen that when P0 is in its critical section, P1 is not allowed to enter its critical section. P1 is allowed to enter its critical section only after P0 comes out of its critical section. Thus, mutual exclusion is satisfied.

We now look at another scenario to understand that the algorithm satisfies mutual exclusion.

Algorithm 3 – Mutual Exclusion

Scenario 2:

In this scenario, initially, both flag[0] and flag[1] are false. Process P0 wants to enter its critical section, changes flag[0] to true and turn to 1. Immediately, there is a context switch and P1 starts executing. P1 changes flag[0] to true and changes turn to 0. Now, the value of flag[0] and flag[1] are true. The value of turn now decides the process that can enter its critical section. When P1 checks the condition in its while loop (flag[0] && turn==0), both flag[0] and turn==0 are true. P1 waits in the while loop. When P0 checks its while loop (flag[1] && turn==1), the condition flag[1] is true, but the condition turn==1 is false. Therefore, P0 comes out of the while loop and enters its critical section. When P0 comes out of its critical section, it changes the value of flag[0] to false and then P1 can enter its critical section. Thus, it is seen that only one process is allowed to enter its critical section at a particular time and hence, mutual exclusion is satisfied.

Algorithm 3 – Progress

Let us now see how progress is satisfied using the sequence shown below:

In the scenario explained above, initially, both flag[0] and flag[1] are false. Process P0 wants to enter its critical section and changes flag[0] to true. Immediately, there is a context switch and P1 starts executing. P1 changes flag[1] to true. Again, there is a context switch and P0 changes turn to 1. There is a context switch again and P1 changes turn to 0. Now, the values of flag[0] and flag[1] are true. Still, based on the value of turn, one of the two processes can enter the critical section. In algorithm 2, we saw that progress is not satisfied when both the processes set the value of flag[0] and flag[1] to true at the same time. Thus, in this algorithm, the decision as to which process can enter the critical section is not postponed indefinitely. Hence, the progress requirement is satisfied.

Algorithm 3 – Progress

Another scenario to explain progress is given below:

Scenario 2:

In the scenario shown above, both P0 and P1 want to enter their respective critical sections. Initially, flag0] and flag[1] are false and turn is 0. flag[0] is changed to true by P0 and flag[1] is changed to true by P1. P1 changes turn to 0. Then, P0 changes turn to 1. In the while loop of P0, flag[1] is true and turn is equal to 1. Since both the conditions are true, the condition checked in the while loop is true. Therefore, P0 continues to wait in the while loop. In the while loop of P1, flag[0] is true, but the value of turn is not equal to 0. Since one of the conditions is not true, the condition checked in the while loop is false and P1 comes out of the while loop. P1 enters its critical section. Thus, it is seen that the value of turn decides which process enters the critical section. The value of turn is based on which process sets the value of turn finally.

Algorithm 3 – Bounded Waiting 

For the bounded waiting requirement, after a process has requested to enter its critical section, the amount of time the process waits should be limited. We will now see how the algorithm satisfies bounded waiting.

To understand that bounded waiting is satisfied, P0 first requests to enter its critical section and then, P1 tries to enter its critical section twice. We need to understand that after P0 requests to enter its critical section, P1 is not allowed to enter its critical section more than once.

Initially, flag[0] and flag[1] are false. Let the value of turn be 0 initially. P0 changes the value of flag[0] to true. Then there is a context switch and P1 changes flag[1] to true. P1 changes turn to 0. Now, again there is a context switch and P0 changes the value of turn to 1. P0 waits in the while loop. P1 can now enter its critical section. P1 comes out of its critical section and changes the value of flag[1] to false. Suppose P1 continues to use the CPU and wants to enter its critical section again. P1 changes the value of flag[1] to true and the value of turn to 0. Now, P1 cannot enter its critical section unless P0 enters its critical section, comes out and changes the value of flag[0] to true. P1 is not allowed to enter critical section twice after P0 had requested to enter critical section. Thus, bounded waiting requirement is satisfied.

5.3  Summary

This module discussed two solutions to the critical section problem. But both of these solutions work when there are only two processes. The first solution discussed in this module satisfies the mutual exclusion requirement but does not satisfy the progress requirement. The second solution discussed in this module satisfies all the three requirements.

References

1. Abraham Silberschatz, Peter B. Galvin, Greg Gagne, “Operating System Concepts”, Ninth Edition, John Wiley & Sons Inc., 2012.
2. William Stallings, “Operating Systems: Internals and Design Principles”, Seventh Edition, Pearson, 2012.