1. 选择哪一个问题

哲学家进餐问题

2. 给出伪代码

问题描述
　　哲学家就餐问题(Dining philosophers problem)是在计算机科学中的一个经典问题，用来演示在并发计算中多线程同步时产生的问题。在1971年，著名的计算机科学家艾兹格·迪科斯彻提出了一个同步问题，即假设有五台计算机都试图访问五份共享的磁带驱动器。稍后，这个问题被托尼·霍尔重新表述为哲学家就餐问题。这个问题可以用来解释死锁和资源耗尽。哲学家就餐问题可以这样表述，假设有五位哲学家围坐在一张圆形餐桌旁，做以下两件事情之一：吃饭，或者思考。吃东西的时候，他们就停止思考，思考的时候也停止吃东西。餐桌中间有一大碗意大利面，每两个哲学家之间有一只餐叉。因为用一只餐叉很难吃到意大利面，所以假设哲学家必须用两只餐叉吃东西。他们只能使用自己左右手边的那两只餐叉。哲学家就餐问题有时也用米饭和筷子而不是意大利面和餐叉来描述，因为很明显，吃米饭必须用两根筷子。

哲学家从来不交谈，这就很危险，可能产生死锁，每个哲学家都拿着左手的餐叉，永远都在等右边的餐叉（或者相反）。

void philosopher(int i)    // i:哲学家编号,从0到4
{
   while(TRUE)
   {
       think();               // 哲学家思考
       take_fork(i);         //饿了,拿起左叉子
       take_fork((i+1)%N); // 拿起右叉子
       eat();               // 进食
       put_fork(i);          // 放下左叉子
       put_fork((i+1)%N); // 放下右叉子
   }
}

容易出现死锁用的是记录型信号量,伪代码为:

semaphore fork fork[5] = {1,1,1,1,1};

do
   {
       //think
       wait(fork[i]);
       wait(fork[(i+1)%5]);
       //eat
       signal(fork[i]);
       signal(fork[(i+1)%5]);
   }while(true)

没有死锁用的是AND信号量解决的,伪代码为:
semaphore fork fork[5] = {1,1,1,1,1};

do
   {
       //think
       Sswait(fork[i],fork[(i+1)%5]);
       //eat
       Ssignal(fork[i],fork[(i+1)%5]);

3. 给出完整代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <stdbool.h>
#include <errno.h>

#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/ipc.h>
#include <sys/sem.h>
#include <sys/wait.h>

union semun
{
int val;
struct semid_ds *buf;
unsigned short *array;
struct seminfo *__buf;
};

#define ERR_EXIT(m)
do {
perror(m);
exit(EXIT_FAILURE);
} while(0)

//申请一个资源
int wait_1fork(int no,int semid)
{
//int left = no;
//int right = (no + 1) % 5;
struct sembuf sb = {no,-1,0};
int ret;
ret = semop(semid,&sb,1);
if(ret < 0) {
ERR_EXIT("semop");
}
return ret;
}

// 释放一个资源
int free_1fork(int no,int semid)
{
struct sembuf sb = {no,1,0};
int ret;
ret = semop(semid,&sb,1);
if(ret < 0) {
ERR_EXIT("semop");
}
return ret;
}

//这里表明叉子是一个临界资源

#define DELAY (rand() % 5 + 1)

//相当于P操作
void wait_for_2fork(int no,int semid)
{
//哲学家左边的刀叉编号和哲学家是一样的
int left = no;
//右边的刀叉
int right = (no + 1) % 5;

//刀叉值是两个
//注意第一个参数是编号
//操作的是两个信号量,即两种资源都满足,才进行操作
struct sembuf buf[2] = {
{left,-1,0},
{right,-1,0}
};
//信号集中有5个信号量，只是对其中的资源sembuf进行操作
semop(semid,buf,2);
}

//相当于V操作 ,释放刀叉
void free_2fork(int no,int semid)
{
int left = no;
int right = (no + 1) % 5;
struct sembuf buf[2] = {
{left,1,0},
{right,1,0}
};
semop(semid,buf,2);
}

//哲学家要做的事
void philosophere(int no,int semid)
{
srand(getpid());
//srand(time(NULL));
for(;;)
{
#if 1
//这里采取的措施是当两把刀叉都可用的时候(即两种资源都满足的时候)
//哲学家才能吃饭，这样不相邻的哲学家就可吃上饭
printf("哲学家 %d 正在思考 ",no); // 思考中
sleep(DELAY);
printf("哲学家 %d 饿了 ",no); // 感觉到饥饿
wait_for_2fork(no,semid);//拿到两把叉子才能吃饭
printf("哲学家 %d 正在进餐 ",no); // 吃饭
sleep(DELAY);
free_2fork(no,semid);//释放两把叉子
#else
//这段代码可能会造成死锁
int left = no;
int right = (no + 1) % 5;
printf("哲学家 %d 正在思考 ",no); // 思考中
sleep(DELAY);
printf("哲学家 %d 饿了 ",no); // 感觉到饥饿
wait_1fork(left,semid); // 拿起左叉子,现在是只要有一个资源,就申请
sleep(DELAY);
wait_1fork(right,semid); // 拿到右叉子
printf("哲学家 %d 正在进餐 ",no); // 吃饭
sleep(DELAY);
free_1fork(left,semid); // 释放左叉子
free_1fork(right,semid); // 释放右叉子
#endif
}
}

int main(int argc,char *argv[])
{
int semid;
//创建信号量
//信号量集中5个信号量
semid = semget(IPC_PRIVATE,5,IPC_CREAT | 0666);
if(semid < 0) {
ERR_EXIT("semid");
}
union semun su;
su.val = 1;
int i;
for(i = 0;i < 5;++i) {
//注意第二个参数也是索引
semctl(semid,i,SETVAL,su);
}
//创建4个子进程
int num = 0;
pid_t pid;
for(i = 1;i < 5;++i)
{
pid = fork();
if(pid < 0)
{
ERR_EXIT("fork");
}
if(0 == pid) // 子进程
{
num = i;
break;
}
}
//这里就是哲学家要做的事情
philosophere(num,semid);
return 0;
}

4. 运行结果并解释

　　对五个叉子分别分配信号量，只有当某个哲学家左右两侧的叉子都空闲时才允许进餐，如上图，五个哲学家都在思考，此时4号哲学家饿了，无人使用叉子，因此他可以进餐，即不让某个哲学家出现只拿一把叉子的情况出现，这样就避免的死锁的情况。