1、摘 要 課程設計是培養學生綜合運用所學知識,發現,提出,分析和解決實際問題,鍛煉實踐能力的重要環節,是對學生實際工作能力的具體訓練和考察過程.隨著科學技術發展的日新日異，當今計算機應用在生活中可以說得是無處不在。因此作為二十一世紀的大學來說掌握計算機開發技術是十分重要的。 通過對操作系統這門課的學習后，要求我們能夠在深刻理解和應用有關經典進程的同步和互斥問題之余，能夠模擬解決打瞌睡的理發師問題。要求以輸出字符串的形式表示理發師和顧客的行為。理發師問題是一個利用信號量進行P、V操作的經典問題。設計程序實現此問題，要使得理發師的活動與顧客的活動得到各自真實的模擬。所執行的程序應體現：理發師在沒有顧

2、客的時候去睡覺，有顧客則工作；顧客在理發師工作時坐下等待，無座時離開，直至等到理發師自己理發。關鍵字：理發師；顧客；PV操作 目 錄摘 要11 設計要求11.1初始條件11.2技術要求12 需求分析22.1具體需求22.2系統實現步驟23 總體設計33.1總體設計思想33.2各功能之間的調用關系43.3創建數據結構64詳細設計64.1控制營業開始的模塊74.2建立一個理發類74.3理發功能模塊85系統實現原理156程序運行界面186.1進入程序友好界面186.2理發店營業界面196.3理發店服務界面206.4 詢問是否繼續工作界面216.5 無顧客界面226.6理發店尚未營業的界面236.7退

3、出程序的界面237 設計總結24參考文獻25致 謝26附錄271 設計要求1.1初始條件（1）操作系統：Windos（2）程序設計語言：C+語言（3）設有三個理發師，3把椅子（另外還有三把理發椅），幾把椅子可用連續 存儲單元。1.2技術要求（1）為每個理發師顧客產生一個線程，設計正確的同步算法。（2）每個顧客進入理發室后，即時顯示“work=1” 及其線程自定義標識，還同時顯示理發室共有幾名顧客及其所坐的位置。（3）為每位顧客提供一個等待沙發（4）若等待人數達到上限則新來顧客離開理發店（5）若理發師理發人數達到3人，則可以詢問理發師是否繼續工作（6）若理發師工作狀態為0，則理發店關門（7）若理

4、發師繼續工作且無顧客則理發師進入睡眠狀態（8）至多有6個顧客，每人理發至少3秒鐘。（9）多個顧客須共享操作函數代碼。 （10）本操作實現并發、并行、進程同步。2 需求分析2.1具體需求通過設計模擬解決打瞌睡的理發師問題，為理發店提供高效便捷的服務。理發店內有三名理發師，三把理發椅，和N把普通的椅子。要實現如果沒有顧客來，那么理發師就坐在理發椅上打瞌睡；當顧客到來時，就喚醒理發師。如果顧客到來時理發師正在理發，顧客就坐下來等待。如果N把椅子都坐滿了，顧客就離開該理發店到別處去理發。理發師剛開始理發時，先看看店里有沒有顧客，如果沒有，則在理發椅上打瞌睡；如果有顧客，則為等待時間最長的顧客理發，且等

5、待人數減1。顧客來到店里，先看看有無空位，如果沒有空位，就不等了。離開理發店；如果有空位則等待，等待人數加1；如果理發師在打瞌睡，則將其喚醒。2.2系統實現步驟 這是一個很簡單的程序，除了用到main（）函數之外，還用到了一個lifa類函數來產生隨機數、lifa（）、lifashi()；另外也用到了for循環和if嵌套語句。 設計的原理是：在開始程序是，先由程序員輸入椅子數chairs，然后詢問程序員是否開門營業：若程序員輸入y，則開門營業；若輸入n，則持續詢問程序員是否營業。在剛開門營業之后，先隨機產生顧客：若沒顧客來，則理發師打瞌睡，再次進行產生顧客；若有顧客來，則直接為顧客理發。在為顧客

