哲学家就餐问题

如果五位哲学家同时饿了,同时拿起左手边的那根筷子,你就会发现他们想去拿右边的筷子的时候,都没有办法拿起右边的筷子,因为右边那根筷子都被旁边的哲学家拿走了,所有的哲学家都处于等待状态而没有办法继续下去。

如果这五位哲学家同时发现没有右边的筷子可用,他们同时放下左手的筷子,冥想5分钟再同时就餐,你会发现程序貌似还在进行,但是哲学家依然还是没有办法就餐,这种现象叫做死锁。在分布式一致性算法中在选主的时候也会有类似的现象,有些实现是通过随机休眠一定的时间,避免各个节点同时请求选主来避免。

死锁的四个条件:

互斥 资源具有排他性

禁止抢占 系统资源不能被强制从一个线程中退出

持有等待 一个线程在等待时持有并发资源

循环依赖 一系列线程互相持有其他进程所需要的资源

解决死锁的问题就是破坏死锁形成的四个条件之一,一般禁止抢占和互斥是必须的条件,所以其它两个条件是我们重点突破的点。

限制最多允许四位哲学家同时就餐,就可以避免循环依赖的条件。针对限制特定数量资源的情况,最好用的并发原语就是信号量(Semaphore)

我们把这个信号量初始值设置为4,代表最多允许同时4位哲学家就餐。把这个信号量传给哲学家对象,哲学家想就餐时就请求这个信号量,如果能得到一个许可,就可以就餐,吃完把许可释放回给信号量。

为资源(这里是筷子)分配一个偏序或者分级的关系,并约定所有资源都按照这种顺序获取,按相反顺序释放,而且保证不会有两个无关资源同时被同一项工作所需要。

由韩非子负责分配筷子,这样我们就可以将拿左手筷子和右手筷子看成一个原子操作,要么拿到筷子,要么等待,就可以破坏死锁的第二个条件(持有和等待