操作系统第六次实验报告——使用信号量解决哲学家进餐问题

操作系统第六次实验报告——使用信号量解决哲学家进餐问题

使用信号量解决哲学家进餐问题

0 个人信息

• 张樱姿
• 201821121038
• 计算1812

1 实验目的

• 通过编程进一步了解信号量。

2 实验内容

• 在服务器上用Vim编写一个程序：使用信号量解决任一个经典PV问题，测试给出结果，并对运行结果进行解释。

3 实验报告

　　3.1 选择哲学家进餐问题

　　　五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五只筷子，他们的生活方式是交替地进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐毕，放下筷子继续思考。

　　3.2 伪代码

　　　　分析：放在圆桌上的筷子是临界资源，在一段时间内只允许一位哲学家的使用。为了实现对筷子的互斥使用，使用一个信号量表示一只筷子，由这五个信号量构成信号量数组：

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

　　　　所有信号量均被初始化为1，则第i位哲学家的活动可描述为：

do{ /*当哲学家饥饿时，总是先拿起左边的筷子，再拿起右边的筷子*/ wait(chopstick[i]);   //拿起左筷子 wait(chopstick[(i+1)%5]);  //拿起右筷子 eat();      //进餐 /*当哲学家进餐完成后，总是先放下左边的筷子，再放下右边的筷子*/ signal(chopstick[i]);   //放下左筷子 signal(chopstick[i+1]%5);  //放下右筷子 think();      //思考 }while(true);

 　　　　但是在上述情况中，假如五位哲学家同时饥饿而各自拿起左边的筷子时，就会使五个信号量chopstick均为0；而当他们再试图去拿右边的筷子时，都将因无筷子可拿造成无限的等待，产生死锁。

　　　   因此，需要对上述算法进行改进，限制仅当哲学家左右的两只筷子都可用时，才允许他拿起筷子进餐。可以利用AND 型信号量机制实现，也可以利用信号量的保护机制实现。利用信号量的保护机制实现的思想是通过记录型信号量mutex对取左侧和右侧筷子的操作进行保护，使之成为一个原子操作，这样可以防止死锁的出现。利用AND型信号量机制可获得最简洁的解法。

　　　　①使用记录信号量实现：

semaphore mutex = 1; // 这个过程需要判断两根筷子是否可用，并保护起来semaphore chopstick[5]={1,1,1,1,1};void philosopher(int i){ while(true) {  /* 这个过程中可能只能由一个人在吃饭，效率低下，有五只筷子，其实是可以达到两个人同时吃饭 */  think();      //思考  wait(mutex);     //保护信号量  wait(chopstick[(i+1)%5]);  //请求右边的筷子  wait(chopstick[i]);    //请求左边的筷子  signal(mutex);     //释放保护信号量  eat();　　　　　　　　　　　　　 //进餐　　　　　　　　　　　　　　　　  signal(chopstick[(i+1)%5]);  //释放右手边的筷子  signal(chopstick[i]);   //释放左手边的筷子 }}

　　　　  ②使用AND型信号量实现：

semaphore chopstick[5]={1,1,1,1,1};do{ think();  //思考 Swait(chopstick[(i+1)%5],chopstick[i]); //请求筷子 eat();   //进餐 Ssignal(chopstick[(i+1)%5],chopstick[i]); //释放筷子}while(true);

　　3.3 完整代码

 1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 #include <stdint.h> 5 #include <stdbool.h> 6 #include <errno.h> 7 #include <unistd.h> 8 #include <sys/types.h> 9 #include <sys/stat.h> 10 #include <sys/ipc.h> 11 #include <sys/sem.h> 12 #include <sys/wait.h> 13  14  15 union semun 16 { 17  int val; 18  struct semid_ds *buf; 19  unsigned short *array; 20  struct seminfo *__buf; 21 }; 22  23 #define ERR_EXIT(m) \ 24  do { \ 25   perror(m); \ 26   exit(EXIT_FAILURE); \ 27  } while(0) 28   29 //申请一个资源 30 int wait_1chop(int no,int semid) 31 {  32  //资源减1 33  struct sembuf sb = {no,-1,0}; 34  int ret; 35  ret = semop(semid,&sb,1); 36  if(ret < 0) { 37   ERR_EXIT("semop"); 38  } 39  return ret; 40 } 41  42 // 释放一个资源 43 int free_1chop(int no,int semid) 44 { 45  //资源加1 46  struct sembuf sb = {no,1,0}; 47  int ret; 48  ret = semop(semid,&sb,1); 49  if(ret < 0) { 50   ERR_EXIT("semop"); 51  } 52  return ret; 53 } 54  55 //筷子是一个临界资源 56 #define DELAY (rand() % 5 + 1) 57  58 //相当于P操作 59 //第一个参数是筷子编号 60 //第二个参数是信号量编号 61 void wait_for_2chop(int no,int semid) 62 { 63  //哲学家左边的筷子编号和哲学家编号是一样的 64  int left = no; 65  //右边的筷子 66  int right = (no + 1) % 5; 67  68  //筷子值是两个 69  //操作的是两个信号量,即两种资源都满足,才进行操作 70  struct sembuf buf[2] = { 71   {left,-1,0}, 72   {right,-1,0} 73  }; 74  //信号集中有5个信号量，只是对其中的资源sembuf进行操作 75  semop(semid,buf,2); 76 } 77  78 //相当于V操作 ,释放筷子 79 void free_2chop(int no,int semid) 80 { 81  int left = no; 82  int right = (no + 1) % 5; 83  struct sembuf buf[2] = { 84   {left,1,0}, 85   {right,1,0} 86  }; 87  semop(semid,buf,2); 88 } 89  90  91 //哲学家要做的事 92 void philosophere(int no,int semid) 93 { 94  srand(getpid()); 95  for(;;)  96  { 97  #if 1 98   //当两只筷子都可用的时候，哲学家才能进餐 99   printf("%d is thinking\n",no); //思考中100   sleep(DELAY);101   printf("%d is hungry\n",no); //饥饿102   wait_for_2chop(no,semid); //拿到两只筷子才能吃饭103   printf("%d is eating\n",no); //进餐104   sleep(DELAY);105   free_2chop(no,semid); //释放两只筷子106  #else107   //可能会造成死锁108   int left = no;109   int right = (no + 1) % 5;110   printf("%d is thinking\n",no); //思考中111   sleep(DELAY); 112   printf("%d is hungry\n",no); //饥饿113   wait_1chop(left,semid);   //拿起左筷子（只要有一个资源就申请）114   sleep(DELAY);   115   wait_1chop(right,semid);  //拿起右筷子116   printf("%d is eating\n",no); //进餐117   sleep(DELAY);118   free_1chop(left,semid);   //释放左筷子119   free_1chop(right,semid);   //释放右筷子120