经典的进程同步问题—–哲学家进餐问题详解

​ 本文和接下来几篇博文是对上篇文章（进程同步机制）的一次实践，通过具体的例子来加深理论的理解，会用三个经典的进程同步问题来进行讲解，并且会配有伪代码和Java实践（使用多线程模拟），深入的进行讲解。

​ 进程同步问题是一个非常重要且相当有趣的问题，本文我们对其中比较有名的哲学家进餐问题来进行探讨。哲学家进餐问题是诸进程间竞争临界资源而导致死锁的典型例子，具有很大的代表性，因此在这里我们也对其进行一些分析。

​ 值得一提的是，哲学家进餐问题又双叒叕是我们的老熟人迪杰斯特拉提出并解决的，让我们一起来看下吧。

1.问题描述

​ 有五个哲学家围在一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和物质筷子，他们的生活方式是交替的进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两支筷子时才能进餐。进餐完毕后，放下筷子继续思考。

​ 我们可以从上面的题目中得出，筷子是临界资源，同一根筷子同一时刻只能有一个哲学家可以拿到。

2.问题分析

​ 由问题描述我们可以知道，一共有五个哲学家，也就是五个进程；五只筷子，也就是五个临界资源；因为哲学家想要进餐，必须要同时获得左边和右边的筷子，这就是要同时进入两个临界区（使用临界资源），才可以进餐。

​ 因为是五只筷子为临界资源，因此设置五个信号量即可。

4.一个错误例子

​ 首先我们根据我们之前学习的知识来解决问题，根据上面的分析，我们先给出伪代码：

