图书
电子书
课程
专栏
文章
视频模块

哲学家就餐问题

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

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

哲学家就餐问题

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

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

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

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

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

准备就绪

确定安装并运行了Visual Studio。

操作步骤

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

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

#pragma once 
#include "targetver.h" 
#define WIN32_LEAN_AND_MEAN 
#include <windows.h> 
#include <commctrl.h> 
#include <stdlib.h> 
#include <malloc.h> 
#include <memory.h> 
#include <tchar.h> 
#include <stdio.h> 
#pragma comment ( lib, "comctl32.lib" ) 
#pragma comment ( linker, "\"/manifestdependency:type='win32' \ 
name='Microsoft.Windows.Common-Controls' \ 
version='6.0.0.0' processorArchitecture='*' \ 
publicKeyToken='6595b64144ccf1df' language='*'\"" )

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

#include "stdafx.h"

#define BUTTON_CLOSE 100
#define PHILOSOPHER_COUNT 5
#define WM_INVALIDATE WM_USER + 1

typedef struct _tagCOMMUNICATIONOBJECT
{
　　HWND hWnd;
　　bool bExitApplication;
　　int iPhilosopherArray[PHILOSOPHER_COUNT];
　　int PhilosopherCount;
} COMMUNICATIONOBJECT, *PCOMMUNICATIONOBJECT;

HWND InitInstance(HINSTANCE hInstance, int nCmdShow);
ATOM MyRegisterClass(HINSTANCE hInstance);
LRESULT CALLBACK WndProc(HWND hWnd, UINT uMsg, WPARAM wParam,
　　LPARAM lParam);
int PhilosopherPass(int iPhilosopher);
void FillEllipse(HWND hWnd, HDC hDC, int iLeft, int iTop, int
　　iRight, int iBottom, int iPass);

TCHAR* szTitle = TEXT("Philosophers Dinner Demo");
TCHAR* szWindowClass = TEXT("__PD_WND_CLASS__");
TCHAR* szSemaphoreName = TEXT("__PD_SEMAPHORE__");
TCHAR* szMappingName = TEXT("__SHARED_FILE_MAPPING__");
PCOMMUNICATIONOBJECT pCommObject = NULL;

