面试官：这个经典的并发问题用 Go 语言如何实现？

前言：由于 LeetCode Concurrency(并发) 还没有 Go 语言版本，我先自行用 Go 语言来解题。为了能在 LeetCode 以外的平台获得讨论，所以我打算逐渐把自己的解题思路写下。

本题 LeetCode 链接

https://leetcode.com/problems/the-dining-philosophers/

本题题目

「哲学家吃饭问题」是一个操作系统中的经典问题，所以抽象题干我就不再赘述，直接说实作要求。

The philosophers' ids are numbered from 0 to 4 in a clockwise order. Implement the function void wantsToEat(philosopher, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork) where:

有几位哲学家，他们的 ID 顺时针由 0~4，实作一个函式 void wantsToEat(philosopher, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork)，其中...

philosopher is the id of the philosopher who wants to eat.

变量 philosopher 代表想要吃饭的哲学家的 ID。

pickLeftFork and pickRightFork are functions you can call to pick the corresponding forks of that philosopher.

变量 pickLeftFork and pickRightFork 是函式，你必须调用他们来使哲学家拿起对应的叉子。

eat is a function you can call to let the philosopher eat once he has picked both forks.

当哲学家拿起两只叉子后，你必须调用 eat 这个函式让哲学家吃一次。

putLeftFork and pickRightFork are functions you can call to put down the corresponding forks of that philosopher.

变量 putLeftFork and pickRightFork 是函式，你必须调用他们来使哲学家放下手中的叉子。

The philosophers are assumed to be thinking as long as they are not asking to eat (the function is not being called with their number).

假设哲学家们都会思考很久，中间都不会要求吃东西（调用函式 thinking() 不必使用哲学家们的 ID）

Five threads, each representing a philosopher, will simultaneously use one object of your class to simulate the process. It is possible that the function will be called for the same philosopher more than once, even before the last call ends.

五个执行绪，每一个执行绪代表都一个哲学家，用一个类(在 Go 语言是 struct)模拟这个 process。这个函式可能被同一个哲学家调用多次，甚至在最后一次调用结束前的途中都有可能。

「叉子」与「筷子」

最早课本里都是说「叉子」。但我大学上 OS 的时候老师就提过一个疑问：「用叉子吃义大利面，一只就够了，没必要用到两只吧？所以，改成用筷子是不是更合理一点？但没办法，谁叫这门学问是西方先发明的？我们就当作筷子吧」。
于是，本文也决定照改，以下都用「筷子」代替「叉子」。

本题考核难点？「拿得起放不下」造成死结、「无限轮回」造成活结饥饿至死

在过去的 LeetCode Concurrency 详解中，我提到过很多次：

goroutine 若不刻意控制，将无法保证执行的先后顺序，因此本题就是要考核对 goroutine 顺序控制的能力。

但前面几题的解法，大多是把判断责任中心化，方便控管顺序。这次，与前面几题不同的是，这一题要求把判断责任分散到每一位哲学家 thread 身上，哲学家彼此之间并不沟通，因此很容易发生资源互卡，也就是 deadlock。本文所示范的 channel 使用方法已经完全避免了死结(deadlock)。但这样就没问题了吗？不，还有可能发生活结(livelock)。

这边我为了示范 goroutine，先用最笨的碰运气解法，也就是不刻意做任何资源配置，要在运气很坏的情况下才会遇上 livelock。什么是「运气很坏的情况」？

就是所有哲学家刚好在同一时间拿起同一边的叉子。但实际上，由于我给每位哲学家一个随机的思考时间 50mS（如下列代码），碰撞的机会是(1/50)^5，所以绝大部分情况下不会发生 livelock。

func Think() {
 Random := func(max int) int {
  rand.Seed(time.Now().Unix())
  return rand.Int() % (max + 1)
 }
 <-time.After(time.Millisecond * time.Duration(Random(50)))
}

Wiki 上有介绍不需要碰运气，保证不会让 thread 饥饿致死的演算法，但我自己也没搞懂，请容我日后再介绍。

解法与思路：

1. 所用 Channel 型态与定位？

本题采用 5 个 buffered channel，分别代表 5 支筷子

type DiningPhilosophers struct {
 wg                     *sync.WaitGroup
 streamForks            [5]chan interface{}
 missingDoubleForkTimes int
}

// Channel 初始化
for i := range diningPhilosophers.streamForks {
 diningPhilosophers.streamForks[i] = make(chan interface{}, 1)
}

