传送门：

进程同步与互斥——信号量（实现锁、条件变量）

进程同步与互斥——哲学家就餐问题源码实现（dining philosopher’s problem）

进程同步与互斥——读者/写者问题源码实现（reader-writer lock）

进程同步与互斥——生产者/消费者（有界缓冲区）问题源码实现

进程同步与互斥——吸烟者问题源码实现（cigarette smoker’s problem）

进程同步与互斥——理发师问题源码实现（sleeping barber problem）

进程同步与互斥——相关问题汇总（源码+伪代码）

哲学家就餐问题

哲学家就餐问题（dining philosopher’s problem）是一个著名的并发问题，它由Dijkstra提出来并解决。这个问题之所以出名，是因为它很有趣，引人入胜，但其实用性却不强。可是，它的名气让我们在这里必须讲。实际上，你可能会在面试中遇到这一问题，假如老师没有提过，导致你们没有通过面试，你们会责怪操作系统老师的。因此，我们这里会讨论这一问题。假如你们因为这个问题得到工作，可以向操作系统老师发感谢信，或者发一些股票期权。

这个问题的基本情况是：假定有5位“哲学家”围着一个圆桌。每两位哲学家之间有一把餐叉（一共5把）。哲学家有时要思考一会，不需要餐叉；有时又要就餐。而一位哲学家只有同时拿到了左手边和右手边的两把餐叉，才能吃到东西。关于餐叉的竞争以及随之而来的同步问题，就是我们在并发编程中研究它的原因。

下面是每个哲学家的基本循环：

while(1)
{
	think();
	getforks();
	eat();
	putfork();
}

关键的挑战就是如何实现getforks()和putforks()函数，保证没有死锁，没有哲学家饿死，并且并发度更高（尽可能让更多哲学家同时吃东西）。

根据Downey的解决方案，我们会用一些辅助函数，帮助构建解决方案。它们是：

int left(int p)  { return p; }
int right(int p) { return (p + 1) % 5;}

如果哲学家p希望用左手边的叉子，他们就调用left§。类似地，右手边的叉子就用right§。模运算解决了最后一个哲学家（p = 4）右手边叉子的编号问题，就是餐叉0。

我们需要一些信号量来解决这个问题。假设需要5个，每个餐叉一个：sem_t forks[5]。

有问题的解决方案

我们开始第一次尝试。假设我们把每个信号量（在fork数组中）都用1初始化。同时假设每个哲学家知道自己的编号（p）。我们可以写出getforks()和putforks()函数。

void getforks()
{
	sem_wait(forks[left(p)]);
	sem_wait(forks[right(p)]);
}

void putforks()
{
	sem_post(forks[left(p)]);
	sem_post(forks[right(p)]);
}

这个（有问题的）解决方案背后的思路如下。为了拿到餐叉，我们依次获取每把餐叉的锁——先是左手边的，然后是右手边的。结束就餐时，释放掉锁。很简单，不是吗？但是，在这个例子中，简单是有问题的。你能看到问题吗？想一想。问题是死锁（deadlock）。假设每个哲学家都拿到了左手边的餐叉，他们每个都会阻塞住，并且一直等待另一个餐叉。具体来说，哲学家0拿到了餐叉0，哲学家1拿到了餐叉1，哲学家2拿到餐叉2，哲学家3拿到餐叉3，哲学家4拿到餐叉4。所有的餐叉都被占有了，所有的哲学家都阻塞着，并且等待另一个哲学家占有的餐叉。我们在后续章节会深入学习死锁，这里只要知道这个方案行不通就可以了。

一种方案：破除依赖

解决上述问题最简单的方法，就是修改某个或者某些哲学家的取餐叉顺序。事实上，Dijkstra自己也是这样解决的。具体来说，假定哲学家4（编写最大的一个）取餐叉的顺序不同。相应的代码如下：

void getforks()
{
	if(p == 4)
	{
		sem_wait(forks[right(p)]);		
		sem_wait(forks[left(p)]);	
	}
	else
	{
		sem_wait(forks[left(p)]);
		sem_wait(forks[right(p)]);		
	}
}

