本节书摘来自异步社区出版社《C++多线程编程实战》一书中的第2章，第2.6节，作者：【黑山共和国】Milos Ljumovic（米洛斯留莫维奇），更多章节内容可以访问云栖社区“异步社区”公众号查看。

2.6　解决典型的IPC问题

进程间通信非常重要，它的实现也很复杂。操作系统的设计人员和开发人员要面临各种问题。接下来，我们讲解一些最常见的问题。

2.6.1　哲学家就餐问题

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

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

d3978c13100591f7d00eba97e1fda631944ea476

图2.9　哲学家就餐问题

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

我们可以等指定的餐叉可用时才去拿。不过，这样想显然是错误的。如果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

define EATING_TIME 1000

define PHILOSOPHER_COUNT 5

define WM_INVALIDATE WM_USER + 1

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 );`
所有的工作完成后，哲学家会释放信号量对象并继续执行。

更多讨论
还有一些经典的IPC问题，如“睡觉的理发师”和“生产者-消费者”问题。本章后面会给出“生产者-消费者”问题的解法。

《C++多线程编程实战》——2.6　解决典型的IPC问题

2.6　解决典型的IPC问题

2.6.1　哲学家就餐问题

include "stdafx.h"

define BUTTON_CLOSE 100

define PHILOSOPHER_COUNT 5

define WM_INVALIDATE WM_USER + 1

ifdef UNICODE

else

endif

include "stdafx.h"

include

define EATING_TIME 1000

define PHILOSOPHER_COUNT 5

define WM_INVALIDATE WM_USER + 1

热门文章

最新文章

相关课程

相关电子书

相关实验场景

《C++多线程编程实战》——2.6 解决典型的IPC问题

2.6 解决典型的IPC问题

2.6.1 哲学家就餐问题

include "stdafx.h"

define BUTTON_CLOSE 100

define PHILOSOPHER_COUNT 5

define WM_INVALIDATE WM_USER + 1

ifdef UNICODE

else

endif

include "stdafx.h"

include

define EATING_TIME 1000

define PHILOSOPHER_COUNT 5

define WM_INVALIDATE WM_USER + 1

热门文章

最新文章

相关课程

相关电子书

相关实验场景

《C++多线程编程实战》——2.6　解决典型的IPC问题

2.6　解决典型的IPC问题

2.6.1　哲学家就餐问题