哲学家进餐问题描述:

哲学家进餐问题是E.W.Dijkstra 在1965年秋，为埃因霍温（Eindhoven)技术大学学生提出的一个考题，原题为五胞胎进餐问题，不久就以牛津大学教授Hoare(霍尔）所取得名字——“哲学家进餐问题”而闻名。经过中国化得哲学家进餐问题可以这样描述:5个哲学家同坐在一张圆桌旁，每个人的面前放着一碗面条，碗的两旁各摆放一根筷子。假设哲学家的生活除了吃饭就是思考（这是一种抽象，即对该问题而言，其他活动无关紧要),而吃饭的时候要左手拿一根筷子，右手拿一根筷子，然后开始进餐。吃完后又将筷子放回原处，继续思考问题。

一个哲学家的活动进程描述:

1. 思考问题
2. 饿了停止思考，左手拿一根筷子（如果左侧哲学家已持有它，则需要等待）；
3. 右手拿一根筷子（如果右侧哲学家已持有它，则需要等待）；
4. 进餐
5. 放右手筷子
6. 放左手筷子
7. 重新回到思考问题的状态分别考虑下面两种情况：

• 按哲学家的活动进程，当所有的哲学家都同时拿起左手的筷子时，则所有的哲学家都将拿不到右手的筷子，并处于等待状态，那么哲学家都将无法进餐，最终饿死。
• 将哲学家的活动进程修改一下，变为当右手的筷子拿不到时，就放下左手的筷子，这种情况不一定没有问题。因为可能在一瞬间，所有的哲学家都同时拿起左手的筷子，则自然拿不到右手的筷子，于是都同时放下左手的筷子，等一会，又同时拿起左手的筷子，如此这样永远重复下去，则所有的哲学家都将无法进餐。

以上两个方面的问题，其实反映的是程序并发执行时进程同步的两个问题，一个是死锁，一个是饥饿。

下面有三种方法避免死锁：

• 最多允许4位哲学家同时拿起左手（或右手）的筷子。
• 仅当哲学家的左、右两支筷子均可用时，才允许他同时拿起左、右手的两支筷子；否则一支筷子也不拿。
• 奇数号哲学家先拿右边的筷子，然后再取左边的筷子；偶数号哲学家先拿左边的筷子，然后再拿右边的筷子。 

 代码1：仅当哲学家的左、右两支筷子均可用时，才允许他同时拿起左、右手的两支筷子；否则一支筷子也不拿

#include<windows.h>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
HANDLE mutex;//互斥变量
HANDLE chopstick[5];
HANDLE philosopher[5];
int num=0;
int random()
{return rand()%100+60;
}
void eating(int id)
{int etime=random();Sleep(etime);printf("\t\t\t哲学家%d号吃了%d秒饭\n",id,etime);
}
//用windows下的WINAPI函数实现简单的多线程，PVOID无类型指针；param参数
DWORD WINAPI phthread(LPVOID param)  
{num++;
int	id=num;
int limittime=0;//进餐的次数限制
int chopstick1,chopstick2;//实现左右2根筷子变量
while(true)
{Sleep(200);//未来100毫秒内不会被唤醒；Unix系统使用的是时间片法，而Windows则属于抢占式，将进程挂起if(limittime>=1)break;
chopstick1=WaitForSingleObject(chopstick[(id+1)%5],0),	chopstick2=WaitForSingleObject(chopstick[id],0);//同时拿起筷子
if(chopstick1==WAIT_OBJECT_0&&chopstick2==WAIT_OBJECT_0)
{WaitForSingleObject(mutex,INFINITE);//一直占主线程，到ReleaseMutex(mutex)为止printf("哲学家%d号拿到两只筷子开始吃饭。\n", id);ReleaseMutex(mutex);//释放互斥信号体limittime++;WaitForSingleObject(mutex,INFINITE);eating(id);ReleaseMutex(mutex);//释放互斥信号体WaitForSingleObject(mutex,INFINITE);printf("\t\t\t哲学家%d号吃完饭啦，放下筷子，继续思考。\n", id);ReleaseMutex(mutex); 
}ReleaseSemaphore(chopstick[(id+1)%5], 1, NULL),ReleaseSemaphore(chopstick[id], 1, NULL);//同时放下筷子WaitForSingleObject(mutex,INFINITE);ReleaseMutex(mutex);
}
return 0 ;
}
int main(){srand((unsigned)time(0));mutex = CreateMutex(NULL, false, NULL);//创建互斥信号量，传递false值for (int i = 0; i < 5; ++i){chopstick[i]=CreateSemaphore(NULL,1,1,NULL);//创建筷子的信号量}for (i = 0; i < 5; ++i){philosopher[i] = CreateThread(NULL, 0, phthread,NULL, 0, NULL);//创建哲学家新线程，线程名为phthread,传递值为空，返回HANDLE}Sleep(10000);for (i = 0; i < 5; ++i){CloseHandle(philosopher[i]);CloseHandle(chopstick[i]);}CloseHandle(mutex);Sleep(500);return 0;
}

 代码2：

奇数号哲学家先拿右边的筷子，然后再取左边的筷子；偶数号哲学家先拿左边的筷子，然后再拿右边的筷子。

