哲學(xué)家就餐問題

1、哲學(xué)家就餐問題哲學(xué)家就餐問題模擬數(shù)學(xué)與計算機學(xué)院課程設(shè)計說明書課程名稱:操作系統(tǒng)原理 - 課程設(shè)計課程代碼:8404061題目:哲學(xué)家就餐問題模擬年級/ 專業(yè)/ 班: 09級信息與計算科學(xué)三班學(xué)生姓名:徐磊學(xué)號: 312009070102301開始 時 間: 2012年05月 14日完成 時 間: 2012年05月 31日課程設(shè)計成績：學(xué)習(xí)態(tài)度及平時技術(shù)水平與實際總 分創(chuàng)新（ 5）說明書撰寫質(zhì)量（ 45 ）成績（ 30 ）能力（ 20 ）（100 ）I哲學(xué)家就餐問題模擬目錄1引言 .11.1問題的提出 .11.2任務(wù)與分析 .12.總體設(shè)計思想及相關(guān)知識 .12.1 總體設(shè)計思想 .12.2臨

2、界區(qū)互斥編程原理 .23程序運行平臺 .24程序類的說明 .25程序各個模塊流程圖 .35.1主程序模塊 .35.2狀態(tài)改變模塊 .45.3返回哲學(xué)家狀態(tài)圖 .56 系統(tǒng)測試 .78結(jié)論 .11I哲學(xué)家就餐問題模擬1 引言1.1 問題的提出哲學(xué)家進餐問題也是一個經(jīng)典的同步問題， 它是由 Dijkstra 提出并解決的。 哲學(xué)家進餐問題是這樣的：個哲學(xué)家以思考、吃飯交替進行的方式生活，他們共享一張周圍有把椅子的圓桌，每人一把椅子， 在桌子上擺有個飯碗和只筷子。當一個哲學(xué)家思考時，他不與鄰座同事發(fā)生聯(lián)系。當一哲學(xué)家餓了，他就試圖拿起他左右兩邊的筷子吃飯。顯然，他不能拿起已抓在他的鄰座手中的筷子，于

3、是，他可能只拿到一只甚至一只筷子也拿不到。當一個饑餓的哲學(xué)家得到了兩只筷子，他就可以吃飯。當他用飯畢，就放下筷子并再次開始思考。 5 個哲學(xué)家共享 5 支筷子，最多只能不相鄰的兩個哲學(xué)家同時就餐。在多道程序設(shè)計環(huán)境下，進程同步問題十分重要，其中“哲學(xué)家進餐問題”是較有代表性的。通過對該問題的研究學(xué)習(xí)和實踐，可以幫助我們更好的理解和掌握臨界資源、進程同步的概念和實現(xiàn)方法。1.2 任務(wù)與分析本課題主要的目的通過實現(xiàn)哲學(xué)家進餐問題的同步深入了解和掌握進程同步和互斥的原理?？傮w設(shè)計思想及相關(guān)知識2.1 總體設(shè)計思想哲學(xué)家的生活就是思考和吃飯，即思考，餓了就餐，再思考，循環(huán)往復(fù)。要求是：每一個哲學(xué)家只有

4、在拿到位于他左右筷子，才能夠就餐；哲學(xué)家只能先拿一只筷子，再去拿另一只筷子， 而不能同時去抓他旁邊的兩只筷子，也不能從其他哲學(xué)家手中搶奪筷子；哲學(xué)家每次就餐后必須放下他手中的兩只筷子后恢復(fù)思考， 不能強抓住筷子不放。設(shè)計一個程序， 能夠顯示當前各哲學(xué)家的狀態(tài)和桌上餐具的使用情況， 并能無死鎖的推算出下一狀態(tài)各哲學(xué)家的狀態(tài)和筷子的使用情況。 即設(shè)計一個能安排哲學(xué)家正常生活的程序。為哲學(xué)家設(shè)計 3 種狀態(tài)，即“等待”“進餐”“思考”。每個哲學(xué)家重復(fù)進行“等待” -“進餐” -“思考”的行動循環(huán)。其中：“等待” -“進餐”：只有一個哲學(xué)家處于等待進餐狀態(tài)，且左右手兩邊的筷子都處于“空閑”狀態(tài)時，可以

5、發(fā)生這種狀態(tài)改變。此狀態(tài)改變發(fā)生后，哲學(xué)家拿起左右手兩邊的筷子?！斑M餐” -“思考”：此狀態(tài)改變發(fā)生后，哲學(xué)家放下左右手上的筷子?？曜訝顟B(tài)1哲學(xué)家就餐問題模擬由“使用中”轉(zhuǎn)變?yōu)椤翱臻e” ?！八伎肌?-“等待”：哲學(xué)家思考結(jié)束后，無條件轉(zhuǎn)入等待狀態(tài)。由上所述，程序中應(yīng)設(shè)置5 個元素的信號量數(shù)組，chopsticks5，用來保持哲學(xué)家之間的同步。2.2 臨界區(qū)互斥編程原理不論是硬件臨界資源，還是軟件臨界資源，多個進程必須互斥地對它進行訪問。每個進程中訪問臨界資源的那段代碼稱為臨界區(qū)（Critical Section ）。每個進程中訪問臨界資源的那段程序稱為臨界區(qū)（Critical Section

6、）（臨界資源是一次僅允許一個進程使用的共享資源） 。每次只準許一個進程進入臨界區(qū)，進入后不允許其他進程進入。不論是硬件臨界資源，還是軟件臨界資源，多個進程必須互斥地對它進行訪問。本程序主要使用了EnterCriticalSection(&cs) 和 LeaveCriticalSection(&cs) 兩個函數(shù)實現(xiàn)臨界區(qū)互斥。EnterCriticalSection (&cs)用來進入臨界區(qū)， LeaveCriticalSection (&cs) 用來離開臨界區(qū)。程序運行平臺Visual Studio 2008。具體操作如下：新建項目，添加相應(yīng)的源文件，再編譯，鏈接，執(zhí)行等。程序類的說明程序中定

7、義一個哲學(xué)家類，包含兩個私有對象和四個公有對象。Philosopher-number:int-status:int+Philosopher(in num:int)+find() const:int+getinfo() const:int+Change():void2哲學(xué)家就餐問題模擬圖 4-1哲學(xué)家類的 UML 圖Number 對象：哲學(xué)家的編號。Status 對象：用于保存當前該哲學(xué)家的狀態(tài)，0 表示正在等待（即處于饑餓狀態(tài)）1 表示得到餐具正在吃飯， 2 表示正在思考Philosopher(int num) 方法：哲學(xué)家類構(gòu)造函數(shù)，參數(shù)num 表示哲學(xué)家編號find() const 方法：

8、返回該哲學(xué)家編號getinfo() const 方法：返回哲學(xué)家當前狀態(tài)Change()方法：根據(jù)題目要求改變哲學(xué)家的狀態(tài)（等待-進餐 -思考 -等待）另外，程序中包含一個公有對象， bool 類型數(shù)組 chopsticks5 ，用來保存 5 只筷子當前狀態(tài)： true 表示該餐具當前空閑， false 表示該餐具當前正被使用。程序中還包含兩個公有函數(shù)： print 和 chopstickstatus 。Print 用來返回一個哲學(xué)家的狀態(tài)， chopstickstatus 用來返回一個餐具的狀態(tài)。程序各個模塊流程圖5.1 主程序模塊開始定義信號量Chopsticks5定義哲學(xué)家類對象p1p5

9、哲學(xué)家的生活狀態(tài)發(fā)生改變3哲學(xué)家就餐問題模擬輸出當前狀態(tài)圖停止程序？否是結(jié)束圖 5-1 主程序模塊流程圖5.2狀態(tài)改變模塊開始哲學(xué)家 處于進餐狀態(tài)？Status=1？否是哲學(xué)家處于思考放下左右手的筷子狀態(tài)？status=2 ？否Chopsticksnumber%5=trueChopsticks(number+14哲學(xué)家 處于等待狀態(tài)？Status=0？哲學(xué)家就餐問題模擬改變狀態(tài)為思考status=2改變狀態(tài)為等待Status=0左右手筷子均空閑？chopsticksnumber%5&chopsticks+1)%5? 否是拿起左右筷子chopsticksnumber%5=falsechopsti

