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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上*實(shí)踐教學(xué)* 蘭州理工大學(xué)計(jì)算機(jī)與通信學(xué)院2011年秋季學(xué)期 操作系統(tǒng) 課程設(shè)計(jì)題 目：理發(fā)師問題的實(shí)現(xiàn) 專業(yè)班級(jí)：計(jì)算機(jī)科學(xué)與技術(shù)姓 名： 學(xué) 號(hào)： 指導(dǎo)教師： 成 績(jī)： 摘 要 理發(fā)師問題是一個(gè)利用信號(hào)量進(jìn)行PV操作的經(jīng)典問題。設(shè)計(jì)程序?qū)崿F(xiàn)此問題，要使得理發(fā)師的活動(dòng)與顧客的活動(dòng)得到各自真實(shí)的模擬。所執(zhí)行的程序應(yīng)體現(xiàn)：理發(fā)師在沒有顧客的時(shí)候去睡覺，有顧客則工作；顧客在理發(fā)師工作時(shí)坐下等待，無座時(shí)離開，直至等到理發(fā)師自己理發(fā)。關(guān)鍵字：理發(fā)師，顧客，PV操作。目錄1 設(shè)計(jì)要求1.1初始條件（1）操作系統(tǒng)：Linux（2）程序設(shè)計(jì)語言：C語言（3）設(shè)有一個(gè)理發(fā)師，5把椅子

2、（另外還有一把理發(fā)椅），幾把椅子可用連續(xù)存儲(chǔ)單元。1.2技術(shù)要求（1）為每個(gè)理發(fā)師顧客產(chǎn)生一個(gè)線程，設(shè)計(jì)正確的同步算法（2）每個(gè)顧客進(jìn)入理發(fā)室后，即時(shí)顯示“Entered” 及其線程自定義標(biāo)識(shí)，還同時(shí)顯示理發(fā)室共有幾名顧客及其所坐的位置。（3）至少有10個(gè)顧客，每人理發(fā)至少3秒鐘。（4）多個(gè)顧客須共享操作函數(shù)代碼。2 總體設(shè)計(jì)思想及開發(fā)環(huán)境與工具2.1 總體設(shè)計(jì)思想題目中要求描述理發(fā)師和顧客的行為，因此需要兩類線程barber()和customer ()分別描述理發(fā)師和顧客的行為。其中，理發(fā)師有活動(dòng)有理發(fā)和睡覺兩個(gè)事件；等待和理發(fā)二個(gè)事件。店里有固定的椅子數(shù)，上面坐著等待的顧客，顧客在到來這個(gè)

3、事件時(shí)，需判斷有沒有空閑的椅子，理發(fā)師決定要理發(fā)或睡覺時(shí)，也要判斷椅子上有沒有顧客。所以，顧客和理發(fā)師之間的關(guān)系表現(xiàn)為：（1）理發(fā)師和顧客之間同步關(guān)系：當(dāng)理發(fā)師睡覺時(shí)顧客近來需要喚醒理發(fā)師為其理發(fā)，當(dāng)有顧客時(shí)理發(fā)師為其理發(fā)，沒有的時(shí)候理發(fā)師睡覺。（2）理發(fā)師和顧客之間互斥關(guān)系：由于每次理發(fā)師只能為一個(gè)人理發(fā)，且可供等侯的椅子有限只有n把，即理發(fā)師和椅子是臨界資源，所以顧客之間是互斥的關(guān)系。（3）故引入3個(gè)信號(hào)量和一個(gè)控制變量：控制變量waiting用來記錄等候理發(fā)的顧客數(shù)，初值為0；信號(hào)量customers用來記錄等候理發(fā)的顧客數(shù)，并用作阻塞理發(fā)師進(jìn)程，初值為0；信號(hào)量barbers用來記錄正

