Dining philosophers

Description

In the dining philosophers a number of philosophers (five, in our example) are seated at a round table. On the table are five plates of food, one in front of each philosopher, and five forks, one between each adjacent pair of plates. So each philosopher has a plate in front of him and a fork to his left and a fork to his right.

The philosophers spend all their time in either of only two states: they are thinking or they are eating. The philosophers may be mental giants, but apparently manual dexterity is not their strong suit. This is evidenced by the fact that in order to eat, any philosopher must be able to pick up both of the forks positioned next to his plate (which he can do, so long as neither of the philosophers next to him is currently eating). So, while eating he must have possession of both forks, and while thinking, he has put down any forks that he had previously used. Therefore, any particular philosopher has the opportunity to eat only when the two philosophers on either side of him are thinking and have made their forks available.

Apart from any negative consequences from the questionable sanitary practices described above, the dining philosophers can, in improperly designed solutions, encounter problems related to concurrency. For example, if all philosophers were to pick up the fork to their right and then wait for the fork to their left to become available (or vice versa), the philosophers would be caught in a deadlock. If, because of a lack of fairness in the solution, some of the philosophers get stuck in thinking mode because they can never secure the two forks necessary to eat, then those philosophers so affected would suffer a condition known as resource starvation.

Highlights

This example includes three classes relevant to the problem: DINING_PHILOSOPHERS, PHILOSOPHER, and FORK. Class DINING_PHILOSOPHERS sets the problem in motion by creating the forks and philosophers all typed as separate, and then applying the feature live to each philosopher after creation.

Class PHILOSOPHER models the philosophers. The totality of a philosopher's exciting activities is modeled by the feature step:

step -- Perform tasks. do think eat (left_fork, right_fork) end

This feature is called by {PHILOSOPHER}.live repeatedly until the philosopher has eaten a prescribed number of times.

The feature think requires no access to shared objects, but the feature eat depends upon the philosopher's ability to secure access to both of the forks adjacent to his plate. Because all forks are separate objects, each call to eat waits until the processors for both the left and right forks are available (in accordance with the Wait rule).

Another interesting feature of this example is the feature {PHILOSOPHER}.eat. If you look at the text of this feature

eat (l, r: separate FORK) -- Eat, having grabbed l and r. do io.put_string ("Philosopher " + id.out + ": taking forks%N") times_eaten := times_eaten + 1 io.put_string ("Philosopher " + id.out + ": eating%N") io.put_string ("Philosopher " + id.out + ": putting forks back%N") end

and you're not wearing your SCOOP glasses, this could look a little odd to you. Here is a routine that takes two arguments l and r representing the left and right forks. But then, l and r are never used in body of the routine!

However, with SCOOP in mind, we realize that the fork objects are shared resources to which exclusive access must be secured before a philosopher can eat. In this example, the fork object themselves don't really do anything except serve that purpose. (Take a look at the FORK class, and you'll see that it has no features.)

In real world concurrency problems, it is likely that shared resources would play a more active role than the forks of the dining philosophers, but here it's just not necessary.