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

0 personal information

• Zhang yingzi
• 201821121038
• Calculation 1812

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