Originally created by Edsger Dijkstra in 1965, the Dining Philosophers problem is a classic synchronization problem that illustrates the challenges of resource sharing and deadlock in concurrent programming. Tony Hoare is credited with phrasing the problem in its current form.
Wikipedia has a nice article on the problem.
Five philosophers sit at a round table with only five chairs, five plates of food, and five chopsticks. Each philosopher has their own plate, and there is exactly one chopstick between each adjacent pair of philosophers. Each philosopher alternates between thinking and eating. To eat, a philosopher needs two chopsticks, the one on their left and one on their right. Two philosophers may not eat with the same chopstick at the same time. A philosopher may not steal a chopstick from another while the latter is eating.
How can the system be implemented that is correct, safe, live, fair, and free of deadlock, livelock, and starvation?
Burns and Wellings describe eight aspects of communication and coordination illustrated by this rather simple-sounding problem.
Here are some things to try out. Some may work and some may not.
This little script maximizes the number of concurrent diners to four using a semaphore for the “table”. Chopsticks use the built-in monitor on every Java object, which is super clean.
// Classic set up with five philosophers and five chopsticks.
static String[] NAMES = {"Haack", "Hume", "Zhaozhou", "Kaṇāda", "Russell"};
static Object[] chopsticks =
Stream.generate(Object::new).limit(NAMES.length).toArray(Object[]::new);
// We will require one seat to be empty to avoid deadlock. Philosophers
// must acquire the table semaphore in order to sit down and eat, and
// release it when they leave the table, which they do after each meal.
static Semaphore table = new Semaphore(NAMES.length - 1);
record Philosopher(int id, int numberOfMeals) implements Runnable {
private void action(String action) {
// For immediate actions, like picking up or putting down a chopstick.
IO.println(NAMES[id] + " " + action);
}
private void action(String action, int maxMillis) throws InterruptedException {
// For actions that take some time, like eating or thinking.
// Sleeps between maxMillis / 2 and maxMillis milliseconds.
action(action);
Thread.sleep(ThreadLocalRandom.current().nextInt(maxMillis / 2, maxMillis + 1));
}
@Override
public void run() {
var left = chopsticks[id];
var right = chopsticks[(id + 1) % chopsticks.length];
try {
for (var i = 0; i < numberOfMeals; i++) {
table.acquire();
action("has sat down and is now thinking", 8000);
synchronized (left) {
action("picked up left chopstick");
synchronized (right) {
action("picked up right chopstick");
action("is eating", 5000);
}
action("put down right chopstick");
}
action("put down left chopstick");
table.release();
action("has left the table", 2000);
}
action("has gone home");
} catch (InterruptedException _) {
Thread.currentThread().interrupt();
}
}
}
void main() {
for (var i = 0; i < NAMES.length; i++) {
Thread.ofPlatform().start(new Philosopher(i, 3));
}
}
Run with java DiningPhilosophers.java.
This is a somewhat direct translation from Java, except that instead of creating a thread object with a runnable task, we use Kotlin’s cool thread() function which runs a block of code:
import java.util.concurrent.Semaphore
import kotlin.concurrent.thread
import kotlin.random.Random
object Restaurant {
val NAMES = arrayOf("Haack", "Hume", "Zhaozhou", "Kaṇāda", "Russell")
val chopsticks = Array(NAMES.size) { Any() }
val table = Semaphore(NAMES.size - 1)
}
class Philosopher(private val id: Int, private val numberOfMeals: Int) {
private fun action(action: String, maxMillis: Int = 0) {
println("${Restaurant.NAMES[id]} $action")
if (maxMillis <= 0) return
Thread.sleep(Random.nextInt(maxMillis / 2, maxMillis + 1).toLong())
}
fun dine() {
val left = Restaurant.chopsticks[id]
val right = Restaurant.chopsticks[(id + 1) % Restaurant.chopsticks.size]
try {
repeat(numberOfMeals) {
Restaurant.table.acquire()
action("has sat down and is now thinking", 8000)
synchronized(left) {
action("picked up left chopstick")
synchronized(right) {
action("picked up right chopstick")
action("is eating", 5000)
}
action("put down right chopstick")
}
action("put down left chopstick")
Restaurant.table.release()
action("has left the table", 2000)
}
action("has gone home")
} catch (e: InterruptedException) {
Thread.currentThread().interrupt()
}
}
}
fun main() {
for (i in Restaurant.NAMES.indices) {
thread { Philosopher(i, 3).dine() }
}
}
Run with kotlinc DiningPhilosophers.kt && kotlin DiningPhilosophersKt.
This one uses mutexes for the chopsticks and a buffered channel of size 4 for the table:
package main
import (
"fmt"
"math/rand"
"sync"
"time"
)
var names = []string{"Haack", "Hume", "Zhaozhou", "Kaṇāda", "Russell"}
var chopsticks = make([]sync.Mutex, len(names))
var table = make(chan struct{}, len(names)-1)
var wg sync.WaitGroup
var rng = rand.New(rand.NewSource(time.Now().UnixNano()))
type Philosopher struct {
id int
numberOfMeals int
}
func (p Philosopher) action(msg string) {
fmt.Printf("%s %s\n", names[p.id], msg)
}
func (p Philosopher) durationAction(msg string, max time.Duration) {
p.action(msg)
time.Sleep(max/2 + time.Duration(rng.Int63n(int64(max/2))))
}
func (p Philosopher) dine() {
defer wg.Done()
left := &chopsticks[p.id]
right := &chopsticks[(p.id+1)%len(chopsticks)]
for i := 0; i < p.numberOfMeals; i++ {
table <- struct{}{} // sit down (acquire a seat)
p.durationAction("has sat down and is now thinking", 8*time.Second)
left.Lock()
p.action("picked up left chopstick")
right.Lock()
p.action("picked up right chopstick")
p.durationAction("is eating", 5*time.Second)
right.Unlock()
p.action("put down right chopstick")
left.Unlock()
p.action("put down left chopstick")
<-table // leave the table (release seat)
p.durationAction("has left the table", 2*time.Second)
}
p.action("has gone home")
}
func main() {
for i := range names {
wg.Add(1)
go Philosopher{id: i, numberOfMeals: 3}.dine()
}
wg.Wait()
}
Run with go run dining-philosophers.go.
defer statement to guarantee that chopsticks are always put down, even if the philosopher panics.
The Ada code is a bit longer, as writing to standard output is not thread-safe, random numbers are little less convenient, and we usually build concurrency objects directly rather than using built in mutexes and semaphores. Actually, though, it’s kind of cool to just build them from protected objects. It feels quite readable! Ada concurrent applications frequently use abstractions that match the real-world actions, making the code easier to understand, maintain, and reason about.
with Ada.Text_IO, Ada.Numerics.Float_Random;
use Ada.Text_IO, Ada.Numerics.Float_Random;
procedure Dining_Philosophers is
type Id is mod 5;
Gen: Generator;
task type Philosopher is
entry Start (My_Id: Id);
end Philosopher;
protected type Chopstick is
entry Pick_Up;
entry Put_Down;
private
Up: Boolean := False;
end Chopstick;
protected type Table is
entry Sit_Down_At;
procedure Get_Up_From;
private
Occupants: Natural := 0;
end Table;
protected type Reporter is
procedure Report (Message: String);
end Reporter;
The_Philosophers: array (Id) of Philosopher;
The_Chopsticks: array (Id) of Chopstick;
The_Table: Table;
The_Reporter: Reporter;
task body Philosopher is
Me: Id;
procedure Action (Message: String; Max_Duration: Duration := 0.0) is
Half_Max_Duration: Float := Float(Max_Duration / 2.0);
begin
The_Reporter.Report ("Philosopher" & Me'Image & " " & Message);
if Max_Duration > 0.0 then
delay Duration(Half_Max_Duration + Random(Gen) * Half_Max_Duration);
end if;
end Action;
begin
accept Start (My_Id: Id) do
Me := My_Id;
end;
for Times_Eaten in 1 .. 3 loop
The_Table.Sit_Down_At;
Action ("has sat down and is now thinking", 8.0);
The_Chopsticks(Me).Pick_Up;
Action ("picked up the left chopstick");
The_Chopsticks(Me+1).Pick_Up;
Action ("picked up the right chopstick and is eating", 5.0);
The_Chopsticks(Me + 1).Put_Down;
Action ("has put down the right chopstick");
The_Chopsticks(Me).Put_Down;
Action ("has put down the left chopstick");
The_Table.Get_Up_From;
Action ("has left the table", 2.0);
end loop;
Action ("has gone home");
end Philosopher;
protected body Chopstick is
entry Pick_Up when not Up is
begin
Up := True;
end Pick_Up;
entry Put_Down when Up is
begin
Up := False;
end Put_Down;
end Chopstick;
protected body Table is
entry Sit_Down_At when Occupants < Id'Modulus - 1 is
begin
Occupants := Occupants + 1;
end Sit_Down_At;
procedure Get_Up_From is
begin
Occupants := Occupants - 1;
end Get_Up_From;
end Table;
protected body Reporter is
procedure Report (Message: String) is
begin
Put_Line (Message);
end Report;
end Reporter;
begin
Reset(Gen);
for I in Id loop
The_Philosophers(I).Start (I);
end loop;
end Dining_Philosophers;
Here we went with making everything a process, and implemented the chopsticks and tables with readable “actions” as Erlang atoms:
% Dining Philosophers Problem in Erlang
main(_) ->
Restaurant = self(),
Names = ["Haack", "Hume", "Zhaozhou", "Kanada", "Russell"],
Chopsticks = [spawn(fun chopstick/0) || _ <- Names],
Table = spawn(fun() -> table(length(Names) - 1) end),
lists:foreach(fun(Id) ->
Name = lists:nth(Id, Names),
Left = lists:nth(Id, Chopsticks),
Right = lists:nth(Id rem length(Chopsticks) + 1, Chopsticks),
spawn(fun() -> philosopher(3, Id, Name, Left, Right, Table, Restaurant) end)
end, lists:seq(1, length(Names))),
wait_for_all_philosophers(length(Names)).
chopstick() ->
receive
{pickup, Philosopher} ->
Philosopher ! granted,
receive putdown -> chopstick() end
end.
table(N) ->
receive
{sitdown, Philosopher} when N > 0 ->
Philosopher ! seat,
table(N - 1);
leave ->
table(N + 1)
end.
philosopher(0, _Id, Name, _Left, _Right, _Table, Restaurant) ->
io:format("~s has gone home~n", [Name]),
Restaurant ! done;
philosopher(Meals, Id, Name, Left, Right, Table, Restaurant) ->
Table ! {sitdown, self()},
receive seat -> ok end,
action(Name, "has sat down and is now thinking", 8000),
Left ! {pickup, self()},
receive granted -> action(Name, "picked up left chopstick") end,
Right ! {pickup, self()},
receive granted -> action(Name, "picked up right chopstick") end,
action(Name, "is eating", 5000),
Right ! putdown,
action(Name, "put down right chopstick"),
Left ! putdown,
action(Name, "put down left chopstick"),
Table ! leave,
action(Name, "has left the table", 2000),
philosopher(Meals - 1, Id, Name, Left, Right, Table, Restaurant).
action(Name, Msg) ->
io:format("~s ~s~n", [Name, Msg]).
action(Name, Msg, MaxMillis) ->
action(Name, Msg),
timer:sleep(rand:uniform(MaxMillis div 2 + 1) + (MaxMillis div 2)).
wait_for_all_philosophers(0) -> ok;
wait_for_all_philosophers(N) ->
receive
done -> wait_for_all_philosophers(N-1)
end.
Run with escript dining_philosophers.erl.
I wrote up an extended version of this problem twenty years ago or so.
Here are some questions useful for your spaced repetition learning. Many of the answers are not found on this page. Some will have popped up in lecture. Others will require you to do your own research.
Runnable interface in Kotlin? thread() function that takes a block of code to run.struct{} with no fields (namely struct{}{}).synchronized statement, since every Java object has a built-in monitor.We’ve covered: