pythonalgorithmblockingdining-philosopher

Non-blocking solution to the dining philosophers


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?


Solution

  • 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.