1226. The Dining Philosophers

https://en.wikipedia.org/wiki/Dining_philosophers_problem

design a discipline of behavior avoid deadlock and livelock： allow at most 4 philosophers to dine so that at least one philosopher can acquire 2 forks

can we allow at most 3 philosophers to dine? Yes but still the min number of philosopher can acquire 2 forks is 1

The 2 rules ensure that at least one philosopher can pick up both forks at any point

from threading import Semaphore

class DiningPhilosophers:
    def __init__(self):
        self.semaphore = Semaphore(4)
        self.locks = [Semaphore(1) for i in range(5)]
        
    # call the functions directly to execute, for example, eat()
    def wantsToEat(self,
                   philosopher: int,
                   pickLeftFork: 'Callable[[], None]',
                   pickRightFork: 'Callable[[], None]',
                   eat: 'Callable[[], None]',
                   putLeftFork: 'Callable[[], None]',
                   putRightFork: 'Callable[[], None]') -> None:
        left, right = philosopher, (philosopher + 1) % 5
        with self.semaphore:
            with self.locks[left], self.locks[right]:
                pickLeftFork()
                pickRightFork()
                eat()
                putLeftFork()
                putRightFork()

Option 2: 该题的本质是考察如何避免死锁。而当5个哲学家都左手持有其左边的叉子或当5个哲学家都右手持有其右边的叉子时，会发生死锁。故只需设计1个避免发生上述情况发生的策略即可。

即可以让一部分哲学家优先去获取其左边的叉子，再去获取其右边的叉子；再让剩余哲学家优先去获取其右边的叉子，再去获取其左边的叉子。

作者：gfu 链接：https://leetcode-cn.com/problems/the-dining-philosophers/solution/1ge-semaphore-1ge-reentrantlockshu-zu-by-gfu/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Suppose P0 acquired his right lock, which means P4 didn't acquire his left lock, and right lock. Thus 4 philosophers are sharing 5 forks
Suppose P0 didn't acquire his right lock, then P0 wouldn't acquire his left lock. Thus 4 philosophers are sharing 5 forks

from threading import Semaphore

class DiningPhilosophers:
    def __init__(self):
        self.locks = [Semaphore(1) for i in range(5)]
        
    # call the functions directly to execute, for example, eat()
    def wantsToEat(self,
                   philosopher: int,
                   pickLeftFork: 'Callable[[], None]',
                   pickRightFork: 'Callable[[], None]',
                   eat: 'Callable[[], None]',
                   putLeftFork: 'Callable[[], None]',
                   putRightFork: 'Callable[[], None]') -> None:
        
        def action():
            pickLeftFork()
            pickRightFork()
            eat()
            putLeftFork()
            putRightFork()
            
        left, right = philosopher, (philosopher + 1) % 5
        if philosopher: # philosopher 1, 2, 3, 4
            with self.locks[left], self.locks[right]:
                action()
        else: # philosopher0
            with self.locks[right], self.locks[left]:
                action()

1226. The Dining Philosophers - cocoder39/coco39_LC GitHub Wiki