第3章2進程的同步與互斥講解學習

第3章進程管理

3.1進程的引入3.2進程的結(jié)構(gòu)3.3進程控制3.4進程的同步與互斥3.5進程間通信3.6進程調(diào)度3.7死鎖3.8線程2/5/20251兩種制約關系直接相互制約關系（同步）

間接相互制約關系（互斥）產(chǎn)生的原因進程合作資源共享

2/5/20252進程的同步（1）直接相互制約關系（同步）指系統(tǒng)中一些進程需要相互合作，共同完成一項任務,這種協(xié)作進程之間相互等待對方消息或信號的協(xié)調(diào)關系稱為進程同步.具體說，并發(fā)進程在一些關鍵點上可能需要互相等待與互通消息，進程間的相互聯(lián)系是有意識的安排的。產(chǎn)生的原因進程合作2/5/20253進程的同步（2）一般同步問題有兩類保證一組合作進程按邏輯需要的執(zhí)行次序執(zhí)行

【例】司機P1

售票員P2

REPEATREPEAT

啟動關門

正常運行售票

到站停開門

UNTILFALSEUNTILFALSE保證共享緩沖區(qū)（共享數(shù)據(jù)）的合作進程的同步

【例】輸入進程PI緩沖區(qū)緩沖區(qū)計算進程PC打印進程PP2/5/20254臨界資源臨界資源

系統(tǒng)中某些資源一次只允許一個進程使用，稱這樣的資源為臨界資源或互斥資源或共享變量。硬件臨界資源：打印機、磁帶機軟件臨界資源：只能排它使用的變量、表格、隊列2/5/20256臨界資源實例二人合作存款

count=100;PAS1:N=count;S2:N=N+100;S3:count=N;PBS4:M=count;S5:M=M+200;S6:count=M;執(zhí)行情況：（1）PA—>PB,PB—>PAcount=400√

（2）S1—>PB—>S2—>S3

count=200×（3）S4—>PA—>S5—>S6

count=300×因count是一個互斥性使用的變量，是一個臨界資源2/5/20257臨界區(qū)臨界區(qū)（臨界段）

在進程中訪問臨界資源的那段代碼區(qū)。例子2/5/20258具有臨界資源的進程結(jié)構(gòu)……/*進入?yún)^(qū)*/criticalsection;/*臨界區(qū)*//*退出區(qū)*/remaindersection;/*剩余區(qū)*/

……entrysectionexitsection2/5/20259訪問臨界區(qū)應遵循的原則空閑讓進當無進程在臨界區(qū)時，任何有權(quán)使用臨界區(qū)的進程可進入。忙則等待不允許兩個以上的進程同時進入臨界區(qū)。有限等待任何進入臨界區(qū)的要求應在有限的時間內(nèi)得到滿足。讓權(quán)等待不能進入臨界區(qū)的進程應放棄占用CPU。2/5/202510臨界區(qū)互斥解決方法硬件缺點：成本高軟件用編程解決缺點：(1)忙等待(2)實現(xiàn)過于復雜，需要高的編程技巧信號量機制2/5/202511信號量機制一類資源抽象成S（信號量）信號量只能由P、V操作對其進行操作的變量。信號量的使用應注意必須置一次且只能置一次初值。初值只能為非負整數(shù)，實現(xiàn)互斥時初值為1。只能執(zhí)行P、V操作。2/5/202512P、V操作

P(S)：表示申請一個資源。

V(S)：表示釋放一個資源。

P、V操作必須成對出現(xiàn)，有一個P操作就一定有一個V操作。2/5/202513整型信號量整型信號量信號量S：整型量，除初始化外僅能通過P、V操作訪問P和V操作原語定義：varS:integer;S=1;

P(S)：whileS≤0dono-opS=S-1；

V(S)：S=S+1；一類資源抽象成S（信號量）整型量2/5/202514利用整型信號量實現(xiàn)進程互斥P(S)V(S)P1P2互斥區(qū)P(S)V(S)2/5/202515記錄型信號量記錄型信號量信號量S：記錄型數(shù)據(jù)結(jié)構(gòu),一個分量為整型量value,另一個分量為信號量隊列L；信號量的物理含義當S.value>0：表示可用資源個數(shù)當S.value＝0：表示可用資源正好用完當S.value<0：表示等待該類資源的進程數(shù)一類資源抽象成S（信號量）value0L=nil信號量的值(-2)信號量隊列指針2/5/202516structsemaphore{intvalue;int*L;}voidP(structsemaphoreS);{S.value=S.value–1;/*把信號量減去1*/ifS.value<0thenblock(S.L);/*若信號量小于0，則調(diào)用P(S)的進程被置成等待信號量S的狀態(tài)*/}物理意義：申請一個資源，如果申請成功，則返回；如果申請不成功，則掛在該資源的等待隊列上。voidV(structsemaphoreS);{S.value=S.value+1; /*把信號量加1*/ifS.value<=0thenwakeup(S.L);/*若信號量小于等于0，則釋放一個等待信號量s的進程*/}物理意義：歸還一個資源，如果沒有進程等待該資源，則返回；如果有進程在等待，把等待的進程從L上移到就緒隊列。記錄型信號量描述2/5/202517利用記錄型信號量實現(xiàn)進程互斥P(mutex)V(mutex)P1P2互斥區(qū)P(mutex)V(mutex)2/5/202518信號量及P、V操作討論(1)

信號量的物理含義：

S.value>0:表示有S.value個資源可用 S.value=0:表示無資源可用 S.value<0:則|S.value|表示等待隊列中的進程個數(shù)

信號量的初值應該大于等于02/5/202519P、V操作討論(2)

P(S)：表示申請一個資源

V(S)：表示釋放一個資源。

P、V操作必須成對出現(xiàn)，有一個P操作就一定有一個V操作P、V操作的優(yōu)點

簡單，而且表達能力強，可解決任何互斥問題P、V操作的缺點不夠安全，P、V操作使用不當會出現(xiàn)死鎖，遇到復雜互斥問題時，實現(xiàn)復雜。2/5/202520用P、V操作實現(xiàn)互斥信號量初值為1對于兩個并發(fā)進程，互斥信號量的值僅取1、0和-1三個值：若mutex.value＝1表示沒有進程進入臨界區(qū)若mutex.value＝0表示有一個進程進入臨界區(qū)若mutex.value

＝-1表示一個進程進入臨界區(qū)，另一個進程等待進入。2/5/202521利用P、V操作實現(xiàn)兩個進程互斥的模板如下：

structsemaphoremutex;

mutex.value=1;mutex.L=nil;{

cobegin

ProcessP1:BeginM

P(mutex);

臨界區(qū)1

V(mutex);MEnd

ProcessP2:BeginM

P(mutex);

臨界區(qū)2

V(mutex);MEnd

coend}

2/5/202522使用PV操作實現(xiàn)互斥應注意識別臨界資源是否被共享;是否有排它性使用要求。臨界區(qū)代碼應盡量短小，不能有死循環(huán)。P和V原語應分別緊靠臨界區(qū)的頭尾。P、V操作在同一進程中必須成對出現(xiàn)。2/5/202523思考題

用記錄型信號量解決二人存款問題，用類C語言編寫進程互斥算法。2/5/202524用P、V操作實現(xiàn)進程的同步只要信號量初值是一個大于等于0的整數(shù)就能達到同步的目的，就可以直接使用P、V操作實現(xiàn)同步互斥是一種特殊的同步P、V操作既可以實現(xiàn)互斥，也可以實現(xiàn)同步2/5/202525利用信號量實現(xiàn)進程同步的實例設有三個并發(fā)執(zhí)行的進程P1、P2、P3，其前趨圖如下，試用信號量實現(xiàn)這三個進程同步。設兩個同步信號量S1、S2分別表示進程P2、P3能否開始執(zhí)行structsemaphoreS1,S2=0,0;/*初值均為0*/{

cobeginP1:{

V(S1);V(S2);}P2:{P(S1);;}P3:{P(S2);;}

coend}

P1P3P22/5/202526使用PV操作實現(xiàn)同步應注意信號量的設置信號量的初值

PV操作要成對出現(xiàn)，并在不同的進程中2/5/202527信號量及P、V操作討論(3)(1)P、V操作必須成對出現(xiàn)，有一個P操作就一定有一個V操作(2)當為互斥操作時，它們同處于同一進程當為同步操作時，則不在同一進程中出現(xiàn)(3)如果P(S1)和P(S2)兩個操作在一起，那么P操作的順序至關重要。一個同步P操作與一個互斥P操作在一起時，同步P操作在互斥P操作前，而兩個V操作無關緊要。2/5/202528PV操作實現(xiàn)互斥與同步的模板進程互斥

S初值為1

P1

P2

P(S)P(S)臨界區(qū)1臨界區(qū)2V(S)V(S)在P1與P2中設置相同的P、V操作進程同步

S1初值為n，S2初值為0

P1

P2

P(S1)

P(S2)段1段2

V(S2)

