模拟“五个哲学家”问题_Unix环境高级编程 Linux

实验描述转自：http://dblab.xmu.edu.cn/blog/unix-philosopher-problem-using-files/
编制模拟“五个哲学家”问题的程序，学习和掌握并发进程同步的概念和方法。
要求：
1、程序语法，是哲学家进餐和沉思的持续时间值，缺省值为2秒。
philosopher [ -t ]
2、五个哲学家的编号为0~4，分别用五个进程独立模拟。
3、程序的输出要简洁，仅输出每个哲学家进餐和沉思的信息。例如，当编号为3的哲学家在进餐时，就打印：
philosopher 3 is eating
而当他在沉思时，则打印：
philosopher 3 is thinking
除此之外不要输出其他任何信息。
4、利用课堂已教授的知识而不使用线程或IPC机制进行同步。
实验思路哲学家就餐问题有多种解决思路可以避免死锁的发生，《实验指导》中的思路时，哲学家一旦拿到其中的一个叉子就不放下，直到拿到另一个叉子并进餐后才把两个叉子都放下。这种思路的前提是保证哲学家中同时存在左撇子和右撇子，则不会发生死锁。

解法[编辑] 服务生解法[编辑]

一个简单的解法是引入一个餐厅服务生，哲学家必须经过他的允许才能拿起餐叉。因为服务生知道哪只餐叉正在使用，所以他能够作出判断避免死锁。
为了演示这种解法，假设哲学家依次标号为A至E。如果A和C在吃东西，则有四只餐叉在使用中。B坐在A和C之间，所以两只餐叉都无法使用，而D和E之间有一只空余的餐叉。假设这时D想要吃东西。如果他拿起了第五只餐叉，就有可能发生死锁。相反，如果他征求服务生同意，服务生会让他等待。这样，我们就能保证下次当两把餐叉空余出来时，一定有一位哲学家可以成功的得到一对餐叉，从而避免了死锁。
资源分级解法[编辑]
另一个简单的解法是为资源（这里是餐叉）分配一个偏序或者分级的关系，并约定所有资源都按照这种顺序获取，按相反顺序释放，而且保证不会有两个无关资源同时被同一项工作所需要。在哲学家就餐问题中，资源（餐叉）按照某种规则编号为1至5，每一个工作单元（哲学家）总是先拿起左右两边编号较低的餐叉，再拿编号较高的。用完餐叉后，他总是先放下编号较高的餐叉，再放下编号较低的。在这种情况下，当四位哲学家同时拿起他们手边编号较低的餐叉时，只有编号最高的餐叉留在桌上，从而第五位哲学家就不能使用任何一只餐叉了。而且，只有一位哲学家能使用最高编号的餐叉，所以他能使用两只餐叉用餐。当他吃完后，他会先放下编号最高的餐叉，再放下编号较低的餐叉，从而让另一位哲学家拿起后边的这只开始吃东西。
尽管资源分级能避免死锁，但这种策略并不总是实用的，特别是当所需资源的列表并不是事先知道的时候。例如，假设一个工作单元拿着资源3和5，并决定需要资源2，则必须先要释放5，之后释放3，才能得到2，之后必须重新按顺序获取3和5。对需要访问大量数据库记录的计算机程序来说，如果需要先释放高编号的记录才能访问新的记录，那么运行效率就不会高，因此这种方法在这里并不实用。
这种方法经常是实际计算机科学问题中最实用的解法，通过为分级锁指定常量，强制获得锁的顺序，就可以解决这个问题。
Chandy/Misra解法[编辑]
1984年，K. Mani Chandy和J. Misra提出了哲学家就餐问题的另一个解法，允许任意的用户（编号P1, ..., Pn）争用任意数量的资源。与资源分级解法不同的是，这里编号可以是任意的。

把筷子凑成对，让要吃的人先吃，没筷子的人得到一张换筷子券。
饿了，把换筷子券交给有筷子的人，有筷子的人吃饱了会把筷子交给给券的人。有了券的人不会再得到第二张券。
保证有筷子的都有得吃。

