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

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

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

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

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

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

6、發(fā)二個事件。店里有固定的椅子數(shù)，上面坐著等待的顧客，顧客在到來這個事件時，需判斷有沒有空閑的椅子，理發(fā)師決定要理發(fā)或睡覺時，也要判斷椅子上有沒有顧客。所以，顧客和理發(fā)師之間的關系表現(xiàn)為：（1）理發(fā)師和顧客之間同步關系：當理發(fā)師睡覺時顧客近來需要喚醒理發(fā)師為其理發(fā)，當有顧客時理發(fā)師為其理發(fā)，沒有的時候理發(fā)師睡覺。（ 2）理發(fā)師和顧客之間互斥關系：由于每次理發(fā)師只能為一個人理發(fā)，且可供等侯的椅子有限只有 n 把，即理發(fā)師和椅子是臨界資源，所以顧客之間是互斥的關系。（ 3）故引入 3 個信號量和一個控制變量：控制變量 waiting 用來記錄等候理發(fā)的顧客數(shù)，初值為 0；信號量 customers用

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

8、 *_arg)第一個參數(shù)為指向線程標識符的指針，第二個參數(shù)用來設置線程屬性，第三個參數(shù)是線程運行函數(shù)的起始地址，最后一個參數(shù)是運行函數(shù)的參數(shù)。函數(shù)thread 不需要參數(shù)時，最后一個參數(shù)設為空指針。第二個參數(shù)設為空指針時，將生成默認屬性的線程。創(chuàng)建線程成功后，新創(chuàng)建的線程則運行參數(shù)三和參數(shù)四確定的函數(shù)，原來的線程則繼續(xù)運行下一行代碼。2.2.2等待一個線程結束pthread_join 用來等待一個線程的結束，函數(shù)原型為：extern int pthread_join _P (pthread_t _th, void *_thread_return);第一個參數(shù)為被等待的線程標識符，第二個參數(shù)為一

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

10、來增加信號量的值。當有線程阻塞在這個信號量上時，調用這個函數(shù)會使其中的一個線程不在阻塞，選擇機制同樣是由線程的調度策略決定的。（3）函數(shù) sem_wait( sem_t *sem ) 被用來阻塞當前線程直到信號量 sem的值大于 0，解除阻塞后將 sem的值減一，表明公共資源經(jīng)使用后減少。 函數(shù) sem_trywait ( sem_t *sem )是函數(shù) sem_wait（）的非阻塞版本，它直接將信號量sem的值減一。2.3偽碼實現(xiàn)difine n 5；/semaphore mutex=1為顧客準備的椅子數(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ù)少一個釋放臨界資源理發(fā)師去為一個顧客理發(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)境實現(xiàn)語言： C 語言開發(fā)工具： NANO 編輯器3 數(shù)據(jù)結構與模塊說明3.1數(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 用戶名、源程序名和目標程序名用戶名： rj070234源程序名： SleepingBarber.c目標程序名：SleepingBarber主機 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 運行結果5.1 運行步驟(1) 打開桌面上的 putty.exe ，輸入 IP 地址 192.168.1.254 ，進入開發(fā)環(huán)境。創(chuàng)建一個用來寫程序的文件，這里用的是nano 編輯器來編寫 c 程序。創(chuàng)建 SleepingBarber.c

21、的命令為： nano 進入編輯環(huán)境，輸入代碼，結束后按ctrl+x 保存為SleepingBarber.c ，進入文件的命令為：nano SleepingBarber.c ，然后可以對其進行修改。(2) 編譯源程序，編譯命令為：cc-lpthread-oSleepingBarberSleepingBarber.c(3) 編譯無錯誤后，運行程序，命令為：./ SleepingBarber5.2 運行結果5.2.1 編輯，編譯和運行的過程圖5.2.2 錯誤部分截圖5.2.3 正確運行結果圖第一次運行結果如下圖：第二次運行結果如下圖：第三次運行結果如下圖；6 調試記錄6.1 調試記錄周一因有培訓與課

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