给力星

Web Developer

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

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

实验描述

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

要求:

1、程序语法,

philosopher [ -t <time> ]

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:

文件版的lock实现文件版的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 进程,否则就是产生了僵尸进程。

使用ps au来查看运行的程序使用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

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

#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); /* 注意,如果父进程不等待子进程的结束,*/
                /* 那么需要终止程序运行时,就只能从控制台删除在后台运行的哲学家进程 */
}