哲学家就餐问题

哲学家就餐问题的定义，选自Andrew S. Tanenbaum所著的Mordern Operating Systems（《现代操作系统》）第三版。作者在书中提供了解决方案。

1965年，Dijkstra提出并解决了一个同步问题，他称之为哲学家就餐问题。这个问题简单地描述如下：5位哲学家围坐在一张圆桌边。每位哲学家前面都放着一盘意大利面条。面条很滑，要用两个餐叉才吃得到。相邻两个盘子之间有一个餐叉。桌上的布局如下图所示。

哲学家就餐问题

假设哲学家的状态是吃面条和思考交替进行。如果哲学家饿了，就会尝试拿起他左边和右边的餐叉，一次只能拿一把。如果成功获得两把餐叉，他就吃一会意大利面，然后放下餐叉，继续思考。关键问题是：能否写一个程序，描述每位哲学家应该怎么做才一定不会卡壳？

我们可以等指定的餐叉可用时才去拿。不过，这样想显然是错误的。如果5位哲学家都同时拿起左边的餐叉，就没人能拿到右边的餐叉，这就出现了死锁。

我们可以修改一下程序，在拿起左边餐叉后，程序检查右边的餐叉是否可用。如果不可用，该哲学家就放下已拿起的左边餐叉，等待一段时间，再重复这一过程。虽然这个解法和上一个解法不同，但是好不到哪里去，也是错误的。如果很不巧，所有的哲学家都同时以该算法开始，拿起他们左边的餐叉，发现右边餐叉不可用，然后放下左边餐叉，等待一会，又同时拿起左边的餐叉……这样永无止尽。这种所有程序无限期不停运行却没有任何进展的情况，叫做饥饿（starvation）。

要实现既不会发生死锁也不会发生饥饿，就要保护“思考”（通过互斥量调用）后面的5个语句。哲学家在开始拿起餐叉之前，要先询问互斥量。互斥量代表相互排斥或者能给对象提供独占访问。在放下餐叉后，哲学家要释放互斥量。理论上，这种解决方案可行。但这实际上有一个性能问题：在任意时刻，只有一个哲学家进餐。桌上有5个餐叉可用，应该能让两个哲学家同时进餐。

下面给出了完整的解决方案。

准备就绪

确定安装并运行了Visual Studio。

操作步骤

1． 创建一个新的默认Win32项目，命名为PhilosophersDinner。

2． 打开stdafx.h，并输入下面的代码：

3． 打开PhilosophersDinner.cpp，并输入下面的代码：

4．右键单击【解决方案资源管理器】，并添加一个新的默认Win32控制台应用程序，命名为Philosopher。

5． 打开stdafx.h，并输入下面的代码：

示例分析

我们要创建5个进程来模仿5位哲学家的行为。每位哲学家（即，每个进程）都必须思考和进餐。哲学家需要两把餐叉才能进餐，在餐叉可用的前提下，他必须先拿起左边的餐叉，再拿起右边的餐叉。如果两把餐叉都可用，他就能顺利进餐；如果另一把餐叉不可用，他就放下已拿起的左边餐叉，并等待下一次进餐。我们在程序中把进餐时间设置为1秒。

PhilosophersDinner是该主应用程序。我们创建了文件映射，可以与其他进程通信。创建Semaphore对象同步进程也很重要。根据前面的分析，使用互斥量能确保同一时刻只有一位哲学家进餐。这种虽然方法可行，但是优化得不够。如果每位哲学家需要两把餐叉才能进餐，可以用FLOOR( NUMBER_OF_PHILOSOPHERS / 2 )实现两位哲学家同时进餐。这就是我们设置同一时刻最多有两个对象可以传递信号量的原因，如下代码所示：

这里注意，信号量最初可以允许一定数量的对象通过，但是通过CreateSemaphoreAPI的第3个参数可以递增这个数量。不过在我们的示例中，用不到这个特性。

初始化信号量对象后，就创建了进程，应用程序可以进入消息循环了。分析完PhilosophersDinner，我们来看Philosopher应用程序。这是一个控制台应用程序，因为我们不需要接口，所以将隐藏它的主窗口（本例中是控制台）。如下代码所示：

接下来，该应用程序要获得它的索引（哲学家的姓名）：

然后，哲学家必须获得文件映射对象的句柄，并进入消息循环。在消息循环中，哲学家询问传递过来的信号量对象，等待轮到他们进餐。当哲学家获得一个传入的信号量时，就可以获得两把餐叉。然后，通过下面的SendMessageAPI，发送一条消息，更新主应用程序的用户接口:

所有的工作完成后，哲学家会释放信号量对象并继续执行。

本文节选自《C++多线程编程实战》

内容简介

本书是一本实践为主、通俗易懂的Windows多线程编程指导。本书使用C++本地调用，让读者能快速高效地进行并发编程。

全书共8章。第1章介绍了C++编程语言的概念和特性。

第2~5章介绍了进程、线程、同步、并发的相关知识。其中，第2章介绍进程和线程的基本概念，详细介绍了进程和线程对象。第3章讲解线程管理方面的知识，以及进程和线程背后的逻辑，简要介绍了线程同步、同步对象和同步技术。第4章重点介绍了消息传递技术、窗口处理器、消息队列和管道通信。第5章介绍了线程同步和并发操作，讲解了并行、优先级、分发器对象和调度技术，解释了同步对象（如互斥量、信号量、事件和临界区）。

第6章介绍.NET框架中的线程，概述了C++/CLI .NET线程对象。简要介绍了托管方法、.NET同步要素、.NET线程安全、基于事件的异步模式和BackgroundWorker对象，以及其他主题。

第7~8章为水平较高的读者准备了一些高级知识，概述了并发设计和高级线程管理。其中，第7章讲解理解并发代码设计，涵盖了诸如性能因素、正确性问题、活跃性问题的特性。第8章讲解高级线程管理，重点介绍更高级的线程管理知识。详细介绍了线程池的抽象、定制分发对象，以及死锁的解决方案。

附录涵盖了MySQL Connector C和WinDDK的具体安装步骤，介绍了如何为驱动程序编译和OpenMP编译设置Visual Studio。另外，还介绍了DebugView应用程序的安装步骤，并演示了它的使用步骤。

本书主要面向中高级读者，可作为用C++进行Windows多线程编程的参考读物。本书介绍的同步概念非常基础，因此也可作为对这方面技术感兴趣的读者和开发人员的参考书籍。

本文转载自异步社区

原文链接：https://www.epubit.com/articleDetails?id=NC7E3EF917D100001114DC3407570FF10