江蘇師范大學操作系統(tǒng)ppt第3章-3 進程的同步與互斥

第3章進程管理

3.1進程的引入

3.2進程的結構

3.3進程控制

3.4進程的同步與互斥

3.5進程間通信

3.6進程調度

3.7死鎖

3.8線程1兩種制約關系直接相互制約關系（同步）

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

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

【例】司機P1

售票員P2

REPEATREPEAT

啟動關門

正常運行售票

到站停開門

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

【例】輸入進程PI緩沖區(qū)緩沖區(qū)計算進程PC打印進程PP4進程的互斥是解決進程間競爭關系(間接制約關系)的手段。間接相互制約關系（互斥）

是指若干個進程同時競爭一個需要互斥使用的資源時，任何時刻最多允許一個進程去使用，其他要使用該資源的進程必須等待，直到該資源被釋放。進程間要通過某種中介發(fā)生聯(lián)系，是無意識安排的。產(chǎn)生的原因資源共享互斥是一種特殊的同步逐次使用互斥資源，也是對進程使用資源次序上的一種協(xié)調。5臨界資源臨界資源

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

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—>S3count=200

×（3）S4—>PA—>S5—>S6count=300

×因count是一個互斥性使用的變量，是一個臨界資源7臨界區(qū)臨界區(qū)（臨界段）在進程中訪問臨界資源的那段代碼區(qū)。例子8具有臨界資源的進程結構

……/*進入?yún)^(qū)*/criticalsection;/*臨界區(qū)*//*退出區(qū)*/remaindersection;/*剩余區(qū)*/……entrysectionexitsection9訪問臨界區(qū)應遵循的原則空閑讓進

當無進程在臨界區(qū)時，任何有權使用臨界區(qū)的進程可進入。忙則等待

不允許兩個以上的進程同時進入臨界區(qū)。有限等待

任何進入臨界區(qū)的要求應在有限的時間內(nèi)得到滿足。讓權等待

不能進入臨界區(qū)的進程應放棄占用CPU。10臨界區(qū)互斥解決方法軟件用編程解決缺點：

(1)忙等待

(2)實現(xiàn)過于復雜，需要高的編程技巧硬件專用機器指令方法屏蔽中斷方法缺點：忙等待信號量機制11硬件解法（1）測試與設置指令int

TS(intlock){TS=lock;lock=1;}測試與設置指令的使用

intlock=0;M/*進入臨界區(qū)前執(zhí)行*/whileTS(lock)doskip;

臨界區(qū)

/*離開臨界區(qū)后執(zhí)行*/

lock:=0;M12硬件解法（2）交換指令Swap(intlock,intkey){

inttemp;temp=lock;lock=key;key=temp}交換指令的應用intlock=0;每個進程定義一個局部變量intkey;進入臨界區(qū)前執(zhí)行：

key=1;

do

swap(lock,key)whilekey=0;離開臨界區(qū)后執(zhí)行：lock=0;13硬件解法（3）

進入臨界區(qū)前執(zhí)行：執(zhí)行“關中斷”指令

離開臨界區(qū)后執(zhí)行：執(zhí)行“開中斷”指令14信號量機制一類資源抽象成S（信號量）信號量只能由P、V操作對其進行操作的變量。信號量的使用應注意必須置一次且只能置一次初值初值只能為非負整數(shù)只能執(zhí)行P、V操作15整型信號量整型信號量信號量S：整型量，除初始化外僅能通過P、V操作訪問P和V操作原語定義：

intS;S=1;

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

V(S)：S=S+1；S（信號量）一類資源抽象成整型量16記錄型信號量記錄型信號量信號量S：記錄型數(shù)據(jù)結構,一個分量為整型量value,另一個分量為信號量隊列L；一類資源抽象成S（信號量）value0L=nil17信號量的物理含義

S.value>0:表示有S.value個資源可用

S.value=0:表示無資源可用

S.value<0:則|S.value|表示等待隊列中的進程個數(shù)

