The sixth experiment report of operating system -- using semaphore to solve the problem of philosophers' meal

0 personal information

  • Zhang yingzi
  • 201821121038
  • Calculation 1812

1 purpose of the experiment

  • Learn more about semaphores by programming.

2 experiment content

  • On the server, we use Vim to write a program: use semaphore to solve any classical PV problem, test the result, and explain the running result.

3. Experiment report

3.1 choosing philosophers to eat

Five philosophers share a round table, sitting on five chairs around them. There are five bowls and five chopsticks on the round table. Their way of life is to think and eat alternately. Usually, when a philosopher is hungry, he tries to use the chopsticks closest to him. He can only eat when he has two chopsticks. After dinner, put down your chopsticks and continue to think.

3.2 pseudo code

Analysis: chopsticks on the round table are critical resources, and only one philosopher is allowed to use them for a period of time. In order to realize the mutually exclusive use of chopsticks, a semaphore is used to represent a chopstick, and the semaphore array is composed of these five semaphores:

semaphore chopstick[5]={1,1,1,1,1};

When all semaphores are initialized to 1, the activities of the ith philosopher can be described as follows:

do{
    /*When philosophers are hungry, they always pick up the chopsticks on the left and then the chopsticks on the right*/
    wait(chopstick[i]);           //Pick up the left chopsticks
    wait(chopstick[(i+1)%5]);     //Pick up the right chopsticks
    eat();                        //Eating
    /*When philosophers finish eating, they always put down the chopsticks on the left and then the chopsticks on the right*/
    signal(chopstick[i]);         //Put down the left chopsticks
    signal(chopstick[i+1]%5);     //Put down the right chopsticks
    think();                      //reflection
    }while(true);

But in the above case, if the five philosophers are hungry at the same time and pick up the chopsticks on the left, they will make the five semaphores chopstick 0; and when they try to take the chopsticks on the right again, they will cause infinite waiting and deadlock due to no chopsticks to take.

Therefore, the above algorithm needs to be improved to restrict the philosopher to pick up his chopsticks AND eat only when both chopsticks are available. It can be realized by AND semaphore mechanism, or by semaphore protection mechanism. The idea of using semaphore protection mechanism is to protect the operation of taking left AND right chopsticks by recording semaphore mutex, making it an atomic operation, which can prevent deadlock. The simplest solution can be obtained by using AND semaphore mechanism.

① using the recorded semaphore:

semaphore mutex = 1; // This process needs to judge whether two chopsticks are available and protect them
semaphore chopstick[5]={1,1,1,1,1};
void philosopher(int i)
{
    while(true)
    {
        /* In this process, only one person can eat. It's inefficient. There are five chopsticks. In fact, two people can eat at the same time */
        think();                        //reflection
        wait(mutex);                    //Protection semaphore
        wait(chopstick[(i+1)%5]);       //Request chopsticks on the right
        wait(chopstick[i]);             //Request chopsticks on the left
        signal(mutex);                  //Release protection semaphore
        eat();                 //Eating                
        signal(chopstick[(i+1)%5]);     //Release the chopsticks on the right
        signal(chopstick[i]);           //Release the chopsticks on the left
    }
}

② AND semaphore is used to realize:

semaphore chopstick[5]={1,1,1,1,1};
do{
    think();        //reflection
    Swait(chopstick[(i+1)%5],chopstick[i]);   //Request chopsticks
    eat();           //Eating
    Ssignal(chopstick[(i+1)%5],chopstick[i]); //Release chopsticks
}while(true);

