操作系統(tǒng)課程設(shè)計(jì)用多線程同步方法解決睡眠理發(fā)師問題

1、學(xué)號：XXXXXXXXXXXXXXX課程設(shè)計(jì)題目學(xué)院用多線程同步方法解決睡眠理發(fā)師問題（ Sleeping-Barber Problem)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院專業(yè)軟件工程班級姓名指導(dǎo)教師2010年6月28日課程設(shè)計(jì)任務(wù)書學(xué)生姓名：專業(yè)班級：指導(dǎo)教師：工作單位：題目 :用多線程同步方法解決睡眠理發(fā)師問題（Sleeping-Barber Problem)初始條件：1操作系統(tǒng)： Linux2程序設(shè)計(jì)語言： C 語言3. 設(shè)有一個(gè)理發(fā)師， 5 把椅子（另外還有一把理發(fā)椅） ，幾把椅子可用連續(xù)存儲單元。要求完成的主要任務(wù) : （包括課程設(shè)計(jì)工作量及其技術(shù)要求，以及說明書撰寫等具體要求）1技術(shù)要求：1）為

2、每個(gè)理發(fā)師顧客產(chǎn)生一個(gè)線程，設(shè)計(jì)正確的同步算法2）每個(gè)顧客進(jìn)入理發(fā)室后，即時(shí)顯示“Entered”及其線程自定義標(biāo)識，還同時(shí)顯示理發(fā)室共有幾名顧客及其所坐的位置。3）至少有 10 個(gè)顧客，每人理發(fā)至少3 秒鐘。4）多個(gè)顧客須共享操作函數(shù)代碼。2 設(shè)計(jì)說明書內(nèi)容要求：1)設(shè)計(jì)題目與要求2) 總的設(shè)計(jì)思想及系統(tǒng)平臺、語言、工具等。3）數(shù)據(jù)結(jié)構(gòu)與模塊說明（功能與流程圖）4）給出 用戶名、源程序名、目標(biāo)程序名和源程序及其運(yùn)行結(jié)果。 （要注明存儲各個(gè)程序及其運(yùn)行結(jié)果的主機(jī) IP 地址和目錄。）5）運(yùn)行結(jié)果與運(yùn)行情況（提示 :(1)連續(xù)存儲區(qū)可用數(shù)組實(shí)現(xiàn)。(2)編譯命令可用：cc-lpthread-o目標(biāo)

3、文件名源文件名(3)多線程編程方法參見附件。 ）3.調(diào)試報(bào)告：1) 調(diào)試記錄2) 自我評析和總結(jié)上機(jī)時(shí)間安排：18 周一 五 08：0 12：00指導(dǎo)教師簽名：年月日系主任（或責(zé)任教師）簽名：年月日目錄1設(shè)計(jì)題目與要求 .41.1設(shè)計(jì)題目 .41.2設(shè)計(jì)要求 .41.2.1初始條件 .41.2.2技術(shù)要求 .42總體設(shè)計(jì)思想及開發(fā)環(huán)境與工具.42.1總體設(shè)計(jì)思想 .42.2多線程編程原理 .52.2.1創(chuàng)建一個(gè)線程 .52.2.2等待一個(gè)線程結(jié)束 .52.2.3信號量 .62.3偽碼實(shí)現(xiàn) .62.4開發(fā)環(huán)境與工具 .73數(shù)據(jù)結(jié)構(gòu)與模塊說明 .83.1數(shù)據(jù)結(jié)構(gòu) .83.2程序模塊說明 .83.2

4、.1主函數(shù)模塊 .83.2.2理發(fā)師模塊 .93.2.3顧客模塊 .94源程序.104.1用戶名、源程序名和目標(biāo)程序名.104.2源程序代碼 .115運(yùn)行結(jié)果 .145.1運(yùn)行步驟 .145.2運(yùn)行結(jié)果 .155.2.1編輯，編譯和運(yùn)行的過程圖.155.2.2錯(cuò)誤部分截圖 .165.2.3正確運(yùn)行結(jié)果圖 .166調(diào)試記錄 .186.1調(diào)試記錄 .186.2自我評析和總結(jié) .197參考文獻(xiàn) .191 設(shè)計(jì)題目與要求1.1設(shè)計(jì)題目用多線程同步方法解決睡眠理發(fā)師問題（Sleeping-Barber Problem)1.2設(shè)計(jì)要求1.2.1初始條件（ 1）操作系統(tǒng)： Linux（ 2）程序設(shè)計(jì)語言：

5、C 語言（ 3）設(shè)有一個(gè)理發(fā)師， 5 把椅子（另外還有一把理發(fā)椅） ，幾把椅子可用連續(xù)存儲單元。1.2.2技術(shù)要求（ 1）為每個(gè)理發(fā)師顧客產(chǎn)生一個(gè)線程，設(shè)計(jì)正確的同步算法（ 2）每個(gè)顧客進(jìn)入理發(fā)室后，即時(shí)顯示“ Entered”及其線程自定義標(biāo)識，還同時(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ā)師有活動有理發(fā)和睡覺兩個(gè)事件；等待和理

6、發(fā)二個(gè)事件。店里有固定的椅子數(shù)，上面坐著等待的顧客，顧客在到來這個(gè)事件時(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è)信號量和一個(gè)控制變量：控制變量 waiting 用來記錄等候理發(fā)的顧客數(shù)，初值為 0；信號量 customers用