4、在等候顧客的理發(fā)師數(shù)，并用作阻塞顧客進(jìn)程，初值為1； 信號(hào)量mutex用于互斥，初值為1 2.2 多線程編程原理此次在Linux下進(jìn)行多線程編程需要用到pthread_create和pthread_join這兩個(gè)函數(shù)。2.2.1 創(chuàng)建一個(gè)線程pthread_create用來創(chuàng)建一個(gè)線程，原型為：extern int pthread_create(pthread_t *_thread, _const pthread_attr_t *_attr,void *(*_start_routine) (void *), void *_arg)第一個(gè)參數(shù)為指向線程標(biāo)識(shí)符的指針，第二個(gè)參數(shù)用來設(shè)置線程屬性，第

5、三個(gè)參數(shù)是線程運(yùn)行函數(shù)的起始地址，最后一個(gè)參數(shù)是運(yùn)行函數(shù)的參數(shù)。函數(shù)thread不需要參數(shù)時(shí)，最后一個(gè)參數(shù)設(shè)為空指針。第二個(gè)參數(shù)設(shè)為空指針時(shí)，將生成默認(rèn)屬性的線程。創(chuàng)建線程成功后，新創(chuàng)建的線程則運(yùn)行參數(shù)三和參數(shù)四確定的函數(shù)，原來的線程則繼續(xù)運(yùn)行下一行代碼。2.2.2 等待一個(gè)線程結(jié)束pthread_join用來等待一個(gè)線程的結(jié)束，函數(shù)原型為：extern int pthread_join _P (pthread_t _th, void *_thread_return);第一個(gè)參數(shù)為被等待的線程標(biāo)識(shí)符，第二個(gè)參數(shù)為一個(gè)用戶定義的指針，它可以用來存儲(chǔ)被等待線程的返回值。這個(gè)函數(shù)是一個(gè)線程阻塞的函數(shù)

6、，調(diào)用它的函數(shù)將一直等待到被等待的線程結(jié)束為止，當(dāng)函數(shù)返回時(shí)，被等待線程的資源被收回。2.2.3 信號(hào)量（1）函數(shù)sem_init（）用來初始化一個(gè)信號(hào)量，函數(shù)原型為： extern int sem_init _P (sem_t *_sem, int _pshared, unsigned int _value);sem為指向信號(hào)量結(jié)構(gòu)的一個(gè)指針；pshared不為時(shí)此信號(hào)量在進(jìn)程間共享，否則只能為當(dāng)前進(jìn)程的所有線程共享；value給出了信號(hào)量的初始值。（2）函數(shù)sem_post( sem_t *sem )用來增加信號(hào)量的值。當(dāng)有線程阻塞在這個(gè)信號(hào)量上時(shí)，調(diào)用這個(gè)函數(shù)會(huì)使其中的一個(gè)線程不在阻塞，

7、選擇機(jī)制同樣是由線程的調(diào)度策略決定的。（3）函數(shù)sem_wait( sem_t *sem )被用來阻塞當(dāng)前線程直到信號(hào)量sem的值大于0，解除阻塞后將sem的值減一，表明公共資源經(jīng)使用后減少。函數(shù)sem_trywait ( sem_t *sem )是函數(shù)sem_wait（）的非阻塞版本，它直接將信號(hào)量sem的值減一。2.3 偽碼實(shí)現(xiàn) difine n 5； /為顧客準(zhǔn)備的椅子數(shù)為5 semaphore mutex=1； /用于互斥 semaphore customers=0；/等候理發(fā)的顧客數(shù) semaphore barbers=1；/正在等候顧客的理發(fā)師數(shù) int waiting=0； /等

8、候理發(fā)的顧客數(shù) /理發(fā)師線程 void barber() while(true) /判斷有無顧客 wait(customers); /若無顧客,理發(fā)師睡眠 wait(mutex); /互斥 waiting-; /等候顧客數(shù)少一個(gè) signal(mutex); /釋放臨界資源signal(barber); /理發(fā)師去為一個(gè)顧客理發(fā)cut_hair; /正在理發(fā) /顧客線程void customer() wait(mutex); /互斥 if (waiting<n) /如果有空椅子，則等待 waiting+; /等候顧客數(shù)加1 signal(mutex); /釋放臨界資源signal(cus

9、tomers); /如果理發(fā)師睡覺，喚醒理發(fā)師 wait(barber); /理發(fā)師在理發(fā), 顧客等候 get_haircut; /顧客坐下等理發(fā)師 else signal(mutex); /店里人滿了,顧客離開 2.4 開發(fā)環(huán)境與工具系統(tǒng)平臺(tái)：LINUX環(huán)境實(shí)現(xiàn)語言：C語言開發(fā)工具：NANO編輯器3數(shù)據(jù)結(jié)構(gòu)與模塊說明3.1 數(shù)據(jù)結(jié)構(gòu)通過分析課程設(shè)計(jì)要求，定義以下的數(shù)據(jù):sem_t mutex,customers,barbers; /design three semaphores: mutex,customer,barbersint waiting=0; /the number of wait

10、ing customersint chair5;3.2函數(shù)的調(diào)用關(guān)系圖3.2.1主函數(shù)模塊主函數(shù)流程圖如下：3.2.2 理發(fā)師模塊 理發(fā)師模塊函數(shù)流程圖如下：3.2.3 顧客模塊顧客模塊函數(shù)流程圖如下：5運(yùn)行結(jié)果5.1運(yùn)行步驟(1) 打開桌面上的putty.exe，輸入IP地址192.168.1.254，進(jìn)入開發(fā)環(huán)境。創(chuàng)建一個(gè)用來寫程序的文件，這里用的是nano編輯器來編寫c程序。創(chuàng)建SleepingBarber.c的命令為：nano 進(jìn)入編輯環(huán)境，輸入代碼，結(jié)束后按ctrl+x保存為SleepingBarber.c，進(jìn)入文件的命令為：nano SleepingBarber.c，然后可以對(duì)其進(jìn)

11、行修改。(2) 編譯源程序，編譯命令為：cc -lpthread -o SleepingBarber SleepingBarber.c(3) 編譯無錯(cuò)誤后，運(yùn)行程序，命令為： ./ SleepingBarber5.2測(cè)試結(jié)果5.2.1 編輯，編譯和運(yùn)行的過程圖5.2.2 錯(cuò)誤部分截圖5.2.3 正確運(yùn)行結(jié)果圖第一次運(yùn)行結(jié)果如下圖：第二次運(yùn)行結(jié)果如下圖：第三次運(yùn)行結(jié)果如下圖；設(shè)計(jì)總結(jié)兩周的的操作系統(tǒng)課程設(shè)計(jì)終于完成了，回想這兩周的努力，感觸良多。拿到題目時(shí)我不知從何下手，想想自己對(duì)Liunx一無所知，無奈，只好去查閱相關(guān)書籍，并在網(wǎng)上查找了相關(guān)資料，了解了linux多線程編程的原理，應(yīng)注意的問題

