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  = ''
        self.total  = 0
        self.text   = self.state .. ' (' .. self.total .. ')'
        local p = POS[self._i]
        screen:add(
            Text {
                text   = self.text,
                face   = 'vera.ttf',
                _color = {r=0,g=0,b=0},
                x = p.x,
                y = p.y, dy=13,
        })
    end
    function run (self)
        local left, right = self._left, self._right
        while true
        do
            -- think
            self.state = 'thinking'
            AWAIT(math.random(5))

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

            -- eat
            left:_get(self)
            right:_get(self)
            self.state = 'eating'
            self.total = self.total() + 1
            AWAIT(math.random(5))

            -- back to think
            left:put(self)
            right:put(self)
        end
    end
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 self.total is enough to update the screen – it’s all about reactivity.

The full example code can be found here.

[1] http://en.wikipedia.org/wiki/Dining_philosophers_problem

Advertisements

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:

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: