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

第3章進(jìn)程管理

3.1進(jìn)程的引入

3.2進(jìn)程的結(jié)構(gòu)

3.3進(jìn)程控制

3.4進(jìn)程的同步與互斥

3.5進(jìn)程間通信

3.6進(jìn)程調(diào)度

3.7死鎖

3.8線程1兩種制約關(guān)系直接相互制約關(guān)系（同步）

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

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

【例】司機(jī)P1

售票員P2

REPEATREPEAT

啟動(dòng)關(guān)門

正常運(yùn)行售票

到站停開門

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

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

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

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

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是一個(gè)互斥性使用的變量，是一個(gè)臨界資源7臨界區(qū)臨界區(qū)（臨界段）在進(jìn)程中訪問臨界資源的那段代碼區(qū)。例子8具有臨界資源的進(jìn)程結(jié)構(gòu)

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

當(dāng)無(wú)進(jìn)程在臨界區(qū)時(shí)，任何有權(quán)使用臨界區(qū)的進(jìn)程可進(jìn)入。忙則等待

不允許兩個(gè)以上的進(jìn)程同時(shí)進(jìn)入臨界區(qū)。有限等待

任何進(jìn)入臨界區(qū)的要求應(yīng)在有限的時(shí)間內(nèi)得到滿足。讓權(quán)等待

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

(1)忙等待

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

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

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

臨界區(qū)

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

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

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

key=1;

do

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

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

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

intS;S=1;

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

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

S.value>0:表示有S.value個(gè)資源可用

S.value=0:表示無(wú)資源可用

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

信號(hào)量的初值應(yīng)該大于等于0信號(hào)量的值(-2)信號(hào)量隊(duì)列指針18structsemaphore{

intvalue;

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

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

P(S)：表示申請(qǐng)一個(gè)資源

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

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

簡(jiǎn)單，而且表達(dá)能力強(qiáng)，可解決任何互斥問題P、V操作的缺點(diǎn)

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

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

-(n-1)～121利用記錄型信號(hào)量實(shí)現(xiàn)進(jìn)程互斥P(mutex)V(mutex)P1P2互斥區(qū)P(mutex)V(mutex)22利用P、V操作實(shí)現(xiàn)兩個(gè)進(jì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操作實(shí)現(xiàn)互斥應(yīng)注意識(shí)別臨界資源是否被共享;是否有排它性使用要求。臨界區(qū)代碼應(yīng)盡量短小，不能有死循環(huán)。P和V原語(yǔ)應(yīng)分別緊靠臨界區(qū)的頭尾。P、V操作在同一進(jìn)程中必須成對(duì)出現(xiàn)。24思考題

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

cobeginP1:{V(S1);

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

;}P3:{P(S2);;}

coend}

P1P3P227使用PV操作實(shí)現(xiàn)同步應(yīng)注意信號(hào)量的設(shè)置信號(hào)量的初值

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

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

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

P操作在互斥P操作前，而兩個(gè)V操作無(wú)關(guān)緊要。29PV操作實(shí)現(xiàn)互斥與同步的模板進(jìn)程互斥

S初值為1

P1

P2

P(S)P(S)

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

S1初值為n，S2初值為0

P1

P2

P(S1)

P(S2)

段1段2

V(S2)

V(S1)30經(jīng)典的進(jìn)程同步問題生產(chǎn)者/消費(fèi)者問題讀者/寫者問題哲學(xué)家進(jìn)餐問題31生產(chǎn)者/消費(fèi)者問題

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

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

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

intin=0,out=0;38生產(chǎn)者/消費(fèi)者問題(解決)Consumerj:while(1){

P(full);

P(mutex);

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

V(mutex);

V(empty);

消費(fèi)產(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)者/消費(fèi)者問題(思考)在生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程中，兩個(gè)P操作的執(zhí)行順序是否能交換？?jī)蓚€(gè)V操作的執(zhí)行順序是否能交換？40思考題

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

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

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

如果讀者來：1）無(wú)讀者、寫者，新讀者可以讀2）有寫者等，但有其它讀者正在讀，則新讀者也可以讀3）有寫者寫，新讀者等如果寫者來：1）無(wú)讀者、寫者，新寫者可以寫2）有讀者，新寫者等待3）有其它寫者，新寫者等待43讀者寫者問題的解法為實(shí)現(xiàn)讀者和寫者、寫者和寫者之間的互斥，設(shè)置一個(gè)互斥信號(hào)量Wmutex=1由于“讀—讀”允許，再設(shè)置一個(gè)整型變量Readcount表示正在讀的進(jìn)程數(shù)，初值Readcount=0由于Readcount是一個(gè)可被多個(gè)讀者進(jìn)程訪問的臨界資源，所以要為它設(shè)置一個(gè)互斥信號(hào)量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哲學(xué)家就餐問題有五個(gè)哲學(xué)家圍坐在一圓桌旁，桌中央有一盤通心粉，每人面前有一只空盤子，每?jī)扇酥g放一只筷子每個(gè)哲學(xué)家的行為是思考，感到饑餓，取筷子，然后吃通心粉，放筷子，思考。為了吃通心粉，每個(gè)哲學(xué)家必須拿到兩只筷子，并且每個(gè)人只能直接從自己的左邊或右邊去取筷子筷子是臨界資源，要用5個(gè)互斥信號(hào)量來表示這5只筷子。45哲學(xué)家就餐問題解設(shè)fork[5]為5個(gè)信號(hào)量，初值均為1struct

semaphore

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

思考；

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

進(jìn)食；

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

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