利用信號量機(jī)制解決哲學(xué)家進(jìn)餐問題

1、成績：課程設(shè)計報告課程名稱：課程設(shè)計（UNIX程序設(shè)計）設(shè)計題目：利用信號量機(jī)制解決哲學(xué)家進(jìn)餐問題姓 名：專 業(yè)：網(wǎng) 絡(luò) 工 程班 級：學(xué) 號：計算機(jī)科學(xué)與技術(shù)學(xué)院網(wǎng)絡(luò)系2013年 12月 28日哈爾濱理工大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院網(wǎng)絡(luò)系實(shí)驗室 實(shí)驗報告設(shè)計項目： 利用信號量機(jī)制解決哲學(xué)家進(jìn)餐問題 一、 選題背景 1965年，數(shù)學(xué)家迪杰斯特拉提出，并成為經(jīng)典的IPC問題哲學(xué)家進(jìn)餐問題。該問題的簡單描述如下：五個哲學(xué)家圍坐在一張圓桌周圍，每個哲學(xué)家面前都一盤通心粉。由于通心粉很滑，需要兩把叉子才能夾住。哲學(xué)家的生活中有兩種交替活動時段，吃飯（EATING）和思考（THINKING）。當(dāng)一個哲學(xué)家覺

2、得餓了時，他就試圖分兩次去取左手邊和右手邊的叉子，每次拿一把，但不分次序。如果成功拿到兩把叉子，就進(jìn)入吃飯狀態(tài)，吃完后放下叉子繼續(xù)思考。二、 設(shè)計思路1.每個哲學(xué)家的行為活動狀態(tài)為兩種：進(jìn)餐（EATING）和思考（THINKING）。因此創(chuàng)建一個有5個元素的狀態(tài)數(shù)組，每個數(shù)組元素的狀態(tài)值為EATING或者THINKING。2.五個哲學(xué)家圍坐成一圈，每兩個人中間有一個叉子，即每個哲學(xué)家的邊和右邊有一個叉子，但這個叉子需要和旁邊的鄰居競爭使用。對于每一個哲學(xué)家來說，其只有成功獲得兩個叉子，才能進(jìn)入進(jìn)餐狀態(tài)。在進(jìn)完餐后，需要成功放下手中的兩個叉子，才能進(jìn)入思考的狀態(tài)。換個角度的描述就是，每個哲學(xué)家查

3、詢左右邊的鄰居當(dāng)前狀態(tài)，如果左右的鄰居當(dāng)前狀態(tài)都為THINKING，則該哲學(xué)家可以進(jìn)餐；如果左右鄰居當(dāng)前狀態(tài)不都是THINKING，則哲學(xué)家不能進(jìn)餐。因此可以為每一個哲學(xué)家設(shè)置一個信號量，來描述哲學(xué)家的活動狀態(tài)。3.因為五只叉子做多只能允許兩個哲學(xué)家進(jìn)餐，所以可以將桌子作為一個臨界資源。通過設(shè)置一個互斥信號量來限制對臨界資源的訪問數(shù)。4.創(chuàng)建兩個動作函數(shù)，對應(yīng)于每個哲學(xué)家的獲取兩把叉子和放下兩把叉子的動作。而每個動作都需要對互斥信號量和哲學(xué)家信號量進(jìn)行訪問操作，因此創(chuàng)建原子操作P和原子操作V，來執(zhí)行對信號量的消耗和釋放操作。5.利用父進(jìn)程創(chuàng)建五個子進(jìn)程來模擬五個哲學(xué)家，在每個子進(jìn)程中執(zhí)行PHI

4、LOSOPHER（phi_num）函數(shù)來模擬每個哲學(xué)家進(jìn)入哲學(xué)家進(jìn)餐問題活動。三、 主要問題的解決方法和關(guān)鍵技術(shù)1.共享狀態(tài)數(shù)組問題。問題描述：因為狀態(tài)數(shù)組是共享的，而每個模擬哲學(xué)家的子進(jìn)程是相互獨(dú)立的，有自己的地址空間，在進(jìn)程之間共享使用狀態(tài)數(shù)組出現(xiàn)問題。解決方法：父進(jìn)程通過利用UNIX系統(tǒng)進(jìn)程通信機(jī)制中共享內(nèi)存機(jī)制的shmget()和shmat系統(tǒng)調(diào)用創(chuàng)建一個共享內(nèi)存區(qū)，并將狀態(tài)數(shù)組地址鏈接到進(jìn)程地址空間，成功的解決了該問題。2.信號量創(chuàng)建及初始化問題問題描述：整個程序使用兩個不同的信號量，一個是記錄型信號量數(shù)組，一個是互斥信號量，并且在信號量創(chuàng)建初就需要對信號量進(jìn)行初始化，這樣才能保證接

5、下來的子進(jìn)程運(yùn)行時，五個子進(jìn)程面對的是相同值的信號量數(shù)組。解決方法：父進(jìn)程通過利用UNIX系統(tǒng)進(jìn)程通信機(jī)制中信號量機(jī)制的semget（）系統(tǒng)調(diào)用和semctl()系統(tǒng)調(diào)用，成功創(chuàng)建一個五元素的信號量數(shù)組和一個元素的信號量數(shù)組，并將其在初始為設(shè)計的初始值，保證了程序后續(xù)操作的正確。3.P和V原子操作問題問題描述：在子進(jìn)程中的對信號量的操作必須是原子操作P和V，而且由于在動作函數(shù)中需要調(diào)用P和V原子操作，所以必須保證P和V操作的原子性，否則函數(shù)之間參數(shù)的傳遞將出現(xiàn)不一致。解決方法：利用UNIX系統(tǒng)進(jìn)程通信機(jī)制中信號量機(jī)制的semop（）系統(tǒng)調(diào)用，封裝P和V操作函數(shù)，保證了函數(shù)的原子性。4.進(jìn)程創(chuàng)建

6、的準(zhǔn)確時刻問題問題描述：根據(jù)設(shè)計的描述，程序是通過五個子進(jìn)程來模擬五個哲學(xué)家，但對進(jìn)程創(chuàng)建的先后順序沒有要求，又由于進(jìn)程分配到時間片是有限的，并且在創(chuàng)建的過程中要保證五個子進(jìn)程都是統(tǒng)一父進(jìn)程創(chuàng)建的，所以對于進(jìn)程的創(chuàng)建時刻不太容易確定。解決方法：利用的UNIX系統(tǒng)的進(jìn)程創(chuàng)建fork（）系統(tǒng)調(diào)用，創(chuàng)建一個有五個子進(jìn)程的進(jìn)程扇，成功的解決創(chuàng)建準(zhǔn)確時刻問題 5.哲學(xué)家動作函數(shù)編譯問題 問題描述：在哲學(xué)家的三個動作函數(shù)中需要對兩個類型的信號量進(jìn)行操作，所以不可避免的需要調(diào)用P和V原子操作。盡管在動作函數(shù)定義之前，已經(jīng)聲明了P和V函數(shù)。但是由于其原子性，在動作函數(shù)中直接使用P，V函數(shù)導(dǎo)致了嚴(yán)重的編譯錯誤問

7、題。 解決方法：通過在各個函數(shù)參數(shù)列表中添加需要指向?qū)⑹褂玫腜和V函數(shù)指針，并在使用時采用（*P）和（*V）形式來解除引用操作，成功的解決了編譯錯誤問題。四、 程序流程圖約定： Take_forks 函數(shù)動作 TKFK Put_forks 函數(shù)動作 PTFK Test 函數(shù)動作 TEST THINKING 思考狀態(tài) THINK EATING 進(jìn)餐狀態(tài) EAT THINKTKFK ？ N YTEST ？ N Y EATPTFK ？ Y N五、 原程序清單#include<stdio.h>#include<unistd.h>#include<assert.h>#

8、include<sys/types.h>#include<sys/ipc.h>#include<sys/sem.h>#include<assert.h>#include<sys/shm.h>#include<signal.h>#include<stdlib.h>#define N 5#define LEFT(i) (i+N-1)%N#define RIGHT(i) (i+1)%N#define THINKING 0#define EATING 1/#include"behavior_philosoph

9、y.h"void philosopher(int , char*, int , int , void (*)(int, int), void (*)(int, int);void take_forks(int , char* , int , int ,void (*)(int, int), void (*)(int, int);void put_forks(int , char* , int , int ,void (*)(int, int), void (*)(int, int);void test(int , char* , int ,void (*)(int, int);voi

10、d think(int );void eat(int );void P(int , int );void V(int , int );/*-哲學(xué)家動作-*/void philosopher(int i, char* state, int sem_phiid, int sem_mutexid, void (*P)(int, int), void (*V)(int, int) sleep(1); think(i); while(1) take_forks(i, state, sem_phiid, sem_mutexid, P, V); eat(i); put_forks(i, state, sem

11、_phiid, sem_mutexid, P, V); think(i); void take_forks(int i, char* state, int sem_phiid, int sem_mutexid, void (*P)(int, int) , void (*V)(int, int) (*P)(sem_mutexid, 0); statei = THINKING; test(i, state, sem_phiid, V); (*V)(sem_mutexid, 0); (*P)(sem_phiid, i);void put_forks(int i, char* state, int s

12、em_phiid, int sem_mutexid,void (*P)(int, int), void (*V)(int, int) (*P)(sem_mutexid, 0); statei = THINKING; test(LEFT(i), state, sem_phiid, V); test(RIGHT(i), state, sem_phiid, V); (*V)(sem_mutexid, 0);void test(int i, char* state, int sem_phiid,void (*V)(int, int) if(statei = THINKING && st

13、ateLEFT(i) != EATING && stateRIGHT(i)!=EATING) statei = EATING; (*V)(sem_phiid, i); void think(int i) printf("philosopher:%d>>>>>is THINKING.n", i);void eat(int i) printf("I'm philosopher:%d>>>>>is EATING.and will eating %d seconds!n", i,

14、 sleep(2);/*-P,V原子操作-*/void P(int semid, int index) struct sembuf sema_buffer; sema_buffer.sem_num = index; sema_buffer.sem_op = -1; sema_buffer.sem_flg = SEM_UNDO; semop(semid, &sema_buffer, 1);void V(int semid, int index) struct sembuf sema_buf; sema_buf.sem_num = index; sema_buf.sem_op = 1; s

15、ema_buf.sem_flg = SEM_UNDO; semop(semid, &sema_buf, 1);/*-*/int main( )/*-創(chuàng)建信號量操作-*/int sem_phiid;sem_phiid = semget(1008, 5, 0666|IPC_CREAT);assert(sem_phiid>=0);unsigned short array5 = 0, 0, 0, 0, 0;union semunint val;unsigned short *array;semopts;semopts.array=array;int ret1 = semctl(sem_p

16、hiid, 0, SETALL, semopts);assert(ret1 = 0);int sem_mutexid;sem_mutexid = semget(0x225, 1, 0666|IPC_CREAT);assert(sem_mutexid >= 0);semopts.val = 1;int ret2 = semctl(sem_mutexid, 0, SETVAL, semopts);assert(ret2 = 0);/*-初始化共享內(nèi)存-*/int shmid;char* state;if(shmid = shmget(IPC_PRIVATE, N, 0600|IPC_CREA

17、T) = -1) semctl(sem_phiid, 0, IPC_RMID, 0);semctl(sem_mutexid, 0, IPC_RMID, 0);perror("shmget faild!");exit(1);if(state = shmat(shmid, 0, 0) = (char *)-1) semctl(sem_phiid, 0, IPC_RMID, 0);semctl(sem_mutexid, 0, IPC_RMID, 0);perror("shmat faild!");exit(1);/*-*/ int i, phinum; pid_t pid; for(i=0; i<5; i+) while(pid = fork() = -1); if(!pid) phinum = i; signal(SIGINT, SIG_DFL); break;if(pid>0) while(wait(int *)0) = -1);semctl(sem_phiid, 0, IPC_RMID, 0);semctl(sem_mutexid, 0, IPC_RMID, 0);shmdt(state);printf("Hi,