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

实验所给的《UNIX环境高级编程实验指导.doc》中其实已经给出了本实验的详细思路：主要就是利用文件来进行进程间的通信。

实验描述

编制模拟“五个哲学家”问题的程序，学习和掌握并发进程同步的概念和方法。

要求：

1、程序语法，是哲学家进餐和沉思的持续时间值，缺省值为2秒。

philosopher [ -t ]

2、五个哲学家的编号为0~4，分别用五个进程独立模拟。
3、程序的输出要简洁，仅输出每个哲学家进餐和沉思的信息。例如，当编号为3的哲学家在进餐时，就打印：
philosopher 3 is eating
而当他在沉思时，则打印：
philosopher 3 is thinking
除此之外不要输出其他任何信息。
4、利用课堂已教授的知识而不使用线程或IPC机制进行同步。

实验思路

哲学家就餐问题有多种解决思路可以避免死锁的发生，《实验指导》中的思路时，哲学家一旦拿到其中的一个叉子就不放下，直到拿到另一个叉子并进餐后才把两个叉子都放下。这种思路的前提是保证哲学家中同时存在左撇子和右撇子，则不会发生死锁。

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

#include  <sys/types.h>
#include  <sys/stat.h>
#include  <fcntl.h>
#include  <unistd.h>
#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);
}

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

可以通过下图来进一步了解该lock：

实验的大部分代码，《实验指导》中已经给出。

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

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

// 在主程序里，可以用下面的程序段生成5个哲学家进程：
#define   N 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] );
  }
}

上面的代码基本无需修改，只要再补充输入参数的检验、think()、eating()就可以了，这个实验重在理解，理解了就非常简单了（代码都给得这么细了...）

比较重要的是 takeFork() ，前面说了哲学家一旦拿到其中的一个叉子就不放下，直到拿到另一个叉子并进餐后才把两个叉子都放下。这种思路的前提是保证哲学家中同时存在左撇子和右撇子，上面给出的代码，其实就是人为将第N个哲学家（编号N-1）设为右撇子，其他人是左撇子。你自己在图上画个圈表示哲学家跟叉子，都编上号，你就明白了。

还有一个点是僵尸进程，主程序中使用了 wait(NULL) 来避免僵尸进程的发生，为何？自己翻书吧...

使用 ps au 可以查看当前用户运行的程序，如运行 ./philosopher 时，新开一个终端并运行 ps au，如下图，可以看到有6个 philosopher 进程（1个主进程，5个子进程），当结束 ./philosopher 后，再运行 ps au 将不会看到 philosopher 进程，否则就是产生了僵尸进程。

最后，程序每次运行的结果都不太一样。例如一开始五个哲学家都进入思考状态，这五条状态的输出顺序不固定，你跑程序时就会发现这一点了，Why？还是自己翻书去吧... 有一点需要注意的是，执行 sleep(1) 时，进程并不会精准的休眠1秒，知道这点有助于你理解程序的运行。

题外话

做实验时有给同学讲解了下，主要是讲了 lock() 的实现和左右撇子的问题，但从实验过程来看，一些同学对 fork() 还是不够了解，比如 fork() 创建的子进程，子进程是从哪里执行的这些都还不是很了解：

使用 fork() 创建子进程后，子进程是从 fork() 的位置继续执行。所以上面给的程序中，子进程实际上是会继续执行主程序里的 for 循环的（若是完整的执行流程，philosopher() 会运行 31 次）。但因为 philopher() 中是 while(1) 循环，因此每个子进程中就一直各自在不断执行一个philosopher()，即可以模拟5个哲学家。

所以还是建议做实验前好好看下书中相关内容，真的，对 fork() 都不太了解的话，实验一的简单 shell 你是怎么做的？这样你确定你期末上机考试能过么... 做这些实验还是得多思考，多翻书的，要真正明白整个实验所涉及的知识点。

完整代码

代码编译时要将 lock.c 一起编译：

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

代码中的结果输出顺带输出了当前时间，只是方便查看结果，实验并不要求，提交代码时也不该输出时间，请自行删去。

#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 <time> ]");
  } else if (argc != 1) {
    err_quit("usage: philosopher [ -t <time> ]");
  }

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

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

厦大数据库实验室博客

实验描述

实验思路

题外话

完整代码