12、，及一些常用命令第一周先設(shè)計(jì)出了該程序的偽代碼即其wait、signal操作。然后，根據(jù)其要求進(jìn)行編程，由于使用的是多線程編程，開始進(jìn)行編譯的時(shí)候，編譯命令輸入錯(cuò)誤，沒有輸入-lpthread，程序總是出現(xiàn)錯(cuò)誤。同時(shí)，創(chuàng)建線程函數(shù)時(shí)，由于對(duì)其格式輸入錯(cuò)誤導(dǎo)致程序無法運(yùn)行。例如sb.c，sb1.c等都為本次調(diào)試時(shí)的程序。第二周主要是不斷的調(diào)試并完善程序。程序可以運(yùn)行，但與要求總有些不符，故不斷的進(jìn)行修改，并對(duì)其輸出的格式進(jìn)行完善，使其輸出看起來美觀一些，容易觀察一些。例如s.c，b.c等程序?yàn)榇舜握{(diào)試結(jié)果。然后是在原有代碼的基礎(chǔ)上，使程序更完整些。并進(jìn)行結(jié)果的截圖，開始設(shè)計(jì)并編寫課程設(shè)計(jì)說明書。

13、通過本次編程我熟悉了linux 下的多線程編程和信號(hào)量實(shí)現(xiàn)wait、signal操作的全過程，對(duì)同步和互斥問題也有了更深一步的理解，同時(shí)，也使我對(duì)linux編程有了更多的了解，在很多方面，它與在windows下編程有著很大的不同，對(duì)與多線程來說更方便一些。 設(shè)計(jì)過程中也遇到不少困難，尤其是對(duì)于多線程的實(shí)現(xiàn)，結(jié)果總是不如想象中完美。比如其顧客編號(hào)的輸出有時(shí)會(huì)不按順序，輸入有點(diǎn)亂。另外，有時(shí)，輸出結(jié)束后，程序仍無法結(jié)束，必須強(qiáng)制性關(guān)閉終端才可以結(jié)束程序，這是本程序的一個(gè)不足之處。在本次課程設(shè)計(jì)中我深深感覺到自己掌握的知識(shí)還遠(yuǎn)遠(yuǎn)不夠，我明白光是知道書本上的知識(shí)是遠(yuǎn)遠(yuǎn)不夠的，一定要把理論知識(shí)和實(shí)踐結(jié)合

14、起來。同時(shí)，要多多學(xué)習(xí)linux的操作。參考文獻(xiàn)1. 湯子瀛，哲鳳屏.計(jì)算機(jī)操作系統(tǒng).西安電子科技大學(xué)學(xué)出版社.2. 王清，李光明.計(jì)算機(jī)操作系統(tǒng).冶金工業(yè)出版社.3.孫鐘秀等. . 高等教育出版社4.曾明.  . 陜西科學(xué)技術(shù)出版社. 5. 張麗芬，劉利雄.操作系統(tǒng)實(shí)驗(yàn)教程. 清華大學(xué)出版社.6. 孟靜， . 高等教育出版社7. 周長(zhǎng)林，. 高等教育出版社8. 張堯?qū)W，清華大學(xué)出版社9. 任滿杰，電子工業(yè)出版社致謝在此次課程設(shè)計(jì)的過程中，我首先要感謝我的指導(dǎo)老師張永老師，給了我很大的幫助，與此同時(shí)感謝宿舍的舍友，對(duì)此次課程設(shè)計(jì)的程序的調(diào)試工作給予了大力的幫助。附錄（源程序

15、代碼）#include<stdio.h>#include<stdlib.h>#include<unistd.h>#include<pthread.h>#include<semaphore.h>#include<fcntl.h>#include<errno.h>#define n 5 /the shop have five chairs/design three semaphores: mutex,customer,barberssem_t mutex,customers,barbers;int waiting=

16、0; /the number of waiting customersint chair5; void * barber();void * customer(void *arg);int main(int argc,char *argv) /create 10 semaphores and one Barber semaphore pthread_t Customer_id10,Barber_id; int i; sem_init(&mutex,0,1); /init mutex semaphore to 1 sem_init(&customers,0,0);/init sem

17、aphore customers to 0 sem_init(&barbers,0,1); for(i=0;i<5;i+) pthread_create(&Barber_id,NULL,(void*)barber,NULL); for (i=0;i<10;i+) pthread_create(&Customer_idi,NULL,(void*)customer,(void*)(i+1); for (i=0;i<10;i+) pthread_join(Customer_idi,NULL); for(i=0;i<5;i+) pthread_join(

18、Barber_id,NULL); return 0;/creat barber pthreadvoid * barber() int i; int next; /wait(customers),if no customers,barber sleeping sem_wait(&customers); sem_wait(&mutex); /wait(mutex) waiting-; /the numer of waiting reduce one for(i=0;i<5;i+) if (chairi!=0) next= chairi; chairi=0; break; printf("The barber is cutting %dth customer's hairn",next); sleep(3); sem_post(&mutex); sem_post(&barbers); /creat customer pthreadvoid * customer(void *arg) int i; sem_wait(&mutex); /wait(mutex) if(waiting<n) if(waiting<n) waiting+; /the numer of waiting plus one fo