V(S1)2/5/202529經(jīng)典的進程同步問題生產(chǎn)者/消費者問題讀者/寫者問題哲學家進餐問題2/5/202530生產(chǎn)者/消費者問題生產(chǎn)者消費者問題是一種同步問題的抽象描述。計算機系統(tǒng)中的每個進程都可以消費（使用）或生產(chǎn)（釋放）某類資源。這些資源可以是硬件資源，也可以是軟件資源。當某一進程使用某一資源時，可以看作是消費，稱該進程為消費者。而當某一進程釋放某一資源時，它就相當于生產(chǎn)者。2/5/202531生產(chǎn)者/消費者問題(描述)

通過一個公用緩沖池可以把一群生產(chǎn)者p1,p2…,pm，和一群消費者Q1,Q2,…,Qn聯(lián)系起來。如圖:只要緩沖區(qū)未滿，生產(chǎn)者就可以把產(chǎn)品送入緩沖區(qū);只要緩沖區(qū)未空，消費者就可以從緩沖區(qū)中取走物品。2/5/202532生產(chǎn)者/消費者問題(圖示)2/5/202533生產(chǎn)者/消費者問題(分析)為解決生產(chǎn)者消費者問題，應該設兩個同步信號量，一個說明空緩沖區(qū)的數(shù)目，用empty表示，初值為緩沖池的大小N，另一個說明已用緩沖區(qū)的數(shù)目，用full表示，初值為０。由于在此問題中有i個生產(chǎn)者和j個消費者，它們在執(zhí)行生產(chǎn)活動和消費活動中要對緩沖池進行操作。由于緩沖池是一個臨界資源，必須互斥使用，所以，另外還需要設置一個互斥信號量mutex，其初值為１。structsemaphoneempty=n,full=0,mutex=1;voidbuffer[n-1];intin=,out=0;2/5/202534生產(chǎn)者/消費者問題(解決)Consumerj:while(1){

P(full);P(mutex);從Buffer[out]取產(chǎn)品;out=(out+1)modn;

V(mutex);

V(empty);消費產(chǎn)品;}coend;cobegin

procedurei:while(1){

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

P(empty);

P(mutex);

往Buffer[in]放產(chǎn)品;in=(in+1)modn;

V(mutex);

V(full);

}2/5/202535生產(chǎn)者/消費者問題(思考)在生產(chǎn)者進程和消費者進程中，兩個P操作的執(zhí)行順序是否能交換？兩個V操作的執(zhí)行順序是否能交換？2/5/202536思考題

兩個進程合作完成數(shù)據(jù)計算和打印工作，計算進程未計算完就不可打印，反之也然，雙方共用一個緩沖區(qū)，寫出此算法。2/5/202537讀者/寫者問題

有兩組并發(fā)進程:讀者和寫者,共享一個數(shù)據(jù)文件

要求：允許多個讀者同時執(zhí)行讀操作不允許讀者、寫者同時操作不允許多個寫者同時操作2/5/202538讀者/寫者問題如果讀者來：1）無讀者、寫者，新讀者可以讀2）有寫者等，但有其它讀者正在讀，則新讀者也可以讀3）有寫者寫，新讀者等如果寫者來：1）無讀者、寫者，新寫者可以寫2）有讀者，新寫者等待3）有其它寫者，新寫者等待2/5/202539讀者寫者問題的解法為實現(xiàn)讀者和寫者、寫者和寫者之間的互斥，設置一個互斥信號量Wmutex=1由于“讀—讀”允許，再設置一個整型變量Readcount表示正在讀的進程數(shù)，初值Readcount=0由于Readcount是一個可被多個讀者進程訪問的臨界資源，所以要為它設置一個互斥信號量Rmutex=1讀者—寫者算法如下：讀者：{

P(Rmutex);ifreadcount=0thenP(Wmutex);Readcount=Readcount+1;

V(Rmutex);讀

P(Rmutex);Readcount=Readcount-1;ifReadcount=0thenV(Wmutex);

V(Rmutex);}寫者：{

P(Wmutex);寫

V(Wmutex);}2/5/202540哲學家就餐問題有五個哲學家圍坐在一圓桌旁，桌中央有一盤通心粉，每人面前有一只空盤子，每兩人之間放一只筷子。每個哲學家的行為是思考，感到饑餓，取筷子，然后吃通心粉，放筷子，思考。為了吃通心粉，每個哲學家必須拿到兩只筷子，并且每個人只能直接從自己的左邊或右邊去取筷子。筷子是臨界資源，要用5個互斥信號量來表示這5只筷子。2/5/202541哲學家就餐問題解設fork[5]為5個信號量，初值均為1struct

semaphore

fork[4];fork[i]:=1;Philosopheri：While(1){

思考；P(fork[i]);P(fork[(i+1)mod5])；