因为最后一个哲学家会尝试先拿右手边的餐叉，然后拿左手边，所以不会出现每个哲学家都拿着一个餐叉，卡住等待另一个的情况，等待循环被打破了。想想这个方案的后果，让你自己相信它有效。

源码实现：

#include <semaphore.h>
#include <unistd.h>
#include <iostream>

using namespace std;

sem_t forks[5];

void think(int i)
{
    cout << "第" << i << "个哲学家正在思考" << endl;
    /* sleep(1); */
}

void eat(int i)
{
    cout << "第" << i << "个哲学家正在吃东西" << endl;
    /* sleep(2); */
}

int left(int p) {return p;}
int right(int p) {return (p + 1) % 5;}

void getforks(int i)
{
    sem_wait(&forks[left(i)]);
    cout << "第" << i << "个哲学家拿起左筷子" << endl;
    sem_wait(&forks[right(i)]);
    cout << "第" << i << "个哲学家拿起右筷子" << endl;
}

void putforks(int i)
{
    sem_post(&forks[left(i)]);
    cout << "第" << i << "个哲学家放下左筷子" << endl;
    sem_post(&forks[right(i)]);
    cout << "第" << i << "个哲学家放下右筷子" << endl;
}

void* philosopher_process_0(void* arg)
{
    int id = *(int*)arg;
    think(id);
    getforks(id);
    eat(id);
    putforks(id);
    pthread_exit(0);
}

void* philosopher_process_1(void* arg)
{
    int id = *(int*)arg;
    think(id);
    getforks(id);
    eat(id);
    putforks(id);
    pthread_exit(0);
}

void* philosopher_process_2(void* arg)
{
    int id = *(int*)arg;
    think(id);
    getforks(id);
    eat(id);
    putforks(id);
    pthread_exit(0);
}

void* philosopher_process_3(void* arg)
{
    int id = *(int*)arg;
    think(id);
    getforks(id);
    eat(id);
    putforks(id);
    pthread_exit(0);
}

void* philosopher_process_4(void* arg)
{
    int id = *(int*)arg;
    think(id);
    getforks(id);
    eat(id);
    putforks(id);
    pthread_exit(0);
}

int main()
{
    for(int i = 0; i < 5; i++)
    {
        sem_init(&forks[i], 0, 1);
    }

    pthread_t philosopher[5];

    int id[5] = {0, 1, 2, 3, 4};
    
    pthread_create(&philosopher[0], nullptr, philosopher_process_0, &id[0]);
    pthread_create(&philosopher[1], nullptr, philosopher_process_1, &id[1]);
    pthread_create(&philosopher[2], nullptr, philosopher_process_2, &id[2]);
    pthread_create(&philosopher[3], nullptr, philosopher_process_3, &id[3]);
    pthread_create(&philosopher[4], nullptr, philosopher_process_4, &id[4]);

    pthread_join(philosopher[0], nullptr);
    pthread_join(philosopher[1], nullptr);
    pthread_join(philosopher[2], nullptr);
    pthread_join(philosopher[3], nullptr);
    pthread_join(philosopher[4], nullptr);

    return 0;
}

触发死锁是概率事件，实际运行结果：

第4个哲学家正在思考
第4个哲学家拿起左筷子
第4个哲学家拿起右筷子
第4个哲学家正在吃东西
第4个哲学家放下左筷子
第4个哲学家放下右筷子
第3个哲学家正在思考
第3个哲学家拿起左筷子
第3个哲学家拿起右筷子
第3个哲学家正在吃东西
第3个哲学家放下左筷子
第3个哲学家放下右筷子
第2个哲学家正在思考
第2个哲学家拿起左筷子
第2个哲学家拿起右筷子
第2个哲学家正在吃东西
第2个哲学家放下左筷子
第2个哲学家放下右筷子
第1个哲学家正在思考
第1个哲学家拿起左筷子
第1个哲学家拿起右筷子
第1个哲学家正在吃东西
第1个哲学家放下左筷子
第1个哲学家放下右筷子
第0个哲学家正在思考
第0个哲学家拿起左筷子
第0个哲学家拿起右筷子
第0个哲学家正在吃东西
第0个哲学家放下左筷子
第0个哲学家放下右筷子

更多推荐

进程同步与互斥——哲学家就餐问题源码实现（dining philosopher’s problem）