6、理發期間，程序自動產生顧客，最多產生3個顧客。顧客進來后，先看看理發師是否在理發，是則看看是否有空椅子，若有則坐下，無則離開。如果理發師正空閑，則直接為顧客理發。當理發完成之后，先判斷已經為多少人理發了，如果未超過3人，則繼續營業。若已超過，則詢問程序員是否繼續營業。若繼續理發，則先判斷是否有人等待，若有則先為等待最久的顧客理發，若沒則理發師打瞌睡，程序繼續回到隨機產生顧客。3 總體設計3.1總體設計思想 題目中要求描述理發師和顧客的行為，本系統主要實現友好模塊，以控制理發店是否開門營業。實現理發師理發模塊，以控制理發師是否開始理發。實現顧客等待模塊，以實現顧客是否選擇等待。實現程序結束模塊，

7、以實現理發師是否停止工作以便結束程序。因此需要兩類線程lifashi()和lifa ()分別描述理發師和顧客的行為。其中，理發師有活動有理發和睡覺兩個事件；等待和理發二個事件。店里有固定的椅子數，上面坐著等待的顧客，顧客在到來這個事件時，需判斷有沒有空閑的椅子，理發師決定要理發或睡覺時，也要判斷椅子上有沒有顧客。所以，顧客和理發師之間的關系表現為：（1）理發師和顧客之間同步關系：當理發師睡覺時顧客近來需要喚醒理發師為其理發，當有顧客時理發師為其理發，沒有的時候理發師睡覺。（2）理發師和顧客之間互斥關系：由于每次理發師只能為一個人理發，且可供等侯的椅子有限只有n把，即理發師和椅子是臨界資源，所以

8、顧客之間是互斥的關系。（3）故引入3個信號量和一個控制變量： <1>控制變量w用來記錄等候理發的顧客數，初值為0； <2>控信號量c用來表示沙發數，初值為3； <3>信號量customers用來記錄等候理發的顧客數，并用作阻塞理發師進 程，初值為0； <4>信號量finish用來記錄已經完成理發的人數，并用作阻塞顧客進程，初值為0； （4）程序只有一個主體函數，用的是幾個循環體來完成理發師和顧客的各項功能。 <1>用第一個循環體實現理發店是否開始營業的功能。 <2>用第二個循環體實現理發師是否開始理發的功能。 <3&

9、gt;在第二個循環體內設置控制程序結束的語句，可根據用戶需 要而結束程序。 輸出友好界面進入控制是否營業循環進入控制理發師理發循環 結束 開始 圖3.1總體設計圖3.2各功能之間的調用關系 (1) 友好模塊是一個控制程序是否開始的循環體，用ii變量來控制循環體會詢問用戶是否開始程序。如果用戶選擇是，就執行后面的程序，如果選擇否，就輸出“對不起，理發店還沒營業”，然后再次詢問是否選擇營業。（2） 理發師的控制模塊是由另一個循環模塊控制的，當沒有顧客光臨時，就輸出“沒有顧客光臨，理發師可以休息”。當有顧客光臨時，就開始繼續運行下去，按照閑則服務，忙則等待，若等待人數超過三個就離開理發店的規則運行下

10、去。當服務人數超過三個，就詢問是否還要繼續服務。（3） 顧客等待模塊，是一個判斷等待條件是否成立的模塊。若c-w>0，則顧客具備等待條件，否則等待條件不成立，顧客離開。 創建顧客進程結束 ii>3 創建理發師線程ii<=0初始化信號量 創建信號量 開始創建理發師線程失敗創建理發師線程 c-w>0創建顧客進程失敗 T F F T F T 圖3.2主函數流程圖3.3創建數據結構 定義一個理發類，便于主程序調用。加快進程調度，提高資源利用率，增大CPU吞吐量，減少內存空間。減少進程等待時間，使得程序清晰可讀，處理機調用高速快捷。 class lifa；int c;/沙發數 i

11、nt customers=0;/顧客數 int count=0;/循環中用來計量的 int w=0;/等候理發的人數 int finish=0;/已經理完發的人數 int work1=0,work2=0,work3=0;/理發師是否在工作 char opendoor;/理發店是否開門接待顧客 int radom;/獲取有無顧客數4詳細設計定義一個lifa類，便于主函數調用。線程lifa()和lifashi()是兩個公有函數，定義私有變量ii用來對進程進行控制，ii<=0 表示沒有顧客，理發師處于休息狀態。ii>0 表示理發店有顧客到來，對A、B、C三個理發師工作狀態進行判斷，若wo

12、rk=1,則顧客進入等待狀態，則對c進行判斷，若c-w>0，則顧客等待。反之理發店人已滿，則顧客離開。若work=0，則顧客直接進行理發不用等待。變量customers自增1，等待變量w減1。若finish>2時，理發師理發人數已達到上限，詢問理發師是否繼續工作。jixu=“y” 則繼續工作，jixu=“n” 則理發師休息。則程序結束，exit()=0。 主函數開始調用，進入友好界面若opendoor=“y”，則開門營業。若opendoor=“n”，則表示理發店尚未開門。4.1控制營業開始的模塊這個功能的實現是用了一個循環，當詢問是否開始營業是，用戶有兩個選擇，一個是，一個否，當選

13、擇是時，輸出“理發店開門營業！”程序跳出該循環 進入下一個功能；當選擇否時，輸出“對不起，理發店還沒有開門”然后繼續詢問是否營業。cout<<"是否營業？y/n"<<endl; cin>>opendoor; while(opendoor!='y') cout<<"對不起，理發店還沒有開門！"<<endl; cout<<"是否營業？y/n"<<endl; cin>>opendoor; cout<<endl; cou

14、t<<"理發店開門營業！"<<endl;cout<<endl;4.2建立一個理發類 建立理發類的作用就是要在主函數中顯得更簡潔明了，不至于覺得繁瑣。使用更方便，也方便改動程序。class lifa public: lifa(int i)ii=i; void lifashi(); private: int ii;4.3理發功能模塊課程設計的主要目的是了解并且掌握進程之間的同步互斥，和進程之間的通信問題。結合課本上的生產者與消費者問題可以從這方面來實現一個多進程的小系統，并且解決多個進程之間的通信，并發等問題，以此來達到課程設計的目的。理發師

15、問題是將顧客看做生產者，將理發師作為消費者。設置一定數量的椅子的數目來作為緩存區的大小。顧客來到的時候坐在椅子上，將自己作為“產品”，理發師理發的時候從椅子上叫走顧客，相當于消費“產品”，從而達到了課程設計要求的前一個要求。 顧客作為生產者，每到來一個就使計數器count增加1，以便讓理發師理發（相當于消費）至最后一個顧客（相當于產品）。并且，第1個到來的顧客應負責喚醒理發師；如果不是第1個到達的顧客，則在有空椅子的情況下坐下等待，否則離開理發店（該消息可由計數器count獲得）。這是理發類中定義的一個控制理發師理發的函數。這里用了兩個循環嵌套，中間小的一層是控制顧客來的數目，當有顧客來訪，就

16、開始往下執行，判斷理發師是否有空，如果有空，就進行理發，若沒有空，就判斷是否有空閑沙發可以讓顧客等待，若果有空閑沙發，則顧客等待，若沒有空閑沙發，顧客就離開理發店。理發完成就顯示理發完成，完成數就加一，如果理發完成數大于三個人，就輸出理發完成的狀態和等待的顧客數。詢問是否繼續理發，如果否，則退出程序，如果是，則先為等待的顧客理發，完成后輸出已完成。由于整個模塊是由一個大的模塊控制循環，所以你選擇繼續，則會又繼續重復上面的功能，知道你選擇退出程序。主要有以下一些函數來實現整個問題的實現過程： （1）用隨機函數lifa()來產生進入理發店的顧客。 （2）定義理發師的理發函數lifashi()用來實

17、現理發操作。 （3）定義一個lifa類用來實現顧客被理發的操作。 （4）用顧客線程customer實現對顧客行為的控制。 （5）用狀態量work實現對理發師行為的控制。 （6）定義主函數main實現對兩個線程的控制和執行操作。Work=1 結束等待理發師線程結束創建顧客線程失敗創建顧客線程 ii<9等待顧客線程結束理發師線程失敗Work=0創建理發師線程信號量初始化失敗 開始創建并初始化信號量Work!=0 F T T F F T F T 圖4.3理發師功能流程圖void lifa:lifashi() int c=3;/沙發數 int customers=0;/顧客數 int count

18、=0;/循環中用來計量的 int w=0;/等候理發的人數 int finish=0;/已經理完發的人數 int work1=0,work2=0,work3=0;/理發師是否在工作 char jixu,p;while(ii<=0) cout<<"沒有顧客來理發，理發師坐在沙發上休息"<<endl<<endl; cout<<"請輸入來的顧客數,輸入0表示沒有顧客來:"<<endl; cin>>ii; while(ii>0) for(count=0;count<=2;c

19、ount+) customers+; cout<<"第"<<customers<<"個顧客到來了。"<<endl; if(work1=1)/判斷是否正為顧客理發，是則新來顧客等待，否則不用等待 if(w<c)/判斷是否有空沙發 cout<<"有"<<c-w<<"張空沙發，顧客坐下等待。"<<endl; w+; else cout<<"沒有空沙發，顧客離開。"<<endl;