3.3 complete code

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <string.h>
  4 #include <stdint.h>
  5 #include <stdbool.h>
  6 #include <errno.h>
  7 #include <unistd.h>
  8 #include <sys/types.h>
  9 #include <sys/stat.h>
 10 #include <sys/ipc.h>
 11 #include <sys/sem.h>
 12 #include <sys/wait.h>
 13  
 14  
 15 union semun
 16 {
 17     int val;
 18     struct semid_ds *buf;
 19     unsigned short *array;
 20     struct seminfo *__buf;
 21 };
 22  
 23 #define ERR_EXIT(m) \
 24     do { \
 25         perror(m); \
 26         exit(EXIT_FAILURE); \
 27     } while(0)
 28      
 29 //Request a resource
 30 int    wait_1chop(int no,int semid)
 31 {    
 32     //Resources minus 1
 33     struct sembuf sb = {no,-1,0};
 34     int ret;
 35     ret = semop(semid,&sb,1);
 36     if(ret < 0) {
 37         ERR_EXIT("semop");
 38     }
 39     return ret;
 40 }
 41  
 42 // Release a resource
 43 int free_1chop(int no,int semid)
 44 {
 45     //Resource plus 1
 46     struct sembuf sb = {no,1,0};
 47     int ret;
 48     ret = semop(semid,&sb,1);
 49     if(ret < 0) {
 50         ERR_EXIT("semop");
 51     }
 52     return ret;
 53 }
 54  
 55 //Chopsticks is a critical resource
 56 #define DELAY (rand() % 5 + 1)
 57  
 58 //amount to P operation
 59 //The first parameter is the number of chopsticks
 60 //The second parameter is the semaphore number
 61 void wait_for_2chop(int no,int semid)
 62 {
 63     //The number of chopsticks on the left of philosopher is the same as that of philosopher
 64     int left = no;
 65     //Chopsticks on the right
 66     int right = (no + 1) % 5;
 67  
 68     //Chopsticks are worth two
 69     //Two semaphores are operated,That is, both resources are satisfied,Operation only
 70     struct sembuf buf[2] = {
 71         {left,-1,0},
 72         {right,-1,0}
 73     };
 74     //There are five semaphores in the signal set, only for the resources sembuf Operate
 75     semop(semid,buf,2);
 76 }
 77  
 78 //amount to V operation  ,Release chopsticks
 79 void free_2chop(int no,int semid)
 80 {
 81     int left = no;
 82     int right = (no + 1) % 5;
 83     struct sembuf buf[2] = {
 84         {left,1,0},
 85         {right,1,0}
 86     };
 87     semop(semid,buf,2);
 88 }
 89  
 90  
 91 //What philosophers do
 92 void philosophere(int no,int semid)
 93 {
 94     srand(getpid());
 95     for(;;) 
 96     {
 97     #if 1
 98         //When both chopsticks are available, philosophers can eat
 99         printf("%d is thinking\n",no);  //Thinking
100         sleep(DELAY);
101         printf("%d is hungry\n",no);    //hunger
102         wait_for_2chop(no,semid); //Two chopsticks to eat
103         printf("%d is eating\n",no);    //Eating
104         sleep(DELAY);
105         free_2chop(no,semid); //Release two chopsticks
106     #else
107         //May cause deadlock
108         int left = no;
109         int right = (no + 1) % 5;
110         printf("%d is thinking\n",no);  //Thinking
111         sleep(DELAY); 
112         printf("%d is hungry\n",no);    //hunger
113         wait_1chop(left,semid);         //Pick up the left chopsticks (apply as long as there is one resource)
114         sleep(DELAY);            
115         wait_1chop(right,semid);        //Pick up the right chopsticks
116         printf("%d is eating\n",no);    //Eating
117         sleep(DELAY);
118         free_1chop(left,semid);         //Release the left chopsticks
119         free_1chop(right,semid);          //Release the right chopsticks
120     #endif
121     }
122 }
123  
124  
125 int main(int argc,char *argv[])
126 {
127     int semid;
128     //Create a semaphore set with 5 semaphores
129     semid = semget(IPC_PRIVATE,5,IPC_CREAT | 0666); 
130     if(semid < 0) {
131         ERR_EXIT("semid");
132     }
133     union semun su;
134     su.val = 1;
135     int i;
136     for(i = 0;i < 5; ++i) {
137         //The second parameter is also the index
138         semctl(semid,i,SETVAL,su);
139     }
140     //Create 4 subprocesses
141     int num = 0;
142     pid_t pid;
143     for(i = 1;i < 5;++i) 
144     {
145        pid = fork(); 
146        if(pid < 0) 
147         {
148            ERR_EXIT("fork");
149         }
150         if(0 == pid)  //Subprocess
151         {
152             num = i;
153             break;
154         }
155     }
156     //What philosophers do
157    philosophere(num,semid);
158     return 0;
159 }

3.4 operation results

3.5 interpretation of operation results

At the beginning, five philosophers are thinking. After a period of time, philosopher 3 is hungry. After applying for two chopsticks, he can start to eat. At this time, philosophers 2, 4 and 1 are also hungry. But because philosophers 2 and 4 are adjacent to philosophers 3, they need to wait until they put down their chopsticks after eating on the third. At this time, philosopher 1 can eat. Then, philosopher 0 was hungry, but because chopsticks were still on philosopher 1, we had to wait. Then the third philosopher finished his meal and began to think that the fourth philosopher could eat. Philosopher 1 finished his meal and began to think that philosopher 2 could eat. No. 3 philosopher is hungry, No. 4 philosopher has finished eating, and starts to think, No. 0 philosopher can eat. Wait for philosopher 2 to finish eating and start thinking. Philosopher 3 can start eating

Note that when the neighboring philosophers need to wait until the left and right chopsticks can be used, they can eat at the same time. Therefore, if the philosophers are five, at most two of them can eat at the same time.

4 References

Tags: Linux Programming vim

Posted on Thu, 28 May 2020 00:52:24 -0700 by gbuck