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

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

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

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

4、LOSOPHER（phi_num）函數(shù)來模擬每個(gè)哲學(xué)家進(jìn)入哲學(xué)家進(jìn)餐問題活動(dòng)。三、 主要問題的解決方法和關(guān)鍵技術(shù)1.共享狀態(tài)數(shù)組問題。問題描述：因?yàn)闋顟B(tài)數(shù)組是共享的，而每個(gè)模擬哲學(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)建一個(gè)共享內(nèi)存區(qū)，并將狀態(tài)數(shù)組地址鏈接到進(jìn)程地址空間，成功的解決了該問題。2.信號(hào)量創(chuàng)建及初始化問題問題描述：整個(gè)程序使用兩個(gè)不同的信號(hào)量，一個(gè)是記錄型信號(hào)量數(shù)組，一個(gè)是互斥信號(hào)量，并且在信號(hào)量創(chuàng)建初就需要對(duì)信號(hào)量進(jìn)行初始化，這樣才能保證接

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

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

7、題。 解決方法：通過在各個(gè)函數(shù)參數(shù)列表中添加需要指向?qū)⑹褂玫腜和V函數(shù)指針，并在使用時(shí)采用（*P）和（*V）形式來解除引用操作，成功的解決了編譯錯(cuò)誤問題。四、 程序流程圖約定： Take_forks 函數(shù)動(dòng)作 TKFK Put_forks 函數(shù)動(dòng)作 PTFK Test 函數(shù)動(dòng)作 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é)家動(dòng)作-*/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)建信號(hào)量操作-*/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,