The Synchronous Blog

A blog about reactive programming languages.

The Dining Philosophers Problem

leave a comment »

Ok, here’s the classical synchronization problem.
I’ll jump the description of the problem [1], as you probably remember it from your operating system class.
A common solution involves mutual exclusion to lock access to shared forks.
Besides deadlock, the solution should avoid starvation and livelock as well.

The result can be seen in the video below:

The solution in LuaGravity uses its AWAIT primitive.

Here’s a possible solution for the problem:

Phil = org.class('phil', function ()
    function init (self)
        self.state  = ''  = 0
        self.text   = self.state .. ' (' .. .. ')'
        local p = POS[self._i]
            Text {
                text   = self.text,
                face   = 'vera.ttf',
                _color = {r=0,g=0,b=0},
                x = p.x,
                y = p.y, dy=13,
    function run (self)
        local left, right = self._left, self._right
        while true
            -- think
            self.state = 'thinking'

            -- wait
            self.state = 'hungry!'
            while not (left:_isFree() and right:_isFree()) do
                AWAIT(left.put, right.put)

            -- eat
            self.state = 'eating'
   = + 1

            -- back to think
end )

The reactor run is a infinity loop where the philosopher thinks, waits for the forks and eats.
The think and eat steps are just an AWAIT on a random time between 1 and 5 seconds.

After thinking, the philosopher enters the inner while, checking whether his forks are available for use, otherwise he waits for them until he succeeds.
After leaving the inner while, the philosopher acquires his forks in order to eat.
Note that, in synchronous languages, there’s no need for mutexes or other means of mutual exclusion.

After acquiring the forks, the philosopher eats for a random time.
Then, he goes back to think, releasing his forks.
The call to reactor put awakes philosopher’s neighbors if they are in their inner while.

Just by changing the variables self.state and is enough to update the screen – it’s all about reactivity.

The full example code can be found here.



Written by francisco

November 3, 2008 at 5:29 pm

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: