技工院--蘋果-桔子問題的實現(xiàn)

1、操作系統(tǒng)課程設(shè)計任務(wù)書題目： 蘋果-桔子問題的實現(xiàn) 學(xué)生姓名： 班 級： 物聯(lián)網(wǎng)工程1班 學(xué) 號： 指導(dǎo)教師： 張清/賈娟娟 一、 設(shè)計目的學(xué)生通過該題目的設(shè)計過程，掌握進程同步問題的原理、軟件開發(fā)方法并提高解決實際問題的能力。二、 設(shè)計內(nèi)容1、了解UNIX的命令及使用格式，熟悉UNIX/LINUX的常用基本命令，練習(xí)并掌握UNIX提供的vi編輯器來編譯C程序，學(xué)會利用gcc、gdb編譯、調(diào)試C程序。2、編寫程序?qū)崿F(xiàn)蘋果-桔子問題。桌上有一個空盤子，只允許放一個水果。爸爸專向盤中放蘋果，媽媽專向盤中放桔子，兒子專等吃盤中的桔子，女兒專等吃盤中的蘋果。規(guī)定當盤空時，一次只能放一個水果。三、 設(shè)計

2、要求及工作量1、 分析設(shè)計要求，給出解決方案（要說明設(shè)計實現(xiàn)所用的原理、采用的數(shù)據(jù)結(jié)構(gòu)）。2、 設(shè)計合適的測試用例，對得到的運行結(jié)果要有分析。3、 設(shè)計中遇到的問題，設(shè)計的心得體會。4、文檔：課程設(shè)計打印文檔每個學(xué)生一份，并裝在統(tǒng)一的資料袋中。 5、光盤：每個學(xué)生的文檔和程序資料建在一個以自己學(xué)號和姓名命名的文件夾下，刻錄一張光盤，裝入資料袋中。四、 要提交的成果1. 設(shè)計說明書一份，內(nèi)容包括：1) 中文摘要100字；關(guān)鍵詞3-5個；2) 設(shè)計思想；3）各模塊的偽碼算法；4）函數(shù)的調(diào)用關(guān)系圖；5）測試結(jié)果；6）源程序（帶注釋）；7）設(shè)計總結(jié)；8) 參考文獻、致謝等。2. 刻制光盤一張。五、設(shè)計

3、進度計劃及時間安排 周次日期內(nèi)容地點第1周星期一二教師講解設(shè)計要求查找參考資料教室圖書館星期三五算法設(shè)計，編程實現(xiàn)教室第2周星期一三調(diào)試測試，撰寫文檔教室星期四五檢查程序，答辯教室六、主要參考資料1.湯子瀛，哲鳳屏.計算機操作系統(tǒng).西安電子科技大學(xué)學(xué)出版社.2.王清，李光明.計算機操作系統(tǒng).冶金工業(yè)出版社.3.孫鐘秀等. 操作系統(tǒng)教程. 高等教育出版社4.曾明.  Linux操作系統(tǒng)應(yīng)用教程. 陜西科學(xué)技術(shù)出版社. 5. 張麗芬，劉利雄.操作系統(tǒng)實驗教程. 清華大學(xué)出版社.6. 孟靜， 操作系統(tǒng)教程原理和實例分析. 高等教育出版社7. 周長林，計算機操作系統(tǒng)教程. 高等教育

4、出版社8. 張堯?qū)W，計算機操作系統(tǒng)教程，清華大學(xué)出版社9. 任滿杰，操作系統(tǒng)原理實用教程，電子工業(yè)出版社10.張坤.操作系統(tǒng)實驗教程，清華大學(xué)出版社目 錄1.緒論11.1設(shè)計任務(wù)11.2設(shè)計思想11.3基礎(chǔ)知識22.各模塊偽碼算法32.1父親進程模塊32.2母親進程模塊52.3兒子進程模塊72.4女兒進程模塊92.5Print函數(shù)113. 函數(shù)調(diào)用關(guān)系圖123.1函數(shù)調(diào)用圖124.測試結(jié)果135.源程序176.設(shè)計總結(jié)22參考文獻23致 謝24摘 要 本設(shè)計實際是生產(chǎn)者消費者的變形，通過有界緩沖區(qū)把生產(chǎn)者和消費者聯(lián)系起來。假定生產(chǎn)者和消費者的優(yōu)先級是相同的，只要緩沖區(qū)未滿，生產(chǎn)者就可以往緩沖區(qū)

5、內(nèi)放入產(chǎn)品。蘋果與橘子的問題是典型的進程同步問題。本問題利用C語言實現(xiàn)相應(yīng)的P、V原語。主要過程可用生產(chǎn)消費者來模擬，這里，生產(chǎn)者（父親和母親）放入緩沖區(qū)（盤子）的產(chǎn)品有兩類（蘋果和桔子），消費者（女兒和兒子）也有兩類，每類消費者只消費其中固定的一類產(chǎn)品。生產(chǎn)者和消費者共享緩沖區(qū)，緩沖區(qū)中有空時，生產(chǎn)者可放入產(chǎn)品（不許放重），待緩沖區(qū)中有產(chǎn)品時，消費者可取出產(chǎn)品（不許取重），否則等待。關(guān)鍵字：進程同步；P、V操作；信號量1.緒論1.1設(shè)計任務(wù)桌上有一個空盤子，只允許放一個水果。爸爸專向盤中放蘋果，媽媽專向盤中放桔子，兒子專等吃盤中的桔子，女兒專等吃盤中的蘋果。規(guī)定當盤空時，一次只能放一個水果。

6、 這個問題實際上是兩個生產(chǎn)者和兩個消費者被連接到僅能放一個產(chǎn)品的緩沖器上。生產(chǎn)者各自生產(chǎn)不同的產(chǎn)品，但就其本質(zhì)而言，他們是同一類生產(chǎn)者。而消費者則各自去需要的產(chǎn)品消費，但消費的方式不同。解決此類問題利用記錄型信號量機制和P、V操作來實現(xiàn)進程同步。進程同步是指一個進程的執(zhí)行依賴于另一個進程的信號或消息，當一個進程沒有得到來自與另一個進程的信號或消息時則等待，直到信號或消息到達才被喚醒。1.2設(shè)計思想本實驗進行操作系統(tǒng)課設(shè)的主要任務(wù)是模擬生產(chǎn)者與消費者問題的一個衍生，即實現(xiàn)蘋果-橘子問題。這個題目有兩個生產(chǎn)者，分別生產(chǎn)橘子和蘋果。有兩個消費者，分別消費蘋果和橘子。同時，因為兩個生產(chǎn)者和兩個消費者同

7、時對一個緩沖區(qū)進行操作。所以應(yīng)互斥的訪問的緩沖區(qū)以保證程序的正確性。本次進程的目的就是加深個進程之間的正確有效的訪問一個存儲單元緩沖區(qū)，即同步和互斥。也要涉及到信號量在互斥訪問中的使用,生產(chǎn)者和消費者問題的實現(xiàn)和流程問題。當計算機中兩個或者多個進程在執(zhí)行時需要使用公用緩沖區(qū)，并且對該緩沖區(qū)采取了互斥措施，這時如果并發(fā)執(zhí)行這些進程的時候就會造成CPU時間的極大浪費，這是操作系統(tǒng)設(shè)計要求不允許的。而這種現(xiàn)象在操作系統(tǒng)和用戶進程中大量存在。因此為了解決這一問題，提出了同步的概念，即把異部環(huán)境下的一組并發(fā)進程，因直接制約而互相發(fā)送消息而進行互相合作、互相等待，使得各進程按一定的速度執(zhí)行的過程稱為進程間

8、的同步。該問題是典型的進程同步問題。某些進程為了完成同一任務(wù)分工合作，由于合作的每一個進程都是獨立的不可預(yù)知的推進，這就需要相互合作的進程在某些合作點上協(xié)調(diào)各自的工作。當合作進程中的一個到達合作點后，在尚未得到其他合作進程發(fā)來的消息或信號前應(yīng)阻塞自己，直到其合作進程發(fā)來協(xié)調(diào)信號或消息后才能被喚醒。這就是進程同步要解決的問題。1.3基礎(chǔ)知識生產(chǎn)者消費者問題（英語：Producer-consumer problem），也稱有限緩沖問題（英語：Bounded-buffer problem），是一個多線程同步問題的經(jīng)典案例。該問題描述了兩個共享固定大小緩沖區(qū)的線程即所謂的“生產(chǎn)者”和“消費者”在實際運

9、行時會發(fā)生的問題。生產(chǎn)者的主要作用是生成一定量的數(shù)據(jù)放到緩沖區(qū)中，然后重復(fù)此過程。與此同時，消費者也在緩沖區(qū)消耗這些數(shù)據(jù)。該問題的關(guān)鍵就是要保證生產(chǎn)者不會在緩沖區(qū)滿時加入數(shù)據(jù)，消費者也不會在緩沖區(qū)中空時消耗數(shù)據(jù)。借助C語言實現(xiàn)進程同步經(jīng)典問題蘋果-桔子問題，用高級語言編寫和調(diào)試一個進程同步程序，以加深對進程同步機制的理解。通過用C語言模擬進程同步實現(xiàn)，加深理解有關(guān)進程同步機制的概念及P、V操作的應(yīng)用。通過該題目的設(shè)計過程，掌握進程同步問題的原理、軟件開發(fā)方法并提高解決實際問題的能力。這是進程同步與互斥問題的模擬，可以把向盤子放或取水果的每一個過程可以轉(zhuǎn)為一個進程的操作，這些進程是互斥的，同時也

10、存在一定的同步關(guān)系。通過編程實踐時，實際是隨機的調(diào)用一個進程的操作，而這些進程的操作相當于程序中的函數(shù)調(diào)用。而計算機在執(zhí)行時每一個時刻只能執(zhí)行一個操作，這就是互斥的表現(xiàn)。同步的模擬可以類似于函數(shù)調(diào)用時的前提關(guān)系即先決條件。這樣進程同步模擬就完全可以通過函數(shù)的調(diào)用來實現(xiàn)。為下面吃水果的問題創(chuàng)建進程并實現(xiàn)進程之間的同步模型。能夠處理以下的情形：桌子上有一只盤子，最多可容納兩個水果，每次只能放入或者取出一個水果。爸爸專門向盤子中放蘋果，媽媽專門向盤子中放橘子，兩個兒子專門等待吃盤子中的橘子，兩個女兒專門等吃盤子中的蘋果。2.各模塊偽碼算法2.1父親進程模塊爸爸向盤子中放一個蘋果操作：Father()

11、，plat_size表示盤子，初始值為0，plat_size=apple+orange，執(zhí)行father操作后，plat_size=1；則daughter處于等待狀態(tài)。cout<<"Father調(diào)用."<<endl; if(Plate_Size=1) Father_lag=1; /Father()等待 Print(); if(Mother_lag=false)MonFa_c=1; else Father(); if(Daughter_lag=true) Daughter01_lag=false;/Daughter等待取消 Daughter (); /

12、處于等待的Daughter自動調(diào)用 break;爸爸放蘋果進程的操作流程如圖2.1： 開始Plat_size=1?father進程調(diào)用:apple+,plat_size=orang+apple,調(diào)用print()daughter等待調(diào)用daughter進程father處于等待狀態(tài)結(jié)束否是是否 圖2.1爸爸放蘋果進程操作流程圖2.2母親進程模塊媽媽向盤子中放一個橘子操作：Mother() ，plat_size表示盤子，初始值為0，plat_size=apple+orange，執(zhí)行mother操作后，plat_size=1；則son處于等待狀態(tài)。如圖所示，若mother放入前plat_size=1

13、，則必須等待。cout<<"Mother調(diào)用."<<endl; if(Plate_Size=1) Mother_lag=true; /Mother()等待 Print(); if(Father_lag=false)MonFa_c=1; else Mother(); if(Son_lag=true) /Son等待 Son_lag=false;/Son等待取消 Son(); /處于等待的Son()自動調(diào)用 break; 媽媽放桔子進程的操作流程如圖2.2：開始Plat_size=1?mother進程調(diào)用：orange+,plat_size=orang+a

14、pple,調(diào)用print()son等待調(diào)用son進程mother處于等待狀態(tài)結(jié)束否是是否圖2.2媽媽放桔子進程操作流程圖2.3兒子進程模塊兒子從盤子取一個橘子操作：Son()，son操作要進行，則必須plat_size=1，且盤子中必須有orange。若orange=0，則son必須等待。cout<<"Son調(diào)用."<<endl; if(orange=0) Son_lag=true; /Son處于等待 Print(); else Son(); if(Father_lag=true)&&(Mother_lag=true) if(MonF

15、a_c=1) /Father和Mother同時處于等待，但Father先等待，因此先調(diào)用 Father_lag=false; Father(); MonFa_c=2; else /Father和Mother同時處于等待，但Mother先等待，因此先調(diào)用 Mother_lag=false; Mother(); MonFa_c=1; break; 兒子取桔子的操作流程如圖2.3：開始orange=0?Son進程處于等待狀態(tài)是son進程調(diào)用：orange-；plat_size-；調(diào)用print()否Mother/father等待狀態(tài)按等待先后順序調(diào)用mother()或father()操作結(jié)束是否圖2

