In case Dijkstra’s original problem was too easy to write, or you’d like a bigger challenge, we offer a little extension. It’s written to highlight not only synchronization and mutual exclusion issues, but to also bring in multiple communication paradigms: asynchronous calls, blocking calls, balking calls, and calls with timeouts.
A restaurant has a dining room with a single round table with five seats and only one chopstick between each setting. The restaurant employs two waiters (Miria and Isaac) and three chefs (Eren, Mikasa, and Armin), and serves six different meals which are:
Paella $13.25
Wu Hsiang Chi $10.00
Bogrács Gulyás $11.25
Spanokopita $6.50
Moui Nagden $12.95
Sambal Goreng Udang $14.95
Each of the entrees comes with an optional soup (which is always Albóndigas, for $3.00) and an optional desert (Berog, for $3.50).
The restaurant’s entire clientèle is made up of five philosophers who spend their lives repeatedly entering the restaurant, thinking, eating, and then leaving. They insist on eating everything, even the Albóndigas soup, with two chopsticks, in the manner described by Dijkstra in the original Dining Philosophers Problem. Each philosopher begins life with a certain amount of money (perhaps $200) and leaves after eating a meal that costs more money than they have.
When a philosopher enters the dining room, they are seated at an available seat, think for a short amount of time, then place an order to an available waiter. The waiter takes the order to the kitchen and hand delivers it to a chef who will then prepare the meal. When a chef finishes the meal, they place it on the counter where a waiter will pick it up and deliver it to the philosopher who ordered it.
After eating (which takes some amount of time), the philosopher pays for their meal and leaves the restaurant. If they cannot afford the meal that they ordered, they leave for good; otherwise they will return at some later time. When all the philosophers have run out of money and left for good, the restaurant closes down.
If a philosopher does not get their order placed within a certain amount of time, they will leave and go to something else. If a waiter cannot immediately place an order with a chef (because all chefs are busy, say) they give the philosopher a coupon good for $5.00 and the philosopher leaves the restaurant. Chefs take a coffee break after every fourth meal they prepare.
The problem is to program, to the specification above, a proper functioning of the restaurant system. There must of course be absence of deadlock and starvation; furthermore, a waiter must not deliver an order to the wrong customer. The table subsystem can be managed as in any classic solution to the original problem (only allowing four diners at a time, one asymmetric diner, and so on). To model diners not getting their orders placed in an acceptable amount of time, table orders can be placed to a blocking queue sized to the number of waiters. To model waiters not finding a chef immediately available to take an order, a balking call can be made to a queue sized to the number of chefs. To ensure prepared meals are delivered to the diner that ordered them, orders must somehow contain an identification of the diner.
Implementations can be animated with cool graphics, or employ a simple log.
The problem becomes interesting due to the variety of constructs offered by different programming languages.Some, like Java, have native semaphores, latches, and blocking queues. Go prefers channels; Erlang prefers processes. Ada’s tasks and protected objects, and direct support for blocking, timed, and balking calls, make for an elegant solution.
You can find solutions in a variety of programming languages at this GitHub Repository.
We’ve covered: