10 Process Synchronization – Solutions III
Mary Anitha Rajam
13.1 Introduction
Cooperating processes may share data among themselves. Cooperating processes use common variables and data structures for sharing data. In a process, that portion of code where the process accesses shared data is called the critical section of the process. If there is no proper synchronization between the processes when they access their critical sections of code, then inconsistency of data may result. We saw a few solutions to the critical section problem in the previous modules (Modules 10, 11 and 12). In this module, we continue to learn more solutions to solve the critical section problem when there are multiple (>=2) processes. The Test And Set and Swap are two hardware instructions that can be executed atomically and can provide solution to the critical section problem. We can use these special instructions to solve the critical section problem.
13.2 Swap instruction
The Swap instruction is defined as follows:
void Swap(boolean &a, boolean &b)
{
boolean temp = a;
a = b;
b = temp;
}
The Swap instruction takes two Boolean variables and swaps the value of the variables. The swapping is done atomically.
13.2.1 Solution to the Critical Section Problem Using the Swap Instruction
A solution to the critical section problem using the Swap instruction is explained in this section. This is a multiple-process solution. More than two processes competing to enter their critical sections can use this solution to solve the critical section problem.
Shared data:
boolean lock; /* (initialized to false) */
The algorithm for process Pi is given below:
do{
key = true;
while (key == true)
Swap(lock, key);
critical section
lock=false;
remainder section
}
In this algorithm, lock is a shared variable and key is a variable local to each process. When process Pi executes this algorithm, it changes the value of its local variable key to true. Then, as long as key is true, Pi keeps swapping the values of lock and key.
If the value of lock is true, even though lock and key are swapped, the value of key remains true. This makes process Pi to continue to check in the while loop.
If the value of lock is false, swapping lock and key will change the value of key to false and the value of lock to true. This makes the process Pi to come out of the while loop (while(key==true) becomes while(false)). If Pi comes out of the while loop, it enters its critical section. The value of lock remains true during this time.
When Pi comes out of its critical section, it changes the value of lock to false.
13.2.2. Mutual Exclusion
Let us now see how this algorithm satisfies mutual exclusion.
P0 key(P0) lock key(P1) P1
| false | ||||
| true | ||||
| Swap | false | true | ||
| true | ||||
| In CS | ||||
| Swap | ||||
| true | ||||
| waits | ||||
| Out of CS | ||||
| false | ||||
| true | false | |||
| In CS |
Let two processes P0 and P1 compete to enter their respective critical sections. Each of the two processes has its own local key variable. Initially, lock is false. The key variables of each of the two processes are true initially. P0 wants to enter critical section first. P0 executes Swap(key(P0), lock). This will make the value of lock true and the value of key false. As key becomes false, P0 comes out of the while loop and enters its critical section. Suppose, P1 wants to enter its critical section when P0 is in its critical section. P1 sets the value of its key to true. P1 executes Swap(key(P1), lock). Since the value of lock is currently true, the value of key also continues to be true. P1 continues to execute in the while loop. When P0 comes out of its critical section, it changes the value of lock to false. Now P1, executing in the while loop, swaps lock and its key. P1’s key becomes false and P1 comes out of the while loop and enters critical section. Thus, it is seen that P1 is not allowed to enter its critical section when P0 is in its critical section. When one process is in its critical section, the value of lock is true and no other process can enter its critical section. Thus, mutual exclusion is satisfied.
13.2.3 Swap – Bounded Waiting
We now see if this algorithm satisfies the bounded waiting requirement.
P0 key(P0) lock key(P1) P1
| false | ||||
| true | ||||
| Swap | false | true | ||
| true | ||||
| In CS | ||||
| Swap | ||||
| true | ||||
| Waits | ||||
| Out of CS | ||||
| Swap | false | true | ||
| In CS | ||||
| Still waits |
Let P0 and P1 be two processes that are competing to access their respective critical sections. Initially, lock is false. Initially, the key variable of each of the two processes is true. P0 wants to enter its critical section first. P0 executes Swap(key(P0), lock). This makes the value of lock true and the value of key false. As key becomes false, P0 comes out of the while loop and enters its critical section. Let P1 want to enter its critical section when P0 is in its critical section. P1 sets the value of its key to true. P1 executes Swap(key(P1), lock). Since the value of lock is currently true, the value of key also continues to be true. P1 continues to execute in the while loop. When P0 comes out of its critical section, it changes the value of lock to false. Let P0 continue to use the CPU without context switch. Say, P0 wants to enter its critical section again. Since the value of lock is currently false, P0 can enter its critical section again. Process P1 continues to wait. Since there was no context switch after P0 came out of its critical section and P0 changed lock to true, P1 could not come out of the while loop. Thus, even though P1 had requested to enter its critical section, P0 is allowed to enter its critical section again and again. Therefore, the bounded waiting requirement is not satisfied.
Thus, it is seen that this algorithm does not satisfy the bounded waiting requirement, though it satisfies the mutual exclusion requirement.
13.3 TestandSet – Bounded-Waiting – Mutual Exclusion
The algorithm given below makes use of the TestAndSet instruction and satisfies all the three requirements for a solution to the critical section problem. This is also a solution when there are n processes.
The shared variables used in the algorithm are as follows:
boolean waiting[n]; //initially false
boolean lock //initially false
The algorithm for process Pi is given below:
do {
waiting[i] = TRUE; key = TRUE;
while (waiting[i] && key) key = TestAndSet(lock);
waiting[i] = FALSE;
// critical section j = (i + 1) % n;
while ((j != i) && !waiting[j]) j = (j + 1) % n;
if (j == i)
lock = FALSE;
else
waiting[j] = FALSE;
// remainder section
} while (TRUE);
The algorithm given above is for process Pi. waiting is an array with ‘n’ elements, where n is the number of processes competing to enter their respective critical sections. lock is a Boolean variable. Each line in the algorithm is explained below:
waiting[i] = TRUE;
Process Pi before checking to enter its critical section sets the value of waiting[i] to true.
key = TRUE;
key is a variable local to process Pi. It is set to true.
while (waiting[i] && key) key = TestAndSet(lock);
For process Pi, waiting[i] and key are true, initially. Therefore, the condition (waiting[i] && key) is true. Since this condition is true, Pi executes TestAndSet(lock). Initially, lock is false. Since lock is false, TestAndSet(lock) returns false and the value of lock is changed to true. The return value is assigned to key. Thus, key is now assigned the value – false. Now, the condition (waiting[i] && key) becomes false. Process Pi comes out of the while loop.
If lock is true, TestAndSet(lock) returns true. Therefore, key is assigned true. The condition in the while loop remains true. Process Pi continues to execute in while loop.
waiting[i] = FALSE;After coming out of the while loop, Pi changes waiting[i] to false and enters its critical section.
Process Pi, after coming out of its critical section, checks if any other process is waiting to enter its critical section. If any other process is waiting to enter its critical section, Pi changes the value of waiting of that process to false. Else, changes the value of lock to false. Changing the value of waiting of a process to false will make that waiting process to come out of the while loop and enter its critical section. If no process is waiting, the value of lock is changed to false. This paves the way for any other process wanting to enter its critical section, to enter its critical section in future.
j = (i + 1) % n;
The next process Pj to be checked is found. j is found by incrementing i.
while ((j != i) && !waiting[j]) j = (j + 1) % n;
Pi checks if waiting[j] is true, for every other process j. If true, Pi comes out of its while loop. This means that there is another process j in its entry section waiting to enter its critical section. If waiting[j] is not true, process j is not in its entry section. Therefore, the other processes are checked one after the other. When j becomes equal to i, it means that all other processes have been checked already. There is no other process waiting in its entry section.
if (j == i)
lock = FALSE;
else
waiting[j] = FALSE;
If j==i, there is no other process in its entry section and lock is made false. Else, waiting[j] (j is the process waiting in its entry section) is made false.
13.3.1 Mutual exclusion
| waiting[0] | P0 | key(0) | lock | key(1) | P1 | waiting[1] |
| false | ||||||
| false | false | |||||
| true | true | true | true | |||
| TestAndSet(lock) | ||||||
| false | true | |||||
| false | ||||||
| Enters CS | ||||||
| TestAndSet(lock) | ||||||
| True | ||||||
| Waits |
The sequence given above shows how the algorithm satisfies the mutual exclusion requirement. Let P0 and P1 be the two processes competing to enter their respective critical sections. Initially, lock, waiting[0] and waiting[1] are false. P0 changes waiting[0] and its local variable key(0) to true. P0 then executes TestAndSet(lock). Since lock is false, TestAndSet(lock) returns false and the value is assigned to key(0). The value of lock is changed to true. Since key(0) becomes false, P0 comes out of its while loop, changes waiting[0] to false and enters its critical section. While P0 is in its critical section, let P1 want to enter its critical section. P1 changes waiting[1] and its local variable key(1) to true. P0 then executes TestAndSet(lock). Since lock is true, TestAndSet(lock) returns true and the value ‘true’ is assigned to key(0). Since key(0) is true, P1 continues to execute in its while loop. Thus, when one process is in its critical section, the other processes are not allowed to enter their respective critical sections. Thus, mutual exclusion is satisfied.
13.3.2 Progress – Scenario 1
| waiting[0] | P0 | key(0) | lock | key(1) | P1 | waiting[1] |
| false | ||||||
| false | false | |||||
| true | true | |||||
| true | true | |||||
| TestAndSet(lock) | ||||||
| false | true | |||||
| false | ||||||
| Enters CS | ||||||
| TestAndSet(lock) | ||||||
| True | ||||||
| Waits | ||||||
| Out of CS | false | |||||
| Enters CS |
The sequence given above, shows how the algorithm satisfies the progress requirement. Let P0 and P1 be the two processes competing to enter their respective critical sections. Initially, lock, waiting[0] and waiting[1] are false. P0 changes waiting[0] and its local variable key(0) to true. Now, there is a context switch and P1 changes waiting[1] and key(1) to true. Again, there is a context switch and P0 executes TestAndSet(lock). Since lock is false, TestAndSet(lock) returns false and the value ‘false’ is assigned to key(0). The value of lock is changed to true. Since key(0) becomes false, P0 comes out of while loop, changes waiting[0] to false and enters its critical section. Now, if P1 gets the CPU, it executes TestAndSet(lock). Since lock is true, TestAndSet(lock) returns true and the value ‘true’ is assigned to key(0). Since key(0) is true, P1 continues to execute in its while loop. When P0 comes out of its critical section, it checks if the waiting value of any other process is true. This checking is done one process after the other. In this example, since there are only two processes, the waiting status of P1 is checked. Since waiting[1] is true, !waiting[1] is false. This makes the condition in the while loop false for P0. P0 comes out of the while loop and changes waiting[1] to false. When waiting[1] becomes false, P1 comes out of the while loop while (waiting[i] && key) key = TestAndSet(lock);. P1 enters its critical section. Hence, there is progress.
13.3.3 Progress – Scenario 2
| waiting[0] | P0 | key(0) | lock | key(1) | P1 | waiting[1] |
| false | ||||||
| false | false | |||||
| true | true | |||||
| TestAndSet(lock) | ||||||
| false | true | |||||
| false | ||||||
| Enters CS | ||||||
| Out of CS | ||||||
| No other process is waiting | ||||||
Another sequence of execution to show that progress is satisfied is given above. Let P0 and P1 be the two processes competing to enter their respective critical sections. Initially, lock, waiting[0] and waiting[1] are false. P0 changes waiting[0] and its local variable key(0) to true. Since lock is false, TestAndSet(lock) returns false and the value is assigned to key(0). The value of lock is changed to true. Since key(0) becomes false, P0 comes out of the while loop, changes waiting[0] to false and enters its critical section. When P0 comes out of its critical section, it checks if the waiting value of any other process is true. This checking is done one process after the other. In this example, since there are only two processes, the waiting status of P1 is checked. Since waiting[1] is false, !waiting[1] becomes true. This makes the condition in the while loop true for P0. So, P0 executes j=j +1 % n. j was 1 earlier. Now, it becomes 0. Since j becomes equal to i, P0 comes out of the while loop and changes lock to false. Since lock is changed to false, any process can enter its critical section in future.
13.3.4 Bounded waiting:
After a process comes out of its critical section, it checks if the next process is waiting to enter its critical section. Similarly, every other process is checked. Only if no other process is in the entry section, the value of lock is changed to false. Thus, when there are n processes, a process may have to wait for n–1 critical section executions before its turn to enter critical section. Thus, the bounded waiting requirement is satisfied.
13.4 Summary
In this module, we first learned a solution to the critical section problem using the Swap instruction. But the solution did not satisfy the bounded waiting requirement. Next, we learned a solution to the critical section problem using the TestAndSet instruction that satisfies all the three requirements.
References
- Abraham Silberschatz, Peter B. Galvin, Greg Gagne, “Operating System Concepts”, Ninth Edition, John Wiley & Sons Inc., 2012.