操作系統(tǒng)哲學(xué)家就餐問(wèn)題課程設(shè)計(jì)c語(yǔ)言

1、<p>　　題目: 用多線程同步方法解決哲學(xué)家就餐問(wèn)題(Dining-Philosophers Problem)</p><p><b>　　初始條件：</b></p><p>　　操作系統(tǒng)：Linux</p><p>　　程序設(shè)計(jì)語(yǔ)言：C語(yǔ)言</p><p>　　3．共有5個(gè)哲學(xué)家需用餐。只許4個(gè)哲學(xué)家入席且

2、桌上有5支筷子。</p><p>　　要求完成的主要任務(wù): （包括課程設(shè)計(jì)工作量及其技術(shù)要求，以及說(shuō)明書(shū)撰寫(xiě)等具體要求）</p><p><b>　　1．技術(shù)要求：</b></p><p>　　1）為每個(gè)哲學(xué)家產(chǎn)生一個(gè)線程，設(shè)計(jì)正確的同步算法</p><p>　　2）每個(gè)哲學(xué)家取得一雙筷子開(kāi)始用餐后，即時(shí)顯示“Dinin

3、g…”和該哲學(xué)家的自定義標(biāo)識(shí)符以及餐桌上所有幾位哲學(xué)家標(biāo)識(shí)符及其所坐的位置。</p><p>　　3）設(shè)定共有5個(gè)哲學(xué)家需用餐。每位用餐耗時(shí)10秒鐘以上。</p><p>　　4）多個(gè)哲學(xué)家須共享操作函數(shù)代碼。</p><p>　　2． 設(shè)計(jì)說(shuō)明書(shū)內(nèi)容要求：</p><p><b>　　1)設(shè)計(jì)題目與要求</b><

4、/p><p>　　2)總的設(shè)計(jì)思想及系統(tǒng)平臺(tái)、語(yǔ)言、工具等。</p><p>　　3）數(shù)據(jù)結(jié)構(gòu)與模塊說(shuō)明（功能與流程圖）</p><p>　　4）給出用戶(hù)名、源程序名、目標(biāo)程序名和源程序及其運(yùn)行結(jié)果。（要注明存儲(chǔ)各個(gè)程序及其運(yùn)行結(jié)果的Linux主機(jī)IP地址和目錄。）</p><p>　　5）運(yùn)行結(jié)果與運(yùn)行情況</p><p&g

5、t;　　（提示: (1)連續(xù)存儲(chǔ)區(qū)可用數(shù)組實(shí)現(xiàn)。</p><p>　　(2)編譯命令可用：　　　　　cc -lpthread -o 目標(biāo)文件名　源文件名</p><p>　　(3)多線程編程方法參見(jiàn)附件。）</p><p>　　3. 調(diào)試報(bào)告：</p><p><b>　　1) 調(diào)試記錄</b></p&g

6、t;<p><b>　　自我評(píng)析和總結(jié)</b></p><p><b>　　上機(jī)時(shí)間安排：</b></p><p>　　18周一~ 五 08：0 － 12：00 </p><p>　　指導(dǎo)教師簽名： 年 月 日</p><p&g

7、t;　　系主任（或責(zé)任教師）簽名： 年 月 日</p><p>　　用多線程同步方法解決哲學(xué)家就餐問(wèn)題</p><p>　　(Dining-Philosophers Problem)</p><p><b>　　1．設(shè)計(jì)題目與要求</b></p><p>　　1.1設(shè)計(jì)題目描述：<

8、/p><p>　　用多線程同步方法解決哲學(xué)家就餐問(wèn)題(Dining-Philosophers Problem)</p><p><b>　　1.2要求：</b></p><p>　　1）為每個(gè)哲學(xué)家產(chǎn)生一個(gè)線程，設(shè)計(jì)正確的同步算法</p><p>　　2）每個(gè)哲學(xué)家取得一雙筷子開(kāi)始用餐后，即時(shí)顯示“Dining…”和該哲學(xué)家

9、的自定義標(biāo)識(shí)符以及餐桌上所有幾位哲學(xué)家標(biāo)識(shí)符及其所坐的位置。</p><p>　　3）設(shè)定共有5個(gè)哲學(xué)家需用餐。每位用餐耗時(shí)10秒鐘以上。</p><p>　　4）多個(gè)哲學(xué)家須共享操作函數(shù)代碼。</p><p>　　2．總體設(shè)計(jì)思想及系統(tǒng)平臺(tái)、語(yǔ)言、工具</p><p><b>　　2.1總體設(shè)計(jì)思想</b></p