semaphore mutex[5] = { 
   1,1,1,1,1}; //初始化信号量 void philosopher(int i){ 
    do { 
    //thinking //思考 P(mutex[i]);//判断哲学家左边的筷子是否可用 P(mutex[(i+1)%5]);//判断哲学家右边的筷子是否可用 //... //eat //进餐 //... V(mutex[i]);//退出临界区，允许别的进程操作缓冲池 V(mutex[(i+1)%5]);//缓冲池中非空的缓冲区数量加1，可以唤醒等待的消费者进程 }while(true); } 

​ 我们来分析下上面的代码，首先我们从一个哲学家的角度来看问题，程序似乎是没有问题的，申请到左右两支筷子后，然后开始进餐。但是如果考虑到并发问题，五个哲学家同时拿起了左边的筷子，此时，五只筷子立刻都被占用了，没有可用的筷子了，当所有的哲学家再想拿起右边筷子的时候，因为临界资源不足，只能将自身阻塞，而所有的哲学家全部都会阻塞，并且不会释放自己手中拿着的左边的筷子，因此就会一直处于阻塞状态，无法进行进餐并思考。

​ 因为，为了解决五个哲学家争用的资源的问题，我们可以采用以下几种解决方法：

1. 至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用餐完毕后能释放他占用的筷子，从而使别的哲学家能够进餐；
2. 仅当哲学家的左、右两支筷子可用时，才允许他拿起筷子；
3. 规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反。

​ 下面我们对每种方法给出哲学家进程的伪代码。

5.解决哲学家进餐问题—方法一

​ 对于方法一，至多只允许有四位哲学家同时去拿左边的筷子，我们可以简单的通过增加一个信号量实现，通过这个信号量限定哲学家并发去进餐的数量。

semaphore mutex[5] = { 
   1,1,1,1,1}; //初始化信号量 semaphore count = 4; //控制最多允许四位哲学家同时进餐 void philosopher(int i){ 
    do { 
    //thinking //思考 p(count); //判断是否超过四人准备进餐 P(mutex[i]); //判断缓冲池中是否仍有空闲的缓冲区 P(mutex[(i+1)%5]);//判断是否可以进入临界区（操作缓冲池） //... //eat //进餐 //... V(mutex[i]);//退出临界区，允许别的进程操作缓冲池 V(mutex[(i+1)%5]);//缓冲池中非空的缓冲区数量加1，可以唤醒等待的消费者进程 V(count);//用餐完毕，别的哲学家可以开始进餐 }while(true); } 

6.解决哲学家进餐问题—方法二

​ 第二种方法，也就是使用AND型信号量，同时对哲学家左右两边的筷子同时申请。下面是伪代码：

semaphore mutex[5] = { 
   1,1,1,1,1}; //初始化信号量 void philosopher(int i){ 
    do { 
    //thinking //思考 Swait(mutex[i], mutex[(i+1)%5]);//判断哲学家左边和右边的筷子是否同时可用 //... //eat  //... Ssignal(mutex[i], mutex[(i+1)%5]);//进餐完毕，释放哲学家占有的筷子 }while(true); } 

​ 对应的AND型信号量的实现可以参看我的另一篇博文。

7.解决哲学家进餐问题—方法三

​ 对于第三种，需要在代码中添加个判断，来决定获取左、右筷子的顺序，其伪代码如下：

semaphore mutex[5] = { 
   1,1,1,1,1}; //初始化信号量 void philosopher(int i){ 
    do { 
    //thinking  if(i%2 == 1){ 
    P(mutex[i]);//判断哲学家左边的筷子是否可用 P(mutex[(i+1)%5]);//判断哲学家右边的筷子是否可用 }else{ 
    P(mutex[(i+1)%5]);//判断哲学家右边的筷子是否可用 P(mutex[i]);//判断哲学家左边的筷子是否可用 } //... //eat //... V(mutex[i]);//退出临界区，允许别的进程操作缓冲池 V(mutex[(i+1)%5]);//缓冲池中非空的缓冲区数量加1，可以唤醒等待的消费者进程 }while(true); } 

8.测试

​ 这里我们通过Java模拟实现哲学家进餐问题，这里我们使用方法一(其他几种方式只需修改对应哲学家线程中的代码即可)，下面是具体的代码：

import com.alibaba.fastjson.JSON; import lombok.extern.slf4j.Slf4j; import java.util.ArrayList; import java.util.List; import java.util.concurrent.Semaphore; / * 者削减进餐问题 */ @Slf4j public class PhilosophersTest { 
    static final Semaphore count = new Semaphore(4); static final Semaphore[] mutex = { 
   new Semaphore(1), new Semaphore(1), new Semaphore(1), new Semaphore(1), new Semaphore(1)}; static class Philosopher extends Thread { 
    Philosopher(String name) { 
    super.setName(name); } @Override public void run() { 
    do { 
    try { 
    count.acquire(); Integer i = Integer.parseInt(super.getName()); mutex[i].acquire(); mutex[(i + 1) % 5].acquire(); log.info("哲学家【{}】号吃了通心粉！", i); mutex[i].release(); mutex[(i + 1) % 5].release(); count.release(); Thread.sleep(5000); } catch (InterruptedException e) { 
    log.error("哲学家执行时产生异常！"); } } while (true); } } public static void main(String[] args) { 
    Philosopher p0 = new Philosopher("0"); Philosopher p1 = new Philosopher("1"); Philosopher p2 = new Philosopher("2"); Philosopher p3 = new Philosopher("3"); Philosopher p4 = new Philosopher("4"); p0.start(); p1.start(); p2.start(); p3.start(); p4.start(); } } 

​ 下图是代码的执行结果，这里的哲学家顺序进餐是因为哲学家每次进餐完毕后sleep了5S，如果想查看并发执行的情况，只需将sleep注释即可。

​ 又到了分隔线以下，本文到此就结束了，本文内容全部都是由博主自己进行整理并结合自身的理解进行总结，如果有什么错误，还请批评指正。

​ 本文的java代码都已通过测试，对其中有什么疑惑的，可以评论区留言，欢迎你的留言与讨论；另外原创不易，如果本文对你有所帮助，还请留下个赞，以表支持。

​ 如有兴趣，还可以查看我的其他几篇博客，都是OS的干货（目录），喜欢的话还请点赞、评论加关注^_。

参考文章列表：

1.进程同步机制—–为进程并发执行保驾护航

2.Java并发编程（JUC）模拟AND型信号量

3.Java并发编程（JUC）模拟信号量集

4.Java并发编程模拟管程（霍尔Hoare管程、汉森Hansan管程、MESA管程)

5.操作系统武功修炼心法

6.经典进程同步问题—-生产者-消费者问题详解

6.经典进程同步问题—-读者-写者问题详解