Dining Philosophers

This is a classic problem to illustrate challenges with concurrency. We will give here a solution based on Dale Schumacher's blogpost ^[1]. First some initial definitions:

using Actors
import Actors: spawn

const eating_time = 5
const thinking_time = 10
const speedup = 100

mutable struct Phil{L}
    left::L
    right::L
    eaten::Float64
end

delay(time, msg, cust) = async() do 
    sleep(time/speedup)
    send(cust, msg)
end

@msg Take Taken Busy Put Eat Think

The first part of an actor based solution is that each chopstick between the philosophers is an actor. So only one access to a chopstick is possible at a time. And the philosophers will have to communicate with the chopsticks to take them:

mutable struct Chopstick
    idle::Bool
    Chopstick() = new(true)
end

function (c::Chopstick)(cust, ::Take)
    if c.idle
        send(cust, self(), Taken())
        c.idle = false
    else
        send(cust, self(), Busy())
    end
end
(c::Chopstick)(::Put) = c.idle = true

We have modeled a chopstick actor as a function object with two message arguments, Take and Put.

Now the philosophers! We model them with behavior functions representing their state, the respective philosopher as an acquaintance and state transitions with become. So a philosopher is modeled as a finite state machine:

function thinking(p::Phil, ::Eat)
    send(p.left, self(), Take())
    send(p.right, self(), Take())
    become(hungry, p)
end
function hungry(p::Phil, chop, ::Taken)
    chop == p.left ?
        become(right_waiting, p) :
        become(left_waiting,  p)
end
hungry(p::Phil, chop, ::Busy) = become(denied, p)
function denied(p::Phil, other, ::Taken)
    send(other, Put())
    become(thinking, p)
    send(self(), Eat())
end
function denied(p::Phil, chop, ::Busy)
    become(thinking, p)
    send(self(), Eat())
end
function right_waiting(p::Phil, chop, ::Taken)
    if chop == p.right 
        become(eating, p)
        p.eaten += te = randn()+eating_time
        delay(te, Think(), self())
    end
end
function right_waiting(p::Phil, chop, ::Busy)
    send(p.left, Put())
    become(thinking, p)
    send(self(), Eat())
end
function left_waiting(p::Phil, chop, ::Taken)
    if chop == p.left
        become(eating, p)
        p.eaten += te = randn()+eating_time
        delay(te, Think(), self())
    end
end
function left_waiting(p::Phil, chop, ::Busy)
    send(p.right, Put())
    become(thinking, p)
    send(self(), Eat())
end
function eating(p::Phil, ::Think)
    send(p.left, Put())
    send(p.right, Put())
    become(thinking, p)
    delay(randn()+thinking_time, Eat(), self())
end

The crucial step in preventing a deadlock is that a philosopher puts down his chopstick if he is right_waiting or left_waiting and gets a :busy or if he is denied and gets a :taken message. Then he switches again to thinking and sends a message to himself to :eat. So he can try again.

We need a stats function for eating time and we setup everything:

eaten(phils...) = Tuple(round(Int, query(p, :bhv).a[1].eaten) for p in phils)

c1 = spawn(Chopstick())
c2 = spawn(Chopstick())
c3 = spawn(Chopstick())
c4 = spawn(Chopstick())
c5 = spawn(Chopstick())

descartes = spawn(thinking, Phil(c1,c2,0.0))
nietzsche = spawn(thinking, Phil(c2,c3,0.0))
kant      = spawn(thinking, Phil(c3,c4,0.0))
hume      = spawn(thinking, Phil(c4,c5,0.0))
plato     = spawn(thinking, Phil(c5,c1,0.0))

for p in (descartes, nietzsche, kant, hume, plato)
    delay(thinking_time, Eat(), p)
end

To get some stats we print the eaten times every second:

julia > for i in 1:5
            sleep(1)
            println(i, "s: ", eaten(descartes, nietzsche, kant, hume, plato))
        end
1s: (24, 34, 32, 31, 31)
2s: (57, 70, 61, 62, 65)
3s: (86, 101, 89, 96, 100)
4s: (119, 129, 123, 124, 132)
5s: (151, 162, 155, 155, 162)

So they are happy thinking and eating asynchronously. Since we have a speedup of 100, we can conclude that in 500 time units our philosophers eat around 155 (much more than programmers). We stop the whole thing in order to prevent overconsumption:

julia > foreach(a->exit!(a), (descartes, nietzsche, kant, hume, plato, c1, c2, c3, c4, c5))

Actually Gul Agha proposed something else. He reasoned about to let philosophers talk to each other:

An actor is free and able to figure out a deadlock situation by querying other actors as to their local state. ... While these philosophers may be "busy" eating or looking for a chopstick, they nevertheless accept communications sent to them. ^[2]

We did not go this road in order to avoid philosophical debates about local state. But you can try for yourself.