課程設(shè)計(jì)哲學(xué)家就餐問(wèn)題

1、<p>　　操作系統(tǒng)課程設(shè)計(jì)報(bào)告</p><p>　　院（系）： 計(jì)算機(jī)科學(xué)學(xué)院 </p><p>　　專業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù)專業(yè) </p><p>　　學(xué)生姓名: 　　</p><p>　　班級(jí)：＿＿ ＿

2、　學(xué)號(hào): </p><p>　　題目：模擬仿真＂哲學(xué)家進(jìn)餐＂問(wèn)題的解決過(guò)程及方法 </p><p>　　起訖日期: 2010.6.30----2010.7.11 </p><p>　　指 導(dǎo) 教 師: </p><p>　　完成

3、日期: 2010 年 7 月 10 日</p><p><b>　　目錄</b></p><p>　　1．設(shè)計(jì)題目與要求2</p><p><b>　　1.1實(shí)驗(yàn)?zāi)康?</b></p><p>　　1.3 初始條件2</p><p>　　2 總體設(shè)計(jì)思想及相關(guān)知識(shí)

4、3</p><p>　　2.1總體設(shè)計(jì)思想3</p><p>　　2.2 臨界區(qū)互斥編程原理3</p><p>　　2.3開(kāi)發(fā)環(huán)境與工具4</p><p>　　3數(shù)據(jù)結(jié)構(gòu)與模塊說(shuō)明4</p><p>　　3.1 數(shù)據(jù)結(jié)構(gòu)4</p><p>　　3.2程序各模塊流程圖6</p&

5、gt;<p>　　3.2.1 主程序模塊6</p><p>　　3.2.2 狀態(tài)改變模塊7</p><p>　　3.2.3 返回哲學(xué)家狀態(tài)模塊8</p><p>　　3.2.4 返回餐具狀態(tài)模塊9</p><p>　　4. 源程序代碼10</p><p>　　5. 測(cè)試及結(jié)果15</p

6、><p>　　6. 課設(shè)總結(jié)17</p><p><b>　　參考文獻(xiàn)18</b></p><p><b>　　1．設(shè)計(jì)題目與要求</b></p><p><b>　　1.1實(shí)驗(yàn)?zāi)康?lt;/b></p><p>　　通過(guò)實(shí)現(xiàn)哲學(xué)家進(jìn)餐問(wèn)題的同步,深入了解和掌

7、握進(jìn)程同步和互斥的原理。1.2設(shè)計(jì)要求</p><p>　　哲學(xué)家有N個(gè)，也定全體到達(dá)后開(kāi)始討論：在討論的間隙哲學(xué)家進(jìn)餐，每人進(jìn)餐時(shí)都需使用刀、叉各一把，所有哲學(xué)家刀和叉都拿到后才能進(jìn)餐。哲學(xué)家的人數(shù)、餐桌上的布置自行設(shè)定，實(shí)現(xiàn)刀和叉的互斥使用算法的程序?qū)崿F(xiàn)。</p><p><b>　　1.3 初始條件</b></p><p>　?。?）操

8、作系統(tǒng)：windows</p><p>　　（2）程序設(shè)計(jì)語(yǔ)言：C++</p><p>　?。?）設(shè)定圓桌上有六個(gè)哲學(xué)家，三對(duì)刀叉，如下圖擺放：</p><p>　　圖1-1 哲學(xué)家進(jìn)餐問(wèn)題設(shè)定圖</p><p>　　2 總體設(shè)計(jì)思想及相關(guān)知識(shí)</p><p><b>　　2.1總體設(shè)計(jì)思想</b>

