乐趣区

关于线程同步:多线程之经典死锁场景及其解决哲学家就餐问题

  1. 编程练习 - 题目来源于宋劲杉《linuxc》
    哲学家就餐问题。这是由计算机科学家 Dijkstra 提出的经典死锁场景。

原版的故事里有五个哲学家 (不过咱们写的程序能够有 N 个哲学家),这些哲学家们只做两件事--思考和吃饭,他们思考的时候不须要任何共享资源,然而吃饭的时候就必须应用餐具,而餐桌上的餐具是无限的,原版的故事里,餐具是叉子,吃饭的时候要用两把叉子把面条从碗里捞进去。很显然把叉子换成筷子会更正当,所以:一个哲学家须要两根筷子能力吃饭。

当初引入问题的要害:这些哲学家很穷,只买得起五根筷子。他们坐成一圈,两个人的两头放一根筷子。哲学家吃饭的时候必须同时失去左手边和右手边的筷子。如果他身边的任何一位正在应用筷子,那他只有等着。

假如哲学家的编号是 A、B、C、D、E,筷子编号是 1、2、3、4、5,哲学家和筷子围成一圈如下图所示:

图 35.2. 哲学家问题

每个哲学家都是一个独自的线程,每个线程循环做以下动作:思考 rand()%10 秒,而后先拿左手边的筷子再拿右手边的筷子(筷子这种资源能够用 mutex 示意),有任何一边拿不到就始终等着,全拿到就吃饭 rand()%10 秒,而后放下筷子。

编写程序仿真哲学家就餐的场景:

Philosopher A fetches chopstick 5
Philosopher B fetches chopstick 1
Philosopher B fetches chopstick 2
Philosopher D fetches chopstick 3
Philosopher B releases chopsticks 1 2
Philosopher A fetches chopstick 1
Philosopher C fetches chopstick 2
Philosopher A releases chopsticks 5 1
...

