The original problems of Dijkstra were related to external devices like tape drives. These issues are studied in concurrent programming. The failures these philosophers may experience are analogous to the difficulties that arise in real computer programming when multiple programs need exclusive access to shared resources. Mutual exclusion is the basic idea of the problem the dining philosophers create a generic and abstract scenario useful for explaining issues of this type. If all five philosophers appear in the dining room at exactly the same time and each picks up the left fork at the same time the philosophers will wait ten minutes until they all put their forks down and then wait a further ten minutes before they all pick them up again. This scheme eliminates the possibility of deadlock (the system can always advance to a different state) but still suffers from the problem of livelock. For example, there might be a rule that the philosophers put down a fork after waiting ten minutes for the other fork to become available and wait a further ten minutes before making their next attempt. Resource starvation might also occur independently of deadlock if a particular philosopher is unable to acquire both forks because of a timing problem. With the given instructions, this state can be reached, and when it is reached, each philosopher will eternally wait for another (the one to the right) to release a fork. This is a state in which each philosopher has picked up the fork to the left, and is waiting for the fork to the right to become available. This attempted solution fails because it allows the system to reach a deadlock state, in which no progress is possible.
SLEEPING BARBER PROGRAM IN C HOW TO
The problem is how to design a discipline of behavior (a concurrent algorithm) such that no philosopher will starve i.e., each can forever continue to alternate between eating and thinking, assuming that no philosopher can know when others may want to eat or think. A philosopher can only take the fork on their right or the one on their left as they become available, and they cannot start eating before getting both forks.Įating is not limited by the remaining amounts of spaghetti or stomach space an infinite supply and an infinite demand are assumed. After an individual philosopher finishes eating, they need to put down both forks so that the forks become available to others.
Each fork can be held by only one philosopher at a time and so a philosopher can use the fork only if it is not being used by another philosopher.
However, a philosopher can only eat spaghetti when they have both left and right forks.
Įach philosopher must alternately think and eat. Now each philosopher will go cyclically through the states 0, 1, 2, 0. In order to be able to give a formal description, we associate with each philosopher a state variable, "C" say, where C = 0 means: philosopher i is thinking, C = 1 means: philosopher i is hungry, C = 2 means: philosopher i is eating. When all five philosophers get hungry simultaneously, each will grab his left-hand fork and from that moment onwards the group is stuck. There are two forks next to each plate, so that presents no difficulty: as a consequence, however, no two neighbours may be eating simultaneously.Ī very naive solution associates with each fork a binary semaphore with the initial value = 1 (indicating that the fork is free) and, naming in each philosopher these semaphores in a local terminology, we could think the following solution for the philosopher's life adequate.īut this solution – although it guarantees that no two neighbours are eating simultaneously – must be rejected because it contains the danger of the deadly embrace ( deadlock). Their only problem – besides those of philosophy – is that the dish served is a very difficult kind of spaghetti, that has to be eaten with two forks.
0 kommentar(er)