9、;</p><p>　　哲學(xué)家的生活就是思考和吃飯，即思考，就餐，再思考，往復(fù)循環(huán)。要求是：每一個(gè)哲學(xué)家只有在拿到位于他左右的刀叉后，才能夠就餐；哲學(xué)家只能先拿一把刀或叉，再去拿另一把刀或叉，而不能同時(shí)去抓他旁邊的兩把餐具，也不能從其他哲學(xué)家手中搶奪餐具；哲學(xué)家每次就餐后必須放下他手中的兩把餐具后恢復(fù)思考，不能強(qiáng)抓住餐具不放。</p><p>　　設(shè)計(jì)一個(gè)程序，能夠顯示當(dāng)前各哲學(xué)家的狀態(tài)和

10、桌上餐具的使用情況，并能無(wú)死鎖的推算出下一狀態(tài)各哲學(xué)家的狀態(tài)和桌上餐具的使用情況。即設(shè)計(jì)一個(gè)能安排哲學(xué)家正常生活的程序。</p><p>　　為哲學(xué)家設(shè)計(jì)3種狀態(tài)，即“等待”“進(jìn)餐”“思考”。每個(gè)哲學(xué)家重復(fù)進(jìn)行“等待”->“進(jìn)餐”->“思考”的行動(dòng)循環(huán)。其中：</p><p>　　“等待”->“進(jìn)餐”：只有一個(gè)哲學(xué)家處于等待進(jìn)餐狀態(tài)，且左右手兩邊的餐具都處于“空閑”狀態(tài)時(shí)

11、，可以發(fā)生這種狀態(tài)改變。此狀態(tài)改變發(fā)生后，哲學(xué)家拿起左右手兩邊的餐具。</p><p>　　“進(jìn)餐”->“思考”：此狀態(tài)改變發(fā)生后，哲學(xué)家放下左右手上的餐具。餐具狀態(tài)由“使用中”轉(zhuǎn)變?yōu)椤翱臻e”。</p><p>　　“思考”->“等待”：哲學(xué)家思考結(jié)束后，無(wú)條件轉(zhuǎn)入等待狀態(tài)。</p><p>　　由上所述，程序中應(yīng)設(shè)置6個(gè)元素的信號(hào)量數(shù)組，tools[6

12、]，用來(lái)保持哲學(xué)家之間的同步。</p><p>　　2.2 臨界區(qū)互斥編程原理</p><p>　　不論是硬件臨界資源，還是軟件臨界資源，多個(gè)進(jìn)程必須互斥地對(duì)它進(jìn)行訪問(wèn)。每個(gè)進(jìn)程中訪問(wèn)臨界資源的那段代碼稱為臨界區(qū)（Critical Section）。 </p><p>　　每個(gè)進(jìn)程中訪問(wèn)臨界資源的那段程序稱為臨界區(qū)（Critical Section）（臨界資源是一次

13、僅允許一個(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)。</p><p>　　本程序主要使用了EnterCriticalSection (&cs)和LeaveCriticalSection (&cs)兩個(gè)函數(shù)實(shí)現(xiàn)臨界區(qū)互斥。</p><p>　　EnterCriticalS

14、ection (&cs)用來(lái)進(jìn)入臨界區(qū)，LeaveCriticalSection (&cs)用來(lái)離開(kāi)臨界區(qū)。</p><p>　　2.3開(kāi)發(fā)環(huán)境與工具</p><p>　　系統(tǒng)平臺(tái)：WINDOW環(huán)境</p><p><b>　　實(shí)現(xiàn)語(yǔ)言：C++</b></p><p>　　開(kāi)發(fā)工具：VC++6.0<

15、/p><p>　　3數(shù)據(jù)結(jié)構(gòu)與模塊說(shuō)明</p><p><b>　　3.1 數(shù)據(jù)結(jié)構(gòu)</b></p><p>　　圖3-1 哲學(xué)家類的UML圖</p><p>　　程序中定義一個(gè)哲學(xué)家類，包含兩個(gè)私有對(duì)象和四個(gè)公有對(duì)象。</p><p>　　Number對(duì)象：哲學(xué)家的編號(hào)。</p>&

16、lt;p>　　Status對(duì)象：用于保存當(dāng)前該哲學(xué)家的狀態(tài)，0表示正在等待（即處于饑餓狀態(tài)）1表示得到餐具正在吃飯，2表示正在思考</p><p>　　Philosopher(int num)方法：哲學(xué)家類構(gòu)造函數(shù)，參數(shù)num表示哲學(xué)家編號(hào)</p><p>　　find() const方法：返回該哲學(xué)家編號(hào)</p><p>　　getinfo() const方

17、法：返回哲學(xué)家當(dāng)前狀態(tài)</p><p>　　Change()方法：根據(jù)題目要求改變哲學(xué)家的狀態(tài)（等待->進(jìn)餐->思考->等待…………）</p><p>　　另外，程序中包含一個(gè)公有對(duì)象，bool類型數(shù)組tools[6]，用來(lái)保存6把餐具當(dāng)前狀態(tài)：true表示該餐具當(dāng)前空閑，false表示該餐具當(dāng)前正被使用。</p><p>　　程序中還包含兩個(gè)公有

18、函數(shù)：print和toolstatus。Print用來(lái)返回一個(gè)哲學(xué)家的狀態(tài)，toolstatus用來(lái)返回一個(gè)餐具的狀態(tài)。</p><p>　　3.2程序各模塊流程圖</p><p>　　3.2.1 主程序模塊</p><p>　　圖3-2 主程序模塊流程圖</p><p>　　3.2.2 狀態(tài)改變模塊</p><p>

19、　　圖3-3 狀態(tài)改變模塊Change()流程圖</p><p>　　3.2.3 返回哲學(xué)家狀態(tài)模塊</p><p>　　圖3-4 返回哲學(xué)家狀態(tài)模塊print()流程圖</p><p>　　3.2.4 返回餐具狀態(tài)模塊</p><p>　　圖3-5 返回餐具狀態(tài)模塊toolstatus(bool a)流程圖</p><p

20、><b>　　4. 源程序代碼</b></p><p>　　//實(shí)驗(yàn)?zāi)康模和ㄟ^(guò)實(shí)現(xiàn)哲學(xué)家進(jìn)餐問(wèn)題的同步深入了解和掌握進(jìn)程同步和互斥的原理。</p><p>　　//設(shè)計(jì)要求：哲學(xué)家有N個(gè)，也定全體到達(dá)后開(kāi)始討論：在討論的間隙哲學(xué)家進(jìn)餐，</p><p>　　//每人進(jìn)餐時(shí)都需使用刀、叉各一把，所有哲學(xué)家刀和叉都拿到后才能進(jìn)餐。哲學(xué)家的人

21、數(shù)、</p><p>　　//餐桌上的布置自行設(shè)定，實(shí)現(xiàn)刀和叉的互斥使用算法的程序?qū)崿F(xiàn)。</p><p>　　#include <windows.h> </p><p>　　#include <time.h> </p><p>　　#include <string> </p><p>

22、;　　#include <iostream> </p><p>　　#include <assert.h> </p><p>　　using namespace std; //控制活動(dòng)線程數(shù)目的信號(hào)量（保護(hù)線程共享資源）</p><p>　　bool tools[6];//全局變量，用餐工具</p><p>　

23、　CRITICAL_SECTION cs; //信號(hào)量, 在線程中使用，臨界區(qū)</p><p>　　class Philosopher</p><p><b>　　{ </b></p><p><b>　　private: </b></p><p>　　int number;</p>

24、<p>　　int status; /*標(biāo)記當(dāng)前哲學(xué)家的狀態(tài),0表示正在等待(即處于饑餓狀態(tài)),1表示得到兩支筷子正在吃飯,2表示正在思考*/</p><p><b>　　public:</b></p><p>　　Philosopher(int num=0): status(2), number(num) { }</p><p&

25、gt;　　int find() const { return number; } </p><p>　　int getinfo() const { return status; } </p><p>　　void Change() ; //狀態(tài)改變函數(shù)</p><p><b>　　}; </b></p><p>　　

