哲学家就餐问题是多线程同步中的经典问题,本文在 windows 上用 C/C++ 实现该问题。
之前在网上看到一个该问题的实现:[/url][url=http://dev.csdn.net/article/77/77383.shtm]http://dev.csdn.net/article/77/77383.shtm,是用临界区作的,但是感觉不是太好,因为当一个哲学家在试图取叉子用餐的时候,其他哲学家必须等待,而实际上,当 1 号哲学家
取叉子时,3号哲学家也可以取叉子,他们是不冲突的。
假设有 5 个哲学家,有 5 把叉子,每个哲学家有思考,饥饿,和吃饭三个状态。我们用 5 个信号量分别表示 5 把叉子。在打印哲学家状态时,使用一个互斥体 mutex ,否则打印出来是乱的。
源代码如下:
// PhilosopherDining.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "windows.h"
#include <process.h>
#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;
const unsigned int PHILOSOPHER_NUM=5;
const char THINKING=1;
const char HUNGRY=2;
const char DINING=3;
// each fork has a semaphore
HANDLE semph[PHILOSOPHER_NUM];
// Mutex for printing
HANDLE mutex;
void philosopherProc(void* param);
int main(int argc, char* argv[])
{
int i;
srand(time(0));
mutex = CreateMutex(NULL, false, NULL);
for (i=0; i<PHILOSOPHER_NUM; i++)
{
semph[i] = CreateSemaphore(NULL, 1, 1, NULL);
_beginthread(philosopherProc, 0, (void*)&i);
Sleep(10);
}
Sleep(2000);
return 0;
}
void philosopherProc(void* param)
{
int myid;
char idStr[128];
char stateStr[128];
char mystate;
int ret;
unsigned int leftFork;
unsigned int rightFork;
myid = *((int*)(param));
itoa(myid, idStr, 10);
//cout << "philosopher " << myid << " begin......" << endl;
Sleep(10);
// initial state is THINKING
mystate = THINKING;
leftFork = (myid) % PHILOSOPHER_NUM;
rightFork = (myid + 1) % PHILOSOPHER_NUM;
while (true)
{
switch(mystate)
{
case THINKING:
// changing my state
mystate = HUNGRY;
strcpy(stateStr, "HUNGRY");
break;
case HUNGRY:
strcpy(stateStr, "HUNGRY");
// first test the left fork ...
ret = WaitForSingleObject(semph[leftFork], 0);
if (ret == WAIT_OBJECT_0)
{
// left fork is ok, take it up !
// then test the right fork ...
ret = WaitForSingleObject(semph[rightFork], 0);
if (ret == WAIT_OBJECT_0)
{
// right fork is also ok !
// changing my state
mystate = DINING;
strcpy(stateStr, "DINING");
}
else
{
// right fork is being used by others, so I must put down
// the left fork.
ReleaseSemaphore(semph[leftFork], 1, NULL);
}
}
break;
case DINING:
// put down both the left and right fork
ReleaseSemaphore(semph[leftFork], 1, NULL);
ReleaseSemaphore(semph[rightFork], 1, NULL);
// changing my state
mystate = THINKING;
strcpy(stateStr, "THINKING");
break;
}
// print my state
WaitForSingleObject(mutex, INFINITE);
cout << "philosopher " << myid << " is : " << stateStr << endl;
ReleaseMutex(mutex);
// sleep a random time : between 1 - 5 s
int sleepTime;
sleepTime = 1 + (int)(5.0*rand()/(RAND_MAX+1.0));
Sleep(sleepTime*10);
}
}