解决方案参考自 https://blog.csdn.net/theLost…

  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 NUM 5
 10 
 11 sem_t chopsticks[NUM];//sem_t 信号量参数,示意每根快筷子最多只能同时被一人拿起
 12 sem_t r;// 拿起左筷子的信号量参数,只能同时有 4 人拿起左筷子,否则后产生死锁
 13 int philosophers[NUM] = {0,1,2,3,4};// 哲学家数组,示意 5 位哲学家 0,1,2,3,4,
 14 
 15 pthread_mutex_t chops[NUM];// 互斥量即锁的控制变量
 16 
 17 //int Islocked[NUM] = {0};// 本人实现互斥锁须要的控制变量数组
 18 // 多个线程同时调用通常的 swap 函数的时候容易产生指令错排从而影响后果
 19 // 而咱们应用 intel X86 的指令集中提供了替换两数的指令 xchg,寄存器管制不会呈现并发的状况
 20 //void xchg(int *x,int *y){// 汇编中的替换指令
 21 //    __asm__("xchgl %0, %1" : "=r" (*x) : "m" (*y));
 22 //}
 23 
 24 // 外围函数 (利用信号量管制最多 4 集体拿起左筷子来杜绝死锁的产生)
 25 void *philosopher(void *arg){//arg 由 init 函数的第四个参数传递而来
 26     int i = *((int *)arg);// i 代表第 i 个哲学家
 27     int left = i;// 右边的筷子设为 i
 28     int right = (i+1)%NUM;// 循环队列构造, 左边筷子设为 i +1 
 29     //int leftkey;// 本人实现左互斥锁须要的 key 变量
 30     //int rightkey;// 本人实现右互斥锁须要的 key 变量
 31     while(1){
 32        //leftkey = 1;
 33        //rightkey = 1;
 34 
 35         printf("哲学家 %d 正在思考 \n",i);
 36         sleep(rand()%NUM);// 过程挂起一段时间,代表思考了一会
 37 
 38         printf("哲学家 %d 饿了 \n",i);
 39 
 40         sem_wait(&r);// 信号量 r - 1(若 r = 0 则挂起期待,r>0 则能够取得线程资源执行后续操作,r 不会 <0)
 41         sem_wait(&chopsticks[left]);// 留神每个 chopsticks 的信号量只有 1 个
 42         pthread_mutex_lock(&chops[left]);
 43         //do{44            //xchg(&leftkey,&Islocked[left]);// 此时 leftkey 为非 1,会将 1 替换给 Islocked[left]
 45             // 于是第二个线程进来时就会阻塞在 do_while 循环实现临界资源的锁定。即 linux 外面的 mutex 性能
 46         //}while(leftkey);
 47         printf("哲学家 %d 拿起了 %d 号筷子, 当初只有一支筷子, 不能进餐 \n",i,left);
 48 
 49         //do{50             //xchg(&rightkey,&Islocked[right]);
 51         //}while(rightkey);
 52         sem_wait(&chopsticks[right]);
 53         pthread_mutex_lock(&chops[right]);
 54         printf("哲学家 %d 拿起了 %d 号筷子, 当初只有两支筷子, 开始进餐 \n",i,right);
 55         sleep(rand()%NUM);// 过程挂起一段时间,代表吃了一段时间完结
 56 
 57         //Islocked[left] = 0;// 以后一个拿左筷子信号执行完就能够让第二个线程进入
 58         sem_post(&chopsticks[left]);
 59         pthread_mutex_unlock(&chops[left]);
 60         printf("哲学家 %d 放下了 %d 号筷子 \n",i,left);
 61 
 62         //Islocked[right] = 0;// 以后一个拿左筷子信号执行完就能够让第二个线程进入
 63         sem_post(&chopsticks[right]);
 64         pthread_mutex_unlock(&chops[right]);
 65         printf("哲学家 %d 放下了 %d 号筷子 \n",i,right);
 66 
 67         sem_post(&r);// 开释资源,信号量 +1,于是能够同时唤醒挂起期待信号量 >0 的线程
 68 
 69     }
 70 }
 71 int main(int argc,char **argv){72     srand(time(NULL));
 73     pthread_t PHD[NUM];// 要开拓的线程组
 74 
 75     int i= 0;
 76     for(i = 0;i < NUM; i++){77         sem_init(&chopsticks[i],0,1);// 信号量初始化,每只筷子只能同时被拿起一次
 78     }
 79     sem_init(&r,0,4);// 信号量控制变量 r, 管制同时拿起左筷子的信号不能超过 4
 80 
 81     int j = 0;
 82     for(j = 0; j < NUM; j++){83         pthread_mutex_init(&chops[j],NULL);// 互斥锁的初始化
 84     }
 85 
 86     int k = 0;
 87     for(k = 0; k < NUM; k++){88         pthread_create(&PHD[k],NULL,philosopher,&philosophers[k]);// 创立 5 个哲学家的行为线程
 89     }
 90 
 91     int l = 0;
 92     for(l = 0; l < NUM; l++){93         pthread_join(PHD[l],NULL);// 期待每个线程终止,将这些线程由终止态变为 detach 态并发出线程所占用的资源
 94     }
 95 
 96     int m = 0;
 97     for(m = 0; m < NUM; m++){98         sem_destroy(&chopsticks[m]);// 开释变量所占用的信号量相干资源
 99     }
100     sem_destroy(&r);// 同上,开释左筷子监控占用的信号量资源
101 
102     int n = 0;
103     for(n = 0; n < NUM; n++){104         pthread_mutex_destroy(&chops[n]);// 销毁互斥锁,开释资源
105     }
106 
107     return 0;
108 }

我这里是在 linux 环境下应用 mutex 实现,在 windows 环境下能够用正文掉的 while-do-while 循环来模仿实现互斥锁 mutex, 也能胜利运行失去后果!
gcc philosopher_mutex.c -o philosopher_mutex -lpthread

./philosopher

退出移动版