int APIENTRY _tWinMain(HINSTANCE hInstance, HINSTANCE
　　hPrevInstance, LPTSTR lpCmdLine, int nCmdShow)
{
　　UNREFERENCED_PARAMETER(hPrevInstance);
　　UNREFERENCED_PARAMETER(lpCmdLine);
　　HANDLE hMapping = CreateFileMapping((HANDLE)-1, NULL,
　　　　PAGE_READWRITE, 0, sizeof(COMMUNICATIONOBJECT), szMappingName);
　　if (!hMapping)
　　{
　　　　MessageBox(NULL, TEXT("Cannot open file mapping"),
　　　　　　TEXT("Error!"), MB_OK);
　　　　return 1;
　　}
　　pCommObject = (PCOMMUNICATIONOBJECT)MapViewOfFile(hMapping,
　　　　FILE_MAP_ALL_ACCESS, 0, 0, 0);
　　if (!pCommObject)
　　{
　　　　MessageBox(NULL, TEXT("Cannot get access to file mapping! "),
　　　　　　TEXT("Error!"), MB_OK);
　　　　CloseHandle(hMapping);
　　　　return 1;
　　}
　　InitCommonControls();
　　MyRegisterClass(hInstance);
　　HWND hWnd = NULL;
　　if (!(hWnd = InitInstance(hInstance, nCmdShow)))
　　{
　　　　return FALSE;
　　}
　　pCommObject->bExitApplication = false;
　　pCommObject->hWnd = hWnd;
　　memset(pCommObject->iPhilosopherArray, 0,
　　　　sizeof(*pCommObject->iPhilosopherArray));
　　pCommObject->PhilosopherCount = PHILOSOPHER_COUNT;
　　HANDLE hSemaphore = CreateSemaphore(NULL,
　　　　int(PHILOSOPHER_COUNT / 2), int(PHILOSOPHER_COUNT / 2),
　　　　szSemaphoreName);
　　STARTUPINFO startupInfo[PHILOSOPHER_COUNT] =
　　　　{ { 0 }, { 0 }, { 0 }, { 0 }, { 0 } };
　　PROCESS_INFORMATION processInformation[PHILOSOPHER_COUNT] =
　　　　{ { 0 }, { 0 }, { 0 }, { 0 }, { 0 } };
　　HANDLE hProcesses[PHILOSOPHER_COUNT];
　　TCHAR szBuffer[8];
　　for (int iIndex = 0; iIndex < PHILOSOPHER_COUNT; iIndex++)
　　{
#ifdef UNICODE
　　　　wsprintf(szBuffer, L"%d", iIndex);
#else
　　　　sprintf(szBuffer, "%d", iIndex);
#endif
　　　　if (CreateProcess(TEXT("..\\Debug\\Philosopher.exe"),
　　　　　　szBuffer, NULL, NULL,
　　　　　　FALSE, 0, NULL, NULL, &startupInfo[iIndex],
　　　　　　&processInformation[iIndex]))
　　　　{
　　　　　　hProcesses[iIndex] = processInformation[iIndex].hProcess;
　　　　}
　　}
　　MSG msg = { 0 };
　　while (GetMessage(&msg, NULL, 0, 0))
　　{
　　　　TranslateMessage(&msg);
　　　　DispatchMessage(&msg);
　　}
　　pCommObject->bExitApplication = true;
　　UnmapViewOfFile(pCommObject);
　　WaitForMultipleObjects(PHILOSOPHER_COUNT, hProcesses, TRUE, INFINITE);
　　for (int iIndex = 0; iIndex < PHILOSOPHER_COUNT; iIndex++)
　　{
　　　　CloseHandle(hProcesses[iIndex]);
　　}
　　CloseHandle(hSemaphore);
　　CloseHandle(hMapping);
　　return (int)msg.wParam;
}
ATOM MyRegisterClass(HINSTANCE hInstance)
{
　　WNDCLASSEX wndEx;
　　wndEx.cbSize = sizeof(WNDCLASSEX);
　　wndEx.style = CS_HREDRAW | CS_VREDRAW;
　　wndEx.lpfnWndProc = WndProc;
　　wndEx.cbClsExtra = 0;
　　wndEx.cbWndExtra = 0;
　　wndEx.hInstance = hInstance;
　　wndEx.hIcon = LoadIcon(hInstance, MAKEINTRESOURCE(IDI_APPLICATION));
　　wndEx.hCursor = LoadCursor(NULL, IDC_ARROW);
　　wndEx.hbrBackground = (HBRUSH)(COLOR_WINDOW + 1);
　　wndEx.lpszMenuName = NULL;
　　wndEx.lpszClassName = szWindowClass;
　　wndEx.hIconSm = LoadIcon(wndEx.hInstance, MAKEINTRESOURCE(IDI_APPLICATION));
　　return RegisterClassEx(&wndEx);
}
HWND InitInstance(HINSTANCE hInstance, int nCmdShow)
{
　　HWND hWnd = CreateWindow(szWindowClass, szTitle, WS_OVERLAPPED
　　　　| WS_CAPTION | WS_SYSMENU | WS_MINIMIZEBOX, 200, 200, 540, 590,
　　　　NULL, NULL, hInstance, NULL);
　　if (!hWnd)
　　{
　　　　return NULL;
　　}
　　HFONT hFont = CreateFont(14, 0, 0, 0, FW_NORMAL, FALSE, FALSE,
　　　　FALSE, BALTIC_CHARSET, OUT_DEFAULT_PRECIS,
　　　　CLIP_DEFAULT_PRECIS, DEFAULT_QUALITY, DEFAULT_PITCH |
　　　　FF_MODERN, TEXT("Microsoft Sans Serif"));
　　HWND hButton = CreateWindow(TEXT("BUTTON"), TEXT("Close"),
　　　　WS_CHILD | WS_VISIBLE | BS_PUSHBUTTON | WS_TABSTOP, 410, 520, 100,
　　　　25, hWnd, (HMENU)BUTTON_CLOSE, hInstance, NULL);
　　SendMessage(hButton, WM_SETFONT, (WPARAM)hFont, TRUE);
　　ShowWindow(hWnd, nCmdShow);
　　UpdateWindow(hWnd);
　　return hWnd;
}
LRESULT CALLBACK WndProc(HWND hWnd, UINT uMsg, WPARAM wParam, LPARAM lParam)
{
　　switch (uMsg)
　　{
　　　　case WM_COMMAND:
　　　　{
　　　　　　switch (LOWORD(wParam))
　　　　　　{
　　　　　　　　case BUTTON_CLOSE:
　　　　　　　　{
　　　　　　　　　　DestroyWindow(hWnd);
　　　　　　　　　　break;
　　　　　　　　}
　　　　　　}
　　　　　　break;
　　　　}
　　　　case WM_INVALIDATE:
　　　　{
　　　　　　InvalidateRect(hWnd, NULL, TRUE);
　　　　　　break;
　　　　}
　　　　case WM_PAINT:
　　　　{
　　　　　　PAINTSTRUCT paintStruct;
　　　　　　HDC hDC = BeginPaint(hWnd, &paintStruct);
　　　　　　FillEllipse(hWnd, hDC, 210, 10, 310, 110,
　　　　　　PhilosopherPass(1));
　　　　　　FillEllipse(hWnd, hDC, 410, 170, 510, 270,
　　　　　　　　PhilosopherPass(2));
　　　　　　FillEllipse(hWnd, hDC, 335, 400, 435, 500,
　　　　　　　　PhilosopherPass(3));
　　　　　　FillEllipse(hWnd, hDC, 80, 400, 180, 500,
　　　　　　　　PhilosopherPass(4));
　　　　　　FillEllipse(hWnd, hDC, 10, 170, 110, 270,
　　　　　　　　PhilosopherPass(5));
　　　　　　EndPaint(hWnd, &paintStruct);
　　　　　　break;
　　　　}
　　　　case WM_DESTROY:
　　　　{
　　　　　　PostQuitMessage(0);
　　　　　　break;
　　　　}
　　　　default:
　　　　{
　　　　　　return DefWindowProc(hWnd, uMsg, wParam, lParam);
　　　　}
　　}
　　return 0;
}
int PhilosopherPass(int iPhilosopher)
{
　　return pCommObject->iPhilosopherArray[iPhilosopher - 1];
}
void FillEllipse(HWND hWnd, HDC hDC, int iLeft, int iTop, int
　　iRight, int iBottom, int iPass)
{
　　HBRUSH hBrush = NULL;
　　if (iPass)
　　{
　　　　hBrush = CreateSolidBrush(RGB(255, 0, 0));
　　}
　　else
　　{
　　　　hBrush = CreateSolidBrush(RGB(255, 255, 255));
　　}
　　HBRUSH hOldBrush = (HBRUSH)SelectObject(hDC, hBrush);
　　Ellipse(hDC, iLeft, iTop, iRight, iBottom);
　　SelectObject(hDC, hOldBrush);
　　DeleteObject(hBrush);
}

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

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

