Dining Philosophers multiThreaded does not end

Question

I am trying to solve the dining philosophers problem using mutex locks in python

import threading
import time
chopstick_a = threading.Lock()
chopstick_b = threading.Lock()
chopstick_c = threading.Lock()
sushi_count = 500
def philosopher(name, first_chopstick, second_chopstick):
global sushi_count
#print(name,'is trying to eat')

while sushi_count > 0:  # eat sushi until it's all gone
    first_chopstick.acquire()
    second_chopstick.acquire()

    if sushi_count > 0:
        sushi_count -= 1
        print(name)
        print(name, 'took a piece! Sushi remaining:', sushi_count)
        
    second_chopstick.release()
    first_chopstick.release()
    


if __name__ == '__main__':
    threading.Thread(target=philosopher, args=('phil_one', chopstick_a, chopstick_b)).start()
    threading.Thread(target=philosopher, args=('phil_two', chopstick_b, chopstick_c)).start()
    threading.Thread(target=philosopher, args=('phil_three', chopstick_c, chopstick_a)).start()

The problem is that the program never terminates with zero and only one philosopher gets to eat

this is a sample output which never reaches to zero

phil_one took a piece! Sushi remaining: 466
phil_one
phil_one took a piece! Sushi remaining: 465
phil_one
phil_one took a piece! Sushi remaining: 464
phil_one
phil_one took a piece! Sushi remaining: 463
phil_one
phil_one took a piece! Sushi remaining: 462
phil_one
phil_one took a piece! Sushi remaining: 461
phil_one
phil_one took a piece! Sushi remaining: 460
phil_one
phil_one took a piece! Sushi remaining: 459
phil_one
phil_one took a piece! Sushi remaining: 458
phil_one
phil_one took a piece! Sushi remaining: 457
phil_one
phil_one took a piece! Sushi remaining: 456

Answer 1

Congratulations, you are deadlocked. Deadlocking is almost a philosophical question in and of itself. What happened?

1. Philosopher One took some sushi and released chopsticks A and B.
2. Philosopher Two then acquired chopstick B.
3. Philosopher One then acquired chopstick A.
4. Philosopher One is still waiting to acquire chopstick B. It may be some time.

Answer 2

The dining philosophers problem is an example of a simple problem that doesn't have a simple solution.

In your particular approach you have a lock for each chopstick. Consider the following scenario:

1. Each philosopher takes left chopstick at the same time. Since it is the beginning, all chopsticks are free to be taken. And exactly that happens. Now there are no chopsticks free.
2. Each philosopher waits for the right chopstick. But this never happens because noone does anything other than waiting.

You've hit a deadlock.

Now, you might be confused because you actually see some output before it hangs. That's because not every philosopher has the same speed. Which is a metaphore for: not every loop iteration works with the same speed, some operations execute a bit faster, some a bit slower. There is also an OS scheduler that determines which thread runs and when. In addition Python has this thing called GIL, which makes it pretty much single threaded. All of that (and more) combined can result in the "phil_one" philosopher to loop few times, before others run and the entire system ends up being deadlocked.

I strongly encourage you to read the wiki page (the one I linked at the begining). You can find some solutions to the problem there.

Answer 3

the program never terminates with zero...

Other answers address that problem,

...and only one philosopher gets to eat

That problem is known as starvation: One (or more) thread(s) continually wins the race to access some resource while other thread(s) continually lose the race.

This is an anti-pattern that usually causes starvation:

    while some_trivial_condition:
        my_mutex.lock()
        do_some_work()
        my_mutex.unlock()

Every time a thread releases my_mutex, almost the very next thing it does is, it tries to lock the mutex again. The window of opportunity for another thread to sneak in there and grab the lock is extremely small. The problem is made worse by the fact that the thread that just released the lock already is running, while the other threads all are asleep, (blocked,) waiting for it.

In most operating systems, the goal of thread scheduling is to make the most efficient use of the CPU. That means, when two or more threads are contending for the same resource, the OS will favor the one that can grab it the most quickly, and not the one that's been waiting the longest.

In some programming systems, but not in the Python standard library, there is something called a fair lock which behaves in exactly the opposite way: The OS always wakes up the thread that's been waiting the longest for a fair lock.