操作系統(tǒng)課程設計報告院（系）：專業(yè)：計算機科學與技術姓名:班級：＿＿學號:題目：售票員與乘客指導教師:2019年11月20日至12月28日目錄一、需求分析 31.1問題概述 31.2理論分析 31.3問題分析 3二、概要設計 42.1售票流程分析 42.2進程分析 52.3信號量機制實現(xiàn)設計 5三、詳細設計 63.1設計思路 63.2程序設計核心要點 73.3主要函數(shù)分析 73.4具體函數(shù)實現(xiàn)分析： 7四、測試分析、測試結果 14五、用戶使用說明 165.1運行環(huán)境 165.2程序語言 165.2使用說明 16六、總結體會 186.1遇到的問題及解決方法 186.2總結心得 18七、參考資料 19一、需求分析1.1問題概述了解進程同步的概念，理解信號量機制的原理，掌握運用信號量解決進程同步問題的方法，進而學會運用進程的同步和互斥。設計要求：編程序模擬車站售票廳進程同步問題，售票廳任何時刻最多可容納20名購票者進入，否則需要在外面等待。每個購票者可以看成一個進程。1.2理論分析在多道程序環(huán)境下，系統(tǒng)中可能存在許多的進程，在這些進程之間必定存在一些制約關系，這種制約關系表現(xiàn)為以下兩種形式：①資源共享關系。進程之間不知道其他進程的存在，而這些進程又處在同一個系統(tǒng)中，對系統(tǒng)資源必須共享使用，而有些資源不允許進程同時訪問，例如打印機。系統(tǒng)只能保證進程間互斥地使用這種臨界資源，稱這種資源共享關系叫做互斥；②相互合作關系。在某些進程間還存在一種相互合作的關系。例如在某個系統(tǒng)中存在兩個進程，輸入進程A和計算進程B，A負責向B提供數(shù)據(jù)，當緩沖區(qū)空時，B進程因不能獲得所需數(shù)據(jù)而等待。當A把數(shù)據(jù)送入緩沖區(qū)后，并向B發(fā)送一個信號將B喚醒，B才能取走數(shù)據(jù)。同樣，當B沒有提取數(shù)據(jù)，也就是說緩沖區(qū)滿時，進程A也無法向其中投入數(shù)據(jù)而等待。這就是一種相互合作關系，稱之為進程間的同步關系。1.3問題分析在售票大廳買票與賣票的過程其實是有共享緩存去的合作進程而引起的同步，而售票大廳就是這個緩存區(qū)，購票者進入售票大廳，由售票者給購票者票后，購票者離開，如圖所示。二、概要設計2.1售票流程分析售票廳任何時刻最多可容納20名購票者進入，當售票大廳超過20人時，系統(tǒng)提示乘客需退出大廳等待；當大廳中人數(shù)少于或等于20人時，售票員開始售票，并提示等待的乘客進入大廳；1、乘客購票操作過程：①乘客先在售票廳外等候排隊購票;②當提示售票廳內(nèi)人數(shù)不足20人時，則按排隊順序進入售票廳內(nèi)進行購票動作;③乘客購票完后則離開售票廳內(nèi)，并提示等待的乘客進入大廳。售票流程如圖所示：2.2進程分析由于售票大廳是緩存區(qū)，最大容量為20，因此會出現(xiàn)3中情況：①若此時售票廳里人數(shù)為零時，則程序會提醒售票大廳為空，售票員的進程阻塞，直到購票者的進程運行完才喚醒該進程；②當進入售票廳內(nèi)的人數(shù)還沒有20時，進程將繼續(xù)執(zhí)行，則表示售票者的進程和購票者的進程都能執(zhí)行;③由于程序中的售票廳最大只能容納20個人，所以，當售票廳內(nèi)的人數(shù)進入將20時，則程序會提醒用戶售票大廳的人數(shù)已滿，請排隊等候，購票者進程阻塞，直到售票者的進程運行完才喚醒該進程。由于是多個購票者和多個售票者對應多個緩存區(qū)，因此，設置3個信號量：同步信號量empty表示空緩存單元的個數(shù)，初值為20；同步信號量full表示滿緩沖單元的個數(shù)，初值為0；互斥信號量mutex表示互斥使用的整個緩存池，初值為1；售票員-乘客進程PV關系如圖：乘客售票員P(empty)P(full)P(mutex)P(mutex)將數(shù)據(jù)放入有界緩沖區(qū)從有界緩沖區(qū)中取數(shù)據(jù)V(mutex)V(mutex)V(full)V(empty)2.3信號量機制實現(xiàn)設計2.2.1功能實現(xiàn)原理定義下列信號量：（1）信號量mutex，初始值為1，用于控制互斥訪問售票大廳。（2）信號量full，初始值為0，用于同步控制，full值表示當前售票大廳的人數(shù)。（3）信號量empty，初始值為20，用于同步控制，empty表示當前售票大廳還可容下的人數(shù)。（4）B=20為可以使用的空緩存區(qū)數(shù)。（5）in=0，out=0為整型變量，用于控制售票大廳的進入和出去的位置指針。M個售票員和N個乘客共20個單元售票大廳的售票員—乘客問題描述如下：ProcessPassengerDo{ Produceapeople; //乘客 P(empty); //售票大廳的人數(shù)為20時，購票者進程阻塞 P(mutex);//控制互斥使用臨界資源 B[in]=people;//乘客放入售票大廳 in=（in+1）mod20;//指針推進 people=B[in]; //乘客離開售票大廳 V(mutex);//退出緩存區(qū) V(full);//若售票大廳由空，則乘客進入，并喚醒售票者}while(1)ProcessConductorDo{ P（full）;//售票大廳的人為空時，售票員進程阻塞 P（mutex）;//控制互斥使用臨界資源 nextc=B[out]; //將票給乘客 out=(out+1)mod20;//指針推進 V(mutex);//退出臨界區(qū) V(empty);//若售票大廳已滿，則售票給乘客，并喚醒乘客}while(1);三、詳細設計3.1設計思路我們從三個方面依次進行分析：

（1）該問題中包括的進程都有哪些？該問題包括售票員進程和乘客進程這兩個。

（2）這些進程都是什么關系，怎么設置信號量，怎么給信號量賦初值？進程之間存在同步和互斥這兩種關系。當售票大廳人數(shù)為0時，售票員無法售票，只有當乘客進入后，售票員才能開始售票。當售票大廳多于20人時，乘客排隊等侯，只有當售票員售票完一個人后，乘客才能繼續(xù)進入。我們設置兩個信號量，full=0（表示滿緩沖區(qū)的個數(shù)），empty=n（表示空緩沖區(qū)的個數(shù)）。售票員和乘客必須互斥，不允許售票員和乘客在同一個緩沖區(qū)，因此設置互斥信號量mutex（當mutex=1時，表示有使用緩沖區(qū)臨界資源的使用權限；當mutex=0時，表示沒有緩沖區(qū)臨界資源的使用權限）。除此之外，還要設置兩個輔助變量。

in表示下一個乘客進入大廳的緩沖區(qū)位置；out表示下一個乘客退出大廳的緩沖區(qū)位置。（3）用PV原語怎么實現(xiàn)該問題？第一步：確定進程之間的關系。售票廳是各進程共享的公有資源，當售票廳中多于20名購票者時，其他的購票者需要在外面等待，所以進程之間是同步互斥的關系。第二步：確定信號量。只有一個公有資源：售票廳，所以設置一個信號量N，售票廳最多可容納20個進程，即可用資源實體數(shù)為20。3.2程序設計核心要點為了能夠動態(tài)的建立售票員和乘客的進程，增加了動態(tài)鏈表添加乘客和售票員的進程方法儲存，使用單鏈表頭結點進入的存儲方式，Buffer中是動態(tài)分配（指針）的。緩沖區(qū)為售票大廳，緩沖區(qū)的設計：（1）緩沖區(qū)是一個先進先出隊列，寫入模塊將信息插入隊列；讀出模塊將信息彈出隊列。（2）寫入模塊與讀出模塊需要進行信息的協(xié)調和同步。（3）對于多線程和多進程的寫入或讀出模塊，寫入模塊間以及讀出模塊間需要進行臨界區(qū)處理。3.3主要函數(shù)分析1、創(chuàng)建的函數(shù)：void*purchaser()；乘客void*seller()；售票員2、系統(tǒng)函數(shù)：main()主函數(shù)；主函數(shù)通過鏈表指針來實現(xiàn)數(shù)據(jù)的放入和取出，運行線程池，但線程池的運行時隨機的pthread_exit();終止調用它的線程并返回一個指向某個對象的指針。pthread_create(&temp,NULL,purchaser,NULL);第一個參數(shù)為指向線程標識符的指針。第二個參數(shù)用來設置線程屬性。第三個參數(shù)是線程運行函數(shù)的起始地址。最后一個參數(shù)是運行函數(shù)的參數(shù)。是類Unix操作系統(tǒng)（Unix、Linux、MacOSX等）的創(chuàng)建線程的函數(shù)pthread_join(threadPool[i],&result);第一個參數(shù)為被連接線程的線程號第二個參數(shù)為一個指向被連接線程的返回碼的指針的指針3.4具體函數(shù)實現(xiàn)分析：1、建立信號量typedefintsemaphore;typedefintitem;itembuffer[N]={0};//緩存區(qū)intin=0;//進來緩存區(qū)的位置intout=0;//出去的緩存區(qū)的位置intnum=0;//此時緩存區(qū)的人數(shù)intproCount=0;//intpurchaserNum,sellerNum;//售票者的人數(shù)，乘客的人數(shù)semaphoremutex=1,empty=N,full=0,proCmutex=1;//信號量的定義，empty=空的緩存區(qū)數(shù)量，full=滿的緩存區(qū)的數(shù)量，proCmutex=1//生產(chǎn)乘客的信號量因為要了解進入售票大廳此時的購票者的號碼，所以需要號碼牌，并且當前一個號碼還沒有執(zhí)行完時，不能發(fā)號碼牌，這是為了防止因為進程的隨機調用，導致號碼發(fā)到了后面，而中途的號碼還沒有執(zhí)行購票操作，就執(zhí)行后面的號碼情況的出現(xiàn)。2、定義鏈表為了能夠動態(tài)的建立售票員和乘客的進程，增加了動態(tài)鏈表添加乘客和售票員的進程方法儲存，使用單鏈表頭結點進入的存儲方式。typedefstructNode{pthread_ttemp;//進程structNode*next;//指針域}Node,*LinkList;//定義鏈表3、建立乘客進程1、乘客進程產(chǎn)生一個乘客：用一個數(shù)紀錄乘客的號碼：表示這是第幾個乘客，產(chǎn)生一個乘客則這個數(shù)加一，同時為了不落掉中間乘客，設置一個阻塞，當此乘客進程沒有結束時，不能產(chǎn)生一個乘客，因此可以使用循環(huán)來表示。判斷進程是否結束則用一個信號量標記，當進程結束則為1，進程未結束則為0，初始值設為1。因此當循環(huán)結束時需要改變信號量的值，由1變?yōu)?。當進程結束時，也改變信號量的值，由1變?yōu)?.while(proCmutex<=0);//判斷乘客是否產(chǎn)生proCmutex--;//已產(chǎn)生proCount++;//乘客的數(shù)量proCmutex++;//乘客已經(jīng)進入售票大廳完，可再產(chǎn)生一名新的乘客2、乘客的進程P(empty)的實現(xiàn)：隨著乘客進入售票大廳后，人數(shù)增加，還可容納的人數(shù)減少，則empty--。當empty為空時，進程阻塞，表示不能運行后面的程序。因此可以使用循環(huán)來表示這個功能。乘客的進程V(full)的實現(xiàn)：同時釋放full的值，則根據(jù)乘客進入售票大廳，售票大廳的乘客數(shù)增加，所以full++。while(empty<=0){printf("售票大廳已滿！請排隊等候\n");}//P(empty),判斷緩存區(qū)是否為滿empty--; //空的緩存區(qū)減少，乘客進來了緩存區(qū)full++; //V(full)，表示滿的緩存區(qū)增加3、乘客進程P(mutex)的實現(xiàn)：當使用緩存區(qū)時，則阻塞，不能運行下面的程序；沒有使用緩存區(qū)時，則運行。因此使用循環(huán)來表示這個功能。設置了mutex信號量，用來標記是否使用緩存區(qū)，正在使用緩存區(qū)表示為0，沒有使用表示為1。當跳出循環(huán)時，則表示緩存區(qū)沒有被占用，因此需要把信號量從沒有使用變成正在使用，由1變成0。乘客進程V(mutex)的實現(xiàn)：進程結束時，釋放緩存區(qū)，信號量由使用緩存區(qū)變成沒有使用緩存區(qū)，由0到1。while(mutex<=0);//P(mutex)，判斷緩沖區(qū)是否被占用mutex--;//將緩存區(qū)的狀態(tài)變?yōu)檎诒徽{用mutex++;//V(mutex)，釋放緩沖區(qū)4、乘客進程放入有界緩存區(qū)的實現(xiàn)：緩存區(qū)由數(shù)組表示，放入則表示緩存區(qū)的某個位置被放入某個數(shù)。用in表示放入的位置，乘客號為放入的數(shù)。位置會改變，又因為是從數(shù)組下標0開始，所以向前推進，同時避免超出緩存區(qū)最大值，取余計算。同時，售票大廳的總人數(shù)增加一個。if(buffer[in]==0)buffer[in]=proCount;//將進來的乘客序號放入緩沖區(qū)in=(in+1)%N;//進來的指針推進一位full++;//滿的緩存區(qū)增加，乘客進來了緩存區(qū)num++;//緩沖區(qū)的人數(shù)加一printf("第%d乘客已進,此時售票大廳的人數(shù)為%d\n",proCount,num);5、乘客進程的代碼流程圖： 乘客開始判斷售票大廳人數(shù)是否已滿，若為滿，則進程阻塞；若沒有滿，則進程接著判斷售票大廳是否被占用，若有，則進程阻塞；若沒有，則售票大廳被乘客占用，進程接著表示乘客進行購票，乘客進入售票大廳，通過全局變量num來統(tǒng)計售票大廳的人數(shù)，因為進來，所以num++，更改售票大廳人數(shù)；4、售票員進程1、線程結束的標志：當乘客全部購票完，且離開售票大廳。所以乘客的進程運行完后結束。而售票者的進程結束是線程結束的標志。乘客全部購票完則表示乘客號碼等于輸入的乘客數(shù)且此時最后一個乘客已經(jīng)完成購票，全部離開售票大廳則表示售票大廳的人數(shù)為0.while(full<=0){printf("售票大廳為空！\n");if(proCount==purchaserNum&&proCmutex==1)//判斷售票員進程結束的標志：乘客全部離開售票大廳exit(0);//進程結束}//P(full)，判斷緩沖區(qū)是否為空2、售票者進程離開有界緩存區(qū)的實現(xiàn)：緩存區(qū)由數(shù)組表示，離開則表示緩存區(qū)的某個位置的某個數(shù)變?yōu)?。用out表示放入的位置，因為要知道離開的乘客，所以先取出乘客號，然后將該位置的值變?yōu)?。位置會改變，又因為是從數(shù)組下標0開始，所以向前推進，同時避免超出緩存區(qū)最大值，取余計算。同時，售票大廳的總人數(shù)減少一個。intnextc=buffer[out];//找出離開位置的序號buffer[out]=0;//售票完將離開售票大廳，此時該位置為0out=(out+1)%N;//離開的指針加一if(nextc!=0){num--;//此時售票大廳的人數(shù)減一full--;//V(empty)，表示滿的緩沖區(qū)減少printf("\t\t\t\t第%d乘客已走,此時售票大廳的人數(shù)為%d\n",nextc,num);}3、售票員進程的代碼流程圖：售票者開始判斷售票大廳是否為空，若為空，則進程阻塞；若不為空，則進程接著判斷售票大廳是否被占用，若有，則進程阻塞；若沒有，則售票大廳被售票者占用，進程接著表示對乘客進行售票，乘客離開售票大廳，通過全局變量num來統(tǒng)計售票大廳的人數(shù)，因為離開，所以num--，更改售票大廳人數(shù)；5、乘客進程與售票員進程之間的關系：售票員的進程P(full)的實現(xiàn)：隨著乘客離開售票大廳后，人數(shù)減少，售票大廳人數(shù)減少，則full--。當full為空時，進程阻塞，表示不能運行后面的程序。因此可以使用循環(huán)來表示這個功能。乘客的進程V(empty)的實現(xiàn)：同時釋放empty的值，則根據(jù)乘客離開售票大廳，售票大廳的乘客數(shù)減少，所以empty++。while(full<=0){printf("售票大廳為空！\n");} //P(full)，判斷緩沖區(qū)是否為空full--; //表示滿的緩存區(qū)數(shù)減少empty++; //V(empty),表示空的緩存區(qū)增加6、主函數(shù)主函數(shù)通過鏈表指針來實現(xiàn)數(shù)據(jù)的放入和取出，運行線程池，但線程池的運行時隨機的。1、由于是多個購票者進程和多個售票者進程：輸入兩個人數(shù)：購票者人數(shù)和售票者人數(shù)（表示購票者進程數(shù)量，和售票者進程數(shù)量）cin>>purchaserNum>>sellerNum；2、建立對用的進程動態(tài)放入線程池：pthread_create//類Unix操作系統(tǒng)的創(chuàng)建進程的函數(shù)pthread_join//當調用函數(shù)時，當前線程會處于阻塞狀態(tài)，直到被調用的線程結束后，當前線程才會重新開始執(zhí)行。用于控制線程池的進程并行運行3、把進程動態(tài)放入線程池中：用鏈表表示線程池，建立進程鏈表，使用尾插入法放入不斷往鏈表中添加進程p->temp=temp;p->next=s->next;s->next=p;//往鏈中增加新的進程s=s->next;//指向下一個結點4、售票大廳最大的人數(shù)已確定，而且我們的結果展示為大廳情況，所以最好使用數(shù)組來表示售票大廳，表示有多少個位置，可以根據(jù)數(shù)組位標確定進入和出去為哪號人,并且初始值設為0表示此位置沒有人。itembuffer[N]={0};//緩存區(qū)5、主函數(shù)實現(xiàn)：當線程池運行時，隨機調用存入線程池的進 程，因為當購票者人數(shù)沒有購票完時，售票者的進 程無法停止，所以當售票大廳為空時，售票者的進 程停止；當購票者全部進來時，購票者進程可 以停止，所以每一個購票者的進程運行完后就停 止，直到所有購票者進入售票大廳，購票者的進 程就全部停止。四、測試分析、測試結果1、當乘客大于20人時，輸入售票員與乘客數(shù)量(以售票員1名，乘客25名為例):此時，因為乘客的人數(shù)為25，所以會出現(xiàn)“售票大廳已滿！請排隊等候”的字體，而當?shù)?5為乘客全部進入后，乘客的進程才會結束。因為售票者的人數(shù)為1，而售票者只有當乘客全部購買完票，使售票大廳為空時，售票者的進程才會結束。因此最后顯示為“售票大廳為空”。2、當乘客小于售票員的人數(shù)時(以乘客10名，售票員15名為例)： 當售票大廳人數(shù)為0時，會出現(xiàn)“售票大廳為空！”的字體，當售票者人數(shù)大于購票者的人數(shù)時，我們在乘客全部走出售票大廳時，線程結束。3、當售票員與乘客人數(shù)相等時(以乘客和售票員都為10人時為例)：當售票員與乘客的相等時，我們以購票者全部進入售票大廳，全部出去售票大廳為結束。五、用戶使用說明5.1運行環(huán)境VS2013及以上版本；Codeblocks5.2程序語言C++5.2使用說明用戶操作距離：1、輸入。輸入項：乘客人數(shù)售票者人數(shù)如圖，以在程序框中輸入乘客10名，售票員15名為例(輸入項為1015)：2、輸出，回車得到輸出結果如圖。輸出項：進入大廳的乘客，大廳中的乘客人數(shù)；推出大廳的乘客，此時大廳中的人數(shù)；售票大廳的空間使用情況。輸入乘客10，售票員15，第1~7名乘客依次進入售票大廳，售票員開始售票，第1~7名乘客購票成功后退出大廳，系統(tǒng)顯示此時售票大廳的人數(shù)，在大廳外等待的顧客可以進入大廳，第8名乘客進入大廳，第8~10名乘客購票完成退出大廳，系統(tǒng)顯示大廳中人數(shù)為零，此時大廳中人數(shù)為零，運行結束?？偨Y體會6.1遇到的問題及解決方法1、產(chǎn)生的乘客不是一個一個的，比如第一個乘客產(chǎn)生后，然后就跳到第五，六個乘客產(chǎn)生的情況發(fā)生。解決方法：增加了一個新的信號量，使乘客產(chǎn)生一個以后，運行完乘客進程后，才能再產(chǎn)生新的乘客，保證乘客一個一個的進入售票大廳。2、因為進程的隨機運行，導致售票大廳的總數(shù)不對。會有乘客進入后，但是會顯示“售票大廳為空”的句子。解決方法：把對售票大廳滿的信號量和空的信號量的值的改變放入了mutex的信號量改變的變化中間，保證在該進程還沒結束時，其他進程阻塞。當該進程結束后，空和滿的信號量一定會發(fā)生相應的改變。3、當遇到乘客大于20時且售票員遠小于乘客，會發(fā)現(xiàn)出現(xiàn)“售票大廳已滿”的句子，并且陷入死循環(huán)。解決方法：因為建立的進程運行沒有停止，當建立的售票員的進程遠小于乘客時，且乘客大于20時，容易出現(xiàn)“售票大廳已滿”，而較少的運行售票員的乘客，所有容易出現(xiàn)死循環(huán)。在售票員和乘客的進程后加了停止該進程的語句，后面會發(fā)現(xiàn)當售票員人數(shù)大于乘客人數(shù)時，會出現(xiàn)“售票大廳為空”，并且陷入死循環(huán)；當乘客人數(shù)大于售票員人數(shù)，會出現(xiàn)“售票大廳已滿”，并且陷入死循環(huán)。于是又在P(empty)和P(full)語句中加了停止語句。后面發(fā)現(xiàn)當乘客人數(shù)大于售票者人數(shù)時，乘客未全部離開售票大廳就已經(jīng)結束。當售票者人數(shù)大于乘客人數(shù)時，乘客未全部進入就停止了運行。最后總結發(fā)現(xiàn)線程池的停止乘客需全部進入售票大廳并且離開售票大廳，所有乘客的進程后加了進程結束，售票者的進程在P(full）中加了條件判斷，當乘客的離開是乘客的數(shù)量，并且此時售票大廳為空時，線程結束。4、為了能夠動態(tài)的建立售票員和乘客的進程，增加了動態(tài)鏈表添加乘客和售票員的進程方法儲存，使用單鏈表頭結點進入的存儲方式。5、程序中的while()不符合臨界區(qū)讓權等待