Rabbet

悦已者

0%

哲学家就餐问题

发表于 更新于 分类于
本文字数： 3.4k 阅读时长 ≈ 3 分钟
简单实现

问题描述

  哲学家就餐问题可以这样表述，假设有五位哲学家围坐在一张圆形餐桌旁，做以下两件事情之一：吃饭，或者思考。吃东西的时候，他们就停止思考，思考的时候也停止吃东西。餐桌中间有一大碗意大利面，每位哲学家之间各有一只餐叉。因为用一只餐叉很难吃到意大利面，所以假设哲学家必须用两只餐叉吃东西。他们只能使用自己左右手边的那两只餐叉。哲学家就餐问题有时也用米饭和五根筷子而不是意大利面和餐叉来描述，因为吃米饭必须用两根筷子。这个问题不考虑意大利面有多少，也不考虑哲学家的胃有多大。假设两者都是无限大。
  问题在于如何设计一套规则，使得在哲学家们在完全不交谈，也就是无法知道其他人可能在什么时候要吃饭或者思考的情况下，可以在这两种状态下永远交替下去。
哲学家就餐——流程：
  1. 先拿起左手的筷子
  2. 再拿起右手的筷子
  3. 若筷子正好被其它人所使用，则需要等待其它人使用结束
  4. 吃完后，需将筷子放加原位
如下图所示：
avatar

问题分析

  系统中有五位哲学家，这五位哲学家与左右邻居对其中间筷子的访问是互斥的关系。这里的哲学家需要同时持有两个临界资源才能开始吃饭，如果解决不当就会导致死锁情况：所有哲学家都饿了，每个哲学家都是左手拿一个筷子，一直在等右手的筷子。(亦可相反)。
  主要是使用锁对两个筷子进行限制，从而避免了死锁情况的发生。

具体实现

原语代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
semaphore chopstick[5] = {1, 1, 1, 1, 1};
semaphore mutex = 1;
Pi() {                                // 哲学家i的进程
    while (1) {
        P(mutex);                     // 互斥地取筷子
        P(chopstick[i]);              // 拿左
        P(chopstick[(i + 1) % 5]);    // 拿右
        V(mutex);                     // 已经取好筷子
        吃饭
        V(chopstick[i]);              // 放左
        V(chopstick[(i + 1) % 5]);    // 放右
        思考
    }
}

C++ 代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include <iostream>
#include <mutex>
#include <thread>

using namespace std;

int main()
{
    const int no_of_philosophers = 5;
    
    struct Chopstics
    {
    public:
        Chopstics(){;}
        std::mutex mu;
    };
    
    auto eat = [](Chopstics &left_chopstics, Chopstics& right_chopstics, int philosopher_number) {
        
        std::unique_lock<std::mutex> llock(left_chopstics.mu);
        std::unique_lock<std::mutex> rlock(right_chopstics.mu);
        
        cout << "Philosopher " << philosopher_number << " is eating" << endl;
        
        std::chrono::milliseconds timeout(1500);
        std::this_thread::sleep_for(timeout);
        
        cout << "Philosopher " << philosopher_number << " has finished eating" << endl;
    };
    
    //create chopstics
    Chopstics chp[no_of_philosophers];
    
    //create philosophers
    std::thread philosopher[no_of_philosophers];
    
    //Philosophers Start reading
    cout << "Philosopher " << (0+1) << " is reading.." << endl;
    philosopher[0] = std::thread(eat, std::ref(chp[0]), std::ref(chp[no_of_philosophers-1]), (0+1));
    
    for(int i = 1; i < no_of_philosophers; ++i) {
        cout << "Philosopher " << (i+1) << " is reading.." << endl;
        philosopher[i] = std::thread(eat, std::ref(chp[i]), std::ref(chp[i-1]), (i+1));
    }
    
    for(auto &ph: philosopher) {
        ph.join();
    }
    
    return 0;
}

解法推广

上面提供的仅仅是一种根据原语改编的基本解法，对于哲学家就餐问题，存在多种更加合理且高效的解法。

服务生解法

  一个简单的解法就是引入服务生，哲学家必须经过他的允许才能拿起餐叉。因为服务生知道哪只餐叉正在使用，所以他能够作出判断避免死锁。
  对于此解法的简单演示，假设哲学家依次标号为A至E。如果A和C在吃东西，则有四只餐叉在使用中。B坐在A和C之间，所以两只餐叉都无法使用，而D和E之间有一只空余的餐叉。假设这时D想要吃东西。如果他拿起了第五只餐叉，就有可能发生死锁。相反，如果他征求服务生同意，服务生会让他等待。这样，我们就能保证下次当两把餐叉空余出来时，一定有一位哲学家可以成功的得到一对餐叉，从而避免了死锁

资源分级解法

  另一个简单的解法是为资源（这里是餐叉）分配一个偏序或者分级的关系，并约定所有资源都按照这种顺序获取，按相反顺序释放，而且保证不会有两个无关资源同时被同一项工作所需要。在哲学家就餐问题中，资源（餐叉）按照某种规则编号为1至5，每一个工作单元（哲学家）总是先拿起左右两边编号较低的餐叉，再拿编号较高的。用完餐叉后，他总是先放下编号较高的餐叉，再放下编号较低的。在这种情况下，当四位哲学家同时拿起他们手边编号较低的餐叉时，只有编号最高的餐叉留在桌上，从而第五位哲学家就不能使用任何一只餐叉了。而且，只有一位哲学家能使用最高编号的餐叉，所以他能使用两只餐叉用餐。当他吃完后，他会先放下编号最高的餐叉，再放下编号较低的餐叉，从而让另一位哲学家拿起后边的这只开始吃东西。
  尽管资源分级能避免死锁，但这种策略并不总是实用的，特别是当所需资源的列表并不是事先知道的时候。例如，假设一个工作单元拿着资源3和5，并决定需要资源2，则必须先要释放5，之后释放3，才能得到2，之后必须重新按顺序获取3和5。对需要访问大量数据库记录的计算机程序来说，如果需要先释放高编号的记录才能访问新的记录，那么运行效率就不会高，因此这种方法在这里并不实用。

Chandy/Misra解法

允许任意的用户争用任意数量的资源。与资源分级解法不同的是，这里编号可以是任意的
   1. 把餐叉凑成对，让要吃的人先吃，没餐叉的人得到一张换餐叉券
   2. 饿了，把换餐叉券交给有餐叉的人，有餐叉的人吃饱了会把餐叉交给有券的人。有了券的人不会再得到第二张券
   3. 保证有餐叉的都有得吃
这个解法允许很大的并行性，适用于任意大的问题