一、开发环境
开发平台： Visual C++6.0
开发环境： Windows XP
开发语言： C语言+API（windows应用程序编程接口）
二、进餐问题
一个圆桌上有一大碗面，5个盘子，5把筷子，5个座位上可以座5个哲学家，当哲学家就坐以后，其左右有且仅有一个筷子，每个筷子左又有且仅有一个哲学家。哲学家动作：思考，取筷（需要两个），取面，吃面。现设计一个礼仪以允许他们就餐，需要避免两个哲学家“抢”同一把筷子，又要避免饥饿和死锁。
三、系统分析
- 互斥解决。每一把筷子使用一个2元信号量，只有获得信号量的哲学家才能使用筷子，从而避免对筷子的“抢夺”。
- 死锁和饥饿解决。餐厅只允许最多4名哲学家进入，因为总有一个哲学家可以得到两把筷子，从而可以正常就餐，因此不会有死锁出现。每为哲学家就餐完毕后，立即离开，放下筷子，以便没有用餐的哲学家可以使用，这也能保证不会有饥饿的存在了。
- 就餐顺序随机。为了较真实地模拟现实就餐问题，哲学家每次进入餐厅的顺序总是随机的，这个随机顺序在哲学家开始进入之间通过一个函数产生（这个过程会花一定时间）。
- 哲学家的各种状态。
位置空闲：当哲学家没有就座的时候，该位置显示空闲状态。
思考等待：当一个哲学家进入餐厅但是没有获得餐具就餐的时候，进入思考等待状态。
就餐：哲学家获得餐具后开始就餐进入就餐状态（就餐时间8000ms）。
离开：哲学家就餐完毕就到了离开状态。 - 每个哲学家的就餐过程通过一个线程函数的调用来实现。
四、程序流程图
五、源代码
5.1 多线程实现
代码如下：
// 解决哲学家就餐问题 // 每个哲学家可用一个线程来模拟。 // 设有5个哲学家，5只筷子，每个哲学家吃饭时间为一个随机值，哲学家吃饭后的思考时间也是一个随机值。 #include <Windows.h> #include <iostream> #include <cstdio> #include <stdlib.h> #include <time.h> /* （1）奇数号的哲学家先拿起右边的筷子再拿起左边的筷子。 （2）偶数号哲学家先拿起左边的筷子，再拿起右边的筷子。 （3）如果哲学家抢到一只筷子，在抢占另一只筷子时失败，则要放弃已经抢占到的资源。 （4）左右两边都抢到筷子的哲学家，吃完放后释放资源。*/ using namespace std; HANDLE chop[5]; HANDLE ph[5]; HANDLE mutex; int nums = 0; int random() { return rand() % 100 + 20; } void eating(int id) { int num = random(); Sleep(num); printf("\t\t\t哲学家%d号吃了%d秒\n", id, num); } DWORD WINAPI phthread(LPVOID param) { nums++; int id = nums; int lc = id - 1; int rc = id % 5; int times = 0; int ret1, ret2; while (true) { Sleep(100); if (times >= 2) break; if (id % 2 == 0) { ret1 = WaitForSingleObject(chop[lc], 0); if (ret1 == WAIT_OBJECT_0) { ret2 = WaitForSingleObject(chop[rc], 0); if (ret2 == WAIT_OBJECT_0) { WaitForSingleObject(mutex, INFINITE); printf("哲学家%d号拿到两只筷子开始吃第%d顿饭。\n", id, times + 1); ReleaseMutex(mutex); times++; WaitForSingleObject(mutex, INFINITE); eating(id); ReleaseMutex(mutex); WaitForSingleObject(mutex, INFINITE); printf("\t\t\t哲学家%d号吃完两顿饭啦，放下筷子。\n", id); ReleaseMutex(mutex); ReleaseSemaphore(chop[rc], 1, NULL); } ReleaseSemaphore(chop[lc], 1, NULL); } } else { ret1 = WaitForSingleObject(chop[rc], 0); if (ret1 == WAIT_OBJECT_0) { ret2 = WaitForSingleObject(chop[lc], 0); if (ret2 == WAIT_OBJECT_0) { WaitForSingleObject(mutex, INFINITE); printf("哲学家%d号拿到两只筷子开始吃%d顿饭。\n", id, times + 1); ReleaseMutex(mutex); times++; WaitForSingleObject(mutex, INFINITE); eating(id); ReleaseMutex(mutex); WaitForSingleObject(mutex, INFINITE); printf("\t\t\t哲学家%d号吃完两顿饭啦，放下筷子。\n", id); ReleaseMutex(mutex); ReleaseSemaphore(chop[lc], 1, NULL); } ReleaseSemaphore(chop[rc], 1, NULL); } } WaitForSingleObject(mutex, INFINITE); ReleaseMutex(mutex); } printf("=======哲学家%d吃饱了然后离开了。=======\n", id); return 0; } int main() { srand((unsigned)time(0)); mutex = CreateMutex(NULL, false, NULL); for (int i = 0; i < 5; ++i) { chop[i] = CreateSemaphore(NULL, 1, 1, NULL); } for (int i = 0; i < 5; ++i) { int j = i + 1; ph[i] = CreateThread(NULL, 0, phthread, NULL, 0, NULL); } Sleep(10000); // 释放句柄 for (int i = 0; i < 5; ++i) { CloseHandle(ph[i]); CloseHandle(chop[i]); } CloseHandle(mutex); Sleep(500); system("pause"); return 0; }
运行结果为：
5.2 C语言模拟
代码如下（不太好）：
#include<iostream> #include<stdlib.h> #include<string> #include<time.h> #include<windows.h> using namespace std; int l = 0; int w = 0; //阻塞的进程个数，用来实现最多有四个哲学家同时拿筷子，避免死锁。 int s[5] = { 1,1,1,1,1 }; //筷子的信号量 int come_order[5] = { 0,0,0,0,0 }; // 就餐顺序 int wake[5] = { 0,0,0,0,0 }; // 阻塞唤醒顺序 int *q = wake; int p(int*); int v(int*); int pro(int);//执行 int p(int *i)//p操作 { *i -= 1; if (*i < 0) { w++; return 1; } else return 0; } int v(int *i) { *i += 1; if (*i <= 0) return 1; else return 0; } void eat(int i) { cout << "第" << i << "位哲学家正在吃饭。" << endl; Sleep(3000); } int pro(int i) { if (p(&s[i - 1])) { cout << "第" << i << "位哲学家请等待...." << endl; return 1; } if (p(&s[i])) { cout << "第" << i << "位哲学家请等待...." << endl; return 1; } eat(i); if (v(&s[i])) *(q + i) = 1; if (v(&s[i - 1])) *(q + i) = 1; cout << "第" << i << "位哲学家吃饱离开了。" << endl; return 0; } int get_rand() {//产生1到5之间的整数 srand((unsigned)time(NULL)); int RANGE_MIN = 1; int RANGE_MAX = 6; int randn = rand() % (RANGE_MAX - RANGE_MIN) + RANGE_MIN; return randn; } bool if_num_exist(int num) { for (int a = 0; a < 5; a++) { if (come_order[a] == num) return true; } return false; } void get_rand_order() {//产生随机的进入顺序 int temp = 0; bool tmp = 1; for (int a = 0; a < 5; a++) { while (tmp) { temp = get_rand(); if (!if_num_exist(temp)) { come_order[a] = get_rand(); tmp = 0; } } tmp = 1; } cout << "饥饿顺序：" << come_order[0] << " " << come_order[1] << " " << come_order[2] << " " << come_order[3] << " " << come_order[4] << endl; } void get_order() { int p[5]; cout << "请输入五位哲学家的状态：" << endl << " 1表示饥饿，0表示思考。" << endl << "若有两个以上的哲学家同时饥饿，优先考虑小号的。" << endl; cin >> p[0] >> p[1] >> p[2] >> p[3] >> p[4]; int a = 0; for (int k = 0; k < 5; k++) { if (p[k] == 1) come_order[a++] = k + 1; } } void main() { int c; cout << "请选择进餐顺序生成方式，0表示随机生成，1表示手动输入：" << endl; cin >> c; if (c == 0) get_rand_order(); else if (c == 1) get_order(); else { cout << "error" << endl; } while (w < 3) { for (int a = 0; a < 5; a++) { if (come_order[a] != 0) pro(come_order[a]); } for (int a = 0; a < 5; a++) { if (*(q + a) != 0) pro(*(q + a)); } } }
运行结果为：
