فكر: الحلاق والفلاسفة الخمسة.

Not Dijkstra's Solution

This is not the solution proposed in Dijkstra's paper cited below and might not even be Dijkstra's solution at all. Dijkstra's paper presents an optimal solution based on private semaphores and state variables and a global mutex, which was described in an older version of this article

Positions of philosophers and forks in ordering solution.One solution is to order the forks and require the philosophers to pick up the forks in increasing order, which mathematically eliminates the possibility of a deadlock. To illustrate this solution, label the philosophers P1, P2, P3, P4, and P5, and label the forks F1, F2, F3, F4, and F5. Each philosopher must pick up forks in a prescribed order and cannot pick up a fork another philosopher already has. Upon acquiring two forks, a philosopher may eat. Philosophers P1 through P4 follow the rule that Px must pick up fork Fx first and then may pick up fork Fx+1. For example, P1 must pick up F1 first and F2 second. Philosopher P5 must, conversely, pick up fork F1 before picking up fork F5, to respect the deadlock-preventing fork ordering rule

Although avoiding a deadlock, this solution is inefficient, because one can arrive to a situation where only one philosopher is eating and everybody else is waiting for him. For example philosophers P1 to P3 could hold forks F1 to F3, waiting to get forks F2 to F4 respectively, philosopher P5 could wait on fork F1 having no fork yet, while philosopher P4 would be eating holding forks F4 and F5. Optimally, either philosopher P1 or philosopher P2 should be able to eat in such circumstances

Preventing starvation depends on the method of mutual exclusion enforcement used. Implementations using spinlocks or busy waiting can cause starvation through timing problems inherent in these methods. Other methods of mutual exclusion that utilize queues can prevent starvation by enforcing equal access to a fork by the adjacent philosophers

Dijkstra's solution can be extrapolated to represent arbitrary contention between philosophers, but requires all the forks to be labeled correctly for such configurations



[Chandy / Misra Solution
In 1984, K. Mani Chandy and J. Misra proposed a different solution to the Dining Philosophers problem to allow for arbitrary agents (numbered P1, ..., Pn) to contend for an arbitrary number of resources (numbered R1, ..., Rm). Unlike in Dijkstra's solution, these labelings can be arbitrary. They solved this general problem using an elegant solution:

For every pair of philosophers contending for a resource, create a fork and give it to the philosopher with the lower ID. Each fork can either be dirty or clean. Initially, all forks are dirty
When a philosopher wants to use a set of resources (i.e. eat), he must obtain the forks from his contending neighbours. For all such forks he does not have, he sends a request message
When a philosopher with a fork receives a request message, he keeps the fork if it is clean, but gives it up when it is dirty. If he sends the fork over, he cleans the fork before doing so
After a philosopher is done eating, all his forks become dirty. If another philosopher had previously requested one of the forks, he cleans the fork and sends it

This solution also allows for a large degree of concurrency

Mathematical mysteries: The Barber's Paradox
by Helen Joyce

A close shave for set theory

Suppose you walk past a barber's shop one day, and see a sign that says

"Do you shave yourself? If not, come in and I'll shave you! I shave anyone who does not shave himself, and noone else"
This seems fair enough, and fairly simple, until, a little later, the following question occurs to you - does the barber shave himself? If he does, then he mustn't, because he doesn't shave men who shave themselves, but then he doesn't, so he must, because he shaves every man who doesn't shave himself... and so on. Both possibilities lead to a contradiction

This is the Barber's Paradox, discovered by mathematician, philosopher and conscientious objector Bertrand Russell, at the begining of the twentieth century. As stated, it seems simple, and you might think a little thought should show you the way around it. At worst, you can just say "Well, the barber's condition doesn't work! He's just going to have to decide who to shave in some different way." But in fact, restated in terms of so-called "naïve" set theory, the Barber's paradox exposed a huge problem, and changed the entire direction of twentieth century mathematics



In naïve set theory, a set is just a collection of objects that satisfy some condition. Any clearly phrased condition is thought to define a set - namely, those things that satisfy the condition. Here are some sets:

The set of all red motorcycles ;
The set of all integers greater than zero;
The set of all blue bananas - which is just the empty set!


This set is not a member of itself

Some sets are not members of themselves - for example, the set of all red motorcycles - and some sets are - for example, the set of all non-motorcycles. Now what about the set of all sets which are not members of themselves? Is it a member of itself or not? If it is, then it isn't, and if it isn't, then it is... Just like the barber who shaves himself, but mustn't, and therefore doesn't, and so must!

So now we realise that Russell's Barber's Paradox means that there is a contradiction at the heart of naïve set theory. That is, there is a statement S such that both itself and its negation (not S) are true. The particular statement here is "the set of all sets which are not members of themselves contains itself". But once you have a contradiction, you can prove anything you like, just using the rules of logical deduction! This is how it goes

If S is true, and Q is any other statement, then "S or Q" is clearly true
Since "not S" is also true, so is "S or Q and not S"
Therefore Q is true, no matter what it is
The paradox raises the frightening prospect that the whole of mathematics is based on shaky foundations, and that no proof can be trusted. In essence, the problem was that in naïve set theory, it was assumed that any coherent condition could be used to determine a set. In the Barber's Paradox, the condition is "shaves himself", but the set of all men who shave themselves can't be constructed, even though the condition seems straightforward enough - because we can't decide whether the barber should be in or out of the set. Both lead to contradictions

Attempts to find ways around the paradox have centred on restricting the sorts of sets that are allowed. Russell himself proposed a "Theory of Types" in which sentences were arranged hierarchically. At the lowest level are sentences about individuals. At the next level are sentences about sets of individuals; at the next level, sentences about sets of sets of individuals, and so on. This avoids the possibility of having to talk about the set of all sets that are not members of themselves, because the two parts of the sentence are of different types - that is, at different levels

But to be a satisfactory philosophy, we have to be able to say why you are not allowed to mix levels. Although, for example, it is not true that the property of being red is itself red, this is surely a wrong statement, rather than actually meaningless. And there are properties that seem reasonably to apply to themselves - the Theory of Types disallows statements such as "It's nice to be nice" but really this seems like a reasonable and true statement!

For this and other reasons, the most favoured escape from Russell's Paradox is the so-called Zermelo-Fraenkel axiomatisation of set theory. This axiomatisation restricts the assumption of naïve set theory - that, given a condition, you can always make a set by collecting exactly the objects satisfying the condition. Instead, you start with individual entities, make sets out of them, and work upwards. This means you do not have to suppose that there is a set of all sets, which means you don't have to try to divide that set up into those sets that contain themselves and those which don't. You only have to be able to make this division for the elements of any given set, which you have built up from individual entities via some number of steps

To end on a more flippant note, if Russell had been aware of the inbuilt sexism of the language of his day, the course of twentieth century mathematics might have been different. There is an easy solution to the Barber's Paradox, which doesn't require the opening of any nasty cans of set-theoretic worms. Just make the barber a woman...


--------------------------------------------------------------------------------

About the author
Helen Joyce is editor of Plus