哲學(xué)家就餐問(wèn)題

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

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

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

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

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

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

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

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

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

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

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

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

13、er:Change()EnterCriticalSection (&cs) ;/進(jìn)入臨界區(qū)if (status=1)/正在進(jìn)餐chopsticks(number)%5= true ; /放下左手工具 chopsticks(number+1)%5= true ; /放下右手工具status=2;/改變狀態(tài)為思考else if (status=2)/思考中12哲學(xué)家就餐問(wèn)題模擬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é)家就餐問(wèn)題模擬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)說(shuō)明示意圖： - endl;cout 哲學(xué)家號(hào)的狀態(tài) 筷子的狀態(tài) 筷子的狀態(tài) 哲學(xué)家號(hào)的狀態(tài) end

16、l;cout 筷子的狀態(tài) endl;cout 哲學(xué)家號(hào)的狀態(tài) 筷子的狀態(tài) 筷子的狀態(tài) 哲學(xué)家號(hào)的狀態(tài) endl;cout 哲學(xué)家號(hào)的狀態(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 當(dāng)前狀態(tài)為： endl;coutP1.find()print(&P1) chopstickstatus(chopsticks1) chopstickstatus(chopsticks2) P2.find()print(&P2)endl;cou