不看会后悔的Windows XP之经验谈	简单快捷DIY实用家庭影院

哲学家进餐问题

楼主songsong2008（）2005-05-03 19:28:19 在 C/C++ / C语言提问

以下是某个网站给出来的算法，不过我觉得有点不能，大家看一下
///////
有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子每个哲学家的行为是思考，感到饥饿，然后吃通心粉.为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子
#define N 5
void philosopher (int i)
{
while (true)
{
思考；
取fork[i]; 取fork[(i+1) % 5]；
进食；
放fork[i]; 放fork[(i+1) % 5]；
}
}
为防止死锁发生可采取的措施：
最多允许4个哲学家同时坐在桌子周围仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子（）给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之为了避免死锁，把哲学家分为三种状态，思考，饥饿，进食，并且一次拿到两只筷子，否则不拿.

　

哲学家就餐问题解法（1）
#define N 5
void philosopher (int i)
{
while (true)
{
思考；
取fork[i]; 取fork[(i+1) % 5]；
进食；
放fork[i]; 放fork[(i+1) % 5]；
}
}
哲学家就餐问题解法（2）
#define N 5
#define THINKING 0
#define HUNGRY 1
#define EATING 2
#typedef int semaphore;
int state[N];
semaphore mutex=1;
semaphore s[N];
void test(int i)
{
if (state[ i ] == HUNGRY)
&& (state [ (i-1) % 5] != EATING)
&& (state [ (i+1) % 5] != EATING)
{
state[ i ] = EATING;
V(&s[ i ]);
}
}
void philosopher (int i)
{ while (true)
{
思考;
P(&mutex);
state[i] = HUNGRY;
test(i);
V(&mutex);//我觉得这个V(&mutex)应放在职while的最后，大家说呢？
P(&s[i]);
拿左筷子；
拿右筷子；
进食；
放左筷子；
放右筷子；
P(&mutex)
state[ i ] = THINKING；
test([i-1] % 5);
test([i+1] % 5);
V(&mutex);
}
}
state[ i ] = THINKING
s[ i ] = 0

问题点数：20、回复次数：11Top

1 楼jackyhubin（想吃三明治）回复于 2005-05-03 20:13:57 得分 2

组合数学的一个经典问题Top

2 楼arrowcy（长弓手）回复于 2005-05-03 20:28:35 得分 0

V(&mutex);//我觉得这个V(&mutex)应放在职while的最后，大家说呢？

=======================================================
这里的mutex知识用于实现互斥的访问每个人的状态那个数组，所以不应该放在while最后，否则一旦有一个哲学家在进餐了，其他人就无法访问那个数组，也就无法进餐，这样在同一个时刻就只能有一个哲学家进餐勒Top

3 楼niuman（青橄榄）回复于 2005-05-03 20:30:42 得分 3

看看操作系统的书，
哲学家平时就是思考，如果饿了而且左右没在吃他就可以吃
pv操作一定要成对出现，所以源程序有问题
pv(mutex)是为了互斥对哲学家状态操作，
Top

4 楼flyingdancing2005（返璞归C）回复于 2005-05-03 20:45:34 得分 2

up
还没学呢Top

5 楼fufangpeng（酷麒麟）回复于 2005-05-03 23:01:27 得分 2

我当时不是这样做的，我是给每个哲学家编号，标号对2取余，为0取做，为1取右的。Top

6 楼mostideal（三甲）回复于 2005-05-04 00:17:33 得分 2

upTop

7 楼songsong2008（）回复于 2005-05-04 07:46:14 得分 0

//其实我的意思是while中只用一个p,v操作,p放在开头,v放在结尾
哲学家就餐问题解法（2）
#define N 5
#define THINKING 0
#define HUNGRY 1
#define EATING 2
#typedef int semaphore;
int state[N];
semaphore mutex=1;
semaphore s[N];
void test(int i)
{
if (state[ i ] == HUNGRY)
&& (state [ (i-1) % 5] != EATING)
&& (state [ (i+1) % 5] != EATING)
{
state[ i ] = EATING;
V(&s[ i ]);
}
}
void philosopher (int i)
{ while (true)
{
思考;
P(&mutex);
state[i] = HUNGRY;
test(i);
V(&mutex);//这句删去
P(&s[i]);
拿左筷子；
拿右筷子；
进食；
放左筷子；
放右筷子；
P(&mutex)//也句也删去
state[ i ] = THINKING；
test([i-1] % 5);
test([i+1] % 5);
V(&mutex);
}
}
state[ i ] = THINKING
s[ i ] = 0
Top

8 楼songsong2008（）回复于 2005-05-04 07:51:20 得分 0

哦,我明白了,谢谢arrowcy(长弓手),谢谢各位Top

9 楼foru1971（虫子）回复于 2005-05-04 08:49:37 得分 2

是不是还有些问题,test是来检查能否进入吃饭状态，而后面在取筷子进食时，却没有检查该状态，也就是说在test不能进入吃饭状态时，仍可执行进食。即是在取筷子时有同步，仍会有state=HUNGRY时，可以进食的情况出现。
不认为该代码能解决这个问题。Top

10 楼songsong2008（）回复于 2005-05-04 18:11:02 得分 0

楼上说的那种情况不会发生吧Top