初始化

// 叫所有哲学家开始动作
start := time.Now()
for i := range diningPhilosophers.streamForks {
 diningPhilosophers.wg.Add(1)
 go diningPhilosophers.WantToEat(i, PickLeftFork, PickRightFork, Eat, PutLeftFork, PutRightFork)
}

这边开始计时后，是一个 foreach。

老方法，用 sync.WaitGroup 同步 5 个哲学家 goroutine 结束时间。
给每一位哲学家起一个「WantToEat」的 goroutine，告诉他 i 你是几号？又给入「PickLeftFork, PickRightFork, Eat, PutLeftFork, PutRightFork」五个函式的的 function reference。

2. 五个 goroutine 之间，如何交接棒？

没有交接棒问题，每位哲学家就凭运气去抢左右边的两只筷子。
要注意的只有三件事情：

1. 无法同时抢到两只筷子的哲学家，必须先放弃到手的一支筷子。
2. 已经同时抢到两只筷子的哲学家，吃完就必须退出餐桌。
3. 还没吃到的哲学家，可以无限次抢。

自循环 & 外部启动注意事项

这次解题没有实作这些协调机制，5 个 goroutine 只靠前述的三条规范野蛮生长。

实作前述的三条规范的 WantToEat()

• 本质上就是代表「还没吃到的哲学家，可以无限次抢」的无限回圈。
• 「已经同时抢到两只筷子的哲学家，吃完就必须退出餐桌」是此回圈的结束条件。
• 「无法同时抢到两只筷子的哲学家，必须先放弃到手的一支筷子。」是此回圈其中一个分支。

有一行「return //吃饱离开」，整个流程最终目的就是要走到这一行。

func (this *DiningPhilosophers) WantToEat(philosopher int, pickLeftFork func(int), pickRightFork func(int), eat func(int), putLeftFork func(int), putRightFork func(int)) {
 defer this.wg.Done()

 var leftNum = (philosopher + 4) % 5  //取得该哲学家左边的号码
 var rightNum = (philosopher + 6) % 5 //取得该哲学家右边的号码

 for {
  select {
  case this.streamForks[leftNum] <- philosopher: //尝试拿起左边筷子
   PickLeftFork(philosopher) //成功拿起左边筷子
   select {
   case this.streamForks[rightNum] <- philosopher: //尝试拿起右边筷子
    PickRightFork(philosopher)  //成功拿起又边筷子
    Eat(philosopher)            //左右边都拿到了，开始吃
    <-this.streamForks[leftNum] //吃完了，放下左边筷子
    PutLeftFork(philosopher)
    <-this.streamForks[rightNum] //吃完了，放下右边筷子
    PutRightFork(philosopher)
    return //吃饱离开
   default: //无法拿起右边筷子
    fmt.Printf("Philosopher %d can't pick fork %d.\n", philosopher, rightNum)
    <-this.streamForks[leftNum] //把已经拿起来的左边筷子释放出去
    PutLeftFork(philosopher)
   }
  default: //无法拿起左边筷子
   fmt.Printf("Philosopher %d can't pick fork %d.\n", philosopher, leftNum)
  }
  this.missingDoubleForkTimes++
  Think()
 }
}

这边对于每一只筷子的具体表现就是一个 buffered channel，回圈流程如下：

1. 先尝试把自己的号码塞入左边的 buffered channel

• 成功了，就是抢到一只筷子，往下。
• 失败了，跳到「default: //无法拿起左边筷子」，思考一下，然后从头开始。

2. 再尝试把自己的号码塞入右边的 buffered channel

• 成功了，就是抢到两只筷子，开始吃，吃饱离开，退出餐桌。
• 失败了，跳到「default: //无法拿起右边筷子」，把已经抢到的左边筷子还回去，思考一下，然后从头开始。

在 console 输出，可以看到代表每一位哲学家的 goroutine 详细动作过程，错过筷子次数并不多，大部分执行结果的错过次数在 3~5 次（点击以下的「完整解题代码」就能体验）。

完整解题代码：

https://play.studygolang.com/p/neTH25E8ayX

示意图：

最后附上本文作者的求职信息：

「座标广东中山，台湾师范大学机电硕士，三年开发经验，有Windows应用、单片机、AI/ML/数据分析、Go后端相关经验，懂 Go/C#/C++/Python，Github:mosdeo」

可以通过 wx 联系他：LinKaoYuan_WeChatID