Classic deadlock scenario of multithreading and its solution (philosopher dining problem)

  1. 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

  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>
  9 #define NUM 5
 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,
 15 pthread_mutex_t chops[NUM];//Mutex is the control variable of the lock
 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 //}
 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;
 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
 38         printf("philosopher%d Hungry\n",i);
 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);
 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
 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);
 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);
 67         sem_post(&r);//Release the resource, semaphore + 1, so you can wake up the thread waiting for semaphore > 0 at the same time
 69     }
 70 }
 71 int main(int argc,char **argv){
 72     srand(time(NULL));
 73     pthread_t PHD[NUM];//Thread group to open
 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
 81     int j = 0;
 82     for(j = 0; j < NUM; j++){
 83         pthread_mutex_init(&chops[j],NULL);//Initialization of mutex
 84     }
 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     }
 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     }
 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
102     int n = 0;
103     for(n = 0; n < NUM; n++){
104         pthread_mutex_destroy(&chops[n]);//Destroy mutex and release resources
105     }
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


Keywords: linux-kernel

Added by jason.carter on Sun, 20 Feb 2022 11:08:25 +0200