I read this article by Uncle Bob called The Lurn (it’s a companion piece to an earlier article of his called The Churn), where he mentioned a lot of topics that he thinks are more important for developers to learn about than just scrambling to keep up with the latest languages and frameworks (not that you shouldn’t learn a few of those, but you’re going to hit diminishing returns pretty quickly because not that many things are actually a meaningful leap forward and eventually you’re going to start seeing enough patterns that learning yet another slightly different framework just isn’t a good use of your time).
One of the topics he mentioned was the Dining Philosphers problem, which I’d never heard of so I went and looked it up. The problem (quoting wikipedia, of course) is:
Five silent philosophers sit at a round table with bowls of spaghetti. Forks are placed between each pair of adjacent philosophers.
Each philosopher must alternately think and eat. However, a philosopher can only eat spaghetti when they have both left and right forks. Each fork can be held by only one philosopher and so a philosopher can use the fork only if it is not being used by another philosopher. After they finish eating, they need to put down both forks so they become available to others. A philosopher can take the fork on their right or the one on their left as they become available, but cannot start eating before getting both of them.
Eating is not limited by the remaining amounts of spaghetti or stomach space; an infinite supply and an infinite demand are assumed.
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.
Yep, it’s a concurrency problem. Specifically, a deadlock problem. Just because it sounds like it should be simple to get all of our philosphers fed doesn’t mean it actually is. The simplest solution would be that each philosopher picks up the fork on their left and waits for the fork on their right to become available – which never happens because the philosopher to their right has already taken it and is waiting for the philosopher on their right to put down their fork.
Okay, so let’s give the philosophers a time limit. If you grab one fork but don’t get another one within five minutes, you put your fork down and wait five minutes, then try again. No dice :( This is something called a livelock (that link explains it particularly well), where all the philosophers grab one fork, wait five minutes, put their forks down, wait five more minutes, and try to get two forks again. Forever. It’s almost the same thing as a deadlock except that the processes can still try to do things, they just can’t actually accomplish anything.
That only happens if every philosopher has the same wait time, though. What if we assign each philosopher a different wait time? That sort of works, but the philosopher with the longest wait time is likely to get less spaghetti because they try to pick up a fork fewer times, and if they’re particularly unlucky may get no spaghetti at all. We could try random wait times too, but only if we wanted to tear our hair out trying to figure out why one process is super slow one day and fine the next. Random numbers are out to get you – if you generate enough of them, eventually you’re going to get a long streak of [insert least helpful result here] and the people trying to use the feature that never manages to get two forks will hate you.
Another solution is to number all the forks and tell the philosophers that they must pick up the lower numbered fork first when they need one. The philosophers each grab the lower numbered fork until we get to philosopher number five, who needs to take fork one before fork five, but fork one is already taken so they don’t take any forks. That leaves fork five available to philosopher four, who sets down forks four and five when they finish eating, which lets philosopher three take forks three and four, and so on around the table.
That actually works pretty well if you only ever need two forks, but if you take forks three and four, then discover you need fork one as well, you have to set down the forks you already have and start over again from two.
Yet another solution is to introduce a waiter and make the philosophers ask them for permission to take forks. The waiter only gives permission to one philosopher at a time to pick up forks, which is great in terms of preventing deadlock but kinda sucks if one philosopher needs forks two and three, and another one needs forks four and five and they can’t get permission to pick up forks at the same time even though they don’t want the same forks.
If you relax the constraint about philosophers talking to each other, there’s another solution: all the forks are either clean or dirty (and start out dirty), and all the philosophers are numbered. When two philosophers want the same fork, the lower numbered one gets it. Any philosopher can ask for a fork, and the philosopher who has it must hand it over if it’s dirty but keeps it if it’s clean. When a philosopher finishes eating, they clean their forks and set them down. This prevents deadlocks and fixes the problem of philosophers who haven’t eaten never getting a fork, but (there’s always a but) introduces more overhead in the form of making it possible for philosophers to talk to each other and keep track of who has which fork.
Those are by no means all the possible solutions, but the individual solutions – and there are plenty of them – are less important than the general point of the exercise, which is that concurrency is hard :) Specifically, it’s prone to weird edge cases and is hard to think about because there are so many moving parts.
And now we both know what the dining philosophers problem is all about.