CLASSICAL IPC PROBLEMS

CLASSICAL IPC PROBLEMS

The operating systems literature is full of interesting problems that have been extensively discussed and analyzed using a variety of synchronization methods. In the following sections we will look at three of the better-known problems.

The Dining Philosophers Problem

In 1965, Dijkstra posed and solved a synchronization problem he called the dining philosophers problem. Since that time, everyone inventing yet another synchronization primitive has felt obligated to demonstrate how wonderful the new primitive is by showing how elegantly it solves the dining philosophers problem. The problem can be explained quite simply as follows. Five philosophers are seated around a circular table. Each philosopher has a plate of spaghetti. The spaghetti is so slippery that a philosopher needs two forks to eat it. Between each pair of plates is one fork. The layout of the table is demonstrated in Figure 1.

Lunch time in the Philosophy Department

The life of a philosopher consists of alternate periods of eating and thinking. (This is something of an abstraction, even for philosophers, but the other activities are irrelevant here). When a philosopher gets hungry, she tries to obtain her left and right forks, one at a time, in either order. If successful in obtaining two forks, she eats for a while, then puts down the forks, and continues to think. The key question is: Can you write a program for each philosopher that does what it is supposed to do and never gets stuck? (It has been pointed out that the two-fork requirement is somewhat artificial; perhaps we should switch from Italian food to Chinese food, substituting rice for spaghetti and chopsticks for forks.)

Figure 2 shows the obvious solution. The procedure take_fork waits until the specified fork is available and then seizes it. Unluckily, the obvious solution is wrong. Assume that all five philosophers take their left forks at the same time. None will be able to take their right forks, and there will be a deadlock.

A nonsolution to the dining philosophers problem

We could change the program so that after taking the left fork, the program checks to see if the right fork is available. If it is not, the philosopher puts down the left one, waits for some time, and then repeats the whole process. This proposal too, fails, although for a different reason. With a little bit of bad luck, all the philosophers could start the algorithm at the same time, picking up their left forks, seeing that their right forks were not available, putting down their left forks, waiting, picking up their left forks again simultaneously, and so on, forever. A situation like this, in which all the programs continue to run indefinitely but fail to make any progress is called starvation. (It is called starvation even when the problem does not take place in an Italian or a Chinese restaurant).

You might think now that if the philosophers would just wait a random time instead of the same time after failing to obtain the right-hand fork, the chance that everything would continue in lockstep for even an hour is very small. This observation is true, and in nearly all applications trying again later is not a  problem. For instance, in the popular Ethernet local area network, if two computers send a packet at the same time, each one waits a random time and tries again; in practice this solution works fine. On the other hand, in a few applications one would prefer a solution that always works and cannot fail due to an unlikely series of random numbers. Think about safety control in a nuclear power plant.

One improvement to Figure 2 that has no deadlock and no starvation is to protect the five statements following the call to think by a binary semaphore. Before starting to obtain forks, a philosopher would do a down on mutex. After replacing the forks, she would do an up on mutex. From a theoretical point of view, this solution is enough. From a practical one, it has a performance bug: only one philosopher can be eating at any instant. With five forks available, we should be able to allow two philosophers to eat at the same time.

The solution presented in Figure 3 is deadlock-free and allows the maximum parallelism for an arbitrary number of philosophers. It uses an array, state, to

A solution to the dining philosophers problem

keep track of whether a philosopher is eating, thinking, or hungry (trying to obtain forks). A philosopher may only move into eating state if neither neighbor is eating. Philosopher i's neighbors are defined by the macros LEFT and RIGHT. In other words, if i is 2, LEFT is 1 and RIGHT is 3.

The program uses an array of semaphores, one per philosopher, so hungry philosophers can block if the required forks are busy. Note that each process runs the procedure philosopher as its main code, but the other procedures, take_forks, put_forks, and test, are ordinary procedures and not separate processes.



Tags

process, algorithm, starvation, binary semaphore