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

1、利用信號量機制解決哲學(xué)家進餐問題作者:日期:電金座外二文咨課程設(shè)計報告課程名稱:設(shè)計題目:姓名:專業(yè):班級:學(xué)號:課程設(shè)計UNIX程序設(shè)計利用信號量機制解決哲學(xué)家進餐問網(wǎng)絡(luò)工程計算機科學(xué)與技術(shù)學(xué)院網(wǎng)絡(luò)系2021年12月28日設(shè)計工程:利用信號量機制解決哲學(xué)家進餐問題一、選題背景1965年,數(shù)學(xué)家迪杰斯特拉提出,并成為經(jīng)典的IPC問題一哲學(xué)家進餐問題.該問題的簡單描述如下：五個哲學(xué)家圍坐在一張圓桌周圍,每個哲學(xué)家面前都一盤通心粉.由于通心粉很滑,需要兩把義子才能夾住.哲學(xué)家的生活中有兩種交替活動時段,吃飯(EATING)和思考(THINKING).當(dāng)一個哲學(xué)家覺得餓了時,他就試圖分兩次去取左手邊

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

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

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

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

6、時刻問題問題描述：根據(jù)設(shè)計的描述,程序是通過五個子進程來模擬五個哲學(xué)家,但對進程創(chuàng)建的先后順序沒有要求,乂由于進程分配到時間片是有限的,并且在創(chuàng)立的過程中要保證五個子進程都是統(tǒng)一父進程創(chuàng)立的,所以對于進程的創(chuàng)立時刻不太容易確定.解決方法：利用的UNIX系統(tǒng)的進程創(chuàng)立fork()系統(tǒng)調(diào)用,創(chuàng)立一個有五個子進程的進程扇,成功的解決創(chuàng)立準(zhǔn)確時刻問題5 .哲學(xué)家動作函數(shù)編譯問題問題描述：在哲學(xué)家的三個動作函數(shù)中需要對兩個類型的信號量進行操作,所以不可防止的需要調(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ù)動作TKFKPut_forks函數(shù)動作PTFKTest函數(shù)動作TESTTHINKING思考狀態(tài)THINKEATING進餐狀態(tài)EAT五、原程序清單#include<stdio.h>#include<unistd.h>#include<assert.h>#include<sys/types.h>#include<sys/ipc.h>#include<

8、;sys/sem.h>#include<assert.h>#include<sys/shm.h>#include<signal.h>#include<stdlib.h>#defineN5defineLEFT(i)(i+N-l)%NSdefineRIGHT(i)(i+l)%NSdefineTHINKING0SdefineEATING1/#include,zbehavior_philosophy.hvoidphilosopher(int,char*,int,int,void(*)(int,int),void(*)(int,int);voidta

9、ke_forks(int,char*,int,int,void(*)(int,int),void(*)(int,int);voidput_forks(int,char*,int,int,void(*)(int,int),void(*)(int,int);voidtest(int,char*,int,void(*)(int,int);voidthink(int);voideat(int);voidP(int,int);voidV(int,int);/*哲學(xué)家動作*/voidphilosopher(inti,char*state,intsem_phiid,intsem_mutexid,void(*

10、P)(int,int),void(*V)(int,int)sleep(l);think(i);while(1)take_forks(i,state,sem_phiid,sem_mutexid,P,V);eat(i);put_forks(i,state,sem_phiid,sem_mutexid,P,V);think(i);)voidtake_forks(inti,char*state,intsem_phiid,intsem_mutexid,void(*P)(int,int),void(*V)(int,int)(*P)(sem_mutexid,0);stateEi二THINKING;test(i

11、,state,sem_phiid,V);(*V)(sem_mutexid,0);(*P)(sem_phiid,i);)voidput_forks(inti,char*state,intsem_phiid,intsem_mutexid,void(*P)(int,int),void(*V)(int,int)(*P)(sem_mutexid,0);stateEi=THINKING;test(LEFT(i),state,sem-phiid,V);test(RIGHT(i),state,sem_phiid,V);(*V)(sem_mutexid,0);)voidtest(inti,char*state,

12、intsem_phiid,void(*V)(int,int)if(stateEi=THINKING&&stateLEFT(i)!=EATING&&stateRIGHT(i)!=EATING)stateEi=EATING;(*V)(sem_phiid,i);)voidthink(inti)printf(''philosopher：%d»»>isTHINKING.n,z,i);)voideat(inti)printf(/zrmphilosopher：%d»»>isEATING,andwilleati

13、ng%dseconds!nz/,i,sleep(2);)/*P,V原子操作*/voidP(intsemid,intindex)structsembufsema_buffer;semabuffer,semnum=index;sema_buffer.sem-op=-1;sema_buffer.sem_flg=SEM_UND0;semop(semid,&sema_buffer,1);)voidV(intsemid,intindex)structsembufsema-buf;semabuf.semnum=index;sema_buf.sem_op=1;sema_buf.sem_flg=SEM_

14、UND0;semop(semid,&sema_buf,1);)/*/intmain()(/*創(chuàng)立信號量操作*/intsem_phiid;sem_phiid=semget(1008,5,0666IPC_CREAT);assert(sem_phiid>=0);unsignedshortarray5=0,0,0,0,0;unionsemunintval;unsignedshort*array;Jsemopts;semopts.array=array;intretl=semctl(sem_phiid,0,SETALL,semopts);assert(retl=0);intsem_mute

15、xid;sem_mutexid=semget(0x225,1,0666IPC_CREAT);assert(sem_mutexid>=0);semopts.val=1;intret2=semctl(sem_mutexid,0,SETVAL,semopts);assert(ret2=0);/*初始化共享內(nèi)存*/intshmid;char*state;if(shmid=shmget(IPC_PRIVATE,N,0600IPC.CREAT)=-1)semctl(sem_phiid,0,IPC_RMID,0);semctl(sem_mutexid,0,IPC_RMID,0);perror(/zsh

16、mgetfaild!)；exit(l);)if(state=shmat(shmid,0,0)=(char*)-1)semctl(sem_phiid,0,IPC_RMID,0);semctl(sem_mutexid,0,IPC_RMID,0);perror("shmatfaild!)；exit(l);)/*/inti,phinum;pid_tpid;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)=T);

17、semctl(sem_phiid,0,IPC_RMID,0);semctl(sem_mutexid,0,IPC_RMID,0);shmdt(state);printf(z,Hi,GAMEOVER!);elsephilosopher(phinum,state,sem_phiid,sem_mutexid,P,V);六、程序運行結(jié)果截圖一C643>力wen卦叫mjb堂m文件aww彩潮1孫愛Ulie»e5l一國!11mphiIosopher:3»»>isEATING.andiphilosopher:3>»»isTHIbKING.rmp

18、hiIosopher:0»»>isEATING.andiphilosopher:0»»>isTHIhKING.I*mphiIosopher:2»»>isEATING.andiphilosopher:2»»>isTHINKING.I'mphilosopherEATING.andiphilosopher:4»»>isTHINKING.rmphilosopher:1»»>isEATING.andiphiIosopher:1»&#

19、187;>isTHINKING.rmphiIosopher:3»»>i$EATING.andiphilosopher:3»»>isTHIhKING.I*mphiIosopher:0»»>isEATING.andiphilosopher:0»»>isTHIbKING.I'mphiIosopher:2»»>isEATING.andiwillwillwillwillwillwillwillwill9r0ot<§)localhast：-Ajni

20、xjxoject應(yīng)用程序,philosopher:3»»>isTHIbKING.rmphiIosopher:0»»>isEATING.andiphilosopher:0>»»isTHINKING.rmphiIosopher:2»»>isEATING.andiphilosopher:2»»>isTHINKING.I'mphiIosopher:4»»>isEATING.andiphilosopher:4»»>isTHIbKING.rmphilosopher:1»»>isEATING.andiphilosopher:1»»