0 個人信息 張櫻姿 201821121038 計算1812 1 實驗目的 通過編程進一步瞭解信號量。 2 實驗內容 在伺服器上用Vim編寫一個程式：使用信號量解決任一個經典PV問題，測試給出結果，並對運行結果進行解釋。 3 實驗報告 3.1 選擇哲學家進餐問題 五個哲學家共用一張圓桌，分別坐在周圍 ...
0 個人信息
- 張櫻姿
- 201821121038
- 計算1812
1 實驗目的
- 通過編程進一步瞭解信號量。
2 實驗內容
- 在伺服器上用Vim編寫一個程式：使用信號量解決任一個經典PV問題，測試給出結果，並對運行結果進行解釋。
3 實驗報告
3.1 選擇哲學家進餐問題
五個哲學家共用一張圓桌，分別坐在周圍的五張椅子上，在圓桌上有五個碗和五隻筷子，他們的生活方式是交替地進行思考和進餐。平時，一個哲學家進行思考，饑餓時便試圖取用其左右最靠近他的筷子，只有在他拿到兩隻筷子時才能進餐。進餐畢，放下筷子繼續思考。
3.2 偽代碼
分析：放在圓桌上的筷子是臨界資源，在一段時間內只允許一位哲學家的使用。為了實現對筷子的互斥使用，使用一個信號量表示一隻筷子，由這五個信號量構成信號量數組：
semaphore chopstick[5]={1,1,1,1,1};
所有信號量均被初始化為1，則第i位哲學家的活動可描述為：
do{ /*當哲學家饑餓時，總是先拿起左邊的筷子，再拿起右邊的筷子*/ wait(chopstick[i]); //拿起左筷子 wait(chopstick[(i+1)%5]); //拿起右筷子 eat(); //進餐 /*當哲學家進餐完成後，總是先放下左邊的筷子，再放下右邊的筷子*/ signal(chopstick[i]); //放下左筷子 signal(chopstick[i+1]%5); //放下右筷子 think(); //思考 }while(true);
但是在上述情況中，假如五位哲學家同時饑餓而各自拿起左邊的筷子時，就會使五個信號量chopstick均為0；而當他們再試圖去拿右邊的筷子時，都將因無筷子可拿造成無限的等待，產生死鎖。
因此，需要對上述演算法進行改進，限制僅當哲學家左右的兩隻筷子都可用時，才允許他拿起筷子進餐。可以利用AND 型信號量機制實現，也可以利用信號量的保護機制實現。利用信號量的保護機制實現的思想是通過記錄型信號量mutex對取左側和右側筷子的操作進行保護，使之成為一個原子操作，這樣可以防止死鎖的出現。利用AND型信號量機制可獲得最簡潔的解法。
①使用記錄信號量實現：
semaphore mutex = 1; // 這個過程需要判斷兩根筷子是否可用，並保護起來 semaphore chopstick[5]={1,1,1,1,1}; void philosopher(int i) { while(true) { /* 這個過程中可能只能由一個人在吃飯，效率低下，有五隻筷子，其實是可以達到兩個人同時吃飯 */ think(); //思考 wait(mutex); //保護信號量 wait(chopstick[(i+1)%5]); //請求右邊的筷子 wait(chopstick[i]); //請求左邊的筷子 signal(mutex); //釋放保護信號量 eat(); //進餐 signal(chopstick[(i+1)%5]); //釋放右手邊的筷子 signal(chopstick[i]); //釋放左手邊的筷子 } }
②使用AND型信號量實現：
semaphore chopstick[5]={1,1,1,1,1}; do{ think(); //思考 Swait(chopstick[(i+1)%5],chopstick[i]); //請求筷子 eat(); //進餐 Ssignal(chopstick[(i+1)%5],chopstick[i]); //釋放筷子 }while(true);
3.3 完整代碼
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 //申請一個資源 30 int wait_1chop(int no,int semid) 31 { 32 //資源減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 // 釋放一個資源 43 int free_1chop(int no,int semid) 44 { 45 //資源加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 //筷子是一個臨界資源 56 #define DELAY (rand() % 5 + 1) 57 58 //相當於P操作 59 //第一個參數是筷子編號 60 //第二個參數是信號量編號 61 void wait_for_2chop(int no,int semid) 62 { 63 //哲學家左邊的筷子編號和哲學家編號是一樣的 64 int left = no; 65 //右邊的筷子 66 int right = (no + 1) % 5; 67 68 //筷子值是兩個 69 //操作的是兩個信號量,即兩種資源都滿足,才進行操作 70 struct sembuf buf[2] = { 71 {left,-1,0}, 72 {right,-1,0} 73 }; 74 //信號集中有5個信號量，只是對其中的資源sembuf進行操作 75 semop(semid,buf,2); 76 } 77 78 //相當於V操作 ,釋放筷子 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 //哲學家要做的事 92 void philosophere(int no,int semid) 93 { 94 srand(getpid()); 95 for(;;) 96 { 97 #if 1 98 //當兩隻筷子都可用的時候，哲學家才能進餐 99 printf("%d is thinking\n",no); //思考中 100 sleep(DELAY); 101 printf("%d is hungry\n",no); //饑餓 102 wait_for_2chop(no,semid); //拿到兩隻筷子才能吃飯 103 printf("%d is eating\n",no); //進餐 104 sleep(DELAY); 105 free_2chop(no,semid); //釋放兩隻筷子 106 #else 107 //可能會造成死鎖 108 int left = no; 109 int right = (no + 1) % 5; 110 printf("%d is thinking\n",no); //思考中 111 sleep(DELAY); 112 printf("%d is hungry\n",no); //饑餓 113 wait_1chop(left,semid); //拿起左筷子（只要有一個資源就申請） 114 sleep(DELAY); 115 wait_1chop(right,semid); //拿起右筷子 116 printf("%d is eating\n",no); //進餐 117 sleep(DELAY); 118 free_1chop(left,semid); //釋放左筷子 119 free_1chop(right,semid); //釋放右筷子 120 #endif 121 } 122 } 123 124 125 int main(int argc,char *argv[]) 126 { 127 int semid; 128 //創建信號量集，其中有5個信號量 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 //第二個參數也是索引 138 semctl(semid,i,SETVAL,su); 139 } 140 //創建4個子進程 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) //子進程 151 { 152 num = i; 153 break; 154 } 155 } 156 //哲學家要做的事情 157 philosophere(num,semid); 158 return 0; 159 }
3.4 運行結果
3.5 解釋運行結果
一開始，五個哲學家都在思考，一段時間後，3號哲學家饑餓，申請兩隻筷子滿足後可以開始進餐，此時2號、4號和1號哲學家也餓了，但由於2號、4號與3號哲學家相鄰，因此，他們需要等待3號進餐完畢放下筷子後，才可以進餐。而此時1號哲學家是可以進餐的。接著，0號哲學家饑餓，但由於筷子還在1號哲學家上，因此需要等待。然後3號哲學家進餐完畢，開始思考，4號哲學家可以進餐。1號哲學家進餐完畢，開始思考，2號哲學家可以進餐。3號哲學家饑餓，4號哲學家進餐完畢，開始思考，0號哲學家可以進餐。等2號哲學家進餐完畢，開始思考，3號哲學家可以開始進餐……
註意到當相鄰的哲學家需要等到左右的筷子都可以使用時才可以進餐，因此如果哲學家是五位時，最多能有兩位不相鄰哲學家可以同時就餐。
4 References
- https://blog.csdn.net/Yun_Ge/article/details/89177918
- https://blog.csdn.net/u014304293/article/details/46004677