10、><p>　　哲學(xué)家就餐問(wèn)題，即共有5個(gè)哲學(xué)家繞一個(gè)圓桌做在5個(gè)位置上，他們每2個(gè)人中間有一只筷子，共5只筷子，只有當(dāng)每個(gè)哲學(xué)家取得他左右兩邊的筷子時(shí)，哲學(xué)家才能開(kāi)始就餐，其它時(shí)間，哲學(xué)家只能思考或等待筷子。為避免哲學(xué)家互相等待對(duì)方的筷子發(fā)生死鎖，本次課程設(shè)計(jì)要求只許4個(gè)哲學(xué)家入席，以保證至少有一個(gè)哲學(xué)家能夠進(jìn)餐。</p><p>　　本課程設(shè)計(jì)將room 作為信號(hào)量，將其初始化為4，以保證只

11、允許4個(gè)哲學(xué)家同時(shí)入席就餐，這樣就能保證至少有一個(gè)哲學(xué)家可以就餐。針對(duì)每個(gè)哲學(xué)家，通過(guò)共享操作函數(shù)代碼，分別建立5個(gè)線程，以實(shí)現(xiàn)同步哲學(xué)家就餐，而申請(qǐng)進(jìn)入餐廳的哲學(xué)家進(jìn)入room 的等待隊(duì)列，根據(jù)FIFO 的原則，總會(huì)進(jìn)入到餐廳就餐，因此不會(huì)出現(xiàn)餓死和死鎖的現(xiàn)象，針對(duì)5只筷子分別設(shè)置了5個(gè)互斥信號(hào)量，以保證每只筷子每次只能被取得一次。</p><p>　　2.2系統(tǒng)平臺(tái)、語(yǔ)言及工具</p><

12、p>　　（1）操作系統(tǒng)：Linux</p><p>　?。?）程序設(shè)計(jì)語(yǔ)言：C語(yǔ)言</p><p>　　（3）工具：編輯工具Vi、編譯器gcc</p><p>　　3．?dāng)?shù)據(jù)結(jié)構(gòu)與模塊說(shuō)明</p><p>　　線程創(chuàng)建函數(shù)pthread_create聲明如下：</p><p>　　#include <pthr

13、ead.h></p><p>　　int pthread_create (pthread_t *thread,pthread_attr_t *attr,Void* (*start_routine)(void *),void *arg);</p><p>　　等待其它線程結(jié)束函數(shù)pthread_join聲明如下：</p><p>　　#include <p

14、thread.h></p><p>　　int pthread_join (pthread_t th,void *thread_return);</p><p>　　信號(hào)量的數(shù)據(jù)類(lèi)型為結(jié)構(gòu)sem_t，它本質(zhì)上是一個(gè)長(zhǎng)整型的數(shù)。</p><p>　　初始化信號(hào)量函數(shù)sem_init聲明如下： </p><p>　　#inc

15、lude <semaphore.h></p><p>　　sem_init (sem_t *sem, int pshared, unsigned int value);</p><p>　　增加信號(hào)量值函數(shù)sem_post聲明如下：</p><p>　　#include <semaphore.h></p><p>　　

16、Sem_post ( sem_t *sem );</p><p>　　減少信號(hào)量值函數(shù)sem_wait聲明如下</p><p>　　#include <semaphore.h></p><p>　　Sem_wait ( sem_t *sem );</p><p><b>　　主要數(shù)據(jù)結(jié)構(gòu)聲明：</b><

17、/p><p>　　#define NUMBERS 5 //將哲學(xué)家人數(shù)NUMBERS定義為5</p><p>　　sem_t chopstics[NUMBERS] //定義5只筷子的互斥信號(hào)量chopstics</p><p>　　sem_t room //定義避免死鎖的同步信號(hào)量room</p><

18、p>　　線程共享函數(shù)偽代碼：</p><p>　　void *Share(int i)</p><p><b>　　{</b></p><p><b>　　think();</b></p><p>　　wait(room); //請(qǐng)求入席進(jìn)餐 </p>

19、<p>　　wait(chopstick[i]); //請(qǐng)求左手邊的筷子 </p><p>　　wait(chopstick[(i+1)%5]); //請(qǐng)求右手邊的筷子</p><p><b>　　eat();</b></p><p>　　signal(chopstick[i]); //釋放左

20、手邊的筷子</p><p>　　signal(chopstick[(i+1)%5]); //釋放右手邊的筷子 </p><p>　　signal(room); //退出席位釋放信號(hào)量chairs</p><p><b>　　} </b></p><p&

21、gt;　　4．用戶(hù)名、源程序名、目標(biāo)程序名和源程序</p><p>　　4.1用戶(hù)名、源程序名、目標(biāo)程序名</p><p><b>　　用戶(hù)名：</b></p><p><b>　　源程序名：</b></p><p><b>　　目標(biāo)程序名：</b></p>&l

22、t;p><b>　　4.2源程序</b></p><p>　　#include <stdio.h></p><p>　　#include <unistd.h></p><p>　　#include <pthread.h></p><p>　　#include <semaph

23、ore.h></p><p>　　#define NUMBERS 5 </p><p>　　sem_t chopstics[NUMBERS];</p><p>　　sem_t room; </p><p>　　sem_t mutex;</p><p>　　int flag[NUMBERS]={0,

24、0,0,0,0};</p><p>　　int chairs[NUMBERS]={0,1,2,3,4};</p><p><b>　　int i,j;</b></p><p>　　void *Share(int threadid);</p><p>　　int main()</p><p><

25、;b>　　{</b></p><p>　　int error;</p><p>　　pthread_t threads[NUMBERS];</p><p>　　for(i=0;i<NUMBERS;i++)</p><p><b>　　{</b></p><p>　　sem_

26、init(&chopstics[i],0,1);</p><p><b>　　}</b></p><p>　　sem_init(&room,0,NUMBERS-1);</p><p>　　sem_init(&mutex,0,1);</p><p>　　for(i=0;i<NUMBERS;i+

27、+)</p><p><b>　　{</b></p><p>　　error = pthread_create(&threads[i],NULL,(void*)Share,(void *)i);</p><p><b>　　if(error)</b></p><p><b>　　{

28、</b></p><p>　　printf("ERROR: thread create failed!!!");</p><p>　　//exit(-1);</p><p><b>　　}</b></p><p><b>　　}</b></p><

29、;p>　　for(i=0;i<NUMBERS;i++)</p><p><b>　　{</b></p><p>　　pthread_join(threads[i],NULL);</p><p><b>　　}</b></p><p><b>　　}</b></

30、p><p>　　void *Share(int threadid)</p><p><b>　　{</b></p><p>　　int i = threadid;</p><p>　　sem_wait(&room);</p><p>　　flag[i]=1;</p><p

31、>　　sem_wait(&chopstics[i]);</p><p>　　printf("philosopher %d get chopstics %d\n",i,i);</p><p>　　sem_wait(&chopstics[(i+1)%NUMBERS]);</p><p>　　printf("philo

32、sopher %d get chopstics %d\n",i,(i+1)%NUMBERS);</p><p>　　sem_wait(&mutex);</p><p>　　printf("\n*********************************************\n");</p><p>　　printf(&

33、quot;Dining...\n");</p><p>　　printf("philosopher: %d ,on chairs %d and eating\n",i,chairs[i]);</p><p>　　for(j=0;j<NUMBERS;j++)</p><p><b>　　{</b></p&

34、gt;<p>　　if((j!=i)&&flag[j]) </p><p>　　printf("philosopher %d ,on chairs %d and hungry\n",j,chairs[j]);</p><p><b>　　}</b></p><p><b>　　s

35、leep(3);</b></p><p>　　sem_post(&mutex);</p><p>　　sem_post(&chopstics[i]);</p><p>　　sem_post(&chopstics[(i+1)%NUMBERS]);</p><p>　　printf("philosop

36、her %d is full and put down chopstics %d and %d and left\n",i,i,(i+1)%NUMBERS);</p><p>　　printf("*********************************************\n\n");</p><p>　　flag[i]=0;</p>

37、<p>　　sem_post(&room);</p><p><b>　　}</b></p><p><b>　　5．運(yùn)行結(jié)果</b></p><p><b>　　6．調(diào)試記錄</b></p><p>　?。?）將寫(xiě)好的代碼進(jìn)行編譯，出現(xiàn)如下錯(cuò)誤提示：&l

38、t;/p><p>　　1.c:(.text+0x37): undefined reference to `sem_init'</p><p>　　1.c:(.text+0x6a): undefined reference to `sem_init'</p><p>　　1.c:(.text+0x86): undefined reference to `s

39、em_init'</p><p>　　1.c:(.text+0xc8): undefined reference to `pthread_create'</p><p>　　1.c:(.text+0x108): undefined reference to `pthread_join'</p><p>　　/tmp/ccq8XD3O.o: I

40、n function `Share':</p><p>　　1.c:(.text+0x13f): undefined reference to `sem_wait'</p><p>　　1.c:(.text+0x160): undefined reference to `sem_wait'</p><p>　　1.c:(.text+0x1b0

41、): undefined reference to `sem_wait'</p><p>　　1.c:(.text+0x1f7): undefined reference to `sem_wait'</p><p>　　1.c:(.text+0x2ad): undefined reference to `sem_post'</p><p>　

42、　1.c:(.text+0x2c0): undefined reference to `sem_post'</p><p>　　1.c:(.text+0x2f5): undefined reference to `sem_post'</p><p>　　1.c:(.text+0x35d): undefined reference to `sem_post'</

43、p><p>　　collect2: ld returned 1 exit status檢查發(fā)現(xiàn)，pthread庫(kù)不是Linux系統(tǒng)默認(rèn)的庫(kù)，連接時(shí)需要使用庫(kù)libpthread.a,所以在使用pthread_create創(chuàng)建線程時(shí)，在編譯中 要加-lpthread參數(shù):gcc -lpthread -o 1 1.c</p><p>　?。?）重新編譯代碼，出現(xiàn)如下錯(cuò)誤提示：</p

44、><p>　　1.c:9: error: invalid initializer</p><p>　　1.c:10: error: invalid initializer</p><p>　　1.c: In function ‘main’:</p><p>　　1.c:35: warning: incompatible implicit decl

45、aration of built-in function ‘exit’</p><p>　　1.c: In function ‘Share’:</p><p>　　1.c:48: error: incompatible types when assigning to type ‘sem_t’ from type ‘int’</p><p>　　1.c:71: err

46、or: expected ‘;’ before ‘sem_post’</p><p>　　1.c:76: error: incompatible types when assigning to type ‘sem_t’ from type ‘int’</p><p>　　仔細(xì)查看代碼，發(fā)是對(duì)信號(hào)燈初始不能在定義的時(shí)候直接初始化，改用sem_init()函數(shù)對(duì)room,mutex 和flag

47、[]進(jìn)行初始化，去掉exit()函數(shù)，找到缺少‘；’的地方，添加‘；’</p><p>　?。?）重新編譯、連接、運(yùn)行程序，出現(xiàn)如下錯(cuò)誤提示：</p><p>　　1.c: In function ‘Share’:</p><p>　　1.c:48: error: incompatible types when assigning to type ‘sem_t’ f

48、rom type ‘int’</p><p>　　1.c:76: error: incompatible types when assigning to type ‘sem_t’ from type ‘int’</p><p>　　查看代碼，發(fā)現(xiàn)對(duì)信號(hào)燈flag[]使用出錯(cuò)，將flag[i]=1改為sem_wait(&flag[i])；flag[i]=0改為sem_post(&am

49、p;flag[i])</p><p>　?。?）重新編譯、連接、運(yùn)行程序，沒(méi)有錯(cuò)誤提示，但是結(jié)果有誤：</p><p>　　philosopher 0 get chopstics 0</p><p>　　I'm philosopher 0 get chopstics 0</p><p>　　程序程出現(xiàn)死鎖，無(wú)法正常進(jìn)行，查看代碼，發(fā)現(xiàn)

50、不應(yīng)該把flag[]設(shè)置為信號(hào)</p><p>　　（5）改正后，重新編譯、連接，運(yùn)行程序，得到正確結(jié)果</p><p>　　philosopher 0 get chopstics 0</p><p>　　philosopher 1 get chopstics 1</p><p>　　philosopher 2 get chopstics 2

51、</p><p>　　philosopher 3 get chopstics 3</p><p>　　philosopher 3 get chopstics 4</p><p>　　*********************************************</p><p><b>　　Dining...</b&

52、gt;</p><p>　　philosopher: 3 ,on chairs 3 and eating</p><p>　　philosopher 0 ,on chairs 0 and hungry</p><p>　　philosopher 1 ,on chairs 1 and hungry</p><p>　　philosopher

53、2 ,on chairs 2 and hungry</p><p>　　philosopher 3 is full and put down chopstics 3 and 4 and left*********************************************</p><p>　　philosopher 2 get chopstics 3</p>&

54、lt;p>　　*********************************************</p><p><b>　　Dining...</b></p><p>　　philosopher: 2 ,on chairs 2 and eating</p><p>　　philosopher 0 ,on chairs 0 and

55、 hungry</p><p>　　philosopher 1 ,on chairs 1 and hungry</p><p>　　philosopher 4 ,on chairs 4 and hungry</p><p>　　philosopher 4 get chopstics 4</p><p>　　philosopher 2 is f

56、ull and put down chopstics 2 and 3 and left</p><p>　　*********************************************</p><p>　　philosopher 1 get chopstics 2</p><p>　　**********************************

57、***********</p><p>　　Dining...philosopher: 1 ,on chairs 1 and eating</p><p>　　philosopher 0 ,on chairs 0 and hungry</p><p>　　philosopher 4 ,on chairs 4 and hungry</p><p&

58、gt;　　philosopher 1 is full and put down chopstics 1 and 2 and left</p><p>　　*********************************************</p><p>　　philosopher 0 get chopstics 1</p><p>　　***********

59、**********************************</p><p><b>　　Dining...</b></p><p>　　philosopher: 0 ,on chairs 0 and eating</p><p>　　philosopher 4 ,on chairs 4 and hungry</p>&l

60、t;p>　　philosopher 0 is full and put down chopstics 0 and 1 and left</p><p>　　*********************************************</p><p>　　philosopher 4 get chopstics 0</p><p>　　*******

61、**************************************</p><p><b>　　Dining...</b></p><p>　　philosopher: 4 ,on chairs 4 and eating</p><p>　　philosopher 4 is full and put down chopstics 4

62、and 0 and left</p><p><b>　　7．自我評(píng)析與總結(jié)</b></p><p>　　通過(guò)本次課程設(shè)計(jì)，我對(duì)哲學(xué)家就餐這一操作系統(tǒng)經(jīng)典問(wèn)題有了進(jìn)一步的了解，尤其是在設(shè)計(jì)進(jìn)程同步算法方面有了新的認(rèn)識(shí)。通過(guò)親自動(dòng)手和查詢(xún)資料，我知道了通過(guò)Linux系統(tǒng)的線程機(jī)制和信號(hào)量控制來(lái)實(shí)現(xiàn)哲學(xué)家就餐問(wèn)題的并發(fā)控制。在這次課程設(shè)計(jì)中，由于沒(méi)有掌握好進(jìn)程同步中的一些

63、關(guān)鍵知識(shí)，導(dǎo)致在實(shí)際操作中遇到了很多問(wèn)題，比如說(shuō)對(duì)信號(hào)燈初始化，可以用sem_init函數(shù)來(lái)很好的實(shí)現(xiàn)，而不需要在定義的時(shí)候就進(jìn)行初始化。在整個(gè)程序設(shè)計(jì)和完善中，遇到很多問(wèn)題，有些是由于對(duì)知識(shí)不了解引起的，有些是由于粗心引起的。此次課程設(shè)計(jì)使我明白，在程序設(shè)計(jì)中，我們需要有一個(gè)清晰的整體結(jié)構(gòu)，然后針對(duì)每個(gè)模塊逐步實(shí)現(xiàn)其功能，在設(shè)計(jì)中也需要有嚴(yán)謹(jǐn)和認(rèn)真的態(tài)度，才會(huì)更好的完成一項(xiàng)任務(wù)。</p><p><b&g

64、t;　　8．參考文獻(xiàn)</b></p><p>　　[1]《操作系統(tǒng)概念》(第七版) ，Abraham Silberschatz等著，高等教育出版社出版</p><p>　　[2]《Linux C 編程實(shí)踐》，童永清著，人民郵電出版社</p><p>　　[3]《操作系統(tǒng)》（第3版）（中譯本），OPERATING SYSTEMS(3RD EDITION),