Non-blocking solution to the dining philosophers

Question

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?

Answer 1

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.

Answer 2

In the context of the problem, non-blocking means no deadlock. I.e., a philosopher will not suspend indefinitely waiting for one fork while already holding the other fork. Suspension means that the thread is disabled for scheduling purposes and will not execute until another thread specifically resumes the suspended thread. The solution must avoid indefinite suspension or deadlock (i.e., 2 or more threads suspended waiting on each other to proceed).

The solution requires an arbitrator that can atomically grant both forks or reject the request. If the philosopher cannot atomically take both forks, then the philosopher must think about life, the universe and everything else for a random amount of time. After thinking, the philosopher again requests to the arbitrator to acquire atomically both forks. Eating also delays for a random time before relinquishing both forks. All random delays are finite with a common upper limit, say, 10 seconds or 10 minutes, whatever.

This design requires a compare-and-swap mechanism to examine and conditionally update a bit mask, with one bit for each fork. The mechanism is atomic. Either both bits are updated or neither are updated.

A sample solution in java for an arbitrary number of philosophers that uses only volatile fields and no synchronized() blocks or suspension locks is available at: sourceforge.net/projects/javamutex/