#pragma once
#include "targetver.h"
#include <stdio.h>
#include <tchar.h>
#include <windows.h>
6． 打开Philosopher.cpp，并输入下面的代码：

#include "stdafx.h"
#include <Windows.h>

#define EATING_TIME 1000
#define PHILOSOPHER_COUNT 5
#define WM_INVALIDATE WM_USER + 1

typedef struct _tagCOMMUNICATIONOBJECT
{
　　HWND hWnd;
　　bool bExitApplication;
　　int iPhilosopherArray[PHILOSOPHER_COUNT];
　　int PhilosopherCount;
} COMMUNICATIONOBJECT, *PCOMMUNICATIONOBJECT;

void Eat();
TCHAR* szSemaphoreName = TEXT("__PD_SEMAPHORE__");
TCHAR* szMappingName = TEXT("__SHARED_FILE_MAPPING__");
bool bExitApplication = false;

int _tmain(int argc, _TCHAR* argv[])
{
　　HWND hConsole = GetConsoleWindow();
　　ShowWindow(hConsole, SW_HIDE);
　　int iIndex = (int)_tcstol(argv[0], NULL, 10);
　　HANDLE hMapping = OpenFileMapping(FILE_MAP_ALL_ACCESS, FALSE,
　　　　szMappingName);
　　while (!bExitApplication)
　　{
　　　　HANDLE hSemaphore = OpenSemaphore(SEMAPHORE_ALL_ACCESS, FALSE,
　　　　　　szSemaphoreName);
　　　　WaitForSingleObject(hSemaphore, INFINITE);
　　　　PCOMMUNICATIONOBJECT pCommObject = (PCOMMUNICATIONOBJECT)
　　　　　　MapViewOfFile(hMapping, FILE_MAP_ALL_ACCESS, 0, 0,
　　　　　　sizeof(COMMUNICATIONOBJECT));
　　　　bExitApplication = pCommObject->bExitApplication;
　　　　if (!pCommObject->iPhilosopherArray[
　　　　　　(iIndex + pCommObject->PhilosopherCount - 1)
　　　　　　　　% pCommObject->PhilosopherCount]
　　　　　　　　&& !pCommObject->iPhilosopherArray[
　　　　　　　　　　(iIndex + 1) % pCommObject->PhilosopherCount])
　　　　{
　　　　　　pCommObject->iPhilosopherArray[iIndex] = 1;
　　　　　　Eat();
　　　　}

　　　　SendMessage(pCommObject->hWnd, WM_INVALIDATE, 0, 0);
　　　　pCommObject->iPhilosopherArray[iIndex] = 0;
　　　　UnmapViewOfFile(pCommObject);
　　　　ReleaseSemaphore(hSemaphore, 1, NULL);
　　　　CloseHandle(hSemaphore);
　　}
　　CloseHandle(hMapping);
　　return 0;
}

void Eat()
{
　　Sleep(EATING_TIME);
}

示例分析

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

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

HANDLE hSemaphore = CreateSemaphore( NULL,
　 int( PHILOSOPHER_COUNT / 2 ),
　 int( PHILOSOPHER_COUNT / 2 ), szSemaphoreName );

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

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

HWND hConsole = GetConsoleWindow( ); 
ShowWindow( hConsole, SW_HIDE );

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

int iIndex = ( int ) _tcstol( argv[ 0 ], NULL, 10 );

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

SendMessage( pCommObject->hWnd, WM_INVALIDATE, 0, 0 );

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

本文节选自《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多线程编程的参考读物。本书介绍的同步概念非常基础，因此也可作为对这方面技术感兴趣的读者和开发人员的参考书籍。

©2019异步社区·人民邮电出版社·All rights reserved

京ICP备05035396号-6

京公网安备11010602100305号

增值电信业务经营许可证（京B2-20201559）Powered by 人民邮电出版社▪出版云