操作系統(tǒng)課程設計---理發(fā)師問題的實現(xiàn)

1、<p>　　*******************</p><p><b>　　實踐教學</b></p><p>　　*******************</p><p><b>　　計算機與通信學院</b></p><p><b>　　2011年秋季學期</b>&

2、lt;/p><p><b>　　操作系統(tǒng) 課程設計</b></p><p>　　題 目：理發(fā)師問題的實現(xiàn) </p><p>　　專業(yè)班級：計算機科學與技術</p><p>　　姓 名： </p><p>　　學 號： </p&

3、gt;<p>　　指導教師： </p><p>　　成 績： </p><p><b>　　摘 要</b></p><p>　　理發(fā)師問題是一個利用信號量進行PV操作的經(jīng)典問題。設計程序實現(xiàn)此問題，要使得理發(fā)師的活動與顧客的活動得到各自真實的模擬。所執(zhí)行的程序

4、應體現(xiàn)：理發(fā)師在沒有顧客的時候去睡覺，有顧客則工作；顧客在理發(fā)師工作時坐下等待，無座時離開，直至等到理發(fā)師自己理發(fā)。</p><p>　　關鍵字：理發(fā)師，顧客，PV操作。</p><p><b>　　目錄</b></p><p><b>　　摘 要2</b></p><p><b>　

5、　1 設計要求4</b></p><p><b>　　1.1初始條件4</b></p><p><b>　　1.2技術要求4</b></p><p>　　2 總體設計思想及開發(fā)環(huán)境與工具4</p><p>　　2.1 總體設計思想4</p><p>　　

6、2.2 多線程編程原理5</p><p>　　2.2.1 創(chuàng)建一個線程5</p><p>　　2.2.2 等待一個線程結束5</p><p>　　2.2.3 信號量6</p><p>　　2.3 偽碼實現(xiàn)6</p><p>　　2.4 開發(fā)環(huán)境與工具8</p><p>　　3數(shù)據(jù)結構

7、與模塊說明8</p><p>　　3.1 數(shù)據(jù)結構8</p><p>　　3.2函數(shù)的調(diào)用關系圖8</p><p>　　3.2.1主函數(shù)模塊8</p><p>　　3.2.2 理發(fā)師模塊9</p><p>　　3.2.3 顧客模塊10</p><p><b>　　5運行結果

8、10</b></p><p>　　5.1運行步驟10</p><p>　　5.2測試結果11</p><p>　　5.2.1 編輯，編譯和運行的過程圖11</p><p>　　5.2.2 錯誤部分截圖12</p><p>　　5.2.3 正確運行結果圖12</p><p>

9、;<b>　　設計總結16</b></p><p><b>　　參考文獻17</b></p><p><b>　　致謝18</b></p><p>　　附錄（源程序代碼）19</p><p><b>　　1 設計要求</b></p>

10、<p><b>　　1.1初始條件</b></p><p>　?。?）操作系統(tǒng)：Linux</p><p>　?。?）程序設計語言：C語言</p><p>　?。?）設有一個理發(fā)師，5把椅子（另外還有一把理發(fā)椅），幾把椅子可用連續(xù)存儲單元。</p><p><b>　　1.2技術要求</b>

11、;</p><p>　?。?）為每個理發(fā)師／顧客產(chǎn)生一個線程，設計正確的同步算法</p><p>　?。?）每個顧客進入理發(fā)室后，即時顯示“Entered” 及其線程自定義標識，還同時顯示理發(fā)室共有幾名顧客及其所坐的位置。</p><p>　?。?）至少有10個顧客，每人理發(fā)至少3秒鐘。</p><p>　?。?）多個顧客須共享操作函數(shù)代碼。

12、</p><p>　　2 總體設計思想及開發(fā)環(huán)境與工具</p><p>　　2.1 總體設計思想</p><p>　　題目中要求描述理發(fā)師和顧客的行為，因此需要兩類線程barber()和customer ()分別描述理發(fā)師和顧客的行為。其中，理發(fā)師有活動有理發(fā)和睡覺兩個事件；等待和理發(fā)二個事件。店里有固定的椅子數(shù)，上面坐著等待的顧客，顧客在到來這個事件時，需判斷有沒

13、有空閑的椅子，理發(fā)師決定要理發(fā)或睡覺時，也要判斷椅子上有沒有顧客。所以，顧客和理發(fā)師之間的關系表現(xiàn)為：</p><p>　　（1）理發(fā)師和顧客之間同步關系：當理發(fā)師睡覺時顧客近來需要喚醒理發(fā)師為其理發(fā)，當有顧客時理發(fā)師為其理發(fā)，沒有的時候理發(fā)師睡覺。</p><p>　?。?）理發(fā)師和顧客之間互斥關系：由于每次理發(fā)師只能為一個人理發(fā)，且可供等侯的椅子有限只有n把，即理發(fā)師和椅子是臨界資源，

14、所以顧客之間是互斥的關系。</p><p>　?。?）故引入3個信號量和一個控制變量：</p><p>　　ⅰ控制變量waiting用來記錄等候理發(fā)的顧客數(shù)，初值為0；</p><p>　?、⑿盘柫縞ustomers用來記錄等候理發(fā)的顧客數(shù)，并用作阻塞理發(fā)師進程，初值為0；</p><p>　?、Ｐ盘柫縝arbers用來記錄正在等候顧客的理發(fā)

15、師數(shù)，并用作阻塞顧客進程，初值為1； ⅳ信號量mutex用于互斥，初值為1 </p><p>　　2.2 多線程編程原理</p><p>　　此次在Linux下進行多線程編程需要用到pthread_create和pthread_join這兩個函數(shù)。</p><p>　　2.2.1 創(chuàng)建一個線程</p><p>　　pthread_create

16、用來創(chuàng)建一個線程，原型為：</p><p>　　extern int pthread_create((pthread_t *__thread, __const pthread_attr_t *__attr,void *(*__start_routine) (void *), void *__arg))</p><p>　　第一個參數(shù)為指向線程標識符的指針，第二個參數(shù)用來設置線程屬性，第三個

17、參數(shù)是線程運行函數(shù)的起始地址，最后一個參數(shù)是運行函數(shù)的參數(shù)。函數(shù)thread不需要參數(shù)時，最后一個參數(shù)設為空指針。第二個參數(shù)設為空指針時，將生成默認屬性的線程。創(chuàng)建線程成功后，新創(chuàng)建的線程則運行參數(shù)三和參數(shù)四確定的函數(shù)，原來的線程則繼續(xù)運行下一行代碼。</p><p>　　2.2.2 等待一個線程結束</p><p>　　pthread_join用來等待一個線程的結束，函數(shù)原型為：<

18、/p><p>　　extern int pthread_join __P ((pthread_t __th, void **__thread_return));第一個參數(shù)為被等待的線程標識符，第二個參數(shù)為一個用戶定義的指針，它可以用來存</p><p>　　儲被等待線程的返回值。這個函數(shù)是一個線程阻塞的函數(shù)，調(diào)用它的函數(shù)將一直等待到被</p><p>　　等待的線程結

19、束為止，當函數(shù)返回時，被等待線程的資源被收回。</p><p><b>　　2.2.3 信號量</b></p><p>　?。?）函數(shù)sem_init（）用來初始化一個信號量，函數(shù)原型為： </p><p>　　extern int sem_init __P ((sem_t *__sem, int __pshared, unsigned int

20、 __value));</p><p>　　sem為指向信號量結構的一個指針；pshared不為０時此信號量在進程間共享，否則只能為當前進程的所有線程共享；value給出了信號量的初始值。</p><p>　?。?）函數(shù)sem_post( sem_t *sem )用來增加信號量的值。</p><p>　　當有線程阻塞在這個信號量上時，調(diào)用這個函數(shù)會使其中的一個線程不

21、在阻塞，選擇機制同樣是由線程的調(diào)度策略決定的。</p><p>　?。?）函數(shù)sem_wait( sem_t *sem )被用來阻塞當前線程直到信號量sem的值大于0，解除阻塞后將sem的值減一，表明公共資源經(jīng)使用后減少。函數(shù)sem_trywait ( sem_t *sem )是函數(shù)sem_wait（）的非阻塞版本，它直接將信號量sem的值減一。</p><p><b>　　2.

22、3 偽碼實現(xiàn)</b></p><p>　　difine n 5； //為顧客準備的椅子數(shù)為5 </p><p>　　semaphore mutex=1； //用于互斥</p><p>　　semaphore customers=0；//等候理發(fā)的顧客數(shù)</p><p>　　semaphore barbers=1；

23、//正在等候顧客的理發(fā)師數(shù)</p><p>　　int waiting=0； //等候理發(fā)的顧客數(shù) </p><p><b>　　//理發(fā)師線程</b></p><p>　　void barber() </p><p><b>　　{</b></p><p>　

24、　while(true) //判斷有無顧客</p><p><b>　　{</b></p><p>　　wait(customers); //若無顧客,理發(fā)師睡眠 </p><p>　　wait(mutex); //互斥 </p><

25、p>　　waiting--; //等候顧客數(shù)少一個</p><p>　　signal(mutex); //釋放臨界資源</p><p>　　signal(barber); //理發(fā)師去為一個顧客理發(fā)</p><p>　　cut_hair;

26、 //正在理發(fā)</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　//顧客線程</b></p><p>　　void customer() </p><p><b>　　{&l

27、t;/b></p><p>　　wait(mutex); //互斥</p><p>　　if (waiting<n) //如果有空椅子，則等待</p><p><b>　　{ </b></p><p>　　waiting++;

28、 //等候顧客數(shù)加1</p><p>　　signal(mutex); //釋放臨界資源</p><p>　　signal(customers); //如果理發(fā)師睡覺，喚醒理發(fā)師</p><p>　　wait(barber); //理發(fā)師在理發(fā), 顧客等候</p><p>　　get_

29、haircut; //顧客坐下等理發(fā)師 </p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　signal(mutex); //店里人滿了,顧客離開 </p><p><b>　　

30、}</b></p><p><b>　　}</b></p><p>　　2.4 開發(fā)環(huán)境與工具</p><p>　　系統(tǒng)平臺：LINUX環(huán)境</p><p><b>　　實現(xiàn)語言：C語言</b></p><p>　　開發(fā)工具：NANO編輯器</p>

31、<p>　　3數(shù)據(jù)結構與模塊說明</p><p><b>　　3.1 數(shù)據(jù)結構</b></p><p>　　通過分析課程設計要求，定義以下的數(shù)據(jù):</p><p>　　sem_t mutex,customers,barbers; //design three semaphores: mutex,customer,barbers<

32、/p><p>　　int waiting=0; //the number of waiting customers</p><p>　　int chair[5];</p><p>　　3.2函數(shù)的調(diào)用關系圖</p><p>　　3.2.1主函數(shù)模塊</p><p><b>　　主函數(shù)流程圖如下：</b&g

33、t;</p><p>　　3.2.2 理發(fā)師模塊</p><p>　　理發(fā)師模塊函數(shù)流程圖如下：</p><p>　　3.2.3 顧客模塊</p><p>　　顧客模塊函數(shù)流程圖如下：</p><p><b>　　5運行結果</b></p><p><b>　　5

34、.1運行步驟</b></p><p>　　(1) 打開桌面上的putty.exe，輸入IP地址192.168.1.254，進入開發(fā)環(huán)境。創(chuàng)建一個用來寫程序的文件，這里用的是nano編輯器來編寫c程序。創(chuàng)建SleepingBarber.c的命令為：nano 進入編輯環(huán)境，輸入代碼，結束后按ctrl+x保存為SleepingBarber.c，進入文件的命令為：nano SleepingBarber.c，然

35、后可以對其進行修改。</p><p>　　(2) 編譯源程序，編譯命令為：</p><p>　　cc -lpthread -o 　 SleepingBarber　 SleepingBarber.c</p><p>　　(3) 編譯無錯誤后，運行程序，命令為：</p><p>　　./ SleepingBarber</p>&

36、lt;p><b>　　5.2測試結果</b></p><p>　　5.2.1 編輯，編譯和運行的過程圖</p><p><b>　　\</b></p><p>　　5.2.2 錯誤部分截圖</p><p>　　5.2.3 正確運行結果圖</p><p>　　第一次運行結

37、果如下圖：</p><p>　　第二次運行結果如下圖：</p><p>　　第三次運行結果如下圖；</p><p><b>　　設計總結</b></p><p>　　兩周的的操作系統(tǒng)課程設計終于完成了，回想這兩周的努力，感觸良多。拿到題目時我不知從何下手，想想自己對Liunx一無所知，無奈，只好去查閱相關書籍，并在網(wǎng)上查

38、找了相關資料，了解了linux多線程編程的原理，應注意的問題，及一些常用命令</p><p>　　第一周先設計出了該程序的偽代碼即其wait、signal操作。然后，根據(jù)其要求進行編程，由于使用的是多線程編程，開始進行編譯的時候，編譯命令輸入錯誤，沒有輸入-lpthread，程序總是出現(xiàn)錯誤。同時，創(chuàng)建線程函數(shù)時，由于對其格式輸入錯誤導致程序無法運行。例如sb.c，sb1.c等都為本次調(diào)試時的程序。</p&

39、gt;<p>　　第二周主要是不斷的調(diào)試并完善程序。程序可以運行，但與要求總有些不符，故不斷的進行修改，并對其輸出的格式進行完善，使其輸出看起來美觀一些，容易觀察一些。例如s.c，b.c等程序為此次調(diào)試結果。</p><p>　　然后是在原有代碼的基礎上，使程序更完整些。并進行結果的截圖，開始設計并編寫課程設計說明書。</p><p>　　通過本次編程我熟悉了linux 下的

40、多線程編程和信號量實現(xiàn)wait、signal操作的全過程，對同步和互斥問題也有了更深一步的理解，同時，也使我對linux編程有了更多的了解，在很多方面，它與在windows下編程有著很大的不同，對與多線程來說更方便一些。</p><p>　　設計過程中也遇到不少困難，尤其是對于多線程的實現(xiàn)，結果總是不如想象中完美。比如其顧客編號的輸出有時會不按順序，輸入有點亂。另外，有時，輸出結束后，程序仍無法結束，必須強制性關

41、閉終端才可以結束程序，這是本程序的一個不足之處。</p><p>　　在本次課程設計中我深深感覺到自己掌握的知識還遠遠不夠，我明白光是知道書本上的知識是遠遠不夠的，一定要把理論知識和實踐結合起來。同時，要多多學習linux的操作。</p><p><b>　　參考文獻</b></p><p>　　1. 湯子瀛，哲鳳屏.《計算機操作系統(tǒng)》.西安電

42、子科技大學學出版社.</p><p>　　2. 王清，李光明.《計算機操作系統(tǒng)》.冶金工業(yè)出版社.</p><p>　　3.孫鐘秀等. 操作系統(tǒng)教程. 高等教育出版社</p><p>　　4.曾明.  Linux操作系統(tǒng)應用教程. 陜西科學技術出版社. </p><p>　　5. 張麗芬，劉利雄.《操作系統(tǒng)實驗教程》. 清華大學出版

43、社.</p><p>　　6. 孟靜， 操作系統(tǒng)教程－－原理和實例分析. 高等教育出版社</p><p>　　7. 周長林，計算機操作系統(tǒng)教程. 高等教育出版社</p><p>　　8. 張堯學，計算機操作系統(tǒng)教程，清華大學出版社</p><p>　　9. 任滿杰，操作系統(tǒng)原理實用教程，電子工業(yè)出版社</p><

44、p><b>　　致謝</b></p><p>　　在此次課程設計的過程中，我首先要感謝我的指導老師xx老師，給了我很大的幫助，與此同時感謝宿舍的舍友，對此次課程設計的程序的調(diào)試工作給予了大力的幫助。</p><p><b>　　附錄（源程序代碼）</b></p><p>　　#include<stdio.h&g

45、t;</p><p>　　#include<stdlib.h></p><p>　　#include<unistd.h></p><p>　　#include<pthread.h></p><p>　　#include<semaphore.h></p><p>　　#in

46、clude<fcntl.h></p><p>　　#include<errno.h></p><p>　　#define n 5 //the shop have five chairs</p><p>　　//design three semaphores: mutex,customer,barbers</p><p&

47、gt;　　sem_t mutex,customers,barbers;</p><p>　　int waiting=0; //the number of waiting customers</p><p>　　int chair[5]; </p><p>　　void * barber();</p><p>　　void * custome

48、r(void *arg);</p><p>　　int main(int argc,char *argv[])</p><p><b>　　{</b></p><p>　　//create 10 semaphores and one Barber semaphore</p><p>　　pthread_t Custome

49、r_id[10],Barber_id;</p><p><b>　　int i;</b></p><p>　　sem_init(&mutex,0,1); //init mutex semaphore to 1</p><p>　　sem_init(&customers,0,0);//init semaphore custome

50、rs to 0</p><p>　　sem_init(&barbers,0,1);</p><p>　　for(i=0;i<5;i++)</p><p>　　pthread_create(&Barber_id,NULL,(void*)barber,NULL);</p><p>　　for (i=0;i<10;i++

51、)</p><p>　　pthread_create(&Customer_id[i],NULL,(void*)customer,(void*)(i+1)); </p><p>　　for (i=0;i<10;i++)</p><p>　　pthread_join(Customer_id[i],NULL);</p><p>　　f

52、or(i=0;i<5;i++)</p><p>　　pthread_join(Barber_id,NULL);</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　//creat barber pthread</p>

53、<p>　　void * barber()</p><p><b>　　{</b></p><p><b>　　int i; </b></p><p>　　int next; </p><p>　　//wait(customers),if no customers,barber slee

54、ping</p><p>　　sem_wait(&customers); </p><p>　　sem_wait(&mutex); //wait(mutex)</p><p>　　waiting--; //the numer of waiting reduce one</p><p>　　for(i=0;i<

55、5;i++)</p><p><b>　　{ </b></p><p>　　if (chair[i]!=0) </p><p><b>　　{ </b></p><p>　　next= chair[i]; </p><p>　　chair[i]=0;</p>&

56、lt;p><b>　　break; </b></p><p><b>　　} </b></p><p><b>　　} </b></p><p>　　printf("The barber is cutting %dth customer's hair\n",next)

57、;</p><p><b>　　sleep(3);</b></p><p>　　sem_post(&mutex);</p><p>　　sem_post(&barbers);</p><p><b>　　} </b></p><p>　　//creat cu

58、stomer pthread</p><p>　　void * customer(void *arg)</p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　sem_wait(&mutex); //wait(mutex) if(wai

59、ting<n)</p><p>　　if(waiting<n)</p><p><b>　　{</b></p><p>　　waiting++; //the numer of waiting plus one</p><p>　　for(i=0;i<5;i++) </p><p&g

60、t;<b>　　{ </b></p><p>　　if (chair[i]==0) </p><p><b>　　{ </b></p><p>　　chair[i]=(int)arg; </p><p><b>　　break;</b></p><p>

61、<b>　　}</b></p><p><b>　　}</b></p><p>　　printf("***************************************************\n"); </p><p>　　printf("Entered:Number %d cus

62、tomer comes,and sits at %d chair \n",(int)arg,(i+1));</p><p>　　printf("There are %d customer on the chair\n",waiting); </p><p>　　printf("The customers' location are:"

63、;); </p><p>　　for(i=0;i<5;i++) </p><p>　　printf("%d ",chair[i]); </p><p>　　printf("\n"); </p><p><b>　　sleep(1);</b></p><

64、p>　　sem_post(&mutex); //signal(mutex)</p><p>　　sem_post(&customers); //signal(customers)</p><p>　　sem_wait(&barbers); //wait(barbers)</p><p><b>　　}</b>&l

65、t;/p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　printf("Number %d comes,there are no chairs,the customer %d is leaving\n",(int)arg,(int)arg); </p