12 Process Synchronization – Classic Problems
Mary Anitha Rajam
15.1 Introduction
In this module, we learn the different classic synchronization problems. These problems can be posed as examples for a large class of concurrency-control problems and can be used for testing newly proposed synchronization schemes. We also learn solutions to these synchronization problems using semaphores. The classic problems of synchronization discussed in this module are bounded-buffer problem, readers-writers problem and dining-philosophers problem.
15.2 Bounded-Buffer Problem
In an earlier module, we learnt a different solution to the bounded-buffer problem. In this module, we learn a solution to this problem using semaphores.
The bounded-buffer problem is defined as follows: There is a pool of n buffers. Each buffer is capable of holding one item. A producer produces items and places them in the buffers. A consumer consumes items from the buffers. When all the buffers are full, the producer has no place to place the item and therefore, the producer waits. The consumer waits when the buffers are empty. Since the buffers are shared between the producer and the consumer, synchronization needs to be provided between the producer and the consumer. That is, both the producer and the consumer should not access the buffers simultaneously. That is, the access of the buffers should be done atomically to avoid inconsistencies in the data stored in the buffers. The solution to this bounded-buffer problem using semaphores is as follows:
Semaphores used: semaphore full, empty, mutex;
The semaphores used in the solution are named as full, empty and mutex. mutex semaphore provides mutual exclusion for access to the buffer pool and is initialized to 1. The empty semaphore counts the number of empty buffers and is initialized to n. The full semaphore counts the number of full buffers and is initialized to 0.
The algorithm for the producer process is given below:
The producer produces an item in a variable called nextp. Then the producer waits on the semaphore empty. The empty semaphore is initialized to n, the number of empty buffers. wait(empty) decrements the value of empty. Since the value of empty was not zero before the decrement, the process proceeds to the next statement. The producer now executes wait(mutex). Since the value of mutex is equal to one, the value of mutex is decremented to zero. The producer now proceeds to place the item in the buffer. After placing the item, the producer executes signal(mutex), which increments the value of mutex to one. The producer then executes signal(full), which increments the value of full from zero to one.
The algorithm for the consumer process is given below:
do {
wait(full)
wait(mutex);
…
remove an item from buffer to nextc
…
signal(mutex);
signal(empty);
…
consume the item in nextc
…
} while (1);
The consumer waits on the semaphore full. The full semaphore is initialized to 0. When the value of the semaphore full is 0, the consumer process cannot proceed and waits. If the producer had placed items in the buffer, the value of full would have been greater than zero. In this case, the consumer decrements the value of full and proceeds to the next statement.
The consumer next executes wait(mutex). If the value of mutex is one, the consumer process decrements the value of mutex and proceeds to the next statement.
The consumer process then removes an item from the buffer and places in a variable nextc. After removing the item, semaphore mutex is signaled. This signal operation increments the value of the semaphore mutex from 0 to 1. The semaphore empty is also signaled. This signal operation increments the value of empty by one.
Let us see an example of how a producer and a consumer synchronize while accessing a common buffer.
Consider a buffer of size 4. That is, four elements can be placed in the buffer. The initial values of the semaphores are given by full = 0, empty = 4 and mutex = 1. Initially, the buffer is empty and is as shown below:
If a consumer wants to consume an item from the buffer, the consumer executes wait(full). Since the value of full is zero, the consumer waits on the semaphore full.
Now, suppose a producer wants to place an item. The producer executes the wait operation on semaphore empty. Therefore, the value of empty is decremented to 3. The producer then executes waits on semaphore mutex. Thus, the value of the semaphores become full = 0, empty = 3, and mutex = 0.
The producer places an item in the buffer.
| Item1 |
After placing the item, the semaphores full and mutex are signaled. The value of the semaphores become full = 1, empty = 3 and mutex = 1.
Suppose the producer wants to place the next item, item2. The producer executes wait(empty), which decrements empty from 3 to 2. The producer then executes wait(mutex), which decrements mutex from 1 to 0. The values of the semaphores are full = 1, empty = 2, and mutex = 0. The producer places item2 in the buffer.
| Item1 | Item2 |
After placing the item, the semaphores full and mutex are signaled. The values of the semaphores become full = 2, empty = 2 and mutex = 1.
Suppose the producer wants to place the next item, item3. The producer executes wait(empty), which decrements empty from 2 to 1. The producer then executes wait(mutex), which decrements mutex from 1 to 0. The values of the semaphores are full = 2, empty = 1, and mutex = 0. The producer places item3 in the buffer. After placing the item, the semaphores full and mutex are signaled. The values of the semaphores become full = 3, empty = 1 and mutex = 1.
`
| Item1 | Item2 | Item3 |
The consumer is still waiting on the semaphore full. Suppose the consumer gets its turn and is scheduled. The consumer is executing wait(full) and decrements full from 3 to 2. The consumer then executes wait(mutex), which decrements mutex from 1 to 0. Now, the values of the semaphores are full = 2, empty = 1, and mutex = 0. The consumer now consumes the item ‘item1’ from the buffer and the buffer looks as shown below.
| Item2 | Item3 |
After consuming the item, the semaphores empty and mutex are signaled. The values of the semaphores are now full = 2, empty = 2, and mutex = 1.
Now, if the producer is scheduled, the producer places the next item and the buffer looks as shown below and the values of the semaphores become full = 3, empty
= 1, and mutex = 1.
| Item2 | Item3 | Item4 |
When the producer places the next item, the buffer is as shown below and the values of the semaphores become full = 4, empty = 0, and mutex = 1.
| Item 5 | Item2 | Item3 | Item4 |
Now, if the producer wants to place another item, the producer waits on semaphore empty. Since the value of the semaphore empty is 0, the producer cannot proceed and it waits.
When the consumer gets its turn, the consumer executing wait(full), decrements full from 4 to 3. The consumer then executes wait(mutex), which decrements mutex from 1 to 0. The values of the semaphores are full = 3, empty = 0, and mutex = 0. The consumer consumes the item from the buffer.
| Item5 | Item3 | Item4 |
After the consumer consumes the item, it executes signal(empty) and signal(mutex). The values of the semaphores now become full = 3, empty = 1, and mutex = 1.
Similarly, the consumer can consume the other items. After all the items in the buffer are consumed, the values of the semaphores become full = 0, empty = 4 and mutex = 1.
The buffer is empty now. Now, if a consumer wants to consume, it waits on semaphore full. The consumer has to wait till the producer places an item in the buffer and executes signal operation on semaphore full.
It is to be noted that the producer or the consumer can be scheduled at any time. There is no particular order in the scheduling of the producer and the consumer. In the example shown above, one such order is discussed.
Thus, in this example we see that the ‘mutex’ semaphore guards the access of the buffer. The ‘full’ semaphore guards the producer from placing items into a full buffer. The ‘empty’ semaphore guards the consumer from trying to remove items from an empty buffer.
15.3 Readers–Writers Problem
The readers–writers problem is defined as follows: A data object (such as a file) is shared among a number of several concurrent processes. Some of these processes may only want to read the content of the data. Some other processes may want to read as well as write. The readers are the processes that only read the data; they do not perform any updates. The writers are the processes that can both read and write.
Multiple readers are allowed to read at the same time. But, only one single writer can access the shared data at the same time. That is, writers should have exclusive access to the shared object. This is because, even if many readers read the data at the same time, it does not result in data inconsistency. But, if many writers write at the same time, it may result in inconsistency. While a writer is writing and a reader wants to read, the reader has to wait. Similarly, while a reader is reading, a writer is not allowed to write.
There are many variants to the readers–writers problem. One of the variants is called the first readers–writers problem. In this problem, the readers are given priority. When one reader is reading, if other readers arrive, all the readers are allowed to read, even if a writer is waiting to write. Only when there is no reader to read, a writer is allowed to write.
Another variant is called the second readers–writers problem. In this variant, once a writer is ready to write, no other new reader is allowed to read. When the readers who are currently reading finish reading, the writer is immediately allowed to write.
In this section, we learn a solution to the first readers–writers problem using semaphores. The solution uses the following shared data:
semaphore mutex, wrt;
int readcount;
mutex and wrt are semaphores and readcount is an integer variable.
Initially, mutex = 1, wrt = 1, readcount = 0
wrt is the semaphore that safeguards the common resource (say, a file) shared by the reader and the writer. mutex is the semaphore that safeguards the readcount variable. (The variable readcount is accessed by both the reader and the writer.)
For the sake of explanation, it is assumed here that the common resource shared is a file. We first look at the implementation of a writer process.
Readers–Writers Problem – Writer Process:
wait(wrt);
…
writing is performed
…
signal(wrt);
As mentioned earlier, the wrt semaphore is used to safeguard the shared resource. Safeguarding the shared resource (file, here) means that it is necessary to provide mutual access to the shared resource. When one process is accessing the shared resource, other processes should not be allowed to access that shared resource.
Before accessing the shared resource, the writer executes wait(wrt). If access is allowed, the writer writes. After completing the writing process, the writer executes signal(wrt).
Only one writer is allowed to write at a particular time. Therefore, the initial value of the wrt semaphore is1.
An example scenario is explained below. Here, it is assumed that the common resource that the readers and the writers are accessing is a file. The initial values of the wrt and the mutex semaphores are 1. The value of the variable readcount gives the number of reader processes reading the file at a particular time. Initially, the value of readcount is 0, as there is no reader reading.
| mutex | wrt | readcount |
| 1 | 1 | 0 |
[File]
When a writer wants to write to the file, the writer executes wait(wrt), which decrements the value of wrt by one. Now the value of wrt becomes 0. The writer proceeds to write into the file.
| mutex | wrt | readcount |
| 1 | 1 | 0 |
| 0 |
[Writer Write]
In the meantime, if any other writer wants to write to the file, the new writer waits. Since the value of wrt semaphore is now 0, executing wait(wrt) puts the new writer to the waiting state.
When the first writer finishes writing, it executes signal(wrt). This increments the value of wrt semaphore and wrt becomes 1.
[Writer finishes writing]
| mutex | Wrt | readcount |
| 1 | 1 | 0 |
| 0 | ||
| 1 |
After the first writer finishes writing, if there is any other writer that is waiting, the waiting writer is allowed to write now.
The code for a reader process is given below:
wait(mutex);
readcount++;
if (readcount == 1) wait(wrt);
signal(mutex);
…
reading is performed
…
wait(mutex);
readcount–;
if (readcount == 0)
signal(wrt);
signal(mutex);
In the entry section of the reader’s code, before entering the critical section, a reader first executes wait(mutex). As mentioned earlier, the mutex semaphore safeguards the readcount variable. ‘readcount’ variable can be accessed by many readers. To avoid inconsistencies, it is necessary to ensure that mutual access is provided to the ‘readcount’ variable. Therefore, the mutex semaphore is provided to safeguard the ‘readcount’ variable. Only one reader process is allowed to access the readcount variable at a particular time. Therefore, the initial value of the mutex semaphore is 1.
When the reader process executes wait(mutex) in the entry section, the value of mutex is decremented from 1 to 0. Then the value of readcount is incremented from 0 to 1. When readcount is equal to 1, it means that it is the first reader. When the first reader tries to read, it needs to get access to the common resource by waiting on the semaphore wrt, which guards the common resource. Therefore, the first reader executes wait(wrt). If the value of wrt is currently 1, the reader process decrements the value from 1 to 0 and proceeds to the next statement signal(mutex) and proceeds to write. signal(mutex) increments the value of mutex from 0 to 1. If the value of wrt is currently 0, it means that there is another writer process that is currently writing into the file and therefore, the reader waits. While the first reader is waiting on wrt, if any other reader arrives, the newly arriving reader waits on mutex semaphore (Note that the value of mutex semaphore is 0, while the first reader waits on wrt).
While a reader is reading from the resource, if any other process arrives, the newly arriving reader executes wait(mutex). This decrements the value of mutex from 1 to 0. Then, readcount is incremented. Since, this is not the first reader, it proceeds to execute signal(mutex), which increments mutex from 0 to 1. Then, the second reader also continues to read. As long as there is at least one reader process that is currently reading from the shared resource, the newly arriving readers can proceed to read.
In the exit section of the readers’ code, after exiting critical section, a reader has to decrement the value of readcount. Before decrementing readcount, the reader executes wait(mutex) and after decrementing, the reader executes signal(mutex). After decrementing readcount, if readcount becomes 0, it means that the last reader is exiting. If the last reader is exiting, it signals wrt semaphore. (Note that wait(wrt) was executed in the entry section by the first reader.)
Assume that there is no writer that is currently writing into the file. Then the values of mutex, wrt, and readcount are as follows:
| mutex | wrt | readcount |
| 1 | 1 | 0 |
Now, the first reader arrives. wait(mutex) decrements mutex from 1 to 0. readcount is incremented from 0 to 1. Since readcount is equal to 1, wait(wrt) decrements wrt from 1 to 0. After this, signal(mutex) increments mutex from 0 to 1 and the reader proceeds to read from the file. Reader1 starts reading from the file. The values of mutex, wrt and readcount are as follows:
| mutex | wrt | readcount |
| 1 | 1 | 0 |
| 0 | ||
| 1 | ||
| 0 | ||
| 1 |
Reader2 arrives. Reader2 waits on mutex, decrementing mutex from 1 to 0. The reader (reader2) then increments readcount from 1 to 2. Since this is not the first reader (readcount is not 1), it does not wait on wrt. signal(mutex) increments mutex from 0 to 1. The second reader also proceeds to read.
| mutex | wrt | readcount |
| 1 | 0 | 1 |
| 0 | ||
| 2 | ||
| 1 |
Let a writer arrive in the meantime. There are two readers currently reading from the file. Therefore, the values of the semaphores and the variable readcount are as follows:
| mutex | wrt | readcount |
| 1 | 0 | 2 |
The writer that arrived now executes wait(wrt). Since the value of wrt is 0, the writer waits on wrt semaphore. As long as the value of wrt semaphore is 0, the writer waits.
Now, suppose reader1 leaves. wait(mutex) executed by the reader in the exit section decrements the value of mutex from 1 to 0. The value of readcount is then decremented from 2 to 1. Since the value of readcount is not 0 (this is not the final reader), the reader executes signal(mutex), which changes the value of mutex from 0 to 1. The values of mutex, wrt, and readcount are shown below:
| mutex | wrt | readcount |
| 1 | 0 | 2 |
| 0 | ||
| 1 | ||
| 1 |
Reader2 is reading and writer is still waiting. Now, suppose reader2 also leaves. wait(mutex) executed by reader2 in the exit section decrements the value of mutex from 1 to 0. The value of readcount is then decremented from 1 to 0. Since the value of readcount is 0 (this is the final reader), reader2 executes signal(wrt), which changes the value of wrt from 0 to 1. The values of mutex, wrt and readcount are shown below:
| mutex | wrt | readcount |
| 1 | 0 | 1 |
| Reader2 leaves | ||
| 0 | 0 | |
| 1 | ||
| 1 |
Writer is waiting on wrt semaphore. Since the wrt semaphore was signaled by reader2, writer can now proceed to write. The changes in the values of the semaphores are shown below:
| mutex | wrt | readcount |
| 1 | 1 | 0 |
| Writer is waiting on wrt
|
||
| 0 | ||
| Writer writes
|
If one or more readers arrive now, the readers wait. If one or more writers arrive, the writers also wait.
15.4 Dining-Philosophers Problem
The dining-philosophers’ problem is defined as follows: There are five philosophers seated in five chairs around a circular table as shown in Figure 15.1. In the center of the table, there is a bowl of rice and the table is laid with five chopsticks. The philosophers spend their time dining and thinking. When a philosopher wants to dine, she picks up the two chopsticks that are closest to her (one to her left and another to her right). She cannot pick up a chopstick that is already in the hand of a neighbor. When a philosopher gets both the chopsticks at the same time, she dines using the two chopsticks. Once she completes dining, she places down the two chopsticks and starts thinking again.
In this problem, the resource to be shared is the chopstick. One way of providing a solution to this problem is to represent each chopstick by a semaphore. A philosopher tries to take a chopstick by executing a wait operation on the semaphore associated with that chopstick. The philosopher releases the chopstick by executing the signal operation on the semaphore.
Fig. 15.1 Situation of the dining philosophers (Source: [1])
A solution to the dining philosophers’ problem using semaphores is given below: The shared data used in the solution is given below:
semaphore chopstick[5];
chopstick[5] is an array with 5 elements. Each element is a semaphore. The initial value of each semaphore in the array is 1.
The algorithm for philosopher i is as follows:
do {
wait(chopstick[i])
wait(chopstick[(i+1) % 5])
…
eat
…
signal(chopstick[i]);
signal(chopstick[(i+1) % 5]);
…
think
…
} while (1);
Philosopher i wanting to eat, executes wait operation on chopstick[i]. Since the initial value of chopstick[i] is 1, wait operation changes the value of the semaphore chopstick[i] from 1 to 0. Philosopher i next executes the wait operation on chopstick[i+1]. Since the value of chopstick[i+1] is 1, wait operation decrements the value of semaphore chopstick[i+1] from 1 to 0. Philosopher i now proceeds to eat. While philosopher i is eating, let philosopher i+1 want to eat. Philosopher i+1 executes wait operation on semaphore chopstick[i+1]. Since the value of the semaphore is 0, philosopher i+1 waits. Philosopher i+1 can proceed only if philosopher i completes eating and releases the semaphore.
After philosopher i completes eating, philosopher i executes signal operation on semaphore chopstick[i]. This signal operation increments the value of the semaphore chopstick[i] from 0 to 1. Philosopher i then executes signal operation on semaphore chopstick[i+1]. This signal operation increments the value of the semaphore chopstick[i+1] from 0 to 1.
For this solution to work, two neighbors should not start picking the chopsticks simultaneously. If every philosopher picks up her left chopstick first, the solution leads to a deadlock. None of the philosophers will be able to pick up the right chopstick. All the philosophers continue to wait for their respective right chopsticks.
15.5 Summary
This module discussed three classic problems of synchronization. Solutions to the three problems using semaphores were also discussed.
References
- Abraham Silberschatz, Peter B. Galvin, Greg Gagne, “Operating System Concepts”, Ninth Edition, John Wiley & Sons Inc., 2012.4