I have been asked to write a simple solution to the dining philosophers problem in python. That itself seems quite straight forward but am some what confused since I am asked to write a non-blocking solution. I am unsure what is meant by this in this context.
Is anyone able to give any hints or point me in the right direction?
Here is a definition of a non-blocking algorithm: http://en.wikipedia.org/wiki/Non-blocking_algorithm.
A pseudo code of a non-blocking solution to this problem:
# The number of forks.
FORKS_COUNT = ...
# Indicates if the i-th fork is taken or not.
taken = new bool[FORKS_COUNT]
# The philosopherId is a position at the table.
def haveDinner(philosopherId):
leftFork = philosopherId
rightFork = (philosopherId + 1) % FORKS_COUNT
if leftFork > rightFork:
swap(leftFork, rightFork)
while true:
# Tries to take the left fork.
while not compare_and_swap(taken[leftFork], false, true):
# Do nothing.
# Tries to take the right fork.
while not compare_and_swap(taken[rightFork], false, true):
# Do nothing.
# Eats.
...
# Returns the forks to the table.
compare_and_swap(taken[leftFork], true, false)
compare_and_swap(taken[rigthFork], true, false)
This solution uses the compare-and-swap idiom.