進程管理44課件

進程的同步與通信1進程互斥2信號量和Ｐ、Ｖ操作3進程同步4經(jīng)典的進程同步問題5進程通信要求：掌握進程同步與互斥，靈活運用信號量描述同步與互斥問題。3/9/20231第二章進程管理1.1互斥的基本概念與時間有關(guān)的錯誤:飛機訂票系統(tǒng)中，兩個終端，運行T1、T2進程

T1:T2: ...... Read(x);Read(x); ifx>=1thenifx>=1then x:=x-1;x:=x-1; write(x);write(x); ......3/9/20232第二章進程管理

同步：對于進程操作的時間順序所加的某種限制，如操作Ａ應(yīng)在Ｂ之前執(zhí)行?；コ猓和降奶乩鄠€操作決不能同時執(zhí)行，

如：操作Ａ和操作Ｂ不能在同時執(zhí)行。3/9/20233第二章進程管理臨界區(qū)(criticalsection)：臨界段，在每個程序中，訪問臨界資源的那段程序。 注意：臨界區(qū)是對某一臨界資源而言的，對于不同臨界資源的臨界區(qū)，它們之間不存在互斥。如有程序段A、B是關(guān)于變量X的臨界區(qū)，而C、D是關(guān)于變量Y的臨界區(qū)，那么，A、B之間需要互斥執(zhí)行，C、D之間也要互斥執(zhí)行，而A與C、B與D之間不用互斥執(zhí)行。3/9/20235第二章進程管理解決互斥的準則1、空閑讓進2、忙則等待3、有限等待4、讓權(quán)等待3/9/20236第二章進程管理1.2軟件方法解決進程互斥

假如有兩個進程Pi和Pj，它們共享一個臨界資源R。如何用軟件方法使進程Pi和Pj能互斥地訪問R。下面介紹四個算法。3/9/20237第二章進程管理進程Pi:RepeatWhileturn<>idono_op;Criticalsectionturn:=j;

OthercodeUntilfalse;

該算法可確保每次只允許一個進程進入臨界區(qū)。但它強制兩個進程輪流進入。如當Pi退出時將turn置為j，以便

Pj能進入，但Pj暫不需要進入，而這時Pi又需要進入時，它無法進入。違反：空閑讓進3/9/20239第二章進程管理算法2設(shè)varflag:array[0..1]ofboolean，flag[i]=true，表示進程Pi正在臨界區(qū)內(nèi)。flag[i]=false，表示進程Pi不在臨界區(qū)內(nèi)。flag[j]=true，表示進程Pj正在臨界區(qū)內(nèi)。flag[j]=false，表示進程Pj不在臨界區(qū)內(nèi)。3/9/202310第二章進程管理Pi進程：RepeatWhileflag[j]dono_op;

flag[i]:=true;

Criticalsectionflag[i]:=false;OthercodeUntilfalse;該算法可確保空閑讓進。但當pi和pj都未進入時，它們各自的訪問標志都為false。如果pi和pj幾乎同時要求進入，它們都發(fā)現(xiàn)對方的標志為false，于是都進入了。問題在于：當進程Pi觀察到進程Pj的標志為false后，便將自己的標志由false改為true，而正是在這兩步之間，可能發(fā)生進程切換。當Pj運行時，它會觀察到Pi的標志為false，從而可以將自己的標志設(shè)為true，并進入臨界區(qū)。3/9/202311第二章進程管理Pi進程：Repeat

flag[i]:=true;//希望進入While(flag[j])dono_op;Criticalsectionflag[i]:=false;OthercodeUntilfalse; 該算法又出現(xiàn)新問題。它可能造成誰也不能進入。如，當pi和pj幾乎同時都要進入，分別把自己的標志置為true，都立即檢查對方的標志，發(fā)現(xiàn)對方為true.最終誰也不能進入。3/9/202313第二章進程管理算法4（正確算法）組合算法1、3為每一進程設(shè)標志位flag[i]，當flag[i]=true時，表示進程pi要求進入，或正在臨界區(qū)中執(zhí)行。再設(shè)一個變量turn，用于指示允許進入的進程編號。3/9/202314第二章進程管理進程為了進入先置flag[i]=true，并置turn為j，表示應(yīng)輪到pj進入。接著再判斷flag[j]andturn=j的條件是否滿足。若不滿足則可進入。或者說，當flag[j]=false或者turn=i時，進程可以進入。前者表示pj未要求進入，后者表示僅允許pi進入。3/9/202315第二章進程管理軟件解法的缺點1.忙等待2.實現(xiàn)過于復(fù)雜，需要較高的編程技巧3/9/202317第二章進程管理3用原語實現(xiàn)進程互斥鎖即操作系統(tǒng)中的一標志位，０表示資源可用，１表示資源已被占用。用戶程序不能對鎖直接操作，必須通過操作系統(tǒng)提供的上鎖和開鎖原語來操作。通常鎖用w表示，上鎖開鎖原語分別用lock(w)、unlock(w)來表示。3/9/202318第二章進程管理上鎖和開鎖原語上鎖原語lock(w)可描述為：L：if(w==1)gotoLelsew=1；上述上鎖原語中存在忙等待。開鎖原語unlock(w)可描述為：w=0；3/9/202319第二章進程管理改進的上鎖原語3/9/202321第二章進程管理改進的開鎖原語3/9/202322第二章進程管理1965年，由荷蘭學者Dijkstra提出（P、V分別是荷蘭語的test(proberen)和increment(verhogen)）一種卓有成效的進程同步機制最初提出的是二元信號量（互斥）后來推廣到一般信號量（多值）（同步）P、V操作是原語2信號量及P、V操作3/9/202323第二章進程管理P操作P(s){s.value=s.value-1;if(s.value<0){ 該進程狀態(tài)置為等待狀態(tài)將該進程的PCB插入相應(yīng)的等待隊列末尾s.queue;}}3/9/202325第二章進程管理V操作V(s){s.value=s.value+1;if(s.value<=0){喚醒相應(yīng)等待隊列s.queue中等待的一個進程改變其狀態(tài)為就緒態(tài)并將其插入就緒隊列}}3/9/202326第二章進程管理用P、V操作解決進程間互斥問題P(mutex)V(mutex)P1P2P3互斥區(qū)P(mutex)P(mutex)V(mutex)V(mutex)3/9/202329第二章進程管理信號量及P、V操作討論對兩個并發(fā)進程，互斥信號量MUTEX僅取1、0和－1三個值若MUTEX＝1表示沒有進程進入臨界區(qū)若MUTEX＝0表示有一個進程進入臨界區(qū)若MUTEX＝－1表示一個進程進入臨界區(qū)，另一個進程等待進入。3/9/202330第二章進程管理1)信號量的物理含義： S>0表示有S個資源可用 S=0表示無資源可用 S<0則|S|表示S等待隊列中的進程個數(shù)P(S)：表示申請一個資源V(S)：表示釋放一個資源。信號量的初值應(yīng)該大于等于0信號量及P、V操作討論3/9/202331第二章進程管理2)P.V操作必須成對出現(xiàn)，有一個P操作就一定有一個V操作當為互斥操作時，它們同處于同一進程當為同步操作時，則不在同一進程中出現(xiàn)如果P(S1)和P(S2)兩個操作在一起，那么P操作的順序至關(guān)重要。一個同步P操作與一個互斥P操作在一起時同步P操作在互斥P操作前而兩個V操作無關(guān)緊要信號量及P、V操作討論3/9/202332第二章進程管理3）P、V操作的優(yōu)缺點優(yōu)點：簡單，而且表達能力強（用P、V操作可解決任何同步互斥問題）缺點：不夠安全，P、V操作使用不當會出現(xiàn)死鎖；遇到復(fù)雜同步互斥問題時實現(xiàn)復(fù)雜。信號量及P、V操作討論3/9/202333第二章進程管理3進程同步同步問題可分為兩類：

保證一組合作進程按確定的次序執(zhí)行保證共享緩沖區(qū)的合作進程的同步。

3/9/202334第二章進程管理合作進程的執(zhí)行次序若干個進程為了完成一個共同任務(wù)而并發(fā)執(zhí)行，有些進程之間有次序的要求，有些進程之間沒有次序的要求為了描述方便，可以用一個圖來表示進程集合的執(zhí)行次序。3/9/202335第二章進程管理例如圖，試用信號量實現(xiàn)這三個進程的同步。

設(shè)有兩個信號量SB、SC，初值均為０Pa：Pb：Pc：…P(SB);

P(SC)

V(SB);……V(SC);3/9/202336第二章進程管理【思考題1】如圖，試用信號量實現(xiàn)這三個進程的同步。3/9/202337第二章進程管理解設(shè)有兩個信號量S1、S2，初值均為０P1：P2：P3：……P(S1)

V(S1);V(S2);P(S2)…3/9/202338第二章進程管理【思考題2】如圖，試用信號量實現(xiàn)這6個進程的同步3/9/202339第二章進程管理解設(shè)有5個信號量S2、S3、S4、S5、S6，初值均為０P1：P2：P3：…P(S2);P(S3)

V(S2);……V(S3)；V(S4);V(S6);V(S5)P4：P5：P6：P(S4);P(S5);P(S6);…P(S5);P(S6);……V(S5)；V(S6);

3/9/202340第二章進程管理【思考題】司機進程：while(1){啟動車輛正常駕駛到站停車}…售票員進程：while(1){關(guān)門售票開門}…用P.V操作解決司機與售票員的問題3/9/202341第二章進程管理解設(shè)有兩個信號量S1，S2，初值均為0。司機進程：while(1){

P(S1)啟動車輛正常駕駛

到站停車

V(S2)}…售票員進程：while(1){關(guān)門

V(S1)售票

P(S2)開門}…3/9/202342第二章進程管理共享緩沖區(qū)的進程的同步設(shè)某計算進程CP和打印進程IOP共用一個單緩沖區(qū)，CP進程負責不斷地計算數(shù)據(jù)并送入緩沖區(qū)T中，IOP進程負責不斷地從緩沖區(qū)T中取出數(shù)據(jù)去打印。3/9/202343第二章進程管理分析通過分析可知，CP、IOP必須遵守以下同步規(guī)則：

當CP進程把計算結(jié)果送入緩沖區(qū)時，IOP進程才

