- 李微微
- 201821121001
- 计算1811
1. 选择哪一个问题
- 哲学家进餐问题
-
有五个哲学家，他们的生活方式是交替地进行思考和进餐，哲学家们共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五支筷子，平时哲学家进行思考，饥饿时便试图取其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐，该哲学家进餐完毕后，放下左右两只筷子又继续思考。约束条件：(1)只有拿到两只筷子时，哲学家才能吃饭。(2)如果筷子已被别人拿走，则必须等别人吃完之后才能拿到筷子。(3)任一哲学家在自己未拿到两只筷子吃完饭前，不会放下手中已经拿到的筷子。
2. 给出伪代码
伪代码如下：
semaphore chopstick[5]; //五种信号量 semaphore m = 4； //最多四个哲学家同时拿起左筷 while(wait(num_mutex)) { wait(chopstick[i]); //拿起左筷 wait(chopstick[(i+1)%5]); //拿起右筷 sem_post(chopstick[i]); //放下左筷 sem_post(m); sem_post(chopstick[(i+1)%5]); //放下右筷 }
算法思想：至多允许有四位哲学家同时去拿左边的筷子，然后再允许拿右边的筷子。最终保证至少有一位哲学家能够进餐，并在用毕时能同时释放他用过的两只筷子，从而使更多的哲学家能够进餐。
3. 给出完整代码
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <malloc.h> 4 #include <time.h> 5 #include <unistd.h> 6 #include <pthread.h> 7 #include <semaphore.h> 8 9 #define N 5 10 11 sem_t chopsticks[N]; //设置5种信号量，有5种不同类型的资源 12 sem_t m; //最多允许4个哲学家同时拿起左筷子 13 14 int philosophers[N] = {0, 1, 2, 3, 4};//代表5个哲学家的编号 15 void delay (int len) { 16 int i = rand() % len; 17 int x; 18 while (i > 0) { 19 x = rand() % len; 20 while (x > 0) { 21 x--; 22 } 23 i--; 24 } 25 } 26 void *philosopher (void* arg) { 27 int i = *(int *)arg; 28 int left = i; //左筷编号和哲学家编号相同 29 int right = (i + 1) % N; //右筷编号为哲学家编号+1 30 while (1) { 31 printf("哲学家%d正在思考问题\n", i); 32 delay(60000); 33 printf("哲学家%d饿了\n", i); 34 sem_wait(&m); /*若前4个哲学家同时拿起左筷，第五个不能同时拿起左筷，保证至少有一位哲学家能吃到饭，解决死锁*/ 35 sem_wait(&chopsticks[left]); //此时这个哲学左筷子的信号量-1后>=0，表示能继续执行 36 37 printf("哲学家%d拿起了%d号筷子,现在只有一支筷子,不能进餐\n", i, left); 38 sem_wait(&chopsticks[right]); 39 printf("哲学家%d拿起了%d号筷子, 现在有两支筷子,开始进餐\n", i, right); 40 delay(60000); 41 sem_post(&chopsticks[left]); 42 printf("哲学家%d放下了%d号筷子\n", i, left); 43 sem_post(&m); //当哲学家释放了左筷子时，信号量m+1 44 sem_post(&chopsticks[right]); 45 printf("哲学家%d放下了%d号筷子\n", i, right); 46 } 47 } 48 49 int main (int argc, char **argv) { 50 srand(time(NULL)); 51 pthread_t philo[N]; 52 //信号量初始化 53 for (int i=0; i<N; i++) { 54 sem_init(&chopsticks[i], 0, 1); 55 } 56 sem_init(&m, 0, 4); 57 //创建线程 58 for (int i=0; i<N; i++) { 59 pthread_create(&philo[i], NULL, philosopher, &philosophers[i]); 60 } 61 //挂起线程 62 for (int i=0; i<N; i++) { 63 pthread_join(philo[i], NULL); 64 } 65 //销毁信号量 66 for (int i=0; i<N; i++) { 67 sem_destroy(&chopsticks[i]); 68 } 69 sem_destroy(&m); 70 return 0; 71 }
4. 运行结果并解释
运行结果：
解释：刚开始所有哲学家（编号0-4）都在思考，无人拿起筷子。随后，因为大家都在思考，所以哲学家1能够拿起两只筷子，同理哲学家4也能够拿着两只筷子。接着哲学家1放下两只筷子，哲学家3因为哲学家4拿走的筷子而只能拿着一只筷子，因而哲学家2和哲学家1只能分别有哲学家1放下的一只筷子……程序不断输出，不存在死锁状态。
5. 加分项
上述解决哲学家进餐问题，解决潜在死锁问题的原理是：最多允许4个哲学家同时拿起左筷，若前4个哲学家同时拿起左筷，第五个不能同时拿起左筷，保证至少有一位哲学家能吃到饭，吃完后放下筷子，以便更多人食用，解决死锁。
6. 遇到的问题
问题：编译代码时报错：undefined reference to sem_init sem_wait.......
解决：因为pthread并非Linux系统的默认库，编译时注意加上-lpthread参数，以调用链接库。
参考链接：https://blog.csdn.net/weixin_39531549/article/details/100857716