16、.3兒子取桔子操作流程圖2.4女兒進程模塊 女兒從盤子取一個蘋果操作：Daugther()，daughter操作要進行，則必須plat_size=1，且盤子中必須有apple。若apple=0，則daughter必須等待。Daghter進程調(diào)用中apple-;plat_size-;cout<<"Daughter調(diào)用."<<endl; if(apple=0) Daughter_lag=true; /Daughter等待 Print(); else Daughter (); if(Father_lag=true)&&(Mother_lag

17、=true) if(MonFa_c=1) /Father和Mother同時處于等待，但Father先等待，因此先調(diào)用 Father_lag=false; Father(); MonFa_c=2; else /Father和Mother同時處于等待，但Mother先等待，因此先調(diào)用 Mother_lag=false; Mother(); MonFa_c=1; 女兒取蘋果的操作流程如圖2.4： 開始apple=0?daughter進程處于等待狀態(tài)是daughter進程調(diào)用：apple-；plat_size-；調(diào)用print()否Mother/father等待狀態(tài)按等待先后順序調(diào)用mother()或

18、father()操作結(jié)束是否圖2.4 女兒取蘋果操作流程圖 2.5 Print模塊用于輸出盤子中蘋果和橘子的個數(shù)，水果總個數(shù)及有哪些進程處于等待狀態(tài)。void Print() /Print函數(shù)（打印盤子剩余水果及各進程等待狀態(tài)）cout<<"現(xiàn)在盤子里有"<<apple<<"個蘋果,"<<orange<<"個橘子,"<<"共有"<<apple+orange<<"個水果."<<endl;if

19、(Father_lag=1)cout<<"Father進程處于等待狀態(tài),"if(Mother_lag=1)cout<<"Mother進程處于等待狀態(tài),"if(Son_lag=1)cout<<"Son進程處于等待狀態(tài),"if(Daughter_lag=1)cout<<"Daughter進程處于等待狀態(tài),"if(Father_lag=0)&&(Mother_lag=0)&&(Son_lag=0)&&(Daughter_lag

20、=0)!=1)cout<<endl;輸出模塊的操作流程如圖2.5： 開始輸出水果個數(shù)Father_lag=1? N Y 輸出父親進程正在等待Mother_lag=1? N Y 輸出母親進程正在等待Son_lag=1? N Y輸出兒子進程正在等待轉(zhuǎn)下頁接上頁Daughter_lag=1? N 輸出女兒進程正在等待 YFather_lag=0? N 輸出結(jié)束 Y 結(jié)束圖2.5Print模塊3.函數(shù)調(diào)用關(guān)系圖本程序有6個函數(shù)組成：main主函數(shù)，father父親函數(shù)，mother母親函數(shù)，son兒子函數(shù)，daughter女兒函數(shù)，print輸出函數(shù)。主函數(shù)調(diào)用父親函數(shù)、母親函數(shù)、兒子函數(shù)

21、、女兒函數(shù)、輸出函數(shù)。父親函數(shù)、母親函數(shù)、兒子函數(shù)、女兒函數(shù)調(diào)用輸出函數(shù)。MainSonDaughterMatherFatherPrint圖3.1函數(shù)調(diào)用關(guān)系圖4.測試結(jié)果4.1調(diào)用次數(shù)1次 初始運行狀態(tài)如下：運行程序后界面上顯示“請輸入調(diào)用次數(shù)”，根據(jù)調(diào)用的次數(shù)，系統(tǒng)會做出相應(yīng)的調(diào)用。初始設(shè)置了1次。初始為mather（）調(diào)用。此過程中初始化緩沖區(qū)（盤子）里有0個蘋果，1個桔子。father，mother，son，daughter進程均處于等待狀態(tài)。處于等待的son自動被調(diào)用。father,mother,daughter進程均處于等待狀態(tài)如圖所示：圖4.1 初始狀態(tài)圖4.2調(diào)用次數(shù)4次 在第

22、二次調(diào)用過程中，消費者daughter被調(diào)用。調(diào)用之后存儲單元的緩沖區(qū)中沒有任何生產(chǎn)者生產(chǎn)的產(chǎn)品。因此father,mother,son進程均處于等待狀態(tài)。當出現(xiàn)daughter（）調(diào)用，son()調(diào)用時，緩沖區(qū)中沒有可供消費的產(chǎn)品。若緩沖區(qū)沒有可供消費的產(chǎn)品則消費者需等待。如圖所示：圖 4.2daughter（）調(diào)用 4.3調(diào)用次數(shù)8次前4次調(diào)用：如圖所示：該操作中設(shè)置了八次調(diào)用。下圖是前四次的過程當執(zhí)行father()操作時，緩沖區(qū)中有一個蘋果。而執(zhí)行mother()操作時，緩沖區(qū)有一個桔子。只有當緩沖區(qū)中有桔子或蘋果時，才會有daughter()調(diào)用，son()調(diào)用，如下圖第三次調(diào)用，若