26、void Philosopher::Change() </p><p><b>　　{ </b></p><p>　　EnterCriticalSection (&cs) ; //進(jìn)入臨界區(qū)</p><p>　　if(status==1)//正在進(jìn)餐</p><p><b>　　{</b>

27、</p><p>　　tools[number%6]=true; //放下左手工具</p><p>　　tools[(number-1)%6]=true; //放下右手工具</p><p>　　status=2;//改變狀態(tài)為思考 </p><p><b>　　} </b></p><p&g

28、t;　　else if(status==2)//思考中</p><p><b>　　{ </b></p><p>　　status=0; //改變狀態(tài)為等待 </p><p><b>　　} </b></p><p>　　else if(status==0)//等待中 </p>

29、<p><b>　　{ </b></p><p>　　if(tools[number%6]&&tools[(number-1)%6]) //左右手兩邊工具均為空閑狀態(tài)</p><p><b>　　{</b></p><p>　　tools[number%6]=false; //拿起左手工具

30、</p><p>　　tools[(number-1)%6]=false; //拿起右手工具</p><p>　　status=1; </p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　LeaveCriticalSect

31、ion (&cs) ; </p><p><b>　　} </b></p><p>　　string print(Philosopher *pA) </p><p><b>　　{ </b></p><p>　　//pA->Change(); </p><p>

32、　　int i=pA->getinfo(); </p><p>　　string str; </p><p><b>　　if(i==0) </b></p><p>　　str="等待"; </p><p>　　else if(i==1) </p><p>　　str=&

33、quot;就餐"; </p><p>　　else str="思考"; </p><p>　　return str; </p><p><b>　　} </b></p><p>　　string toolstatus(bool a)</p><p><b>

34、　　{</b></p><p>　　string state;</p><p>　　if(a==true)</p><p>　　state="閑";</p><p>　　if(a==false)</p><p>　　state="用";</p><

35、p>　　return state;</p><p><b>　　}</b></p><p>　　int main() </p><p><b>　　{ </b></p><p>　　char con = 'y'; //判斷是否繼續(xù)</p><p>　　f

36、or(int i=0;i<6;i++) </p><p>　　tools[i]=true; //3組刀叉都未使用，初始化</p><p>　　Philosopher P1(1),P2(2),P3(3),P4(4),P5(5),P6(6); </p><p>　　InitializeCriticalSection (&cs) ; //初始化初始化臨界區(qū)&

37、lt;/p><p>　　cout<<"-----------------------狀態(tài)說(shuō)明示意圖：-----------------------"<<endl;</p><p>　　cout<<""<<"哲學(xué)家0號(hào)的狀態(tài)"<<""<&

38、lt;endl;</p><p>　　cout<<"哲學(xué)家5號(hào)的狀態(tài)"<<""<<"叉3的狀態(tài)"<<""<<"刀1的狀態(tài)"<<""<<"哲學(xué)家1號(hào)的狀態(tài)"<<endl;

39、</p><p>　　cout<<" "<<"刀3的狀態(tài)"<<" "<<"叉1的狀態(tài)"<<endl;</p><p>　　cout<<"哲學(xué)家4號(hào)的狀態(tài)"<<"&q

40、uot;<<"叉2的狀態(tài)"<<""<<"刀2的狀態(tài)"<<""<<"哲學(xué)家2號(hào)的狀態(tài)"<<endl;</p><p>　　cout<<""<<"哲學(xué)家3號(hào)的狀態(tài)"&l

41、t;<""<<endl;</p><p>　　cout<<"餐具的狀態(tài)，\“用\”表示使用中，\“閑\”表示空閑中。"<<endl;</p><p>　　cout<<"--------------------------"<<endl;</p>

42、<p>　　cout<<"哲學(xué)家們開(kāi)始生活："<<endl;</p><p>　　cout<<endl;</p><p>　　cout<<endl;</p><p>　　while(con=='y') </p><p><b>　　{ &

43、lt;/b></p><p>　　P1.Change();</p><p>　　P2.Change();</p><p>　　P3.Change();</p><p>　　P4.Change();</p><p>　　P5.Change();</p><p>　　P6.Change();&

44、lt;/p><p>　　cout<<"當(dāng)前狀態(tài)為："<<endl;</p><p>　　cout<<""<<P1.find()<<print(&P1)<<""<<endl;</p><p>　　cout<

45、;<P6.find()<<print(&P6)<<""<<toolstatus(tools[0])<<""<<toolstatus(tools[1])<<""<<P2.find()<<print(&P2)<<endl;</p>

46、<p>　　cout<<" "<<toolstatus(tools[5])<<" "<<toolstatus(tools[2])<<endl;</p><p>　　cout<<P5.find()<<print(&P5)<<"

47、;"<<toolstatus(tools[4])<<""<<toolstatus(tools[3])<<""<<P3.find()<<print(&P3)<<endl;</p><p>　　cout<<""<<P

48、4.find()<<print(&P4)<<""<<endl;</p><p>　　cout<<"--------------------------"<<endl;</p><p>　　cout<<"若要繼續(xù)下一狀態(tài)，輸入y；輸入其他，結(jié)束程序：&quo

49、t;;</p><p><b>　　cin>>con;</b></p><p>　　Sleep(20); </p><p><b>　　} </b></p><p>　　DeleteCriticalSection (&cs) ; //退出資源區(qū)</p><p&

50、gt;　　return 0; </p><p><b>　　}</b></p><p><b>　　5. 測(cè)試及結(jié)果</b></p><p>　　圖5-1 程序運(yùn)行開(kāi)始界面</p><p>　　圖5-2 哲學(xué)家狀態(tài)1</p><p>　　圖5-3 哲學(xué)家狀態(tài)2</p&g

51、t;<p>　　圖5-4 哲學(xué)家狀態(tài)3</p><p>　　圖5-5 哲學(xué)家狀態(tài)4</p><p><b>　　圖5-6 退出程序</b></p><p><b>　　6. 課設(shè)總結(jié)</b></p><p>　　經(jīng)過(guò)了前后共2周的時(shí)間，我完成了這次課程設(shè)計(jì)。</p>&l

52、t;p>　　通過(guò)這次課程設(shè)計(jì)，我學(xué)到了許多課本上學(xué)不到的知識(shí)，注意到了許多課本上沒(méi)有提到的東西。</p><p>　　而且，通過(guò)這次設(shè)計(jì)，我得到了一個(gè)很好的理論聯(lián)系實(shí)際的機(jī)會(huì)，鍛煉了通過(guò)理論解決實(shí)際問(wèn)題的能力。正所謂“實(shí)踐出真知”，有些代碼看上去沒(méi)什么問(wèn)題，但是實(shí)際運(yùn)行起來(lái)就是不出正確結(jié)果。代碼內(nèi)部可能存在邏輯或語(yǔ)法等方面我們平時(shí)不會(huì)注意到的小問(wèn)題，通過(guò)這次課程設(shè)計(jì)，我積累了不少這樣小問(wèn)題的解決方法。<

53、;/p><p>　　設(shè)計(jì)中總會(huì)遇到這樣那樣的問(wèn)題，遇到問(wèn)題勢(shì)必要自己分析問(wèn)題，通過(guò)各種渠道解決問(wèn)題，比如利用互聯(lián)網(wǎng)。這次課程設(shè)計(jì)也加強(qiáng)了我上網(wǎng)查數(shù)檢索問(wèn)題的能力。有些時(shí)候，學(xué)習(xí)到的知識(shí)是次要的，重要的是學(xué)習(xí)知識(shí)的方法。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1]宗大華，宗濤，陳吉人著 操作系統(tǒng) 北京：人民郵電出版社