#include<windows.h>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
HANDLE mutex;//互斥变量
HANDLE chopstick[5];
HANDLE philosopher[5];
int num;
int random()
{return rand()%100+60;
}
void eating(int id)
{int etime=random();Sleep(etime);printf("\t\t\t哲学家%d号吃了%d秒饭\n",id,etime);
}
//用windows下的WINAPI函数实现简单的多线程，PVOID无类型指针；param参数
DWORD WINAPI phthread(LPVOID param)  
{num++;
int limittime=0;//进餐的次数限制
int id=num;//哲学家的号数
int chopstick1,chopstick2;//实现左右2根筷子变量
while(true)
{Sleep(100);//未来100毫秒内不会被唤醒；Unix系统使用的是时间片法，而Windows则属于抢占式
if(limittime>=1)
break;
if(id%2!=0)
{//奇数号的哲学家先拿起右边的筷子再拿起左边的筷子;chopstick1=WaitForSingleObject(chopstick[(id+1)%5],0);//等待筷子发出信号，如果条件满足，则返回WAIT_OBJECT_0 ,否则返回WAIT_TIMEOUTif(chopstick1==WAIT_OBJECT_0){chopstick2=WaitForSingleObject(chopstick[id],0);if(chopstick2==WAIT_OBJECT_0){WaitForSingleObject(mutex,INFINITE);//一直占主线程，到ReleaseMutex(mutex)为止printf("哲学家%d号拿到两只筷子开始吃饭。\n", id);ReleaseMutex(mutex);//释放互斥信号体limittime++;WaitForSingleObject(mutex,INFINITE);eating(id);ReleaseMutex(mutex);//释放互斥信号体WaitForSingleObject(mutex,INFINITE);printf("\t\t\t哲学家%d号吃完饭啦，放下筷子，继续思考。\n", id);ReleaseMutex(mutex);ReleaseSemaphore(chopstick[id], 1, NULL);//释放当前左边筷子的信号量}//如果哲学家抢到一只筷子，在抢占另一只筷子时失败，则要放弃已经抢占到的资源。ReleaseSemaphore(chopstick[(id+1)%5], 1, NULL);//释放当前右边筷子的信号量}
}
else
{//偶数号哲学家先拿起左边的筷子，再拿起右边的筷子chopstick1=WaitForSingleObject(chopstick[id],0);if(chopstick1==WAIT_OBJECT_0){chopstick2=WaitForSingleObject(chopstick[(id+1)%5],0);if(chopstick2==WAIT_OBJECT_0){//一直占主线程，到ReleaseMutex(mutex)为止WaitForSingleObject(mutex,INFINITE);printf("哲学家%d号拿到两只筷子开始吃饭。\n", id);ReleaseMutex(mutex);//释放互斥信号体,不然其他哲学家拿不到筷子limittime++;WaitForSingleObject(mutex,INFINITE);eating(id);ReleaseMutex(mutex);//释放互斥信号体WaitForSingleObject(mutex,INFINITE);printf("\t\t\t哲学家%d号吃完饭啦，放下筷子，继续思考。\n", id);ReleaseMutex(mutex);//左右两边都抢到筷子的哲学家，吃完放后释放资源ReleaseSemaphore(chopstick[(id+1)%5], 1, NULL);//释放当前右边筷子的信号量}//如果哲学家抢到一只筷子，在抢占另一只筷子时失败，则要放弃已经抢占到的资源。ReleaseSemaphore(chopstick[id], 1, NULL);//释放当前左边筷子的信号量}
}WaitForSingleObject(mutex,INFINITE);ReleaseMutex(mutex);
}
return 0 ;
}
int main(){srand((unsigned)time(0));//3个参数lpMutecAttributes:指向SECURITY_ATTRIBUTES型态的结构指针，NULL使用默认安全//blnitialOwner BOOL：建立互斥体，互斥体同时只能一个线程拥有//lpName String:指定互斥体对象的名子，为NULL不指定mutex = CreateMutex(NULL, false, NULL);//创建互斥信号量，传递false值for (int i = 0; i < 5; ++i){//4个参数分别为lpSemaphoreAttributes:为信号量的属性，一般设置为NULL//lInitialCount:信号量初始值，为0 默认为unsignal状态，为 1 默认为signal状态//lpMaximumCount：信号量的最大值为1//lpName:信号量的名字，可设置为NULLchopstick[i]=CreateSemaphore(NULL,1,1,NULL);//创建筷子的信号量}for (i = 0; i < 5; ++i){//6个参数分别为：lpThreadAttributes:指向SECURITY_ATTRIBUTES型态的结构指针，NULL使用默认安全//dwStackSize:设置初始栈的大小，为0 默认将使用与调用该函数的线程相同的栈空间大小//lpStartAdress:指向线程函数的指针，函数名//lpParameter:向线程函数传递参数，不需要传递参数是为NULL//dwCreationFlags:线程标志，为 0 时，表示创建后立即激活//lpThreadld:保存新线程的id,返回线程id,不想返回id设置为NULLphilosopher[i] = CreateThread(NULL, 0, phthread,NULL, 0, NULL);//创建哲学家新线程，线程名为phthread,传递值为空，返回HANDLE}Sleep(10000);for (i = 0; i < 5; ++i){CloseHandle(philosopher[i]);CloseHandle(chopstick[i]);}CloseHandle(mutex);Sleep(500);return 0;
}