7、來記錄等候理發(fā)的顧客數(shù)，并用作阻塞理發(fā)師進(jìn)程，初值為0；信號量 barbers用來記錄正在等候顧客的理發(fā)師數(shù)，并用作阻塞顧客進(jìn)程，初值為1；信號量 mutex 用于互斥，初值為 12.2多線程編程原理此次在 Linux 下進(jìn)行多線程編程需要用到pthread_create和 pthread_join這兩個(gè)函數(shù)。2.2.1創(chuàng)建一個(gè)線程pthread_create用來創(chuàng)建一個(gè)線程，原型為：externintpthread_create(pthread_t*_thread,_constpthread_attr_t*_attr,void*(*_start_routine) (void *), void

8、 *_arg)第一個(gè)參數(shù)為指向線程標(biāo)識符的指針，第二個(gè)參數(shù)用來設(shè)置線程屬性，第三個(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)識符，第二個(gè)參數(shù)為一

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

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

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

12、nal(customers);wait(barber);/get_haircut;/等候顧客數(shù)加 1釋放臨界資源如果理發(fā)師睡覺，喚醒理發(fā)師理發(fā)師在理發(fā) ,顧客等候顧客坐下等理發(fā)師elsesignal(mutex);/店里人滿了, 顧客離開2.4開發(fā)環(huán)境與工具系統(tǒng)平臺： 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 threesemaphores: mutex,customer,barbersint waiting=0; /the

13、 number of waiting customersint chair5;3.2 程序模塊說明3.2.1主函數(shù)模塊主函數(shù)流程圖如下：3.2.2理發(fā)師模塊理發(fā)師模塊函數(shù)流程圖如下：3.2.3顧客模塊顧客模塊函數(shù)流程圖如下：4 源程序4.1 用戶名、源程序名和目標(biāo)程序名用戶名： rj070234源程序名： SleepingBarber.c目標(biāo)程序名：SleepingBarber主機(jī) IP 地址： 192.168.1.2544.2 源程序代碼#include<stdio.h>#include<stdlib.h>#include<unistd.h>#includ

14、e<pthread.h>#include<semaphore.h>#include<fcntl.h>#include<errno.h>#define n 5/the shop have five chairs/design three semaphores: mutex,customer,barbers sem_t mutex,customers,barbers;int waiting=0; /the number of waiting customersint chair5;void * barber();void * customer(voi

15、d *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 1sem_init(&customers,0,0);/init semaphore customers to 0 sem_init(&barbers,0,1);for(i=0;i<5;i+)pthread_create(&am

16、p;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(Barber_id,NULL);return 0;/creat barber pthreadvoid * barber()int i;int next;/wait(customers)

17、,if no customers,barber sleepingsem_wait(&customers);sem_wait(&mutex);/wait(mutex)waiting-;/the numer of waiting reduce onefor(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_p

18、ost(&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 onefor(i=0;i<5;i+)if (chairi=0)chairi=(int)arg;break;printf("*n");printf("Entered:Number %d customer come

19、s,and sits at %d chair n",(int)arg,(i+1);printf("There are %d customer on the chairn",waiting);printf("The customers' location are:");for(i=0;i<5;i+)printf("%d",chairi);printf("n");sleep(1);sem_post(&mutex); /signal(mutex)sem_post(&customer

20、s); /signal(customers)sem_wait(&barbers); /wait(barbers)elseprintf("Number%dcomes,therearenochairs,thecustomer%disleavingn",(int)arg,(int)arg);sem_post(&mutex);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

21、的命令為： nano 進(jìn)入編輯環(huán)境，輸入代碼，結(jié)束后按ctrl+x 保存為SleepingBarber.c ，進(jìn)入文件的命令為：nano SleepingBarber.c ，然后可以對其進(jìn)行修改。(2) 編譯源程序，編譯命令為：cc-lpthread-oSleepingBarberSleepingBarber.c(3) 編譯無錯(cuò)誤后，運(yùn)行程序，命令為：./ SleepingBarber5.2 運(yùn)行結(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é)果如下圖；6 調(diào)試記錄6.1 調(diào)試記錄周一因有培訓(xùn)與課

22、設(shè)時(shí)間沖突，故沒有上機(jī)操作，查閱了相關(guān)書籍，并在網(wǎng)上查找了相關(guān)資料，了解了linux多線程編程的原理，應(yīng)注意的問題，及一些常用命令周二先設(shè)計(jì)出了該程序的偽代碼即其wait 、signal操作。然后，根據(jù)其要求進(jìn)行編程，由于使用的是多線程編程， 開始進(jìn)行編譯的時(shí)候， 編譯命令輸入錯(cuò)誤， 沒有輸入 -lpthread，程序總是出現(xiàn)錯(cuò)誤。同時(shí)，創(chuàng)建線程函數(shù)時(shí)，由于對其格式輸入錯(cuò)誤導(dǎo)致程序無法運(yùn)行。例如 sb.c ， sb1.c 等都為本次調(diào)試時(shí)的程序。周三主要是不斷的調(diào)試并完善程序。程序可以運(yùn)行，但與要求總有些不符，故不斷的進(jìn)行修改，并對其輸出的格式進(jìn)行完善， 使其輸出看起來美觀一些， 容易觀察一些。 例如 s.c ，b.c 等程序?yàn)榇舜握{(diào)試結(jié)果。周四主要是在原有代碼的基礎(chǔ)上，使程序更完整些。并進(jìn)行結(jié)果的截圖，開始設(shè)計(jì)并編寫課程設(shè)計(jì)報(bào)告。6.2 自我評析和總結(jié)通過本次編程我熟悉了 linux 下的多線程編程和信號量實(shí)現(xiàn) wait 、signal 操作的全過程，對同步和互斥問題也有了更深一步的理解，同時(shí)，也