I'll jump the description of the problem, as you probably remember it from your operating system class [1].
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.
The AWAIT command puts the running reaction (method) to sleep until one of its parameters happens (other reactions or a timeout).
It's like a LINK, but it is created in the middle of a reaction and is broken when triggered for the first time.
This primitive brings Esterel capabilities to LuaGravity, that is, imperative reactivity.
Here's a possible solution for the problem:
Phil = Class('phil', function ()
function init (self, left, right)
... -- initialization code omitted
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.get(self) and right.get(self)) do
AWAIT(0) -- controversial delay
left.put(self)
right.put(self)
AWAIT(left.put, right.put)
end
-- eat
self.state = 'eating'
self.total = self.total() + 1
AWAIT(math.random(5))
-- back to think
left.put(self)
right.put(self)
end
end
end)
local fork = {}
for i=1, 5 do
fork[i] = Fork() -- Fork definition omitted
end
local phil = {}
phil[1] = Phil(1, fork[1], fork[2])
phil[2] = Phil(2, fork[2], fork[3])
phil[3] = Phil(3, fork[3], fork[4])
phil[4] = Phil(4, fork[4], fork[5])
phil[5] = Phil(5, fork[5], fork[1])
for i=1, 5 do
phil[i].s_run()
end
The important function is run, in the philosopher class.
It's a loop in which 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.
In the inner while, the philosopher first tries to get both forks.
If he succeeds, the loop is finished, otherwise the forks (the one he got) are put back in the table.
Then, he waits for any of his forks to be released by his neighbors to repeat the process.
The statement AWAIT(0) is used to avoid a cycle in a call to fork.put(), I'll dig into it anytime.
Just by changing the variables self.state and self.total is enough to update the screen - it's all about reactivity.
[1] http://en.wikipedia.org/wiki/Dining_philosophers_problem
Posts