能從緩沖區(qū)中取出結(jié)果去打印;當IOP進程把緩沖區(qū)中的數(shù)據(jù)取出打印后，CP進程才能把下一個計算結(jié)果送入緩沖區(qū)3/9/202344第二章進程管理解為此設(shè)有兩個信號量Sa=0，Sb=1，Sa表示緩沖區(qū)中有無數(shù)據(jù)，Sb表示緩沖區(qū)中有無空位置。兩個進程的同步可以描述如下：3/9/202345第二章進程管理【思考題】1.用P.V操作解決下圖之同步問題提示：分別考慮對緩沖區(qū)S和T的同步，再合并考慮getcopyputst3/9/202346第二章進程管理get：while（1）{

P(Sin）;將數(shù)放入S;

V(Sout);}copy：while（1）{

P(Sout）;

P(Tin）;將數(shù)從S取出放入T;

V(Tout);V(Sin);}put：while（1）{

P(Tout）;將數(shù)從T取走;

V(Tin);}3/9/202347第二章進程管理【思考題】桌上有一空盤，最多允許存放一只水果。爸爸可向盤中放一個蘋果或放一個桔子，兒子專等吃盤中的桔子，女兒專等吃蘋果。 試用P、V操作實現(xiàn)爸爸、兒子、女兒三個并發(fā)進程的同步。提示：設(shè)置一個信號量表示可否向盤中放水果，一個信號量表示可否取桔子，一個信號量表示可否取蘋果。3/9/202348第二章進程管理解 設(shè)置三個信號量S,So,Sa，初值分別為1，0，0。分別表示可否向盤中放水果，可否取桔子，可否取蘋果。3/9/202349第二章進程管理Father(){while(1){

p(S);

將水果放入盤中;if(是桔子)v(So);elsev(Sa);}}Son(){while(1){p(So)取桔子

v(S);吃桔子;}}Daughter(){while(1){p(Sa)取蘋果

v(S);吃蘋果;}}3/9/202350第二章進程管理2.4經(jīng)典的進程同步問題

4.1生產(chǎn)者/消費者問題

4.2讀者/寫者問題

4.3哲學家進餐問題

3/9/202351第二章進程管理2.4.1生產(chǎn)者/消費者問題是一種同步問題的抽象描述。計算機系統(tǒng)中的每個進程都可以消費（使用）或生產(chǎn)（釋放）某類資源。這些資源可以是硬件資源，也可以是軟件資源。當某一進程使用某一資源時，可以看作是消費，稱該進程為消費者。而當某一進程釋放某一資源時，它就相當于生產(chǎn)者。3/9/202352第二章進程管理問題描述通過一個有界緩沖區(qū)把一群生產(chǎn)者P1,P2…,Pm，和一群消費者Q1,Q2,…,Qn聯(lián)系起來。只要緩沖區(qū)未滿，生產(chǎn)者就可以把產(chǎn)品送入緩沖區(qū);只要緩沖區(qū)未空，消費者就可以從緩沖區(qū)中取走物品。3/9/202353第二章進程管理圖3/9/202354第二章進程管理問題分析設(shè)兩個同步信號量，一個說明空緩沖區(qū)的數(shù)目，用S1表示，初值為有界緩沖區(qū)的大小N，另一個說明已用緩沖區(qū)的數(shù)目，用S2表示，初值為０。M個生產(chǎn)者和N個消費者要對有界緩沖區(qū)進行操作。而有界緩沖區(qū)是一個臨界資源，必須互斥使用，設(shè)置一個互斥信號量mutex，其初值為１。3/9/202355第二章進程管理用一個數(shù)組來表示具有n個(0，1，…，n-1)緩沖區(qū)的緩沖池，整型變量counter，其初始值為0。每當生產(chǎn)者進程向緩沖中投放一個消息后，使counter加1；每當消費者進程從中取走一個消息時，counter減1。3/9/202356第二章進程管理輸入指針in：指示下一個可投放消息的緩沖區(qū)，初值為1，每當生產(chǎn)投放一個消息后，in指針加1，即in:=(in+1)modn，輸出指針out指示下一個可獲取消息的緩沖區(qū)，初值為1，每當取走一個消息后，out指針加1，即out：＝(out+1)modn。緩沖池滿：(in+1)modn＝out緩沖池空：in=out3/9/202357第二章進程管理問題的解Q：j=0;while(1){

P(S2);P(mutex);從Buffer[j]取產(chǎn)品;j=(j+1)%n;

V(mutex);

V(S1);消費產(chǎn)品;};P：

i=0;

while(1){

生產(chǎn)產(chǎn)品;

P(S1);

P(mutex);往Buffer[i]放產(chǎn)品;i=(i+1)%n;

V(mutex);

V(S2);

};3/9/202358第二章進程管理【思考題】有一個倉庫，可以存放A和B兩種產(chǎn)品，但要求：（1）

每次只能存入一種產(chǎn)品（A或B）（2）

－N＜A產(chǎn)品數(shù)量－B產(chǎn)品數(shù)量＜M。其中，N和M是正整數(shù)。試用P、V操作描述產(chǎn)品A與B的入庫過程。提示：設(shè)兩個信號量Sa、SbSa表示允許A產(chǎn)品比B產(chǎn)品多入庫的數(shù)量Sb表示允許B產(chǎn)品比A產(chǎn)品多入庫的數(shù)量3/9/202359第二章進程管理解設(shè)兩個信號量Sa、Sb，初值分別為M-1，N-1Sa表示允許A產(chǎn)品比B產(chǎn)品多入庫的數(shù)量Sb表示允許B產(chǎn)品比A產(chǎn)品多入庫的數(shù)量設(shè)互斥信號量mutex，初值為1。3/9/202360第二章進程管理

B產(chǎn)品入庫進程：j=0;while(1){

P(Sb);P(mutex);B產(chǎn)品入庫

V(mutex);V(Sa);消費產(chǎn)品;};A產(chǎn)品入庫進程：

i=0;

while(1){

生產(chǎn)產(chǎn)品;

P(Sa);

P(mutex);A產(chǎn)品入庫

V(mutex);

V(Sb);

};3/9/202361第二章進程管理2.4.3讀者/寫者問題

有兩組并發(fā)進程:讀者和寫者,共享一組數(shù)據(jù)區(qū)要求：允許多個讀者同時執(zhí)行讀操作不允許讀者、寫者同時操作不允許多個寫者同時操作3/9/202362第二章進程管理第一類：讀者優(yōu)先如果讀者來：1）無讀者、寫者，新讀者可以讀2）有寫者等，但有其它讀者正在讀，則新讀者也可以讀3）有寫者寫，新讀者等如果寫者來：1）無讀者，新寫者可以寫2）有讀者，新寫者等待3）有其它寫者，新寫者等待3/9/202363第二章進程管理第一類讀者寫者問題的解法設(shè)有兩個信號量w=1，mutex=1另設(shè)一個全局變量readcount=0w用于讀者和寫者、寫者和寫者之間的互斥readcount表示正在讀的讀者數(shù)目mutex用于對readcount這個臨界資源的互斥訪問3/9/202364第二章進程管理讀者：while(1){P(mutex);readcount++;if(readcount==1)P(w);V(mutex);讀P(mutex);readcount--;if(readcount==0)V(w);V(mutex);};寫者：while(1){P(w);寫V(w);};3/9/202365第二章進程管理【思考題】寫優(yōu)先修改以上讀者寫者問題的算法，使之對寫者優(yōu)先，即一旦有寫者到達，后續(xù)的讀者必須必須等待，無論是否有讀者在讀。提示，增加一個信號量，用于在寫者到達后封鎖后續(xù)的讀者3/9/202366第二章進程管理解

增加一個信號量s，初值為1讀者：while(1){P(s);P(mutex);readcount++;if(readcount==1)P(w);V(mutex);

V(s);讀P(mutex);readcount--;if(readcount==0)V(w);V(mutex);};寫者：while(1){

P(s);

P(w);寫V(w);

V(s);};3/9/202367第二章進程管理2.4.2哲學家就餐問題有五個哲學家圍坐在一圓桌旁，桌中央有一盤通心粉，每人面前有一只空盤子，每兩人之間放一只筷子每個哲學家的行為是思考，感到饑餓，然后吃通心粉為了吃通心粉，每個哲學家必須拿到兩只筷子，并且每個人只能直接從自己的左邊或右邊去取筷子3/9/202368第二章進程管理設(shè)fork[5]為5個信號量，初值為均1Philosopheri：while(1){思考；P(fork[i]);P(fork[(i+1)%5])；進食；V(fork[i]);V(fork[(i+1)%5])；}解3/9/202369第二章進程管理以上解法會出現(xiàn)死鎖為防止死鎖發(fā)生可采取的措施：最多允許4個哲學家同時坐在桌子周圍僅當一個哲學家左右兩邊的筷子都可用時，才允許他拿筷子（）給所有哲學家編號，奇數(shù)號的哲學家必須首先拿左邊的筷子，偶數(shù)號的哲學家則反之

分析3/9/202370第二章進程管理使用一個數(shù)組state來跟蹤一個哲學家是在吃飯、思考還是正在試圖拿筷子。一個哲學家只有在兩個鄰居都不在進餐時才允許轉(zhuǎn)移到進餐狀態(tài)。第i位哲學家的鄰居由宏LEFT和RIGHT定義，換言之，若i為2，則LEFT為1，RIGHT為3。3/9/202371第二章進程管理信號量集——AND型信號量集AND型信號量集是指同時需要多種資源且每種占用一個時的信號量操作

AND型信號量集的基本思想：在一個原語中申請整段代碼需要的多個臨界資源，要么全部分配給它，要么一個都不分配AND型信號量集P原語為SwaitAND型信號量集V原語為Ssignal3/9/202372第二章進程管理

Swait(S1,S2,…,Sn) //P原語；{while(TRUE){if(S1>=1&&S2>=1&&…&&Sn>=1){ //滿足資源要求時的處理；for(i=1;i<=n;++i)-–Si;//注：與P的處理不同，這里是在確信可滿足//資源要求時，才進行減1操作；break;}else{ //某些資源不夠時的處理；

調(diào)用進程進入第一個小于1信號量的等待隊列Sj.queue;

阻塞調(diào)用進程;}3/9/202373第二章進程管理

Ssignal(S1,S2,…,Sn){for(i=1;i<=n;++i){++Si; //釋放占用的資源；for(在Si.queue中等待的每一個進程P)//檢查每種資源的等待隊列的所有進程；{從等待隊列Si.queue中取出進程P;

3/9/202374第二章進程管理

if(判斷進程P是否通過Swait中的測試)//注：與signal不同，這里要進行重新判斷；{//通過檢查（資源夠用）時的處理；

進程P進入就緒隊列;}else{//未通過檢查（資源不夠用）時的處理；

進程P進入某等待隊列；}}}}3/9/202375第二章進程管理一般“信號量集”一般信號量集是指同時需要多種資源、每種占用的數(shù)目不同、且可分配的資源還存在一個臨界值時的信號量處理

一般信號量集的基本思路就是在AND型信號量集的基礎(chǔ)上進行擴充，在一次原語操作中完成所有的資源申請。3/9/202376第二章進程管理進程對信號量Si的測試值為ti（表示信號量的判斷條件，要求Si>=ti；即當資源數(shù)量低于ti時，便不予分配）占用值為di（表示資源的申請量，即Si=Si-di）對應(yīng)的P、V原語格式為：Swait(S1,t1,d1;...;Sn,tn,dn);Ssignal(S1,d1;...;Sn,dn);3/9/202377第二章進程管理一般“信號量集”可以用于各種情況的資源分配和釋放，幾種特殊情況：Swait(S,d,d)表示每次申請d個資源，當少于d個時，便不分配Swait(S,1,1)表示互斥信號量Swait(S,1,0)可作為一個可控開關(guān)（當S1時，允許多個進程進入臨界區(qū)；當S=0時，禁止任何進程進入臨界區(qū)）3/9/202378第二章進程管理2.5管程機制 Hoare（1974）和BrinchHansen（1975）提出了一種高級的同步原語，稱為管程(monitor)。一個管程是一個由過程、變量及數(shù)據(jù)結(jié)構(gòu)等組成的一個集合，它們組成一個特殊的模塊或軟件包。進程可在任何需要的時候調(diào)用管程中的過程，但它們不能在管程外的過程中直接訪問管程內(nèi)的數(shù)據(jù)結(jié)構(gòu)。3/9/202379第二章進程管理在OS中引入管程的目的是為了更簡便、更可靠地解決進程之間的同步、互斥問題。在未引入管程之間，進程間的同步、互斥問題是由程序員處理的。例如，在臨界區(qū)的前后插入P、V操作。但是，由程序員處理同步、互斥問題有可能引入種種人為的錯誤。管程主要是管理對共享數(shù)據(jù)的操作和使用，即把對共享數(shù)據(jù)互斥使用的控制這一任務(wù)從程序員身上，交由編譯程序去處理，這樣既方便了編程，又不會產(chǎn)生人為的同步、互斥上的錯誤。3/9/202380第二章進程管理管程機制 管程有一個很重要的特性，任一時刻管程中只能有一個活躍進程。 使管程能有效地完成互斥，只要把臨界區(qū)代碼放在管程中即可。 管程提供了一種實現(xiàn)互斥的簡便途徑，但這還不夠，還需要一種辦法以使得進程在無法繼續(xù)運行時被阻塞。 例如，在生產(chǎn)者－消費者問題中，很容易將針對緩沖區(qū)滿和緩沖區(qū)空的測試放到管程的過程中，但是生產(chǎn)者在發(fā)現(xiàn)緩沖區(qū)滿的時候如何阻塞?3/9/202381第二章進程管理 解決方法在于引入條件變量(conditionvariables)，及相關(guān)的兩個操作：WAIT和SIGNAL。當一個管程過程發(fā)現(xiàn)它無法繼續(xù)時（例如，生產(chǎn)者發(fā)現(xiàn)緩沖區(qū)滿），它在某些條件變量上執(zhí)行WAIT，如full。這個動作引起調(diào)用進程阻塞。它也允許另一個先前被擋在管程之外的進程現(xiàn)在進入管程。

3/9/202382第二章進程管理另一個進程，如消費者，可以通過對其伙伴正在其上等待的一個條件變量執(zhí)行SIGNAL來喚醒正在睡眠的伙伴進程。為避免管程中同時有兩個活躍進程，我們需要一條規(guī)則來通知在SIGNAL之后該怎么辦。Hoare建議讓新喚醒的進程運行，而掛起另一個進程。BrinchHansen則建議要求執(zhí)行SIGNAL的進程必須立即退出管程。換言之，SIGNAL語句只可能作為一個管程過程的最后一條語句。我們將采納BrinchHansen的建議，因為它在概念上更簡單，并且更容易實現(xiàn)。如果在一個條件變量上正有若干進程等待，則對該條件變量執(zhí)行SIGNAL操作，調(diào)度程序?qū)⒃谄渲羞x擇一個使其恢復(fù)運行。3/9/202383第二章進程管理使用管程解決生產(chǎn)者－消費者問題數(shù)據(jù)結(jié)構(gòu)monitorProducerConsumerconditionfull，empty;integercount;procedureenter;beginifcount=Nthenwait（full）;enter_item;count：=count+1;ifcount=1thensignal（empty）end;3/9/202384第二章進程管理procedureremove;beginifcount=0thenwait（empty）;remove_item;count：=count-1;ifcount=N-1thensignal（full）;end;count：=0;endmonitor;3/9/202385第二章進程管理procedureproducer;begin whiletruedo begin produce-item; ProducerConsumer.enter endend3/9/202386第二章進程管理procedureconsumer;begin whiletruedo begin ProducerConsumer.remove; consume-item; endend3/9/202387第二章進程管理2.6進程通信所謂進程通信是指進程之間可直接以較高的效率傳遞較多數(shù)據(jù)的信息交換方式。P.V操作實現(xiàn)的是進程之間的低級通訊，所以P.V為低級通訊原語。它只能傳遞簡單的信號，不能傳遞交換大量信息。如果要在進程間傳遞大量信息則要用Send/Receive原語（高級通訊原語）3/9/202388第二章進程管理2.6.1進程通信類型1、共享存儲器系統(tǒng)

