Classical Problems in Synchronization

3) Deadlocks and resource starvation

Implementing a semaphore with a queue can result in a situation where two or more processes are waiting indefinitely for an event generated by one of the waiting processes, such as a signal operation. When such a state occurs, the processes are said to be deadlocked.

To elaborate, let us consider a system containing two processes P0 and P1, each accessing two semaphores, S and Q, set to 1.

Suppose that P0 executes wait(S) and then P1 executes wait(Q). When P0 executes wait(Q), it must wait until P1 executes signal(Q). Similarly, when P1 executes wait(S), it must wait until P0 executes signal(S). Since these signal operations cannot be performed, P0 and P1 are deadlocked.

Maybe you are interested!

We say that a set of processes is in a deadlock state when every process in the set is waiting for an event that can be caused by only one other process in the set. The events that we are primarily interested in here are resource acquisition and release, but there are a number of other events that can also lead to deadlocks (which we will discuss later).

A problem related to deadlocks is infinite blocking or starvation , where processes wait indefinitely on a semaphore. Infinite blocking can occur if we add and remove processes from a list linked to a semaphore in last-in, first-out (LIFO) order.

Binary Semaphore

The semaphore construction described in the above section is called a counting semaphore because the integer value of the semaphore can have a wide range. A binary semaphore is a semaphore with an integer value that has only two values, 0 and 1. Binary semaphores can be simpler to implement than

Counting semaphore and depends on the underlying hardware architecture. We will show how a counting semaphore can be implemented using the semaphore binary below:

Suppose S is a counting semaphore. To implement it in binary semaphore form we need the following data structures:

Binary-semaphore S1, S2; int C;

Initialize S1 = 1, S2 = 0 and integer value C is set to the initial value of counting semaphore S.

The wait operation on the counting semaphore S can be implemented as follows:

wait(S);

C--;

If (C<0) {

signal(S1); wait(S2);

}

signal(S1);

The signal operation on the counting semaphore S can be implemented as follows: wait(S1);

C++;

if (C<=0)

signal(S2);

else

signal(S1);

2.3.4 Classical problems in synchronization

In this section, we present several synchronization problems as examples of a large class of concurrency control problems. These problems are used

for testing all the recently proposed synchronization mechanisms. Semaphore is used for synchronization in the solutions below.

1) Producer-consumer problem

The Producer-Consumer problem is often used to demonstrate the power of synchronization primitives. Two processes share a buffer of limited size n. The semaphore mutex provides mutual exclusion for accessing the buffer and is initialized to 1 . The semaphore variables empty and full count the number of empty and full slots, respectively. The semaphore empty is initialized to n ; the semaphore full is initialized to 0 .

The code for the production process is shown in Figure 2.34. do{

…

produce products in nextp

… wait(empty); wait(mutex);

…

add nextp to buffer

… signal(mutex); signal(full);

} while (1);

Figure 2.34 Structure of the producer process

The code for the consumer process is shown in the figure below: do{

wait(full); wait(mutex);

…

get an item from buffer to nextc

… signal(mutex);

signal(empty);

} while (1);

Figure 2.35 Structure of the consumer process

2) Reader-writer problem

A Reader-Writer is a data object (such as a file or record) that is shared among multiple concurrent processes. Some of the processes may only need to read the contents of the shared object, whereas some other processes may need to update (i.e., read and write) the shared object. We distinguish between the two types of processes by calling the processes that only read as readers and the processes that need to update as writers. Note that if two readers access the shared object at the same time, there will be no effect. However, if one writer and several other processes (either readers or writers) access it at the same time, chaos may result.

To ensure that these difficulties do not arise, we require that writers have mutually exclusive access to the shared object. This synchronization is called the reader-writer problem. The reader-writer problem has several variations that involve priorities. The simplest form is the first reader-writer problem . In this form, no reader has to wait unless a writer has been granted access to the shared object. In other words, no reader has to wait for other readers to complete simply because a writer is waiting. The second readers-writer problem requires that once a writer is ready, that writer performs its write as soon as possible. In other words, if a writer is waiting to access the object, no reader can start reading.

The solution to this problem can lead to starvation. In the first case, the writers can starve; in the second case, the readers can starve. In the solution to the first-reader-first-writer problem, the reader processes share the following data structures:

semaphore mutex, wrt; int readcount;

The semaphore variables mutex and wrt are initialized to 1 ; the readcount variable is initialized

