7 Process Synchronization
Mary Anitha Rajam
10.1 Introduction
Cooperating processes share data either directly or through files. When two or more processes access shared data concurrently, data inconsistency may result. Maintaining data consistency requires mechanisms that will ensure the orderly execution of cooperating processes. The section of code in each process in which the process accesses shared data is called the critical-section of the process. During the execution of a process, the process may access many such shared data or the same shared data a number of times. Thus, a process may execute critical-sections of code multiple times during its execution. This module introduces the critical-section problem and discusses solutions to the critical-section problem.
10.2 Bounded-buffer problem
To understand the critical-section problem, we will revisit the bounded-buffer problem we learnt in an earlier module. The shared-memory solution to the bounded-buffer problem, discussed in the earlier module, allows at most N – 1 items in the buffer at the same time. The solution is as follows:
Shared data:
#define BUFFER_SIZE 10
typedef struct {
. . .
} item;
item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;
There is a buffer of size BUFFER_SIZE (10), which is used by the producer and the consumer processes to place and remove items respectively. There are two variables in and out, which point to the locations in the buffer where the producer places items and the consumer consumes items respectively. Initially, in and out point to the same location in the buffer.
Code for producer process:
item next Produced;
while (1) {
while (((in + 1) % BUFFER_SIZE) == out) ; /* do nothing */
buffer[in] = nextProduced;
in = (in + 1) % BUFFER_SIZE;
}
When (in + 1) % BUFFER_SIZE == out, buffer is full. The producer waits if the buffer is full. Else, the producer places the item in the location pointed to by the in variable and increments the in variable.
Code for consumer process:Item nextConsumed;
while (1) {
while (in == out); /* do nothing */
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
}
The buffer is empty when in == out. The consumer waits when the buffer is empty. If the buffer is not empty, the consumer consumes the item pointed to by the out variable and increments the out variable.
Suppose the consumer had not consumed any data. Then, the initial location will be pointed to by the out pointer. When the in pointer is pointing to the N – 1th location, the condition “(in + 1) % BUFFER_SIZE == out” will be true and the producer will wait. Thus, this solution uses only N – 1 locations of the buffer.
A solution, where all N buffers are used is not simple. A solution is possible when we modify the producer-consumer code by adding a variable counter, initialized to 0 and incrementing it each time a new item is added to the buffer. The code for the solution to the bounded buffer problem using the counter variable is given below:
#define BUFFER_SIZE 10
typedef struct { . . .
} item;
item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;
int counter = 0;
/*Producer process
item nextProduced;
while (1) {
while (counter == BUFFER_SIZE); /* do nothing */
buffer[in] = nextProduced;
in = (in + 1) % BUFFER_SIZE;
counter++;
}
/*Consumer process
item nextConsumed; while (1) {
while (counter == 0); /* do nothing */
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
counter–;
}
In this solution, the variable counter is shared between the producer and the consumer. Whenever the producer places an item in the buffer, it increases the value of the variable. When the consumer consumes an item from the buffer, it decreases the value of the counter variable. Thus, the value of the variable counter maintains the count of the items present in the buffer. Now, we will see how the increment and decrement operations performed on the variable counter can lead to inconsistencies.
The statements “counter++;” and “counter–;” must be performed atomically. Atomic operation means an operation that completes in its entirety without interruption. The reason for this is explained below:
The statement “counter++” may be implemented in machine language as:
register1 = counter
register1 = register1 + 1
counter = register1
Thus, it is seen that the single statement counter++ in the producer’s code is not executed as a single instruction. Rather, it is executed in three different instructions. Similarly, the single statement counter– in the consumer’s code is implemented in three different instructions.
The statement “counter–” may be implemented as:
register2 = counter
register2 = register2 – 1
counter = register2
If both the producer and consumer attempt to update the buffer concurrently, the assembly language statements may get interleaved. Interleaving depends upon how the producer and consumer processes are scheduled.
Assume counter is initially 5.
One such interleaving of statements is:
producer: register1 = counter (register1 = 5)
producer: register1 = register1 + 1 (register1 = 6)
consumer: register2 = counter (register2 = 5)
consumer: register2 = register2 – 1 (register2 = 4)
producer: counter = register1 (counter = 6)
consumer: counter = register2 (counter = 4)
Thus, the value of counter may be either 4 or 6, where the correct result should be 5.
This situation is called a race condition, that is, the situation where several processes access and manipulate shared data concurrently. The final value of the shared data depends upon which process finishes last. To prevent race conditions, concurrent processes must be synchronized. Thus, by understanding the above-mentioned race condition, the critical- section problem can be understood.
10.3 The Critical-Section Problem
There are n processes that compete to use some shared data. Each process has a code segment, called critical-section, in which the shared data is accessed. Hence, the problem is to ensure that, when one process is executing in its critical-section, no other process is allowed to execute in its critical-section. In the above example, the critical-section of code for the producer is counter++ and the critical-section of code for the consumer is counter–. It should be ensured that when the producer is executing counter++, the consumer should not be allowed to access counter–.
10.3.1 Solution to the Critical-Section Problem
Any solution to the critical-section problem should satisfy the following conditions:
Mutual Exclusion: If process Pi is executing in its critical-section, then no other processes can be executing in their critical-sections.
Progress: If no process is executing in its critical-section and there exist some processes that wish to enter their critical-section, then the selection of the processes that will enter the critical-section next cannot be postponed indefinitely.
Bounded Waiting: After a process has made a request to enter its critical-section and before that request is granted, a bound must exist on the number of times that other processes are allowed to enter their critical-sections.
Many algorithms were designed by researchers to solve the critical-section problem. The initial attempt to solve the critical-section problem provided a two-process solution.
The general structure of any process Pi (the other process being Pj) is given below:
do {
entry section
critical-section
exit section
remainder section
} while (1);
Before entering the critical-section, each process executes a piece of code called the entry section and after coming out of the critical-section, the process executes a piece of code called the exit section. The entry and the exit sections of code help in providing synchronization between the two processes. In the solutions provided, the processes share some common variables to synchronize their actions. One of the solutions to the critical- section problem, providing a two-process solution is given in Algorithm 1. The two processes are P0 and P1.
10.3.2 Algorithm 1
• Shared variables:
– int turn; (initially turn = 0)
– turn – i Þ Pi can enter its critical-section
• Process Pi
do { while (turn != i) ;
critical-section
turn = j;
remainder section
} while (1);
The variable turn is common between the two processes. The value of the variable turn can be initialized to either 0 or 1. In this example, the value of turn is initialised to 0.
In this algorithm, the entry section is the code “while (turn != i);”. Any process before entering the critical-section, executes the entry section. The process checks the value of turn. If P0 finds that the value of turn is 0, it enters critical-section. If P0 finds that the value of turn is 1, it waits till the value of turn becomes 1. Similar is the case with process P1. Here, we need to note the semicolon (;) at the end of the while statement.
“while (turn != i) ;”
is the same as
while(turn!=i)
{
}
As long as the condition (turn !=i) in the while loop is true, the process continues to loop in while. Only when the condition becomes false, the process comes out of the while loop.
Therefore, when P0 executes the entry section, if the value of turn is 0, the condition turn!=0 becomes false and therefore, P0 comes out of the while loop and enters critical section. If the value of turn is 1, the condition turn!=0 is true and therefore, P0 continues to execute in the while loop till the value of turn is changed to 0.
When a process comes out of the critical-section, it executes the exit section. In this algorithm, the exit section is the code “turn = j;”. The process changes the value of turn. That is, when process P0 is in the critical-section, the value of turn would have been 0. When it comes out of the critical-section, it changes the value of turn to 1. Similarly, when process P1 comes out of the critical-section, it changes the value of turn to 0.
This algorithm satisfies the mutual exclusion condition, but not the progress condition. This is explained below:
Algorithm 1 – Mutual Exclusion
P0 turn P1
0
Checks turn Checks turn
Enters CS waits
Exits CS
Changes turn 1 Enters CS
Checks turn
Waits … …
According to the mutual exclusion condition, when process P0 is in its critical-section, process P1 should wait and vice versa. Here, the value of turn is initialized to 0. Both processes P0 and P1 want to enter critical-section. Hence, they are in the entry sections of their respective codes. Both the processes check the value of turn. Since the value of turn is 0, P0 comes of the loop (the condition turn!=i becomes false). P0 enters its critical-section. At the same time, process P1 finds the value of turn to be 0 and waits (turn != i is true for P1). When process P0 comes out of its critical-section, it changes the value of turn to 1 (turn = j). Now process P1 comes out of the while loop and enters its critical-section. Thus, it seen that, when process P0 is in its critical-section, process P1 waits, and when process P1 is in its critical-section, process P0 waits. Thus, mutual exclusion is satisfied.
Algorithm 1 – Progress
P0 turn P1
0
Checks turn
Enters CS
Exits CS
Changes turn 1
P0 wants to enter CS
Checks turn
Waits …
According to the progress requirement, if there is no process executing in its critical- section and if there are some processes that are wanting to enter their critical-sections, then the selection of the process that will enter the critical-section next cannot be postponed indefinitely. In the example shown above, process P0 comes out of its critical-section and changes the value of turn to 1. Process P1 does not want to enter its critical-section. Now, process P0 wants to enter its critical-section again. But P0 cannot enter its critical-section because the value of turn is 1. Unless process P1 enters its critical-section and exits its critical-section and then changes the value of turn to 0, P0 cannot enter its critical-section. Thus, it is seen that there needs to be a strict alternation between the processes P0 and P1. After P0 comes out of its critical-section, P1 should enter its critical-section. Only after that, P0 can enter its critical-section the second time. Thus, it is seen that the progress requirement is not satisfied by this algorithm. Since this algorithm does not satisfy all the requirements for a solution to the critical-section problem, it is not a proper solution.
10.4 Summary
This module discussed the need for process synchronization when cooperating processes share data. The portion of code in each process that involves the access of shared data is called the critical-section of code. The access of the critical-section of each process should be synchronized. Any solution to this critical-section problem should satisfy the mutual exclusion, progress and the bounded waiting requirements. This module discussed one such solution to the critical-section problem where only two processes are involved. We saw that this solution satisfies the mutual exclusion requirement but not the progress requirement.
References
1. Abraham Silberschatz, Peter B. Galvin, Greg Gagne, “Operating System Concepts”, Ninth Edition, John Wiley & Sons Inc., 2012.
- William Stallings, “Operating Systems: Internals and Design Principles”, Seventh Edition, Pearson, 2012.