哲学家就餐问题

1、实验一1、 实验名称：哲学家就餐问题的实现2、 实验学时：23、 实验内容和目的：实验目的：实现哲学家就餐问题，要求不能出现死锁。通过本实验熟悉Linux系统的基本环境，了解Linux下进程和线程的实现。实验内容：在Unix系统下实现教材2.4.2节中所描述的哲学家就餐问题。要求显示出每个哲学家的工作状态，如吃饭，思考。连续运行30次以上都未出现死锁现象。4、 实验原理： 由Dijkstra提出并解决的哲学家进餐问题(The Dinning Philosophers Problem)是典型的同步问题。该问题是描述有五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五只筷子，他

2、们的生活方式是交替地进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐完毕，放下筷子继续思考。5、 实验器材（设备、元器件）（1） 学生每人一台PC，安装WindowsXP/2000操作系统。（2） 局域网络环境。（3） 个人PC安装VMware虚拟机和Ubuntu系统。6、 实验内容：（一） 熟悉Ubuntu系统下的多线程编程。（二）实现哲学家就餐问题1. 算法思想 规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子，而偶数号哲学家则相反。按此规定，将是1、2号哲学家竞争1号筷子；3、4号哲学家竞争3号筷子。即五位哲学家都

3、生竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而进餐。2. 流程图开始正在进餐正在等待 否否正在思考 是是否放下左右手筷子拿起左右手筷子是状态为等待状态为思考 状态为进餐结束3. 程序代码（重要代码请注释）#include <stdio.h>#include <pthread.h>#include <semaphore.h>#include <stdlib.h>#include <string.h>#define NOC 5/number of chopstic#define NOP 5/number

4、 of philosophersem_t chopsticNOC; /semaphoreint flag5;/philosopher's statusvoid *eat(int i)int position;int temp = 0;int j = (i+1)%NOC;position = i%2;while(1)if(position = 0)/odd take left firstsem_wait(&chopstici);printf("philosopher%d get %dn", i, i);sem_wait(&chopsticj);prin

5、tf("philosopher%d get %dn", i, j);flagi = 1;/philosopher is eatingprintf("waitting:");/print others' statuswhile(temp < 5)if(!flagtemp)printf("philosopher%dt", temp);temp+;temp = 0;printf("n");printf("eating:");/print others' statuswhile(t

6、emp < 5)if(flagtemp)printf("philosopher%dt", temp);temp+;printf("nn");temp = 0;/printf("nphilosopher%d is eatingnn", i);sleep(2);flagi = 0;printf("philosopher%d put %dn", i, i);sem_post(&chopstici);printf("philosopher%d put %dn", i, j);sem_pos

7、t(&chopsticj);else/even take right firstsem_wait(&chopsticj);printf("philosopher%d get %dn", i, j);sem_wait(&chopstici);printf("philosopher%d get %dn", i, i);flagi = 1;printf("waitting:");while(temp < 5)if(!flagtemp)printf("philosopher%dt", temp

8、);temp+;temp = 0;printf("n");printf("eating:");while(temp < 5)if(flagtemp)printf("philosopher%dt", temp);temp+;printf("nn");temp = 0;/printf("nphilosopher%d is eatingnn", i);sleep(2);flagi = 0;printf("philosopher%d put %dn", i, j);sem_po

9、st(&chopsticj);printf("philosopher%d put %dn", i, i);sem_post(&chopstici);int main(void)int i = 0;int error;pthread_t philosopherNOP;/init semwhile(i < 5)flagi = 0;sem_init(&chopstici, 0, 1);i+;i = 0;/create threadwhile(i < 5)error = pthread_create(&philosopheri, NULL

10、, (void *)eat, (void *)i);if(error)printf("error:create thread failed!n");exit(0);i+;i = 0;/destroy threadwhile(i < 5)pthread_join(philosopheri, NULL);i+;i = 0;/destroy semwhile(i < 5)sem_destroy(&chopstici);i+;return 0;7、 实验及结果分析：运行结果：udbwxfsoubuntu:/Desktop/sy2$ gcc gphilosophe

11、r.c -pthreadudbwxfsoubuntu:/Desktop/sy2$ ./a.outphilosopher4 get 4philosopher4 get 0waitting:philosopher0philosopher1philosopher2philosopher3eating:philosopher4philosopher2 get 2philosopher2 get 3waitting:philosopher0philosopher1philosopher3eating:philosopher2philosopher4philosopher4 put 4philosophe

12、r4 put 0philosopher4 get 4philosopher4 get 0waitting:philosopher0philosopher1philosopher3eating:philosopher2philosopher4philosopher2 put 2philosopher2 put 3philosopher2 get 2philosopher2 get 3waitting:philosopher0philosopher1philosopher3eating:philosopher2philosopher4philosopher4 put 4philosopher3 g

13、et 4philosopher4 put 0philosopher0 get 0philosopher0 get 1waitting:philosopher1philosopher3philosopher4eating:philosopher0philosopher2philosopher2 put 2philosopher2 put 3philosopher2 get 2philosopher2 get 3waitting:philosopher1philosopher3philosopher4eating:philosopher0philosopher2philosopher2 put 2

14、philosopher2 put 3philosopher2 get 2philosopher2 get 3waitting:philosopher1philosopher3philosopher4eating:philosopher0philosopher2经分析可知，放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用，为了实现对筷子的互斥使用，用一个信号量表示一只筷子，由这五个信号量组成信号量数组。若哲学家饥饿时总是先拿其左边的筷子，成功后，再去拿右边的筷子，容易造成死锁。当规定奇数号哲学家先拿起右边筷子，然后再去拿左边筷子，而偶数号哲学家则相反后，死锁现象得到了解决。8、 实验结论、心得体会和改进建议：通过这次操作系统的实验，我了解到了进程的创建及进行，明白了死锁产生的原因和一些解决的办法，