0 . The semaphore variable wrt is common to both the reader and writer processes.

The mutex semaphore is used to ensure mutual exclusion when the readcount variable is updated. The readcount variable keeps track of how many processes are currently reading the object. The wrt semaphore variable functions as a mutual exclusion semaphore for readers. It is also used by the first or last reader that enters or exits the critical section. It is also not used by readers that enter or exit while other readers are in the critical section.

The code for the writer process is shown in Figure 2.36. wait(wrt);

…

The write operation is performed signal(wrt);

Figure 2.36 Structure of the writing process

The code of the read process is shown in Figure 2.37. wait(mutex);

readcount++;

if (readcount == 1) wait(wrt); signal(mutex);

…

The read operation is performed wait(mutex); readcount--;

if (readcount == 0) signal(wrt); signal(mutex);

Figure 2.37 Structure of the reader

Note that if the writer is in the critical section and n readers are waiting, then one reader is queued on wrt, and n-1 are queued on the mutex. Also note that when a writer executes signal(wrt), we can either continue the execution of the waiting readers or a waiting writer. This choice can be made by the scheduler.

3) The dinner philosophers problem

There are five philosophers, thinking while having dinner. The philosophers sit at a round table surrounded by five chairs, each chair is occupied by a philosopher. In the middle of the table is a bowl of rice and five chopsticks as shown in Figure 2.38

Figure 2.38 Situation of philosophers having dinner

When a philosopher thinks, he does not interact with other philosophers. Sometimes a philosopher feels hungry and tries to choose the two nearest chopsticks (the two chopsticks between him and his left and right neighbors). A philosopher can take only one chopstick at a time. Note that he cannot take the chopsticks that are being used by his neighbor. When a philosopher is hungry and has two chopsticks at the same time, he eats without putting them down. When the philosopher finishes eating, he puts his chopsticks down and starts thinking again.

The Dinner Philosophers Problem is a classic synchronization problem. It presents the requirement to allocate multiple resources between processes in a way that avoids deadlocks and starvation.

A simple solution is to represent each chopstick by a semaphore variable. A philosopher tries to capture one chopstick by performing a wait operation on that semaphore variable; the philosopher puts down two chopsticks by performing a signal operation on the corresponding semaphore variables. Thus, the shared data is:

semaphore chopstick[5];

Here all the elements of chopstick are initialized to 1. The structure of philosopher i is shown below:

by{

wait(chopstick[ i ]); wait(chopstick[ ( i + 1 ) % 5 ]);

… eat

…

signal(chopstick[ i ]); signal(chopstick[ ( i + 1 ) % 5 ]);

…

think

…

} while (1);

Figure 2.39 Structure of the i-th philosopher

Although this solution ensures that no two neighbors are eating at the same time, it is likely to cause a deadlock. Suppose that five philosophers are hungry at the same time and each philosopher takes the chopstick on his left. Now all the chopstick elements will be 0. When each philosopher tries to take the chopstick on his right, the philosopher will be left waiting forever.

Several possible solutions to the deadlock problem are listed next. A solution to the dinner philosophers problem that guarantees no deadlock.

- Allows up to four philosophers to sit at the table at the same time

- Allow a philosopher to take his chopsticks only if both chopsticks are available (to do this he must take them in the critical section).

- Use an asymmetric solution; that is, an odd philosopher chooses his left chopstick first and then his right chopstick, whereas an even philosopher chooses his right chopstick first and then his right chopstick.

In short, any satisfactory solution to the dinner philosophers problem must be based on the possibility that one of the philosophers will starve to death. The solution to deadlock need not eliminate the possibility of starvation.

2.3.5 Critical Areas

2.3.6 Monitors

To make it easier to write correct synchronization programs, Hoare (1974) and Brinch & Hansen (1975) proposed a higher-level synchronization mechanism provided by the programming language called a monitor . A monitor is described by a set of operators defined by the programmer. The type representation of a monitor includes the declaration of variables whose values specify the state of an instance of the type, as well as the body of the procedure or function that implements operations on the type. The syntax of a monitor is shown in the figure below:

Monitor < monitor name>

{

declare shared variables procedure P1 (…){

…

}

procedure P2 (…){

…

}

procedure Pn (…){

…

}

{

initialization code

}

Figure 2.40 Syntax of monitor

Monitor type representations cannot be used directly by different processes. Therefore, a procedure defined within a monitor can access only variables declared locally within that monitor and its formal parameters.

Comment