哲学家就餐问题

问题描述

哲学家就餐问题（Dining philosophers problem）可以这样表述，假设有五位哲学家围坐在一张圆形餐桌旁，做以下两件事情之一：吃饭，或者思考。吃东西的时候，他们就停止思考，思考的时候也停止吃东西。餐桌上每两位哲学家之间有一只餐叉，哲学家吃东西必须且只能使用左右手两边的两只餐叉。

之所以被称为一个“问题”，是因为这个系统可能会出现无法进行下去的情况。

第一种情况，假设某一时刻，所有的哲学家都想要吃东西，他们同时拿起了各自左手边的餐叉，然后当他们想要拿起右手边的餐叉时，发现已经被右边的哲学家拿起来了，如果每一个哲学家都不同意放弃自己已经拿到手的餐叉，则整个系统就无法运行下去了，出现了被称为“死锁”的状态。

另一种情况，哲学家觉得不能这么自私，如果自己已经拿起了一个餐叉，而迟迟无法获得另一个餐叉时，则他在等待一段时间后会放下自己已经拿起的餐叉。当所有哲学家都这样想，他们同时拿起左手边的餐叉，等待相同的时间，又同时放下餐叉，然后拿起、放下、拿起、放下如此循环，出现被成为“活锁”的状态。

这个问题模型最初是著名的计算机科学家艾兹格·迪科斯彻（Edsger Wybe Dijkstra）在1971年提出的一个同步问题，他假设有五台计算机都试图访问五份共享的磁带驱动器。后来，这个问题被托尼·霍尔（Charles Antony Richard Hoare）重新表述为哲学家就餐问题。这个问题可以用来解释死锁和资源耗尽。

哲学家就餐问题就是要采用适当的算法保证系统不会出现死/活锁。

解决算法

一共有三种解法，分别是 服务生解法，资源分级解法 和 Chandy/Misra解法

服务生算法

一个简单的解法是引入一个餐厅服务生，哲学家要想得到餐叉，必须先叫服务生送给他，服务生按先来后到的顺序服务完一位哲学家后才能服务下一为哲学家。这时，如果正在被服务生服务的哲学家两边的餐叉都没有被占用的话，这位哲学家就一定会得到这两个餐叉，而不会被别的哲学家抢走，从而避免死锁。

这种解法的特点是简单但并发度很低。举个例子，假设现在2号哲学家已经在就餐了，他占用了2号和3号餐叉，这时1号哲学家叫了服务生，服务生给了1号哲学家1号餐叉，随后发现2号餐叉正在被占用，则服务生必须等待2号哲学家就餐结束才能把2号餐叉给1号哲学家。因为服务生对1号哲学家的服务还没有结束，所以这时有其他哲学家申请服务的时候服务生无法响应，造成整个系统都阻塞，知道2号哲学家就餐结束。

python 风格伪代码：

thread_philosophers():
    lock(mutex_waiter)    #如果请求失败将在这里阻塞
    wait(sem_firstFork)
    wait(sem_secondFork)
    unlock(mutex_waiter)

    eating()

    post(second_fork)
    post(first_fork)

    thread_exit()

资源分级算法

另一个简单的解法是为资源分配一个偏序或者分级的关系，并约定所有资源都按照这种顺序获取，按相反顺序释放。对应在哲学家就餐问题中就是为各个餐叉设置 1 - 2 - 3 - 4 - 5 的序号，每一个哲学家总是先拿起左右两边编号较低的餐叉，再拿编号较高的。用完餐叉后，他总是先放下编号较高的餐叉，再放下编号较低的。在这种情况下，1-4号哲学家都是左边的餐叉序号小，而5号哲学家是右边的餐叉序号小，当1-4号哲学家同时拿起他们手边编号较低的餐叉即1-4号餐叉时，只有编号最高的5号餐叉留在桌上，5号哲学家先申请序号较小的1号，发现已经被拿走，所以他就只能等待。而剩下的那支5号餐叉被4号哲学家成功获得。当4号哲学家吃完后，他会先放下编号最高的餐叉，再放下编号较低的餐叉，从而使得3号哲学家成功获得他所需的第二支餐叉，以此类推，整个系统不会发生死锁。

python 风格伪代码：

thread_philosophers(num_fork1, num_fork2):
    if num_fork1 < num_fork2:
        sem_firstFork = num_fork1
        sem_secondFork = num_fork2
    else:
        sem_firstFork = num_fork2
        sem_secondFork = num_fork1

    wait(sem_firstFork)
    wait(sem_secondFork)

    eating()

    post(sem_secondFork)
    post(sem_firstFork)

    thread_exit()

这种解法的特点是需要对资源进行分级，相对较实用。但同时在很多情况下，我们是无法得知系统运行所需要的资源有哪些，以及算法对于请求、释放的顺序的限制，使得某些情况下这种方法并不适用。

Chandy/Misra 算法

1984年，K. Mani Chandy和J. Misra提出了哲学家就餐问题的另一个解法，允许任意的用户（编号P1, ..., Pn）争用任意数量的资源。与资源分级解法不同的是，这里编号可以是任意的。这个解法允许很大的并行性，适用于任意大的问题。

我的实现

我在这里实现了 服务生算法 和 资源分级算法 ，以及一个用于演示死锁的错误方法。

build

cd Dining-philosophers-problem/
make

run

./main               #错误解法，将出现死锁

./main --correct1    #执行服务生解法

./main --correct2    #执行资源分级解法