- Programming practice - the topic comes from Song Jinshan's "linuxc"
Philosopher dining problem. This is a classic deadlock scenario proposed by computer scientist Dijkstra.
There are five philosophers in the original story (but the program we wrote can have N philosophers). These philosophers only do two things - think and eat. They don't need any shared resources when thinking, but they have to use tableware when eating. The tableware on the table is limited. In the original story, the tableware is a fork, When eating, use two forks to take the noodles out of the bowl. Obviously, it would be more reasonable to replace a fork with chopsticks, so: a philosopher needs two chopsticks to eat.
Now the key to the problem is that these philosophers are very poor and can only afford five chopsticks. They sat in a circle with a chopstick between them. Philosophers must get both left-hand and right-hand chopsticks when eating. If anyone around him is using chopsticks, he has to wait.
Suppose the numbers of philosophers are A, B, C, D and E, and the numbers of chopsticks are 1, 2, 3, 4 and 5. The philosophers and chopsticks form A circle, as shown in the figure below:
Figure 35.2 Philosopher problem
Each philosopher is a separate thread. Each thread loops to do the following actions: think rand()%10 seconds, then take the left-hand chopsticks first, and then the right-hand chopsticks (chopsticks can be expressed as mutex). If you can't get them on either side, you'll wait all the time, eat rand()%10 seconds, and 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 ...
Solution reference 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 parameter, which means that each fast chopstick can only be picked up by one person at most at the same time
12 sem_t r;//When picking up the semaphore parameters of the left chopsticks, only four people can pick up the left chopsticks at the same time, otherwise they will have a life and death lock
13 int philosophers[NUM] = {0,1,2,3,4};//Philosopher array, representing 5 Philosophers 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 //When multiple threads call the usual swap function at the same time, it is easy to produce instruction misdirection, which will affect the result
19 //The instruction set of intel X86 provides the instruction xchg to exchange two numbers, and the register control will not be concurrent
20 //void xchg(int *x,int *y) {/ / exchange instruction in assembly
21 // __asm__("xchgl %0, %1" : "=r" (*x) : "m" (*y));
22 //}
23
24 //Core function (use semaphore to control up to 4 people to pick up left chopsticks to prevent deadlock)
25 void *philosopher(void *arg){//arg is passed from the fourth parameter of the init function
26 int i = *((int *)arg);//i stands for the ith philosopher
27 int left = i;//Set the chopsticks on the left as i
28 int right = (i+1)%NUM;//Circular queue structure, set chopsticks on the right as i+1
29 //int leftkey;// The key variable required to implement the left mutex
30 //int rightkey;// The key variable needed to implement the right mutex
31 while(1){
32 //leftkey = 1;
33 //rightkey = 1;
34
35 printf("philosopher%d Thinking\n",i);
36 sleep(rand()%NUM);//The process was suspended for some time and the representative thought for a while
37
38 printf("philosopher%d Hungry\n",i);
39
40 sem_wait(&r);//Semaphore R - 1 (if r=0, wait is suspended; if r > 0, thread resources can be obtained to perform subsequent operations, and R will not be < 0)
41 sem_wait(&chopsticks[left]);//Note that there is only one semaphore per chopsticks
42 pthread_mutex_lock(&chops[left]);
43 //do{
44 //xchg(&leftkey,&Islocked[left]);// At this time, the leftkey is not 1, and 1 will be exchanged to islocked [left]
45 //So when the second thread comes in, it will block in do_ The while loop locks critical resources. mutex function in linux
46 //}while(leftkey);
47 printf("philosopher%d Picked it up%d No. chopsticks,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 Picked it up%d No. chopsticks,Now there are only two chopsticks,Start eating\n",i,right);
55 sleep(rand()%NUM);//The process is suspended for a period of time, which represents the end of eating for a period of time
56
57 //Islocked[left] = 0;// At present, the second thread can enter after the execution of a signal to take the left chopstick
58 sem_post(&chopsticks[left]);
59 pthread_mutex_unlock(&chops[left]);
60 printf("philosopher%d Put it down%d No. chopsticks\n",i,left);
61
62 //Islocked[right] = 0;// At present, the second thread can enter after the execution of a signal to take the left chopstick
63 sem_post(&chopsticks[right]);
64 pthread_mutex_unlock(&chops[right]);
65 printf("philosopher%d Put it down%d No. chopsticks\n",i,right);
66
67 sem_post(&r);//Release the resource, semaphore + 1, so you can wake up the thread waiting for semaphore > 0 at the same time
68
69 }
70 }
71 int main(int argc,char **argv){
72 srand(time(NULL));
73 pthread_t PHD[NUM];//Thread group to open
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);//The semaphore control variable r controls that the 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]);//Create 5 behavioral threads for philosophers
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 termination state to detach state, and recover the resources occupied by the threads
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);//As above, 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 and release resources
105 }
106
107 return 0;
108 }
I use mutex to realize mutex in linux environment. In windows environment, the annotated while do while loop can be used to simulate mutex, which can also run successfully and get results!
gcc philosopher_mutex.c -o philosopher_mutex -lpthread
./philosopher