23、緩沖區(qū)有一個蘋果，則daughter()操作自動被調(diào)用。圖4.3 father（）調(diào)用圖 后4次調(diào)用：在本次程序運行過程中，由于第八次是father調(diào)用，則該進程中消費者兒子與消費者女兒互斥。生產(chǎn)者放入存儲緩沖區(qū)（盤子）的產(chǎn)品（蘋果），被兒子取走后，另一位生產(chǎn)者才能生產(chǎn)（橘子）供女兒消費。當操作完成后，按任意鍵退出該程序界面。如圖所示：圖4.4 father（）調(diào)用5.源程序#include<stdio.h>#include<stdlib.h>#include<time.h>int apple=0;int orange=0;int father_lag=1;

24、int mother_lag=1;int son_lag=1;int daughter_lag=1;int plat_size=0;int mf=0;void print();void father() /父進程apple+;print();void mother() /母進程orange+;print();void son() /兒子進程orange-;print();void daughter() /女兒進程apple-;print();void print()printf("There is %d Apple,%d Orange on the platen",appl

25、e,orange);if(father_lag=1) printf("father Process is in wait staten");if(mother_lag=1) printf("mother Process is in wait staten");if(son_lag=1)printf("son Process is in wait staten");if(daughter_lag=1)printf("daughter Process is in wait staten");if(father_lag=

26、0)&&(mother_lag=0)&&(son_lag=0)&&(daughter=0)printf("n");int main()int k;int i;int d;printf("Please enter the number of calls: n");scanf("%d",&d);srand(unsigned)time(NULL); /隨機產(chǎn)生一個以當前時間開始的隨機種子 for(k=0;k<d;k+) printf("n"); printf(

27、"The %d operation: n",k+1); i=rand()%4; /隨機生成1-5 plat_size=apple+orange; switch(i) case 0: printf("father Call.n"); if(plat_size=1) father_lag=1; /father處于等待狀態(tài) print(); if(mother_lag=0) mf=1; / father與mother互斥信號量決定先后順序 else father(); if(daughter_lag=1) daughter_lag=0; /等待取消 print

28、f("Waiting tasks in daughter Automatically calledn"); daughter(); printf("n"); break; case 1: printf("mother Call.n"); if(plat_size=1) mother_lag=1; /mother處于等待狀態(tài) print(); if(father_lag=0) mf=2; else mother();/ print(); if(son_lag=1) /等待取消 son_lag=0; printf("Waitin

29、g tasks in son Automatically called.n"); son(); printf("n"); break; case 2: printf("son Call.n"); if(orange=0) son_lag=1; /son處于等待狀態(tài) print(); else son(); if(mother_lag=1&&father_lag=1) if(mf=1) father_lag=0; printf("Waiting tasks in father Automatically calledn&

30、quot;); father(); mf=2;else mother_lag=0; printf("Waiting tasks in mother Automatically calledn"); mother(); mf=1; else if(mother_lag=1) mother_lag=0; printf("Waiting tasks in mother Automatically calledn"); mother();mf=0; else if(father_lag=1) father_lag=0; printf("Waiting

31、tasks in father Automatically calledn"); father(); mf=0; printf("n"); break; case 3: printf("daughter Calln"); if(apple=0) daughter_lag=1; print(); else daughter(); /print(); if(mother_lag=1&&father_lag=1) if(mf=1) father_lag=0; printf("Waiting tasks in father A

32、utomatically calledn"); father(); mf=2; else mother_lag=0; printf("Waiting tasks in mother Automatically calledn"); mother(); mf=1; else if(mother_lag=1) mother_lag=0; printf("Waiting tasks in mother Automatically calledn"); mother();mf=0; else if(father_lag=1) father_lag=0; printf("Waiting tasks in father Automatically calledn"); father(); mf=0; printf("n"); break; 6.設(shè)計總結(jié)在此次操作系統(tǒng)課程設(shè)計中,我的題目是：蘋果桔子問題的實現(xiàn)。剛拿到這個任務(wù)時就感覺到了一種困難和挑戰(zhàn)。不知道從何下手開始設(shè)計程序，經(jīng)過三天的思考，才有了一定的眉目。最后在老師和同學(xué)的幫助下，終于得出了一套可行的方案。依照策劃的設(shè)計思想，又過了六天的編寫和測試，終于實現(xiàn)了進