这个解法允许很大的并行性，适用于任意大的问题。
解法来自维基百科：https://zh.wikipedia.org/wiki/%E5%93%B2%E5%AD%A6%E5%AE%B6%E5%B0%B1%E9%A4%90%E9%97%AE%E9%A2%98

下面的代码其实和维基百科的解法不一样，因为代码里面先放下低编号，后高编号。但是维基百科建议先放高编号，后低编号，
因为先放高的效率更高，不过因为放叉子是不会有死锁嘛，所以一点点效率损失问题不大。

并且也给了lock.c，实现了文件版本的lock()和unlock()，理解这个lock()的实现是关键:

#include
#include
#include
#include
#include"apue.h"

void initlock(const char *lockfile)
{
int i;

unlink(lockfile);
}

void lock(const char *lockfile)
{
int fd;
while ( (fd = open(lockfile, O_RDONLY | O_CREAT | O_EXCL, FILE_MODE)) < 0)
sleep(1);
close(fd);
}

void unlock(const char *lockfile)
{
unlink(lockfile);
}

C 语言 lock(): 同时指定open()的 O_CREAT 和 O_EXCL 位，可用于判断文件是否存在(书中第48页)。fd<0表示文件已存在，于是sleep1秒，然后继续尝试。如果文件不存在，则创建文件，创建后，别人则无法再创建该文件。通过这样的方式来模拟lock，即该叉子(文件)已被某哲学家(进程)使用(创建)，在叉子未放下(未删除)前，其他人不能使用(创建)。对应的unlock()就是删除该文件。
可以通过下图来进一步了解该lock：

文章图片
文件版的lock实现
实验的大部分代码，《实验指导》中已经给出。

// 定义5个文件，分别表示5个叉子。其文件名可以按如下方式说明：
static char* forks[5] = {“fork0“, “fork1“, “fork2“, “fork3“, “fork4“};

// 哲学家的行为可以用如下函数描述：
voidphilosopher(int i)
{
while(1) {
thinking(i, nsecs); // 哲学家i思考nsecs秒
takeFork(i); // 哲学家i拿起叉子
eating(i, nsecs); // 哲学家i进餐nsecs秒
putFork(i); // 哲学家i放下叉子
}
}

// 在主程序里，可以用下面的程序段生成5个哲学家进程：
#defineN 5
for(i = 0; i < N; i++) {
pid = fork();
if( pid == 0 )
philosopher(i)；
// …………………
}
wait(NULL); /* 注意，如果父进程不等待子进程的结束，那么需要终止程序运行时，就只能从控制台删除在后台运行的哲学家进程 */

// 拿起叉子可以如此定义：
void takeFork(i)
{
if( i == N - 1 ) {
lock( forks[0] );
lock( forks[i] );
}
else {
lock( fork[i] );
lock( fork[i + 1] );
}
}

// 放下叉子可以如此定义：
void putFork(i)
{
if( i == N - 1 ) {
unlock( forks[0] );
unlock( forks[i] );
}
else {
unlock( fork[i] );
unlock( fork[i + 1] );
}
}

C 语言上面的代码基本无需修改，只要再补充输入参数的检验、think()、eating()就可以了，这个实验重在理解，理解了就非常简单了（代码都给得这么细了…）
比较重要的是 takeFork() ，前面说了哲学家一旦拿到其中的一个叉子就不放下，直到拿到另一个叉子并进餐后才把两个叉子都放下。这种思路的前提是保证哲学家中同时存在左撇子和右撇子，上面给出的代码，其实就是人为将第N个哲学家（编号N-1）设为右撇子，其他人是左撇子。你自己在图上画个圈表示哲学家跟叉子，都编上号，你就明白了。
还有一个点是僵尸进程，主程序中使用了 wait(NULL) 来避免僵尸进程的发生，为何？自己翻书吧…
使用 ps au 可以查看当前用户运行的程序，如运行 ./philosopher 时，新开一个终端并运行 ps au，如下图，可以看到有6个 philosopher 进程（1个主进程，5个子进程），当结束 ./philosopher 后，再运行 ps au 将不会看到 philosopher 进程，否则就是产生了僵尸进程。