2、消息傳遞系統(tǒng)

3、管道通信(共享文件方式)3/9/202389第二章進程管理1、共享存儲器系統(tǒng)基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式諸進程公用某些數(shù)據(jù)結(jié)構(gòu)，進程通過它們交換信息。如生產(chǎn)者-消費者問題中的有界緩沖區(qū)3/9/202390第二章進程管理基于共享存儲區(qū)的通信方式高級通信，在存儲器中劃出一塊共享存儲區(qū)，進程在通信前，向系統(tǒng)申請共享存儲區(qū)中的一個分區(qū)，并指定該分區(qū)的關(guān)鍵字，若系統(tǒng)已經(jīng)給其它進程分配了這樣的分區(qū)，則將該分區(qū)的描述符返回給申請者。接著，申請者把獲得的共享存儲分區(qū)連接到本進程上，此后可讀寫該分區(qū)。

以上兩種方式的同步互斥都要由進程自己負責。3/9/202391第二章進程管理2、消息傳遞系統(tǒng) 進程間的數(shù)據(jù)交換以消息為單位，程序員利用系統(tǒng)的通信原語實現(xiàn)通信。操作系統(tǒng)隱藏了通信的實現(xiàn)細節(jié)，簡化了通信程序編制的復(fù)雜性。因而得到廣泛應(yīng)用。3/9/202392第二章進程管理消息傳遞系統(tǒng)可分為：直接通信：發(fā)送進程直接把消息發(fā)送給接收者，并將它掛在接收進程的消息緩沖隊列上。接收進程從消息緩沖隊列中取得消息。 也稱為消息緩沖通信3/9/202393第二章進程管理間接通信：發(fā)送進程將消息發(fā)送到某種中間實體中（信箱），接收進程從中取得消息。 也稱信箱通信。在網(wǎng)絡(luò)中稱為電子郵件系統(tǒng)。3/9/202394第二章進程管理3、管道通信所謂管道，是指用于連接一個讀進程和一個寫進程的文件，稱pipe文件。向管道提供輸入的進程（稱寫進程），以字符流的形式將大量數(shù)據(jù)送入管道，而接受管道輸出的進程（讀進程）可從管道中接收數(shù)據(jù)。該方式首創(chuàng)于UNIX，它能傳送大量數(shù)據(jù)，被廣泛采用。

