Schopenhauer is Bogarting the Chopstick: Resource Scarcity in a Time of Sufficiency.Posted: November 11, 2012 | |
There’s a classic problem in Computer Science called the Dining Philosophers’ problem and I’m going to introduce it here for those who haven’t heard it before. The original formulation (Tony Hoare after Dijkstra’s basic problem) used forks and spaghetti. I’m Australian so I’m going bow to the delight of fusion cuisine and use chopsticks and rice (I didn’t invent this, let me hasten to add, this has been a common restatement for years now). For those who don’t know, to pick anything up, you need two chopsticks. Here’s the problem:
Five philosophers are sitting around a circular table, silently, with a chopstick between each pair of philosophers. There is a bowl of rice on that table that every philosopher can reach (or they each have a bowl, it doesn’t matter, the rice is infinite but cannot be consumed without chopsticks). These philosophers aren’t talking: they either think (silently) or eat. If they wish to eat they need to pick up the chopsticks on either side of them. A philosopher will eat for a while, then stop and put down the chopsticks on the table. A philosopher can pick up the chopsticks separately or at the same time, as long as they are on the table. He or she cannot start eating without having both chopsticks.
The problem that is presented in terms of philosophers who think or eat, in a world of rice and chopsticks, is actually a very good example of competing access to shared resources and it very neatly and quickly identifies how such a simpler set-up can quickly fail if we don’t think carefully about how we control access. What we want is way that the philosophers can behave that allows them all to eat and think alternately without having to provide some sort of fixed schedule or perfect knowledge of what every other philosopher is going to do.
There are enough chopsticks for at most two philosophers to eat at the same time (there must be five chopsticks and we need two to eat) so we know that it is possible that the philosophers can eat, given how the chopsticks are arranged. (If we had stated the problem the same way but included only 1 chopstick, or 2 in a way that no philosopher could grab both, then we could determine that everyone would starve.) What might be less obvious is that it is possible to enter a state called deadlock, where our system reaches a state where no progress is possible. What would happen, for example, if after a period of thinking, every philosopher decided to pick up their left hand chopstick, pausing before picking up the right? In this case, every philosopher holds one chopstick, which is not enough to allow eating, but now there are none left on the table! If we have not thought about how we will give that resource back then we are at risk of leaving the system in that state. If, more subtly, we haven’t thought about the possibility that we can’t start eating (and we know that eating has a duration), then we will wait indefinitely for a second chopstick that will never come, because we didn’t consider that waiting for a chopstick could also have a finite duration.
Of course, just putting in a time interval that we wait before putting the fork down is not necessarily going to work either. If all philosophers pick up their left chopstick at the same time, but put it down after 10 minutes, then this behaviour will cycle forever – now we’re seeing livelock. (I won’t go into the technical detail but the key difference between deadlock and live lock is that deadlock sticks in one state, where livelock switches between states but still makes no progress in this transition. Deadlock is a brick wall in the corridor, livelock is the dance between you and a coworker as you try to sidestep each other in the same corridor until you both die of politeness.)
This problem is at the core of Computer Science and Operating Systems, in particular, as modern systems are made up of lots and lots of activity being conducted over one set of resources. There are several very interesting solutions to these types of problems and it illustrates one very important point in communicating ideas to students: the analogy that we use (if we use one) has to be familiar to the students and robust enough to correctly demonstrate the idea.
The original version of the problem, as I heard it as well, involved forks and spaghetti. Philosophers needed two forks to eat. That’s fine, but most of my students then say “but I only need one fork to eat spaghetti” and you then have the choice of saying “Ah, but you need two forks to lift spaghetti” or you start making the model arbitrarily fixed (“you just need two in this case”). If you make it a knife and a fork, which is how many people eat, then you immediately have a problem as you cannot require a knife and a fork pair and expect anything sensible to happen with an odd number. For an odd number of pieces of cutlery, one philosopher is sitting there with either two forks (default problem) or two knives (and commits seppuku rather than wait to die a slow longer death of starvation).
The other interesting thing that we lead into, when we present this problem, is that we can talk about two very important ideas: safety and liveness. Safety constraints stop anything bad from happening and are sometimes placed on to systems to protect them (from us, or us from them). Liveness goals require us to try and make something good happen whenever we can do so, so that we may make as much progress as possible towards our goal. Adding these two new considerations adds new dimensions to our original problem, which amounted to “let the philosophers think and eat without starving”. Now we have to think about how to potentially protect the philosophers from each other and from themselves but this is balanced against a requirement to ensure that we actually allow the philosophers to make as much progress as possible.
In discussing “Dining Philosophers” and the reason that we might use chopsticks, we immediately start to get the students thinking about what they do, with an example that matches what the real experience is. Of course, in Australia, we use chopsticks a lot. The restatement (which is both commonly used and effectively global) takes a good abstraction that conceals some clever thinking and makes it even better. Like many things that start well, more thought and the involvement of more people can often be beneficial. Of course, many of my students ask “why can’t they just speak to each other?’ which is a perfectly reasonable question but then requires co-ordination and communication burden – but it’s worth noting that the Chandy / Ayushi solution does add that as well! This question gives us a way to talk about how the real systems work in more detail but, more subtly, it’s a question and that means that someone is potentially interested in the answer, even if they thought they were being flippant.