问题描述

有五个哲学家围坐在桌旁，每个人前面有一盘意面。相邻的哲学家之间有一把叉子。

每个哲学家轮流地思考和吃饭。当一个哲学家同时拥有左右叉子时，才能用餐。每把叉子只能够被一个哲学家拿起。当用餐完毕后，哲学家会放下左右两把叉子，这时其他哲学家有机会拿到。一个哲学家可以拿起手边可用的叉子，但是只有当拿到两把叉子时才能用餐。

用餐不受意面数量或者胃空间的限制，假设食品是无限量供应，需求也是无限的。

设计一个规则，让哲学家不会饿着。比如每个人都可以不停的轮流吃饭和思考，假设哲学家不知道其他人会在什么时候吃饭或者思考。

哲学家们按顺时针方向分别编号为 0~4。如下图所示：

QQ20200405-160702@2x.png

要求实现方法 void wantsToEat(philosopher, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork)，已知如下条件：

philosopher 表示哲学家编号。
pickLeftFork 表示拿起左手边叉子，pickRightFork 表示拿起右手边叉子。
eat 表示用餐。
putLeftFork 表示放下左手边叉子，putRightFork 表示放下右手边叉子。
假设哲学家们只要不进餐的时候就在思考。

五个线程，每个分别对应一个哲学家，会同时使用同一个实例对象来模拟整个过程。wantsToEat 会被一个哲学家调用多次。

想看英文描述的戳这里。

解题思路

经典的哲学家用餐问题，主要考察多线程中资源竞争问题。

由于有 5 个哲学家，5 把叉子。如果哲学家们同时拿起左手边/右手边的叉子，那么每个人都只能获得一把叉子，都在等待其他人放下叉子。因此谁都吃不了饭，导致死锁。

对共享的资源，需要采取一些机制来进行保护性的访问。

解决方法有如下几种：

一次只允许一个哲学家拿叉子

将拿叉子的动作进行限制，当第一个哲学家拿叉子的时候，其他人不能拿，因此，他可以拿起左右两个叉子，满足用餐条件。

Java 代码如下：

Semaphore forks[] = { new Semaphore(1), new Semaphore(1), new Semaphore(1), new Semaphore(1), new Semaphore(1)};

// 拿叉限制
Semaphore pick = new Semaphore(1);

public void wantsToEat(int philosopher,
                           Runnable pickLeftFork,
                           Runnable pickRightFork,
                           Runnable eat,
                           Runnable putLeftFork,
                           Runnable putRightFork) throws InterruptedException {

    Semaphore left = forks[philosopher];
    Semaphore right = forks[(philosopher + 4) % 5];

    // 拿叉时锁住，这样其中一个人可以同时拿起左右叉
    pick.acquire();
    
    // 左手叉
    left.acquire();
    pickLeftFork.run();

    // 右手叉
    right.acquire();
    pickRightFork.run();

    eat.run();
    pick.release();

    // 释放
    // 左手叉
    putLeftFork.run();
    left.release();

    // 右手叉
    putRightFork.run();
    right.release();        
}

同时只允许四个哲学家进餐

因为有 5 把叉子，只有 4 个人用餐。这样就可以保证始终有一个哲学家可以拿到 2 把叉子，满足用餐条件。


Semaphore forks[] = { new Semaphore(1), new Semaphore(1), new Semaphore(1), new Semaphore(1), new Semaphore(1)};

// 最多允许 4 人用餐
Semaphore mostEat = new Semaphore(4);

// 同时最多 4 个人拿起叉子，96.23% 
public void wantsToEat4(int philosopher,
                       Runnable pickLeftFork,
                       Runnable pickRightFork,
                       Runnable eat,
                       Runnable putLeftFork,
                       Runnable putRightFork) throws InterruptedException {
    
  Semaphore left = forks[philosopher];
  Semaphore right = forks[(philosopher + 4) % 5];
  
  mostEat.acquire();

  left.acquire();
  pickLeftFork.run();

  right.acquire();
  pickRightFork.run();

  eat.run();

  putLeftFork.run();
  left.release();

  putRightFork.run();
  right.release();

  mostEat.release();
}

偶数号哲学家先拿左手边叉子，再拿右手边叉子；奇数号哲学家先拿右手边叉子，再拿左手边叉子

让竞争范围缩小，3 号和 2 号哲学家竞争，1 号和 0 号哲学家竞争。4 号哲学家能拿到两个叉子，从而可以进餐。

Semaphore forks[] = { new Semaphore(1), new Semaphore(1), new Semaphore(1), new Semaphore(1), new Semaphore(1)};

// 96.23% 
public void wantsToEat(int philosopher,
                       Runnable pickLeftFork,
                       Runnable pickRightFork,
                       Runnable eat,
                       Runnable putLeftFork,
                       Runnable putRightFork) throws InterruptedException {
    Semaphore left = forks[philosopher];
    Semaphore right = forks[(philosopher + 4) % 5];
                
    // 偶数先左后右
    if (philosopher % 2 == 0) {
        // 先左后右
        left.acquire();
        pickLeftFork.run();

        right.acquire();
        pickRightFork.run();

    } else {
        // 奇数先右后左
        right.acquire();
        pickRightFork.run();

        left.acquire();
        pickLeftFork.run();
    }

    eat.run();

    putLeftFork.run();
    left.release();

    putRightFork.run();
    right.release();
}

参考资料：https://blog.csdn.net/qq_28602957/article/details/53538329