20、 else cout<<"A理發師為第"<<customers<<"個顧客理發。"<<endl; work1=1; customers+; cout<<"第"<<customers<<"個顧客到來了。"<<endl; if(work2=1)/判斷是否正為顧客理發，是則新來顧客等待，否則不用等待 if(w<c) /判斷是否有空沙發 cout<<"有"<<c-w<<

21、;"張空沙發，顧客坐下等待。"<<endl; w+; else cout<<"沒有空沙發，顧客離開。"<<endl; else cout<<"B理發師為第"<<customers<<"個顧客理發"<<endl; work2=1; customers+; cout<<"第"<<customers<<"個顧客到來了。"<<endl; if(work3

22、=1)/判斷是否正為顧客理發，是則新來顧客等待，否則不用等待 if(w<c)/判斷是否有空沙發 cout<<"有"<<c-w<<"把空沙發，顧客坐下等待。"<<endl; w+; else cout<<"沒有空沙發，顧客離開。"<<endl; else cout<<"C理發師為第"<<customers<<"個顧客理發。"<<endl; work3=1; if(work1

23、=1) cout<<"A理發完成。"<<endl; work1=0;/理發完成，理發師空閑 finish+;/理發完人數加1 if(work2=1) cout<<"B理發完成。"<<endl; work2=0;/理發完成，理發師空閑 finish+;/理發完人數加1 if(work3=1) cout<<"C理發完成。"<<endl; work3=0;/理發完成，理發師空閑 finish+;/理發完人數加 if(finish>2) /完成為3個人理發的任務，詢

24、問理發師是否繼續工作 cout<<"已經為"<<finish<<"位顧客理發了，還有"<<w<<"個顧客在等待，是否繼續工作？y/n"<<endl; cin>>jixu; if(jixu='n') cout<<"謝謝光臨!"<<endl; exit(0); if(w>0) /看看是否有人在等待理發 cout<<"有"<<w<<&qu

25、ot;位顧客等待，A理發師繼續為等待的第一位顧客理發"<<endl; w-; work1=1; /有則進入工作狀態 if(w>0) /看看是否有人在等待理發 cout<<"有"<<w<<"位顧客等待，B理發師繼續為等待的第二位顧客理發"<<endl; w-; work2=1;/有則進入工作狀態 if(w>0) /看看是否有人在等待理發 cout<<"有"<<w<<"位顧客等待，C理發師繼續為等待的第三位顧客理

26、發"<<endl; w-; work3=1;/有則進入工作狀態 if(work1=1) cout<<"A將等待的顧客理發完成。"<<endl; work1=0;/理發完成，理發師空閑 finish+;/理發完人數加1 if(work2=1) cout<<"B將等待的顧客理發完成。"<<endl; work2=0;/理發完成，理發師空閑 finish+;/理發完人數加1 if(work3=1) cout<<"C將等待的顧客理發完成。"<<end

27、l; work3=0;/理發完成，理發師空閑 finish+;/理發完人數加1 cout<<"已經為"<<finish<<"位顧客理發了，還有0個顧客在等待，是否繼續工作？y/n"<<endl; cin>>p; if(p='y') jixu=p; if(p='n') jixu=p; cout<<"謝謝光臨!"<<endl; exit(0); 5系統實現原理目的：深入掌握進程調度的概念原理和實現方法。調試要求：編寫一個進程

28、調度程序，允許多個進程并行執行。 進程調度算法：采用最高優先數優先的調度算法（即把處理機分配給優先數最高的進程）、先來先服務算法、按時間片輪轉調度算法，最終總結該算法的優缺點。 每個進程有一個進程控制塊（PCB）表示，進程控制塊可以包含如下信息： 進程名、優先數、到達時間、需要運行時間、已用CPU時間、進程狀態等。 進程的優先數及需要的運行時間可以事先人為指定（也可以由隨機數產生）。進程的到達時間為輸入進程的時間。進程的運行時間以時間片為單位進行計算。每個進程的狀態可以是就緒W（wait）、運行R（run）或完成F（finish）三種狀態之一。 如果運行下個時間片后，進程的已占用CPU時間已達