文章图片
使用ps au来查看运行的程序
最后，程序每次运行的结果都不太一样。例如一开始五个哲学家都进入思考状态，这五条状态的输出顺序不固定，你跑程序时就会发现这一点了，Why？还是自己翻书去吧… 有一点需要注意的是，执行 sleep(1) 时，进程并不会精准的休眠1秒，知道这点有助于你理解程序的运行。
题外话
做实验时有给同学讲解了下，主要是讲了 lock() 的实现和左右撇子的问题，但从实验过程来看，一些同学对 fork() 还是不够了解，比如 fork() 创建的子进程，子进程是从哪里执行的这些都还不是很了解：
使用 fork() 创建子进程后，子进程是从 fork() 的位置继续执行。所以上面给的程序中，子进程实际上是会继续执行主程序里的 for 循环的（若是完整的执行流程，philosopher() 会运行 31 次）。但因为 philopher() 中是 while(1) 循环，因此每个子进程中就一直各自在不断执行一个philosopher()，即可以模拟5个哲学家。
所以还是建议做实验前好好看下书中相关内容，真的，对 fork() 都不太了解的话，实验一的简单 shell 你是怎么做的？这样你确定你期末上机考试能过么… 做这些实验还是得多思考，多翻书的，要真正明白整个实验所涉及的知识点。
实验讲解PPT 把PPT放出来好了(已转成PDF): UNIX实验四讲解PPT下载
完整代码代码编译时要将 lock.c 一起编译：

gcc philosopher.c error2e.c lock.c -o philosopher

Shell 命令【模拟“五个哲学家”问题_Unix环境高级编程】 代码中的结果输出顺带输出了当前时间，只是方便查看结果，实验并不要求，提交代码时也不该输出时间，请自行删去。

#include "apue.h"
#include "time.h"

#define N 5
static char* forks[N] = {"fork0", "fork1", "fork2", "fork3", "fork4"};
static int nsecs = 2;

/* 显示时间，方便查看结果，提交时应删除 */
static char now[80];
char* getTime() {
time_t tim;
struct tm *at;
time(&tim);
at=localtime(&tim);
strftime(now, 79, "%H:%M:%S", at);
return now;
}

/*
* 拿叉子的定义
* 如果哲学家中同时存在左撇子和右撇子，则哲学家问题有解
*/
void takeFork(int i) {
if(i == N-1) { // 人为设定第N-1位哲学家是右撇子
lock(forks[0]);
lock(forks[i]);
} else { // 其他是左撇子
lock(forks[i]);
lock(forks[i+1]);
}
}

/* 放下叉子 */
void putFork(int i) {
if(i == N-1) {
unlock(forks[0]);
unlock(forks[i]);
}
else {
unlock(forks[i]);
unlock(forks[i+1]);
}
}

void thinking(int i, int nsecs) {
printf("philosopher %d is thinking\t%s\n", i, getTime());
sleep(nsecs);
}

void eating(int i, int nsecs) {
printf("philosopher %d is eating\t\t%s\n", i, getTime());
sleep(nsecs);
}

/* 哲学家行为 */
void philosopher(int i) {
while(1) {
thinking(i, nsecs); // 哲学家i思考nsecs秒
takeFork(i); // 哲学家i拿起叉子
eating(i, nsecs); // 哲学家i进餐nsecs秒
putFork(i); // 哲学家i放下叉子
}
}

int main(int argc, char * argv[]) {
int i;
pid_t pid;

/* 初始化叉子 */
for(i = 0; i < N; i++) {
initlock(forks[i]);
}

/* 处理输入 */
if(argc == 3 && strcmp(argv[1], "-t") == 0) {
nsecs = atoi(argv[2]);
// if (!nsecs) err_quit("usage: philosopher [ -t ]");
} else if (argc != 1) {
err_quit("usage: philosopher [ -t ]");
}

/* 创建五个子进程来模拟五个哲学家 */
for(i = 0; i < N; i++) {
pid = fork();
if (pid == 0) {
philosopher(i);
} else if (pid < 0) {
err_quit("fork error");
}
}

wait(NULL); /* 注意，如果父进程不等待子进程的结束，*/
/* 那么需要终止程序运行时，就只能从控制台删除在后台运行的哲学家进程 */
}