發(fā)送進程接收進程字符流方式寫入讀出先進先出順序3/9/202395第二章進程管理2.6.2消息緩沖通信的實現(xiàn)在操作系統(tǒng)空間設(shè)置一組緩沖區(qū)。當發(fā)送進程需要發(fā)送消息時，執(zhí)行send系統(tǒng)調(diào)用，產(chǎn)生訪管中斷，進入操作系統(tǒng)。操作系統(tǒng)為發(fā)送進程分配一個空緩沖區(qū)，并將所發(fā)送的消息從發(fā)送進程copy到緩沖區(qū)中，然后將該載有消息的緩沖區(qū)連接到接收進程的消息鏈鏈尾，如此就完成了發(fā)送過程。發(fā)送進程返回到用戶態(tài)繼續(xù)執(zhí)行。3/9/202396第二章進程管理在以后某個時刻，當接收進程執(zhí)行到receive接收原語時，也產(chǎn)生訪管中斷進入操作系統(tǒng)。由操作系統(tǒng)將載有消息的緩沖區(qū)從消息鏈中取出，并把消息內(nèi)容copy到接收進程空間，之后收回緩沖區(qū)，如此就完成了消息的接收，接收進程返回到用戶態(tài)繼續(xù)進行3/9/202397第二章進程管理PCB......Send(R,M)......SIZE:消息長度TEXT:消息正文......消息鏈指針............Receive(N)......SIZE:消息長度TEXT:消息正文......M:N:接收進程R發(fā)送進程S消息消息消息......圖示3/9/202398第二章進程管理typemessageBuffer=recordsender;//發(fā)送者IDsize;//消息長度text;//消息正文next;//消息隊列指針end消息緩沖區(qū)結(jié)構(gòu)3/9/202399第二章進程管理PCB中有關(guān)通信的數(shù)據(jù)項typePCB=record…mq;//消息隊列首指針mutex;//消息隊列互斥信號量sm;//消息隊列資源信號量end3/9/2023100第二章進程管理send（R,M）begin