11 楼lingzantia（迟早是高手）回复于 2005-05-04 19:50:25 得分 7

//---------------------------------------------------------------------------

//#include <vcl.h>
//#pragma hdrstop

//---------------------------------------------------------------------------
//#pragma argsused

#include <stdio.h>
#include <windows.h>
#include <iostream.h>
#include <winbase.h>

#define MAX_NUM 5

struct tagThread{
DWORD IDThread;
HANDLE hThread;
int iParam;
};
HANDLE hMutex[MAX_NUM+1];
//---------------------------------------------------------------------------
DWORD WINAPI PhilosopherOrder(LPVOID pParam)
{
int iPhiloID=*(int *)pParam;
char strPhiloID[20];
char info[64];

sprintf(strPhiloID,"%d",iPhiloID );
strcpy(info,"第");
strcat(info,strPhiloID);
strcat(info,"个哲学家");

do
{
MessageBox(NULL,"正在思考。。。", info, MB_OK|MB_ICONINFORMATION);

if (iPhiloID!=MAX_NUM-1)
{ MessageBox(NULL,"想进餐，企图使用左筷子", info, MB_OK|MB_ICONINFORMATION);
WaitForSingleObject(hMutex[iPhiloID],INFINITE);
MessageBox(NULL,"拿到左筷子，企图使用右筷子", info, MB_OK|MB_ICONINFORMATION);
WaitForSingleObject(hMutex[iPhiloID+1],INFINITE);
}
else
{ MessageBox(NULL,"想进餐，企图使用右筷子", info, MB_OK|MB_ICONINFORMATION);
WaitForSingleObject(hMutex[0],INFINITE);
MessageBox(NULL,"拿到右筷子，企图使用左筷子", info, MB_OK|MB_ICONINFORMATION);
WaitForSingleObject(hMutex[iPhiloID],INFINITE);
}

MessageBox(NULL,"拿到两只筷子,正在进餐。。。", info, MB_OK|MB_ICONINFORMATION);

MessageBox(NULL,"筷子使用完毕，准备通告", info, MB_OK|MB_ICONINFORMATION);
ReleaseMutex(hMutex[iPhiloID]);
ReleaseMutex(hMutex[(iPhiloID+1)%MAX_NUM]);

} while( MessageBox(NULL,"通告完毕，继续思考进餐吗？",
info, MB_YESNO|MB_ICONINFORMATION)
==IDYES);
ExitThread(NO_ERROR);
return 0;
}
//-----------------------------------------
/*
DWORD WaitForMultipleObjects(
DWORD nCount, // number of handles in the object handle array
CONST HANDLE *lpHandles, // pointer to the object-handle array
BOOL bWaitAll, // wait flag
DWORD dwMilliseconds // time-out interval in milliseconds
);
*/
DWORD WINAPI PhilosopherAll(LPVOID pParam)
{
int iPhiloID=*(int *)pParam;
char strPhiloID[20];
char info[64];

sprintf(strPhiloID,"%d",iPhiloID );
strcpy(info,"第");
strcat(info,strPhiloID);
strcat(info,"个哲学家");

do
{
MessageBox(NULL,"正在思考。。。", info, MB_OK|MB_ICONINFORMATION);

MessageBox(NULL,"想进餐，企图使用筷子", info, MB_OK|MB_ICONINFORMATION);
WaitForMultipleObjects(
2, // number of handles in the object handle array
&(hMutex[iPhiloID]), // pointer to the object-handle array
TRUE, // wait flag
INFINITE // time-out interval in milliseconds
);

MessageBox(NULL,"拿到两只筷子,正在进餐。。。", info, MB_OK|MB_ICONINFORMATION);

MessageBox(NULL,"筷子使用完毕，准备通告", info, MB_OK|MB_ICONINFORMATION);
ReleaseMutex(hMutex[iPhiloID]);
ReleaseMutex(hMutex[iPhiloID+1]);

} while( MessageBox(NULL,"通告完毕，继续思考进餐吗？",
info, MB_YESNO|MB_ICONINFORMATION)
==IDYES);
ExitThread(NO_ERROR);
return 0;
}
//-----------------------------------------
int main()
{
int i;
for (i=0;i<MAX_NUM;i++)
hMutex[i]=CreateMutex(NULL,false,NULL);
hMutex[MAX_NUM]=hMutex[0];

tagThread arrThread[MAX_NUM];
int Flag;
Flag=MessageBox(NULL,"全部分配方案(Y)，有序分配方案(N)","选择",
MB_YESNO|MB_ICONINFORMATION);

cout << "CreateThread Start" << endl;
for(i=0;i<MAX_NUM;i++)
{ arrThread[i].iParam=i;
if (Flag==IDYES)
arrThread[i].hThread =CreateThread(NULL,0, PhilosopherAll,
&(arrThread[i].iParam),0,
&(arrThread[i].IDThread));
else
arrThread[i].hThread =CreateThread(NULL,0,PhilosopherOrder,
&(arrThread[i].iParam),0,
&(arrThread[i].IDThread));
if (arrThread[i].hThread == NULL)
cout << "CreateThread error" << endl;
}
cout << "CreateThread End" << endl;

cin.get();
for (i=0;i<MAX_NUM;i++)
CloseHandle(hMutex[i]);
return 0;
}

Top