29、到所需要的運行時間，則撤消該進程，如果運行一個時間片后進行已占用CPU時間還未達到所需要的運行時間，也就是進程還需要繼續運行，此時應將進程的優先數減1(即降低一級)，然后把它插入就緒隊列等待CPU。每進行一次調度程序都打印一次運行進程、就緒隊列、以及各個進程的PCB，以便進行檢查。重復以上過程，直到所有進程都完成為止。因為理發店的營業是持續的，在一個階段完成后，怎么選擇繼續執行呢，這里我用了一個選擇語句，然后利用循環不斷地來完成這個過程。在顧客接受服務的過程中，有很多判斷條件，以保證顧客的分類，到底是接受服務，還是等待，又或者是離開。這個功能是利用很多if語句來完成的。這里用的類的調用，使得主

30、函數變得簡單，而在改動程序時也方便許多。特點：既照顧了短進程，又考慮了進程到達的先后次序，也不會使長進程長期得不到服務，因此是一個比較全面考慮的算法，但每次進行調度時，都需要對各個進程計算響應比。所以系統開銷很大，比較復雜。 原理：每次調度是從就緒隊列中，選擇一個最先進入就緒隊列的進程，把處理器分配給該進程，使之得到執行。該進程一旦占有了處理器，它就一直運行下去，直到該進程完成或因發生事件而阻塞，才退出處理器。特點：利于長進程，而不利于短進程。原理：它是從就緒隊列中選擇一個估計運行時間最短的進程，將處理器分配給該進程，使之占有處理器并執行，直到該進程完成或因發生事件而阻塞，然后退出處理器，再重

31、新調度。原理：它是從就緒隊列中選擇一個響應比最高的進程，讓其獲得處理器執行，直到該進程完成或因等待事件而退出處理器為止。 P原語操作如下： <1>sem減1。 <2>若sem減1后仍大于零，則P原語返回，該進程繼續執行。sem>=0調用進程入等待隊列轉進程調度 返回Sem=sem-1 入口 <3>若sem減1后小于零，則該進程被阻塞后進入與該信號相對應的隊列 中，然后轉進程調度。 T F 圖5.4 P原語操作功能圖 V原語操作如下： <1>sem加1。 <2>若sem加1后仍大于零，則V原語停止執行，該進程返回調用處，繼續執行。

32、 <3>若sem加1后小于或等于零，則從該信號的等待隊列中喚醒一個等待進程，然后再返回原進程繼續執行或轉進程調度。 返回或轉進程調度Sem=sem+1Sem<=0 返回 入口Sem=sem+1Sem<=0 返回 入口 F T喚醒等待隊列中一個進程 圖5.5 V原語操作功能圖6程序運行界面 6.1進入程序友好界面 進入程序友好界面，程序初始化c=3,則輸出“理發店內總共有3張沙發” 給變量opendoor負值，以選擇理發店是否開門。 圖6.1 友好界面6.2理發店營業界面 若opendoor=“y”，則輸出“理發店開門營業” ii的取值范圍在19之間，輸入0表示沒有顧客上

33、門，輸入隨機數表示顧客數。 圖6.2 營業界面6.3理發店服務界面 若opendoor=“y”，給變量ii賦值為2，則A、B、C三位理發師開始理發且對c-w進行判斷，是否有空的沙發。有空沙發則顧客等待，沒有空沙發則顧客離開。 圖6.3 有顧客來的服務界面6.4 詢問是否繼續工作界面 當finish>2時，已經為3位顧客理完發。若opendoor=“y”，則表示理發師繼續工作且三位等待的顧客都已經理完發，此時w=0。判斷opendoor的狀態。 圖6.4 詢問是否繼續工作的界面6.5 無顧客界面 若變量 opendoor=“y”且ii=0,則輸出“沒有顧客來理發，理發師坐在沙發上休息” 表示理發店開門營業，但無顧客上門。 圖6.5 沒有顧客來的界面6.6理發店尚未營業的界面 若opendoor=“n”,則輸出“理發店還沒有開門” 圖6.6 理發店尚未營業的界面6.7退出程序的界面若finish>2且jixu=“n” 表示已經達到顧客數上限，理發師不在理發。則輸出“謝謝光臨”，退出程序。 圖6.7 退出程序的界面7 設計總結為期兩個星期操作系統課程設計馬上就要結束了，現在我來總結一下這兩個星期所學的內容和感想。課程設計對學生而言是其對所學課程內容掌握情況的一次自我驗證，從而有著極其重要