信號量的初值應該大于等于0信號量的值(-2)信號量隊列指針18structsemaphore{

intvalue;

int*L;}voidP(structsemaphoreS);{S.value=S.value–1;/*把信號量減去1*/

ifS.value<0thenblock(S.L);/*若信號量小于0，則調用P(S)的進程被置成等待信號量S的狀態(tài)*/}物理意義：申請一個資源，如果申請成功，則返回；如果申請不成功，則掛在該資源的等待隊列上。voidV(structsemaphoreS);{S.value=S.value+1; /*把信號量加1*/ifS.value<=0thenwakeup(S.L);/*若信號量小于等于0，則釋放一個等待信號量s的進程*/}物理意義：歸還一個資源，如果沒有進程等待該資源，則返回；如果有進程在等待，把等待的進程從L上移到就緒隊列。記錄型信號量描述19P、V操作討論

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

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

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

簡單，而且表達能力強，可解決任何互斥問題P、V操作的缺點

不夠安全，P、V操作使用不當會出現(xiàn)死鎖，遇到復雜互斥問題時，實現(xiàn)復雜。20用P、V操作實現(xiàn)互斥信號量初值為1對于兩個并發(fā)進程，互斥信號量的值僅取1、0和-1三個值：若mutex.value＝1表示沒有進程進入臨界區(qū)若mutex.value＝0表示有一個進程進入臨界區(qū)若mutex.value

＝-1表示一個進程進入臨界區(qū)，另一個進程等待進入。對于n個并發(fā)進程，互斥信號量的取值范圍是？

-(n-1)～121利用記錄型信號量實現(xiàn)進程互斥P(mutex)V(mutex)P1P2互斥區(qū)P(mutex)V(mutex)22利用P、V操作實現(xiàn)兩個進程互斥的模板如下：

structsemaphoremutex;

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

{

cobegin

ProcessP1:{

M

P(mutex);

臨界區(qū)1

V(mutex);

M

}ProcessP2:{

M

P(mutex);

臨界區(qū)2

V(mutex);

M

}

coend}

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

用記錄型信號量解決二人存款問題，用類C語言編寫進程互斥算法。25用P、V操作實現(xiàn)進程的同步只要信號量初值是一個大于等于0的整數(shù)就能達到同步的目的，就可以直接使用P、V操作實現(xiàn)同步互斥是一種特殊的同步P、V操作既可以實現(xiàn)互斥，也可以實現(xiàn)同步26利用信號量實現(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}

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

PV操作要成對出現(xiàn)，并在不同的進程中28信號量及P、V操作討論(1)

P、V操作必須成對出現(xiàn)，有一個P操作就一定有一

個V操作(2)當為互斥操作時，它們同處于同一進程當為同步操作時，則不在同一進程中出現(xiàn)(3)如果P(S1)和P(S2)兩個操作在一起，那么P操作的順序至關重要。一個同步P操作與一個互斥P操作在一起時，同步

P操作在互斥P操作前，而兩個V操作無關緊要。29PV操作實現(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)30經(jīng)典的進程同步問題生產(chǎn)者/消費者問題讀者/寫者問題哲學家進餐問題31生產(chǎn)者/消費者問題

生產(chǎn)者消費者問題是一種同步問題的抽象描述。計算機系統(tǒng)中的每個進程都可以消費（使用）或生產(chǎn)（釋放）某類資源。這些資源可以是硬件資源，也可以是軟件資源。當某一進程使用某一資源時，可以看作是消費，稱該進程為消費者。而當某一進程釋放某一資源時，它就相當于生產(chǎn)者。32生產(chǎn)者/消費者問題(描述)

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

semaphoneempty=n,full=0,mutex=1;voidbuffer[n-1];

intin=0,out=0;38生產(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);

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

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

讀者和寫者,共享一個數(shù)據(jù)文件

要求：允許多個讀者同時執(zhí)行讀操作不允許讀者、寫者同時操作不允許多個寫者同時操作42讀者/寫者問題

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

P(Rmutex);

ifreadcount=0then

P(Wmutex);

Readcount=Readcount+1;

V(Rmutex);

讀

P(Rmutex);

Readcount=Readcount-1;ifReadcount=0then

V(Wmutex);

V(Rmutex);}寫者：

{

P(Wmutex);

寫

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

semaphore

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

思考；

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

進食；

V(fork[i]);V(fork[(i+1)mod5])；}

以上解法會出現(xiàn)死鎖,為防止死鎖發(fā)生可采