在OS中分配M.size大小的緩沖區(qū)t;將M中的內(nèi)容復(fù)制到t;得到進程R的PCB的指針q；P(q.mutex); 將t掛到隊列q.mq隊尾；

V(q.mutex);

V（q.sm);end用P、V操作來實現(xiàn)Send原語3/9/2023101第二章進程管理Receive(N）begin得到本進程PCB的指針q；P(q.sm);P(q.mutex);從q.mq隊首取下一個緩沖區(qū)t；

V(q.mutex);將t的內(nèi)容復(fù)制到N，并釋放tend用P、V操作來實現(xiàn)Receive原語3/9/2023102第二章進程管理用消息傳遞解決生產(chǎn)者－消費者問題#defineN100 /*緩沖區(qū)中的槽數(shù)*/voidproducer(void){intitem;messagem; /*消息緩沖區(qū)*/while(TRUE){ produce-item(&item); /*產(chǎn)生數(shù)據(jù)*/ receive(consumer,&m); /*等待空消息*/ build-message(&m,item);/*構(gòu)造消息供發(fā)送*/ send(consumer,&m); /*向消費者發(fā)送*/}}3/9/2023103第二章進程管理voidconsumer(void){intitem,i;messagem; /*消息緩沖區(qū)*/for(i=0;i<N;i++)send(producer,&m);/*發(fā)送N條空消息*/while(TRUE){ receive(producer,&m); /*收取一條消息*/ extract-item(&m,&item); /*從消息提取數(shù)據(jù)*/ send(producer,&m); /*回送空消息作為應(yīng)答*/ consume-item(item); /*使用數(shù)據(jù)項*/}}3/9/2023104第二章進程管理信箱通信的實現(xiàn)信箱使用規(guī)則若發(fā)送信件時信箱已滿，則發(fā)送進程被置為“等信箱”狀態(tài)，直到信箱有空時才被喚醒若取信件時信箱中無信，則接收進程被置為“等信件”狀態(tài)，直到有信件時才被喚醒3/9/2023105第二章進程管理Send實現(xiàn)send（MailBox，M）：把信件M送到指定的信箱MailBox中步驟：查找指定信箱MailBox；若信箱未滿，則把信件M送入信箱且喚醒“等信件”者；若信箱已滿置發(fā)送信件進程為“等信箱”狀態(tài)；3/9/2023106第二章進程管理Receive實現(xiàn)receive（MailBox，X）：從指定信箱MailBox中取出一封信，存放到指定的地址X中步驟：查找指定信箱MailBox；若信箱中有信，則取出一封信存于X中且喚醒“等信箱”者；若信箱中無信件則置接收信件進程“等信件”狀態(tài)；3/9/2023107第二章進程管理把信箱分為以下三類： 私用信箱。 用戶進程為自己建立的，并作為該進程的一部分。 信箱的擁有者有權(quán)從信箱中讀取消息，其他用戶則只能將消息發(fā)送到該信箱中。 私用信箱可采用單向通信鏈路實現(xiàn)。 當擁有該信箱的進程結(jié)束時，信箱也隨之消失。

其

他

用

戶

信箱

進程

3/9/2023108第二章進程管理公用信箱由操作系統(tǒng)創(chuàng)建，提供給系統(tǒng)中的所有核準進程使用。核準進程可使用該信箱收、發(fā)消息。公用信箱在系統(tǒng)運行期間始終存在。公用信箱應(yīng)采用雙向通信鏈路的信箱來實現(xiàn)。3/9/2023109第二章進程管理共享信箱 某進程在創(chuàng)建時或創(chuàng)建后，指明它是可供共享的，同時指出共享進程(用戶)的名字。 擁有者和共享者，都有權(quán)從信箱中取走發(fā)送給自己的消息。

3/9/2023110第二章進程管理在利用信箱通信的發(fā)送進程和接收進程之間，存在下述的四種關(guān)系：一對一關(guān)系。發(fā)送進程和接收進程之間建立一條專用的通信鏈路進行通信，不受其它進程的影響。多對一關(guān)系。又稱為客戶／服務(wù)器交互，提供服務(wù)的進程與多個用戶進程之間進行交互。一對多關(guān)系。一個發(fā)送進程與多個接收進程進行交互，發(fā)送進程可用廣播形式，向接收者發(fā)送消息。多對多關(guān)系。建立一個公用信箱；讓多個進程都能向信箱中投遞消息，也可從信箱中取走屬于自己的消息。3/9/2023111第二章進程管理2.6.3消息傳遞系統(tǒng)實現(xiàn)中的幾個問題通信鏈路為了在發(fā)送進程和接收進程之間能進行通信，必須在它們之間建立一條通信鏈路。有兩種方式建立通信鏈路：顯式建立鏈路。由發(fā)送進程在通信之前，用“建立連接”命令(原語)請求系統(tǒng)為之建立一條通信鏈路；在鏈路使用完后，也應(yīng)用顯式方式拆除鏈路。這種方式主要用于計算機網(wǎng)絡(luò)中。隱式建立鏈路。利用系統(tǒng)提供的發(fā)送命令(原語)時，系統(tǒng)會自動地為之建立一條鏈路。主要用于單機系統(tǒng)中。3/9/2023112第二章進程管理根據(jù)通信鏈路的連接方法，又可把通信鏈路分為：點——點連接通信鏈路。一條鏈路只連接兩個結(jié)點(進程)；多點連接鏈路。指用一條鏈路連接多個(M＞2)結(jié)點(進程)。根據(jù)通信方式的不同，又可把鏈路分為：單向通信鏈路。只允許發(fā)送進程向接收進程發(fā)送消息；雙向鏈路。3/9/2023113第二章進程管理根據(jù)通信鏈路的容量的不同也可把鏈路分成：無容量通信鏈路。沒有緩沖區(qū)，不能暫存任何消息；有容量通信鏈路。設(shè)置了暫存消息的緩沖區(qū)，緩沖區(qū)數(shù)目愈多，通信鏈路的容量愈大。3/9/2023114第二章進程管理進程同步方式（完成消息的發(fā)送或接收之后）發(fā)送進程阻塞、接收進程阻塞主要用于進程之間緊密同步、發(fā)送進程和接收進程之間無緩沖區(qū)時。兩個進程平時都處于阻塞狀態(tài)，直到有消息傳遞時。這種同步方式稱為匯合。送進程不阻塞、接收進程阻塞平時發(fā)送進程不阻塞，而接收進程則處于阻塞狀態(tài)，直到發(fā)送進程發(fā)來消息時被喚醒。應(yīng)用得最廣。例如：在服務(wù)器上的服務(wù)進程，平時都處于阻塞狀態(tài)，直到有請求服務(wù)的消息到達時。3/9/2023115第二章進程管理發(fā)送進程與接收進程均不阻塞平時發(fā)送進程和接收進程都在忙于自己的事情，僅當發(fā)生某個事件，使它無法繼續(xù)運行時，才把自己阻塞起來等待。例如，在發(fā)送進程和接收進程之間聯(lián)系著一個最多可接納N個消息的消息隊列時。只有消息隊列中的消息數(shù)目為N個時，發(fā)送進程才會阻塞；消息數(shù)為0時，接收進程才會阻塞。3/9/2023116第二章進程管理習題

進程A1、A2，。。。An1通過m個緩沖區(qū)向進程B1、B2、。。。Bn2不斷發(fā)送消息。發(fā)送和接收工作遵循下列規(guī)則：（1）每個發(fā)送進程一次發(fā)送一個消息，寫入一個緩沖區(qū)，緩沖區(qū)大小等于消息長度（2）對每個消息，B1，B2，Bn2都須各接收一次，讀入各自的數(shù)據(jù)區(qū)內(nèi)（3）m個緩沖區(qū)都滿時，發(fā)送進程等待，沒有可讀消息時，接收進程等待。試用P、V操作組織正確的發(fā)送和接收工作。3/9/2023117第二章進程管理提示：每個緩沖區(qū)只要寫一次但要讀n2次，因此，可以看成n2組緩沖區(qū)，每個發(fā)送者要同時寫n2個緩沖區(qū)，而每個接收者只要讀它自己的緩沖區(qū)。Sin[n2]=mSout[n2]=0;3/9/2023118第二章進程管理解先將問題簡化：設(shè)緩沖區(qū)的大小為1有一個發(fā)送進程A1有二個接收進程B1、B2設(shè)有信號量Sin[1]、Sin[2]初值為1設(shè)有信號量Sout[1]、Sout[2]初值為03/9/2023119第二章進程管理Bi：while(1){

P(Sout[i]);

從緩沖區(qū)取數(shù)V(Sin[i]);}A1:

while(1){

P(Sin[1]);

P(Sin[2]);

將數(shù)據(jù)放入緩沖區(qū) V(Sout[1]);V(Sout[2]);

}3/9/2023120第二章進程管理設(shè)緩沖區(qū)的大小為m有一個發(fā)送進程A1有二個接收進程B1、B2設(shè)有信號量Sin[1]、Sin[2]初值為m設(shè)有信號量Sout[1]、Sout[2]初值為03/9/2023121第二章進程管理Bi：while(1){

P(Sout[i]);

P(mutex); 從緩沖區(qū)取數(shù)

V(mutex);V(Sin[i]);};A1:

while(1){

P(Sin[1]);

P(Sin[2]);

P(mutex); 將數(shù)據(jù)放入緩沖區(qū)

V(mutex); V(Sout[1]);V(Sout[2]);

}3/9/2023122第二章進程管理設(shè)緩沖區(qū)的大小為m有n1個發(fā)送進程A1….An1有n2個接收進程B1…Bn2設(shè)有n2個信號量Sin[n2]初值均為m設(shè)有n2個信號量Sout[n2]初值均為03/9/2023123第二章進程管理Bi：while(1){

P(Sout[i]);

P(mutex);

從緩沖區(qū)取數(shù)

V(mutex);V(Sin[i]);};Aj:while(1){for(i=1;i<=n2;i++)

P(Sin[i]);

P(mutex); 將數(shù)據(jù)放入緩沖區(qū)

V(mutex); for(i=1;i<=n2;i++) V(Sout[2]);}3/9/2023124第二章進程管理oZr%u(x+B2E5H9KcOfRiUmXp#s&v)z0C3F7IaLdPgSkVnYq$t*w-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9KcOfRjUmXp!s&v)z0C4F7IaMdPgSkVnZq$t*x-A1D5G8KbNeQiTlWo#r%v(y+B3E6H9LcOgRjUmYp!s&w)z1C4F7JaMdPhSkVnZq$u*x-A2D5G8KbNfQiTlXo#r%v(y0B3E6I9LcOgRjVmYp!t&w)z1C4G7JaMePhSkWnZr$u*x+A2D5H8KcNfQiUlXo#s%v)y0B3F6I9LdOgRjVmYq!t&w-z1C4G7JbMePhTkWnZr$u(x+A2E5H8KcNfRiUlXp#s%v)y0C3F6IaLdOgSjVnYq!t*w-z1D4G8JbMeQhTkWoZr$u(x+B2E5H9KcNfRiUmXp#s&v)y0C3F7IaLdPgSjVnYq$t*w-A1D4G8JbNeQhTlWoZr%u(y+B2E6H9KcOfRjUmXp!s&v)z0C4F7IaMdPgSkVnYq$t*x-A1D5G8JbNeQiTlWo#r%u(y+B3E6H9LcOfRjUmYp!s&w)z0C4F7JaMdPhSkVnZq$u*x-A2D5G8KbNfQiTlXo#r%v(y+B3E6I9LcOgRjUmYp!t&w)z1C4F7JaMePhSkWnZq$u*x+A2D5H8KbNfQiUlXo#s%v(y0B3F6I9LdOgRjVmYq!t&w-z1C4G7JaMePhTkWnZr$u*x+A2E5H8KcNfQiUlXp#s%v)y0B3F6IaLdOgSjVmYq!t*w-z1D4G7JbMeQhTkWoZr$u(x+B2E5H9KcNfRiUmXp#s&v)y0C3F6IaLdPgSjVnYq!t*w-A1D4G8JbMeQhTlWoZr%u(x+B2E6H9KcOfRiUmXp!s&v)z0C3F7IaMdPgSkVnYq$t*x-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9LcOfRjUmXp!s&w)z0C4F7IaMdPhSkVnZq$t*x-A2D5G8KbNeQiTlXo#r%v(y+B3E6I9LcOgRjUm$t*w-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9LcOfRjUmXp!s&w)z0C4F7IaMdPhSkVnZq$t*x-A2D5G8KbNeQiTlXo#r%v(y+B3E6H9LcOgRjUmYp!s&w)z1C4F7JaMdPhSkWnZq$u*x-A2D5H8KbNfQiTlXo#s%v(y0B3E6I9LdOgRjVmYp!t&w-z1C4G7JaMePhSkWnZr$u*x+A2D5H8KcNfQiUlXo#s%v)y0B3F6I9LdOgSjVmYq!t&w-z1D4G7JbMePhTkWoZr$u(x+A2E5H9KcNfRiUlXp#s&v)y0C3F6IaLdOgSjVnYq!t*w-z1D4G8JbMeQhTkWoZr%u(x+B2E5H9KcOfRiUmXp#s&v)z0C3F7IaLdPgSkVnYq$t*w-A1D5G8JbNeQhTlWoZr%u(y+B2E6H9KcOfRjUmXp!s&v)z0C4F7IaMdPgSkVnZq$t*x-A1D5G8KbNeQiTlWo#r%v(y+B3E6H9LcOgRjUmYp!s&w)z1C4F7JaMdPhSkVnZq$u*x-A2D5G8KbNfQiTlXo#r%v(y0B3E6I9LcOgRjVmYp!t&w)z1C4G7JaMePhSkWnZr$u*x+A2D5H8KcNfQiUlXo#s%v(y0B3F6I9LdOgRjVmYq!t&w-z1C4G7JbMePhTkWnZr$u(x+A2E5H8KcNfRiUlXp#s%v)y0C3F6IaLdOgSjVnYq!t*w-z1D4G7JbMeQhTkWoZr$u(x+B2E5H9KcNfRiUmXp#s&v)y0C3F7IaLdPgSjVnYq$t*w-A1D4G8JbNeQhTlWoZr%u(y+B2E6H9KcOfRjUmXp!s&v)z0C3F7IaMdPgSkVnYq$t*x-A1D5G8JbNeQiTlWo#r%u(y+B3E6H9LcOfRjUmYp!s&w)z0C4F7JaMdPhSkVnZq$u*x-A2D5G8KbNeQiTlXo#r%v(y+B3E6I9LcOgRjUmYpx-A1D5G8JbNeQiTlWo#r%u(y+B3E6H9LcOfRjUmYp!s&w)z0C4F7JaMdPhSkVnZq$t*x-A2D5G8KbNeQiTlXo#r%v(y+B3E6I9LcOgRjUmYp!t&w)z1C4F7JaMePhSkWnZq$u*x+A2D5H8KbNfQiUlXo#s%v(y0B3E6I9LdOgRjVmYp!t&w-z1C4G7JaMePhTkWnZr$u*x+A2E5H8KcNfQiUlXp#s%v)y0B3F6IaLdOgSjVmYq!t*w-z1D4G7JbMePhTkWoZr$u(x+A2E5H9KcNfRiUlXp#s&v)y0C3F6IaLdPgSjVnYq!t*w-A1D4G8JbMeQhTlWoZr%u(x+B2E6H9KcOfRiUmXp!s&v)z0C3F7IaLdPgSkVnYq$t*w-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9LcOfRjUmXp!s&w)z0C4F7IaMdPhSkVnZq$t*x-A2D5G8KbNeQiTlWo#r%v(y+B3E6H9LcOgRjUmYp!s&w)z1C4F7JaMdPhSkWnZq$u*x-A2D5H8KbNfQiTlXo#s%v(y0B3E6I9LdOgRjVmYp!t&w-z1C4G7JaMePhSkWnZr$u*x+A2D5H8KgRjUmYp!s&w)z1C4F7JaMdPhSkWnZq$u*x-A2D5H8KbNfQiTlXo#s%v(y0B3E6I9LcOgRjVmYp!t&w)z1C4G7JaMePhSkWnZr$u*x+A