- Programming practice - The title comes from songjingshan 《linuxc》
The dining problem of philosophers . This was done by computer scientists Dijkstra The classic deadlock scenario .
There are five philosophers in the original story ( But the program we write can have N Philosophers ), These philosophers do only two things －－ Think and eat , They don't need any shared resources to think , But you must use tableware when you eat , The tableware on the table is limited , In the original story , The cutlery is a fork , When eating, you should use two forks to take the noodles out of the bowl . Obviously, it would be more reasonable to replace the fork with chopsticks , therefore ： A philosopher needs two chopsticks to eat .
Now introduce the key to the problem ： These philosophers are poor , I can only afford five chopsticks . They sit in a circle , Put a chopstick between two people . Philosophers must have both left and right chopsticks when they eat . If anyone around him is using chopsticks , Then he has to wait .
Suppose the philosopher's number is A、B、C、D、E, Chopsticks number is 1、2、3、4、5, Philosophers and chopsticks form a circle, as shown in the figure below ：
chart 35.2. The question of philosophers
Each philosopher is a separate thread , Each thread loop does the following ： reflection rand()%10 second , Then take the left-hand chopsticks first and then the right-hand chopsticks （ Chopsticks can be used as a resource mutex Express ）, If you can't get either side, you'll be waiting , Take it all and eat rand()%10 second , Then put down the chopsticks .
Write a program to simulate the dining scene of philosophers ：
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
...The solution is referenced from 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 Semaphore parameters , It means that each quick chopstick can only be picked up by one person at the same time
12 sem_t r;// Pick up the semaphore parameter of the left chopstick , There can only be 4 People pick up their left chopsticks , Otherwise, there will be a lock of life and death
13 int philosophers[NUM] = {0,1,2,3,4};// Philosopher array , Express 5 A philosopher 0,1,2,3,4,
14
15 pthread_mutex_t chops[NUM];// Mutex is the control variable of the lock
16
17 //int Islocked[NUM] = {0};// The array of control variables needed to implement the mutex
18 // Multiple threads call the usual... At the same time swap It is easy to cause instruction misdirection when executing a function, thus affecting the result
19 // And we use intel X86 The instruction set of provides instructions for exchanging two numbers xchg, Register control does not have concurrency
20 //void xchg(int *x,int *y){// Exchange instructions in assembly
21 // __asm__("xchgl %0, %1" : "=r" (*x) : "m" (*y));
22 //}
23
24 // Core function ( Use semaphores to control up to 4 I picked up the left chopsticks to prevent deadlock )
25 void *philosopher(void *arg){//arg from init The fourth parameter of the function is passed
26 int i = *((int *)arg);//i On behalf of the i Philosophers
27 int left = i;// The chopsticks on the left are set to i
28 int right = (i+1)%NUM;// Cyclic queue structure , Set the chopsticks on the right as i+1
29 //int leftkey;// You need to implement the left mutex by yourself key Variable
30 //int rightkey;// You need to implement the right mutex by yourself key Variable
31 while(1){
32 //leftkey = 1;
33 //rightkey = 1;
34
35 printf(" philosopher %d Thinking \n",i);
36 sleep(rand()%NUM);// The process is suspended for some time , The representative thought for a while
37
38 printf(" philosopher %d I'm hungry \n",i);
39
40 sem_wait(&r);// Semaphore r - 1( if r=0 Suspend waiting ,r>0 You can obtain thread resources to perform subsequent operations ,r Can't <0)
41 sem_wait(&chopsticks[left]);// Note that each chopsticks The semaphore of is only 1 individual
42 pthread_mutex_lock(&chops[left]);
43 //do{
44 //xchg(&leftkey,&Islocked[left]);// here leftkey For the wrong 1, Will 1 In exchange for Islocked[left]
45 // So when the second thread comes in, it will block in do_while Loop to lock critical resources . namely linux Inside mutex function
46 //}while(leftkey);
47 printf(" philosopher %d Pick it up %d Chopsticks no. , Now there is only one chopstick , No meals \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(" philosopher %d Pick it up %d Chopsticks no. , Now there are only two chopsticks , Start eating \n",i,right);
55 sleep(rand()%NUM);// The process is suspended for some time , It means eating for a period of time
56
57 //Islocked[left] = 0;// At present, after a left chopstick signal is executed, the second thread can enter
58 sem_post(&chopsticks[left]);
59 pthread_mutex_unlock(&chops[left]);
60 printf(" philosopher %d Put it down %d Chopsticks no. \n",i,left);
61
62 //Islocked[right] = 0;// At present, after a left chopstick signal is executed, the second thread can enter
63 sem_post(&chopsticks[right]);
64 pthread_mutex_unlock(&chops[right]);
65 printf(" philosopher %d Put it down %d Chopsticks no. \n",i,right);
66
67 sem_post(&r);// Release resources , Semaphore +1, The pending semaphore can then be awakened at the same time >0 The thread of
68
69 }
70 }
71 int main(int argc,char **argv){
72 srand(time(NULL));
73 pthread_t PHD[NUM];// Thread group to be opened
74
75 int i= 0;
76 for(i = 0;i < NUM; i++){
77 sem_init(&chopsticks[i],0,1);// Semaphore initialization , Each chopstick can only be picked up once at the same time
78 }
79 sem_init(&r,0,4);// Semaphore control variable r, The control signal of picking up the left chopsticks at the same time cannot exceed 4
80
81 int j = 0;
82 for(j = 0; j < NUM; j++){
83 pthread_mutex_init(&chops[j],NULL);// Initialization of mutex
84 }
85
86 int k = 0;
87 for(k = 0; k < NUM; k++){
88 pthread_create(&PHD[k],NULL,philosopher,&philosophers[k]);// establish 5 A philosopher's thread of behavior
89 }
90
91 int l = 0;
92 for(l = 0; l < NUM; l++){
93 pthread_join(PHD[l],NULL);// Wait for each thread to terminate , Change these threads from the termination state to detach State and reclaim the resources occupied by the thread
94 }
95
96 int m = 0;
97 for(m = 0; m < NUM; m++){
98 sem_destroy(&chopsticks[m]);// Release semaphore related resources occupied by variables
99 }
100 sem_destroy(&r);// ditto , Release the semaphore resources occupied by the left chopstick monitoring
101
102 int n = 0;
103 for(n = 0; n < NUM; n++){
104 pthread_mutex_destroy(&chops[n]);// Destroy mutex , Release resources
105 }
106
107 return 0;
108 }
Here I am linux Environmental use mutex Realization , stay windows Environment can be commented out while-do-while Loop to simulate the implementation of mutexes mutex, It can also run successfully and get results ！
gcc philosopher_mutex.c -o philosopher_mutex -lpthread
./philosopher