10、cksnumber%5=false改變狀態(tài)為進餐Status=1結(jié)束圖 5-2 狀態(tài)改變模塊 Change()流程圖5.3返回哲學(xué)家狀態(tài)圖5哲學(xué)家就餐問題模擬圖 5-3 返回哲學(xué)家狀態(tài)模塊print() 流程圖6哲學(xué)家就餐問題模擬5.4 返回餐具狀態(tài)模塊圖 5- 4 返回餐具狀態(tài)模塊 chopsticksstatus(bool a) 流程圖系統(tǒng)測試首先進入 Visual Studio 2008，進入源程序。生成稱解決方案，然后運行。7哲學(xué)家就餐問題模擬圖 6-1 哲學(xué)家開始狀態(tài)18哲學(xué)家就餐問題模擬圖 6-2 哲學(xué)家狀態(tài) 29哲學(xué)家就餐問題模擬圖 6-3 哲學(xué)家狀態(tài) 3圖 6-4 哲學(xué)家狀態(tài)

11、410哲學(xué)家就餐問題模擬結(jié)論對自己完成的題目進行總結(jié)，包括程序的功能、創(chuàng)新點（與眾不同的地方）及程序存在的問題和修改對策。通過本次課程設(shè)計的過程，我了解了金典的同步問題哲學(xué)家就餐問題。發(fā)現(xiàn)自己對互斥變量把握不太清楚。及在編程過程中自己對 C+語法的不熟悉。本程序通過定義一個哲學(xué)家類，模擬了哲學(xué)家就餐，思考和等待的不同狀態(tài)。11哲學(xué)家就餐問題模擬附錄附錄 1源程序清單#include #include #include#include#includeusingnamespacestd;bool chopsticks5;/全局變量，用餐工具CRITICAL_SECTION cs;/信號量 , 在線

12、程中使用，臨界區(qū)class Philosopherprivate :int number;int status;/*標記當前哲學(xué)家的狀態(tài),0表示正在等待 (即處于饑餓狀態(tài) ),1表示得到兩支筷子正在吃飯 ,2表示正在思考 */public :Philosopher(int num=1): status(2), number(num) int find() /定義常成員函數(shù)返回該哲學(xué)家編號constreturnnumber;int getinfo() /定義常成員函數(shù)返回哲學(xué)家當前狀態(tài)constreturn status;void Change() ;/狀態(tài)改變函數(shù);void Philosoph

13、er:Change()EnterCriticalSection (&cs) ;/進入臨界區(qū)if (status=1)/正在進餐chopsticks(number)%5= true ; /放下左手工具 chopsticks(number+1)%5= true ; /放下右手工具status=2;/改變狀態(tài)為思考else if (status=2)/思考中12哲學(xué)家就餐問題模擬status=0;/改變狀態(tài)為等待else if (status=0)/等待中if (chopsticksnumber%5&chopsticks(number+1)%5)/左右手兩邊筷子均為空閑狀態(tài)chopsticksnum

14、ber%5= false ; /拿起左邊的筷子 chopsticks(number+1)%5= false ; /拿起右邊的筷子 status=1;LeaveCriticalSection (&cs) ;/釋放臨界區(qū)string print(Philosopher *pA)/返回哲學(xué)家狀態(tài)/pA-Change();int i=pA-getinfo();string str;if (i=0)str= 等待 ;else if (i=1)str= 就餐 ;else str= 思考 ;returnstr;string chopstickstatus(bool a)/返回筷子狀態(tài)string state

15、;if (a= true )state= 閑 ;if (a= false )state= 用 ;returnstate;int main()char con = y ; /判斷是否繼續(xù)13哲學(xué)家就餐問題模擬for (int i=1;i=5;i+)chopsticksi=true ; /5 根筷子都未使用，初始化Philosopher P1(1),P2(2),P3(3),P4(4),P5(5);InitializeCriticalSection (&cs) ;/初始化初始化臨界區(qū)cout - 狀態(tài)說明示意圖： - endl;cout 哲學(xué)家號的狀態(tài) 筷子的狀態(tài) 筷子的狀態(tài) 哲學(xué)家號的狀態(tài) end

16、l;cout 筷子的狀態(tài) endl;cout 哲學(xué)家號的狀態(tài) 筷子的狀態(tài) 筷子的狀態(tài) 哲學(xué)家號的狀態(tài) endl;cout 哲學(xué)家號的狀態(tài) endl;cout 筷子的狀態(tài)， “用”表示使用中， “閑”表示空閑中。 endl;cout -endl;cout 哲學(xué)家們開始生活： endl;coutendl;coutendl;while (con= y )P1.Change();P2.Change();P3.Change();P4.Change();P5.Change();/P6.Change();cout 當前狀態(tài)為： endl;coutP1.find()print(&P1) chopstickstatus(chopsticks1) chopstickstatus(chopsticks2) P2.find()print(&P2)endl;cou