3.5進(jìn)程互斥和同步Why?How?Examples進(jìn)程間的關(guān)系互斥算法信號量(semaphore)經(jīng)典進(jìn)程同步問題管程(monitor)WindowsNT的進(jìn)程互斥和同步第三章進(jìn)程管理3.5進(jìn)程互斥和同步回顧操作系統(tǒng)的特性：并發(fā)資源共享異步性（不確定性或隨機(jī)性）虛擬性第三章進(jìn)程管理3.5進(jìn)程互斥和同步3.5.1進(jìn)程間的關(guān)系——并發(fā)執(zhí)行舉例例1：利用堆棧管理一塊內(nèi)存區(qū)中各數(shù)據(jù)塊的使用情況。用getaddr(top)從棧頂取出相應(yīng)的內(nèi)存塊的地址。用reladdr(blk)將數(shù)據(jù)（以bkl

為地址）放入堆棧中。第三章進(jìn)程管理3.5進(jìn)程互斥和同步3.5.1進(jìn)程間的關(guān)系——并發(fā)執(zhí)行舉例procgetaddr()Beginlocalr;1.1rs[top];1.2toptop+1;1.3return(r);EndProcreladdr(blk)Begin2.1toptop-1;2.2s[top]blk;EndProcessABegin

getaddr()

EndProcessBBegin

reladdr(blk)

End序號可能的執(zhí)行順序結(jié)果11.1,1.2,1.3,

2.1,2.2正確22.1,2.2,1.1,1.2,1.3正確32.1,

1.1,

2.2,

1.2,1.3錯誤41.1,

2.1,2.2，1.2,1.3

混亂第三章進(jìn)程管理3.5進(jìn)程互斥和同步3.5.1進(jìn)程間的關(guān)系——并發(fā)執(zhí)行舉例

例2：一飛機(jī)訂票系統(tǒng)，兩個終端，運(yùn)行T1、T2進(jìn)程

T1:T2:......Read(x);Read(x);y1:=x;y2:=x;ify1>=1thenify2>=1theny1:=y1-1;y2:=y2-1;x:=y1;x:=y2;write(x);write(x);......設(shè)x的當(dāng)前值為：1001.若執(zhí)行順序?yàn)椋合萒1;后T2;

則結(jié)果：x=982.若執(zhí)行順序?yàn)椋篢1:Read(x);T2:Read(x);T1:ify1>=1theny1:=y1-1;T2:ify2>=1theny2:=y2-1;T1:write(x);T2:write(x);則結(jié)果x=99分析：產(chǎn)生錯誤的原因是不加控制地訪問共享變量x第三章進(jìn)程管理3.5進(jìn)程互斥和同步3.5.1進(jìn)程間的關(guān)系——并發(fā)執(zhí)行舉例例3：與進(jìn)程的執(zhí)行順序有關(guān)的錯誤復(fù)制一個記錄

Cobeginget;copy;put;

Coend第三章進(jìn)程管理f源記錄sgettcopyg目標(biāo)記錄put3.5進(jìn)程互斥和同步3.5.1進(jìn)程間的關(guān)系——并發(fā)執(zhí)行舉例例3：與進(jìn)程的執(zhí)行順序有關(guān)的錯誤f

s

t

g

0初始狀態(tài)

3,4,...,m22(1,2)1g,c,p4,5,...,m33(1,2,3)

2g,p,c4,5,...,m33(1,2,2)X3c,g,p4,5,...,m32(1,2,2)X4c,p,g4,5,...,m32(1,2,2)X5p,c,g4,5,...,m32(1,2,2)X6p,g,c4,5,...,m33(1,2,2)X

序

初始狀態(tài)源記錄的目標(biāo)記錄結(jié)果正確性號

及執(zhí)行順序剩余部分的當(dāng)前值

注：從1到6的各個執(zhí)行，是在0（初始狀態(tài)）的基礎(chǔ)上進(jìn)行的錯誤的原因是get,copy,put過程沒有按照應(yīng)該的順序執(zhí)行第三章進(jìn)程管理3.5進(jìn)程互斥和同步3.5.1進(jìn)程間的關(guān)系——并發(fā)執(zhí)行舉例例3：與進(jìn)程的執(zhí)行順序有關(guān)的錯誤正確執(zhí)行順序第三章進(jìn)程管理cmpmc1g2p1c2g3p2g13.5進(jìn)程互斥和同步

3.5.1進(jìn)程間的關(guān)系——進(jìn)程間的交互進(jìn)程的交互關(guān)系：可以按照相互感知的程度來分類互斥:

指多個進(jìn)程不能同時使用同一個資源；死鎖:

指多個進(jìn)程互不相讓，都得不到足夠的資源；饑餓:

指一個進(jìn)程一直得不到資源（其他進(jìn)程可能輪流占用資源）。第三章進(jìn)程管理3.5進(jìn)程互斥和同步3.5.1進(jìn)程間的關(guān)系——進(jìn)程間的交互進(jìn)程間的制約關(guān)系間接制約：進(jìn)行競爭——獨(dú)占分配到的部分或全部共享資源，“互斥”。進(jìn)程間要通過某種中介發(fā)生聯(lián)系，是無意識安排的，可發(fā)生在相關(guān)進(jìn)程之間，也可發(fā)生在無關(guān)進(jìn)程之間直接制約：進(jìn)行協(xié)作——等待來自其他進(jìn)程的信息，“同步”。進(jìn)程間的相互聯(lián)系是有意識的安排的，直接作用只發(fā)生在相關(guān)進(jìn)程間第三章進(jìn)程管理3.5進(jìn)程互斥和同步3.5.1進(jìn)程間的關(guān)系——進(jìn)程間的交互進(jìn)程的互斥（間接作用）mutualexclusion由于各進(jìn)程要求共享資源，而有些資源需要互斥使用，因此各進(jìn)程間競爭使用這些資源，進(jìn)程的這種關(guān)系為進(jìn)程的互斥。臨界資源

criticalresource系統(tǒng)中某些資源一次只允許一個進(jìn)程使用，這樣的資源為臨界資源或互斥資源或共享變量。第三章進(jìn)程管理3.5進(jìn)程互斥和同步3.5.1進(jìn)程間的關(guān)系——進(jìn)程間的交互進(jìn)程的同步（直接作用）synchronism指系統(tǒng)中一些進(jìn)程需要相互合作，共同完成一項(xiàng)任務(wù)；具體說，一個進(jìn)程運(yùn)行到某一點(diǎn)時要求另一伙伴進(jìn)程為它提供消息，在未獲得消息之前，該進(jìn)程處于等待狀態(tài)，獲得消息后被喚醒進(jìn)入就緒態(tài)第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.1進(jìn)程間的關(guān)系——進(jìn)程間的交互

司機(jī)P1

售票員P2

REPEATREPEAT

啟動關(guān)門

正常運(yùn)行售票

到站停開門

UNTILFALSEUNTILFALSE

第三章進(jìn)程管理3.5進(jìn)程互斥和同步3.5.2互斥算法實(shí)現(xiàn)對共享變量的正確訪問臨界區(qū)的訪問過程使用臨界區(qū)應(yīng)遵循的準(zhǔn)則進(jìn)程互斥的軟件方法進(jìn)程互斥的硬件方法第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.2互斥算法——臨界區(qū)的訪問過程entrysectionexitsectioncriticalsectionremaindersection臨界區(qū)：進(jìn)程中訪問臨界資源的一段代碼進(jìn)入?yún)^(qū)：在進(jìn)入臨界區(qū)之前，檢查可否進(jìn)入臨界區(qū)的一段代碼。如果可以進(jìn)入臨界區(qū)，通常設(shè)置相應(yīng)“正在訪問臨界區(qū)”標(biāo)志退出區(qū)：用于將“正在訪問臨界區(qū)”標(biāo)志清除剩余區(qū)：代碼中的其余部分第三章進(jìn)程管理3.5進(jìn)程互斥和同步3.5.2互斥算法——使用臨界區(qū)應(yīng)遵循的準(zhǔn)則有空讓進(jìn)：當(dāng)無進(jìn)程在互斥區(qū)時，任何有權(quán)使用互斥區(qū)的進(jìn)程可進(jìn)入無空等待：不允許兩個以上的進(jìn)程同時進(jìn)入互斥區(qū)多中擇一：當(dāng)沒有進(jìn)程在臨界區(qū)，而同時有多個進(jìn)程要求進(jìn)入臨界區(qū)，只能讓其中之一進(jìn)入臨界區(qū)，其他進(jìn)程必須等待有限等待：任何進(jìn)入互斥區(qū)的要求應(yīng)在有限的時間內(nèi)得到滿足讓權(quán)等待：處于等待狀態(tài)的進(jìn)程應(yīng)放棄占用CPU平等競爭：任何進(jìn)程無權(quán)停止其它進(jìn)程的運(yùn)行，進(jìn)程之間相對運(yùn)行速度無硬性規(guī)定第三章進(jìn)程管理while(turn!=i);criticalsectionremaindersectioncriticalsectionremaindersection3.5進(jìn)程互斥和同步

3.5.2互斥算法——進(jìn)程互斥的軟件方法有兩個進(jìn)程Pi、Pj

算法1：單標(biāo)志turn=j;while(turn!=j);turn=i;PiPj在Pi出讓臨界區(qū)之后，Pj使用臨界區(qū)之前，Pi不可能再次使用臨界區(qū)第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.2互斥算法——進(jìn)程互斥的軟件方法算法1：單標(biāo)志設(shè)立一個公用整型變量turn：描述允許進(jìn)入臨界區(qū)的進(jìn)程標(biāo)識在進(jìn)入?yún)^(qū)循環(huán)檢查是否允許本進(jìn)程進(jìn)入：turn為i時，進(jìn)程Pi可進(jìn)入在退出區(qū)修改允許進(jìn)入進(jìn)程標(biāo)識：進(jìn)程Pi退出時，改turn為進(jìn)程Pj的標(biāo)識j缺點(diǎn)：強(qiáng)制輪流進(jìn)入臨界區(qū)，沒有考慮進(jìn)程的實(shí)際需要。容易造成資源利用不充分：在Pi出讓臨界區(qū)之后，Pj使用臨界區(qū)之前，Pi不可能再次使用臨界區(qū)。第三章進(jìn)程管理PiWhileflag<>0;flag=1;criticalsection;flag=0;remaindersection;PjWhileflag<>0;flag=1;criticalsection;flag=0;remaindersection;?第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.2互斥算法——進(jìn)程互斥的軟件方法

算法2：雙標(biāo)志、先檢查Pi:while(flag[j]);<a>flag[i]=TRUE;<b>criticalsectionflag[i]=FALSE;remaindersectionwhile(flag[i]);<a>flag[j]=TRUE;<b>criticalsectionflag[j]=FALSE;remaindersectionPj:Pi和Pj可能同時進(jìn)入臨界區(qū)第三章進(jìn)程管理3.5進(jìn)程互斥和同步3.5.2互斥算法——進(jìn)程互斥的軟件方法算法2：雙標(biāo)志、先檢查設(shè)立一個標(biāo)志數(shù)組flag[]：描述進(jìn)程是否在臨界區(qū)，初值均為FALSE。先檢查，后修改：在進(jìn)入?yún)^(qū)檢查另一個進(jìn)程是否在臨界區(qū)，不在時修改本進(jìn)程在臨界區(qū)的標(biāo)志在退出區(qū)修改本進(jìn)程在臨界區(qū)的標(biāo)志第三章進(jìn)程管理3.5進(jìn)程互斥和同步3.5.2互斥算法——進(jìn)程互斥的軟件方法算法2：雙標(biāo)志、先檢查優(yōu)點(diǎn)：不用交替進(jìn)入，可連續(xù)使用；缺點(diǎn)：Pi和Pj可能同時進(jìn)入臨界區(qū)。在Pi和Pj都不在臨界區(qū)時，假設(shè)按下面序列執(zhí)行時，會同時進(jìn)入：“Pi<a>;Pj<a>;Pi<b>;Pj<b>”。即在檢查對方flag之后和切換自己flag之前有一段時間，結(jié)果都檢查通過。這里的問題出在檢查和修改操作不能連續(xù)進(jìn)行。第三章進(jìn)程管理Pi和Pj可能都進(jìn)入不了臨界區(qū)3.5進(jìn)程互斥和同步

3.5.2互斥算法——進(jìn)程互斥的軟件方法

算法3：雙標(biāo)志、后檢查flag[j]=TRUE;<a>While(flag[i]);<b>criticalsectionflag[j]=FALSE;remaindersectionflag[i]=TRUE;<a>while(flag[j]);<b>criticalsectionflag[i]=FALSE;remaindersectionPiPj第三章進(jìn)程管理3.5進(jìn)程互斥和同步3.5.2互斥算法——進(jìn)程互斥的軟件方法算法3：雙標(biāo)志、后檢查類似于算法2，與互斥算法2的區(qū)別在于先修改后檢查?？煞乐箖蓚€進(jìn)程同時進(jìn)入臨界區(qū)。缺點(diǎn)：Pi和Pj可能都進(jìn)入不了臨界區(qū)。在Pi和Pj都不在臨界區(qū)時，假設(shè)按下面序列執(zhí)行時，會都進(jìn)不了臨界區(qū)："Pi<a>Pj<a>Pi<b>Pj<b>"。即在切換自己flag之后和檢查對方flag之前有一段時間，結(jié)果都切換flag，都檢查不通過。第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.2互斥算法——進(jìn)程互斥的軟件方法算法4(Peterson’sAlgorithm)：先修改、后檢查、后修改者等待flag[i]=TRUE;turn=j;while(flag[j]&&turn==j);criticalsectionflag[i]=FALSE;remaindersectionPi作業(yè)：分析算法4，能否出現(xiàn)算法3和算法2中的問題flag[j]=TRUE;turn=i;while(flag[i]&&turn==i);criticalsectionflag[j]=FALSE;remaindersectionPj第三章進(jìn)程管理3.5進(jìn)程互斥和同步3.5.2互斥算法——進(jìn)程互斥的軟件方法算法4(Peterson’sAlgorithm)：先修改、后檢查、后修改者等待結(jié)合算法1和算法3，是正確的算法turn=j；描述可進(jìn)入的進(jìn)程（同時修改標(biāo)志時）在進(jìn)入?yún)^(qū)先修改后檢查，并檢查并發(fā)修改的先后：檢查對方flag，如果不在臨界區(qū)則自己進(jìn)入——空閑則入；否則再檢查turn：保存的是較晚的一次賦值，則較晚的進(jìn)程等待，較早的進(jìn)程進(jìn)入——先到先入，后到等待。第三章進(jìn)程管理3.5進(jìn)程互斥和同步3.5.2互斥算法——進(jìn)程互斥的硬件方法完全利用軟件方法，有很大局限性（如不適于多進(jìn)程），現(xiàn)在已很少采用?？梢岳媚承┯布噶睢渥x寫操作由一條指令完成，因而保證讀操作與寫操作不被打斷。第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.2互斥算法——進(jìn)程互斥的硬件方法

Test-and-Set指令

TS指令該指令讀出標(biāo)志后設(shè)置為TRUE：boolean

TS(boolean*lock){

booleanold;old=*lock;*lock=TRUE;returnold;}lock表示資源的兩種狀態(tài)：TRUE表示正被占用，F(xiàn)ALSE表示空閑。Test-and-Set指令,可保證在一個指令周期內(nèi)對一個存儲單元的讀和寫。第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.2互斥算法——進(jìn)程互斥的硬件方法

Test-and-Set指令互斥算法（TS指令）whileTS(&lock);lock=FALSE;criticalsectionremaindersection相當(dāng)于測試并加鎖相當(dāng)于解鎖測試并加鎖：lock(int*lock){whileTS(&lock);}解鎖：unlock(int*lock){*lock=FALSE;}booleanTS(boolean*lock){

booleanold;old=*lock;*lock=TRUE;returnold;}第三章進(jìn)程管理3.5進(jìn)程互斥和同步3.5.2互斥算法——進(jìn)程互斥的硬件方法Test-and-Set指令互斥算法（TS指令）利用TS實(shí)現(xiàn)進(jìn)程互斥：每個臨界資源設(shè)置一個公共布爾變量lock，初值為FALSE；在進(jìn)入?yún)^(qū)利用TS進(jìn)行檢查：有進(jìn)程在臨界區(qū)時，重復(fù)檢查；直到其它進(jìn)程退出時，檢查通過。第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.2互斥算法——進(jìn)程互斥的硬件方法Swap指令（或Exchange指令）

Swap指令Swap指令（或Exchange指令）,可保證在一個指令周期內(nèi)交換一個寄存器和一個存儲單元內(nèi)容，其工作原理如下：交換兩個字（字節(jié)）的內(nèi)容voidSWAP(int*a,int*b){

inttemp;temp=*a;*a=*b;*b=temp;}第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.2互斥算法——進(jìn)程互斥的硬件方法Swap指令（或Exchange指令）互斥算法（Swap指令）利用Swap實(shí)現(xiàn)進(jìn)程互斥：每個臨界資源設(shè)置一個公共布爾變量lock，初值為FALSE。每個進(jìn)程設(shè)置一個私有布爾變量keykey=TRUE;do{

SWAP(&lock,&key);}while(key);lock=FALSE;criticalsectionremaindersectionvoidSWAP(int*a,int*b){

inttemp;temp=*a;*a=*b;*b=temp;}第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.2互斥算法——進(jìn)程互斥的硬件方法開關(guān)中斷指令互斥算法（開關(guān)中斷指令）進(jìn)入臨界區(qū)前執(zhí)行：執(zhí)行“關(guān)中斷”指令離開臨界區(qū)后執(zhí)行：執(zhí)行“開中斷”指令

特點(diǎn)：代價高，CPU只能交替執(zhí)行；不能用于多處理機(jī)結(jié)構(gòu)，因?yàn)殛P(guān)中斷只能屏蔽本機(jī)的中斷。第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.2互斥算法——進(jìn)程互斥的硬件方法硬件方法的優(yōu)點(diǎn)適用于任意數(shù)目的進(jìn)程，在單處理器或多處理器上（除中斷方法）；簡單，容易驗(yàn)證其正確性；可以支持進(jìn)程內(nèi)存在多個臨界區(qū)，只需為每個臨界區(qū)設(shè)立一個布爾變量。第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.2互斥算法——進(jìn)程互斥的硬件方法硬件方法的缺點(diǎn)等待要耗費(fèi)CPU時間，不能實(shí)現(xiàn)“讓權(quán)等待”；可能“饑餓”（不公平）：從等待進(jìn)程中隨機(jī)選擇一個進(jìn)入臨界區(qū)，有的進(jìn)程可能一直選不上；可能死鎖：進(jìn)程P1執(zhí)行TS或Exchange指令并進(jìn)入臨界區(qū)，然后P1被P2中斷并把CPU給具有更高優(yōu)先級的P2,若P2試圖使用與P1相同的資源，由于互斥機(jī)制，它被拒絕訪問，因此進(jìn)入忙等待循環(huán)，又因P2優(yōu)先級高于P1，所以P1總得不到調(diào)度執(zhí)行。第三章進(jìn)程管理3.5進(jìn)程互斥和同步3.5.3信號量(semaphore)前面的互斥算法都存在問題，它們是平等進(jìn)程間的一種協(xié)商機(jī)制，需要一個地位高于進(jìn)程的管理者來解決公有資源的使用問題；OS可從進(jìn)程管理者的角度來處理互斥的問題，信號量就是OS提供的管理公有資源的有效手段；信號量的值代表可用資源實(shí)體的數(shù)量。第三章進(jìn)程管理3.5進(jìn)程互斥和同步3.5.3信號量(semaphore)信號量和P、V原語信號量的實(shí)現(xiàn)信號量集第三章進(jìn)程管理3.5進(jìn)程互斥和同步3.5.3信號量semaphore——信號量和P、V原語1965年，由荷蘭學(xué)者Dijkstra提出（所以P、V分別是荷蘭語的test(proberen)和increment(verhogen)），是一種卓有成效的進(jìn)程同步機(jī)制。信號量：semaphore是一個數(shù)據(jù)結(jié)構(gòu)，定義如下：

typedef

struct{

intcount; Pointer_PCBQueue;}Semaphore;信號量說明：

Semaphores;第三章進(jìn)程管理3.5進(jìn)程互斥和同步3.5.3信號量semaphore

——信號量和P、V原語每個信號量s除一個整數(shù)值s.count（計數(shù)）,還有一個進(jìn)程等待隊列s.queue，其中是阻塞在該信號量的各個進(jìn)程的標(biāo)識。信號量只能通過初始化和兩個標(biāo)準(zhǔn)的原語來訪問——作為OS核心代碼執(zhí)行，不受進(jìn)程調(diào)度的打斷初始化指定一個非負(fù)整數(shù)值，表示空閑資源總數(shù)（又稱為“資源信號量”）：若為非負(fù)值表示當(dāng)前的空閑資源數(shù)，若為負(fù)值其絕對值表示當(dāng)前等待臨界區(qū)的進(jìn)程數(shù)“二進(jìn)制信號量(binarysemaphore)”：只允許信號量取0或1值第三章進(jìn)程管理3.5進(jìn)程互斥和同步3.5.3信號量semaphore——信號量和P、V原語P原語--P(s)或wait(s)

在互斥問題中，申請使用臨界資源時調(diào)用它P(Semaphores){--s.count; //表示申請一個資源;if(s.count<0) //表示沒有空閑資源;{

調(diào)用進(jìn)程進(jìn)入等待隊列s.queue;

阻塞調(diào)用進(jìn)程;}}第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.3信號量semaphore

——信號量和P、V原語V原語—V(s)或signal(s)

V原語通常喚醒進(jìn)程等待隊列中的頭一個進(jìn)程V(Semaphores){++s.count; //表示釋放一個資源；

if(s.count<=0)//表示有進(jìn)程處于阻塞狀態(tài)；

{

從等待隊列s.queue中取出一個進(jìn)程P;

進(jìn)程P進(jìn)入就緒隊列;}}

功能：釋放資源，或喚醒進(jìn)程使用時機(jī)：進(jìn)程退出臨界區(qū)之后第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.3信號量semaphore——信號量和P、V原語利用信號量實(shí)現(xiàn)互斥V(mutex);criticalsectionremaindersectionP(mutex);第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.3信號量semaphore

——信號量和P、V原語利用信號量實(shí)現(xiàn)互斥為臨界資源設(shè)置一個互斥信號量mutex(MutualExclusion)，其初值為1；在每個進(jìn)程中將臨界區(qū)代碼置于P(mutex)和V(mutex)原語之間必須成對使用P和V原語：遺漏P原語則不能保證互斥訪問，遺漏V原語則不能在使用臨界資源之后將其釋放（給其他等待的進(jìn)程）；P、V原語不能次序錯誤、重復(fù)或遺漏第三章進(jìn)程管理constintn=進(jìn)程數(shù)；Semaphores=1;

VoidProcess(inti){

while(true){

P(s);//wait(s)

<criticalsection>

V(s)//signal(s)remaindersection}}voidmain(){parbegin(Process(1),Process(2),...,Process(n));}3.5進(jìn)程互斥和同步

3.5.3信號量semaphore

——信號量和P、V原語利用信號量實(shí)現(xiàn)互斥

互斥舉例：n個進(jìn)程共用一個臨界區(qū)第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.3信號量semaphore

——信號量和P、V原語利用信號量實(shí)現(xiàn)互斥

圖示：用P.V操作解決進(jìn)程間互斥問題P1P2P3臨界區(qū)第三章進(jìn)程管理P(S)V(S)P(S)V(S)P(S)V(S)

3.5進(jìn)程互斥和同步

3.5.3信號量semaphore

——信號量和P、V原語利用信號量實(shí)現(xiàn)進(jìn)程同步

問題1：進(jìn)程Pc和Pp合作完成計算和打印任務(wù)緩沖區(qū)bufPcPp計算打印非空空放入條件=緩沖區(qū)空緩沖區(qū)buf取出結(jié)果條件=buf

非空緩沖區(qū)buf第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.3信號量semaphore

——信號量和P、V原語利用信號量實(shí)現(xiàn)進(jìn)程同步

問題1：進(jìn)程Pc和Pp合作完成計算和打印任務(wù)解：設(shè)信號量：bufempty:表示buf

空，=1

buffull:表示buf滿,=0Pc:Pp:A:P(bufempty);B:P(buffull);

計算；取出buf中的數(shù)據(jù)

buf

計算結(jié)果置空標(biāo)記，打印

V(buffull);V(bufempty);

GotoA;GotoB;--bufempty;Ifbufempty<0;++buffullIfbuffull<=0……--buffull;Ifbuffull<0;++bufemptyIfbuffull<=0……第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.3信號量semaphore

——信號量和P、V原語利用信號量實(shí)現(xiàn)進(jìn)程同步

進(jìn)程Pc和Pp合作完成計算和打印任務(wù)思考：若Pc和Pp如下Pc：

Pp：RepeatRepeat

計算；

P(buffull);

buf

計算結(jié)果取出buf中的數(shù)據(jù)

V(buffull);

置空標(biāo)記，打印

P(bufempty)

V(bufempty);UntilfalseUntilfalse則：bufempty初值為？buffull初值為？第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.3信號量semaphore

——信號量和P、V原語利用信號量實(shí)現(xiàn)進(jìn)程同步

生產(chǎn)者/消費(fèi)者問題(theproducer/consumerproblem)

問題描述：若干進(jìn)程通過有限的共享緩沖區(qū)交換數(shù)據(jù)。其中，"生產(chǎn)者"進(jìn)程不斷寫入，而"消費(fèi)者"進(jìn)程不斷讀出；共享緩沖區(qū)共有N個；任何時刻只能有一個進(jìn)程可對共享緩沖區(qū)進(jìn)行操作。緩沖區(qū)不滿，生產(chǎn)者才能寫入；緩沖區(qū)不空，消費(fèi)者才能讀出——同步互斥第三章進(jìn)程管理共享緩沖區(qū)生產(chǎn)指針消費(fèi)指針Producer1Producer2...ProducerMConsumer1Consumer2...ConsumerN滿空指針移動方向PPPCCPC同步互斥

設(shè)信號量：

full是“滿”數(shù)目，初值為0，

empty是“空”數(shù)目，初值為N。實(shí)際上，full和

empty是同一個含義：full+empty==N

mutex用于訪問緩沖區(qū)時的互斥，初值是1ProducerP(empty);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(empty);//退出區(qū)

每個進(jìn)程中各個P操作的次序是重要的：先檢查資源數(shù)目，再檢查是否互斥——否則可能死鎖(為什么？)ProducerP(empty);P(mutex);

oneunit

buffer;V(mutex);V(full);第三章進(jìn)程管理ProducerP(empty);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=5Full=0Mutex=1緩沖區(qū)等待隊列第三章進(jìn)程管理ProducerP(empty);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=5Full=0Mutex=1緩沖區(qū)生產(chǎn)者進(jìn)程生產(chǎn)一個新數(shù)據(jù)等待隊列第三章進(jìn)程管理ProducerP(empty);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=4Full=0Mutex=1緩沖區(qū)生產(chǎn)者進(jìn)程測試一個“empty”等待隊列第三章進(jìn)程管理ProducerP(empty);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=4Full=0Mutex=0緩沖區(qū)生產(chǎn)者進(jìn)程測試臨界區(qū)等待隊列第三章進(jìn)程管理ProducerP(empty);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=4Full=0Mutex=0緩沖區(qū)生產(chǎn)者進(jìn)程將數(shù)據(jù)放入緩沖區(qū)等待隊列第三章進(jìn)程管理ProducerP(empty);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=4Full=0Mutex=1緩沖區(qū)生產(chǎn)者進(jìn)程釋放臨界區(qū)等待隊列第三章進(jìn)程管理ProducerP(empty);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=4Full=1Mutex=1緩沖區(qū)生產(chǎn)者進(jìn)程釋放一個“full”等待隊列第三章進(jìn)程管理ProducerP(empty);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=0Full=5Mutex=1緩沖區(qū)重復(fù)4次…等待隊列第三章進(jìn)程管理ProducerP(empty);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=0Full=5Mutex=1緩沖區(qū)生產(chǎn)者進(jìn)程又生產(chǎn)一個新數(shù)據(jù)…等待隊列第三章進(jìn)程管理ProducerP(empty);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=-1Full=5Mutex=1緩沖區(qū)生產(chǎn)者進(jìn)程測試一個“empty”等待隊列P1第三章進(jìn)程管理ProducerP(empty);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=-1Full=4Mutex=1緩沖區(qū)消費(fèi)者進(jìn)程測試一個“full”等待隊列P1第三章進(jìn)程管理ProducerP(empty);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=-1Full=4Mutex=0緩沖區(qū)消費(fèi)者進(jìn)程測試臨界區(qū)等待隊列P1第三章進(jìn)程管理ProducerP(empty);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=-1Full=4Mutex=0緩沖區(qū)消費(fèi)者進(jìn)程從緩沖區(qū)獲得一個數(shù)據(jù)等待隊列P1第三章進(jìn)程管理ProducerP(empty);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=-1Full=4Mutex=1緩沖區(qū)消費(fèi)者進(jìn)程釋放臨界區(qū)等待隊列P1第三章進(jìn)程管理ProducerP(empty);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=0Full=4Mutex=1緩沖區(qū)消費(fèi)者進(jìn)程釋放一個“empty”等待隊列P1第三章進(jìn)程管理ProducerP(empty);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=0Full=4Mutex=0緩沖區(qū)生產(chǎn)者進(jìn)程測試臨界區(qū)等待隊列第三章進(jìn)程管理ProducerP(empty);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=0Full=4Mutex=0緩沖區(qū)生產(chǎn)者進(jìn)程將一個數(shù)據(jù)放入緩沖區(qū)等待隊列第三章進(jìn)程管理ProducerP(empty);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=0Full=4Mutex=0緩沖區(qū)生產(chǎn)者與生產(chǎn)者互斥消費(fèi)者與消費(fèi)者互斥生產(chǎn)者與消費(fèi)者同步作業(yè)：以該圖為基礎(chǔ)，寫（畫）出緩沖區(qū)已空時，①一個消費(fèi)者進(jìn)程執(zhí)行P(full)后；②又一個消費(fèi)者進(jìn)程執(zhí)行P(full)后；③一個生產(chǎn)者進(jìn)程執(zhí)行V(full)后；各變量的值及等待隊列的情況。第三章進(jìn)程管理操作的順序很重要，不當(dāng)會產(chǎn)生死鎖。如假定Producer和Consumer如下：Consumer：Producer：P(empty);P(mutex);

oneunit

buf;V(mutex);V(full);P(full);P(mutex);//進(jìn)入?yún)^(qū)

oneunit

buf;V(mutex);V(empty);//退出區(qū)當(dāng)full=0,mutex=1時，執(zhí)行順序：

Consumer.P(mutex);Consumer.P(full);//C阻塞，等待Producer發(fā)出的full信號

Producer.P(empty);Producer.P(mutex);//P阻塞，等待Consumer發(fā)出的empty信號死鎖，還有其他的執(zhí)行序列可以產(chǎn)生死鎖嗎？第三章進(jìn)程管理思考與作業(yè)：上述的生產(chǎn)者和消費(fèi)者之間是互斥的，生產(chǎn)者與生產(chǎn)者之間以及消費(fèi)者與消費(fèi)者之間也是互斥的，是否可以實(shí)現(xiàn)生產(chǎn)者和消費(fèi)者之間的并行？如何實(shí)現(xiàn)？用P.V操作解決司機(jī)與售票員的問題3.用P.V操作解決下圖之同步問題:第三章進(jìn)程管理f源記錄sgettcopyg目標(biāo)記錄put3.5進(jìn)程互斥和同步

3.5.3信號量semaphore——信號量P、V操作的實(shí)現(xiàn)S初始值為1P(s)臨界區(qū)V(s)P(s)臨界區(qū)V(s)互斥S1初始值n，s2初始值0P(s1)臨界區(qū)1V(s2)P(s2)臨界區(qū)2V(s1)同步第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.3信號量semaphore——信號量P、V操作的實(shí)現(xiàn)P(s)BEGIN

封鎖中斷

lock(lockbit);--s.count; //表示申請一個資源;if(s.count<0) //表示沒有空閑資源;{調(diào)用進(jìn)程進(jìn)入等待隊列s.queue;

阻塞調(diào)用進(jìn)程;}

unlock(lockbit)

開放中斷

END;第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.3信號量semaphore——信號量P、V操作的實(shí)現(xiàn)V(s)BEGIN

封鎖中斷

lock(lockbit);++s.count; if(s.count<=0){從等待隊列s.queue中取出一個進(jìn)程P;進(jìn)程P進(jìn)入就緒隊列;}

unlock(lockbit);

開放中斷

END;第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.4經(jīng)典進(jìn)程同步問題——

讀者－寫者問題（thereaders-writersproblem）問題描述：對共享資源的讀寫操作，任一時刻“寫者”最多只允許一個，而“讀者”則允許多個“讀－寫”互斥，“寫－寫”互斥，“讀－讀”允許第三章進(jìn)程管理情景3：無讀者、寫者情景2：一個寫者情景1：若干讀者…思路：進(jìn)入臨界區(qū)阻塞阻塞寫者阻塞阻塞進(jìn)入阻塞讀者、寫者可以讀可以讀，阻止寫

可以寫，阻止讀、寫判斷讀者數(shù)量：>0讀者加1；=0判斷可讀否，可則讀者加1判斷可寫否，可則寫第一個讀者判斷是否有寫者第三章進(jìn)程管理思路：退出臨界區(qū)情景1：若干讀者…讀者數(shù)量減1情景2：只剩下一個讀者讀者數(shù)量減1，釋放寫者情景3：一個寫者釋放寫者最后一個讀者釋放寫者第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.4經(jīng)典進(jìn)程同步問題——

讀者－寫者問題（thereaders-writersproblem）分析采用信號量機(jī)制：Wmutex表示“允許寫”，初值是1。公共變量Rcount表示“正在讀”的進(jìn)程數(shù)，初值是0；

Rmutex表示對Rcount的互斥操作，初值是1。只要一個reader進(jìn)程在讀，便不允許writer進(jìn)程去寫。僅當(dāng)Rcount=0，reader進(jìn)程才需要執(zhí)行P(Wmutex)操作僅當(dāng)reader進(jìn)程執(zhí)行了Rcount減1操作后其值為0時，才須執(zhí)行V(Wmutex)操作第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.4經(jīng)典進(jìn)程同步問題——讀者－寫者問題thereaders-writersproblemP(Rmutex);if(Rcount==0)P(Wmutex);++Rcount;V(Rmutex);read;P(Rmutex);--Rcount;if(Rcount==0)V(Wmutex);V(Rmutex);ReaderP(Wmutex);

write;V(Wmutex);Writer第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.4典進(jìn)程同步問題——哲學(xué)家進(jìn)餐問題thediningphilosophersproblem

5個哲學(xué)家圍繞一張圓桌而坐，桌子上放著5支筷子，每兩個哲學(xué)家之間放一支；哲學(xué)家的動作包括思考和進(jìn)餐，進(jìn)餐時需要同時拿起他左邊和右邊的兩支筷子，思考時則同時將兩支筷子放回原處。

問題描述：（由Dijkstra首先提出并解決）第三章進(jìn)程管理考慮問題：如何保證哲學(xué)家們的動作有序進(jìn)行？如：

不出現(xiàn)相鄰者同時要求進(jìn)餐；不出現(xiàn)有人永遠(yuǎn)拿不到筷子；哲學(xué)家的生活規(guī)律3.5進(jìn)程互斥和同步

3.5.4經(jīng)典進(jìn)程同步問題——哲學(xué)家進(jìn)餐問題thediningphilosophersproblemRepeat

思考；取fork[i];取fork[(i+1)mod5]；進(jìn)食；

放fork[i];放fork[(i+1)mod5]；Untilfalse;第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.4經(jīng)典進(jìn)程同步問題——哲學(xué)家進(jìn)餐問題thediningphilosophersproblem一個信號量表示一根筷子，五個信號量構(gòu)成信號量組chop[5]，所有信號量初始值為1。第i個哲學(xué)家的進(jìn)餐過程為：思考問題P(chop[i]);P(chop[(i+1)mod5]);進(jìn)餐V(chop[i]);V(chop[(i+1)mod5]);該算法可保證兩個相鄰的哲學(xué)家不能同時進(jìn)餐，但不能防止五位哲學(xué)家同時拿起各自左邊的筷子、又試圖拿起右邊的筷子，這會引起死鎖第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.4經(jīng)典進(jìn)程同步問題——哲學(xué)家進(jìn)餐問題thediningphilosophersproblem

為防止死鎖發(fā)生可采取的措施最多允許4個哲學(xué)家同時坐在桌子周圍（

）；僅當(dāng)一個哲學(xué)家左右兩邊的筷子都可用時，才允許他拿筷子（

）；給所有哲學(xué)家編號，奇數(shù)號的哲學(xué)家必須首先拿左邊的筷子，偶數(shù)號的哲學(xué)家則反之；為了避免死鎖，把哲學(xué)家分為三種狀態(tài)，思考，饑餓，進(jìn)食，并且一次拿到兩只筷子，否則不拿。第三章進(jìn)程管理

ProgramdiningphilosophersSemaphorefork[5]={1};Semaphoreroom=4;inti;Voidphilospher(inti){while(true){thinking();P(room);P(fork[i]);P(fork[(i+1)mod5])eating();V(fork[i]);V(fork[(i+1)mod5])V(room);}}第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.4經(jīng)典進(jìn)程同步問題——作業(yè)分析前面描述的讀者/寫者問題，說明對讀者和寫者是否公平？第二類讀者寫者問題(并分析對讀者和寫者是否公平)，條件：多個讀者可以同時進(jìn)行讀；寫者必須互斥（只允許一個寫者寫，也不能讀者、寫者同時進(jìn)行）；寫者優(yōu)先于讀者（一旦有寫者，則后續(xù)讀者必須等待，喚醒時優(yōu)先考慮寫者）。給出對讀者/寫者都公平的關(guān)于讀者寫者問題的描述第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.4經(jīng)典進(jìn)程同步問題——作業(yè)

變量設(shè)置:state:array[0..4]of(思考，饑餓，進(jìn)食）；

ph:array[0..4]ofsemaphore;

mutex:semaphore;

i:0..4;哲學(xué)家就餐問題的另一種解法，請分析其實(shí)現(xiàn)互斥的過程:第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.4經(jīng)典進(jìn)程同步問題——作業(yè)哲學(xué)家就餐問題的另一種解法，請分析其實(shí)現(xiàn)互斥的過程:Proceduretest(i:=0…4);beginif(state[i]=饑餓)And(state[(i-1)mod5]<>進(jìn)食)And(state[(i+1)mod5]<>進(jìn)食)thenbegin

state[i]=進(jìn)食

V(ph[i])end

end第三章進(jìn)程管理Procedurephilosopher(i:0～4)BeginRepeat

思考；

state[i]:=饑餓；

P(mutex);test(i);

V(mutex);P(ph[i]);

拿左筷子；拿右筷子；進(jìn)食；放左筷子；放右筷子；

P(mutex)

state[i]:=思考；test([i-1]mod5);tset([i+1]mod5);

V(mutex);untilfalesEnd

初始值：

state[i]=思考

ph[i]=0

Mutex=1第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.5信號量集

用于同時需要多個資源時的信號量操作AND型信號量集一般信號量集第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.5信號量集——AND型信號量集用于同時需要多種資源且每種占用一個時的信號量操作一段處理代碼需要同時獲取兩個或多個臨界資源——可能死鎖：各進(jìn)程分別獲得部分臨界資源，然后等待其余的臨界資源，“各不相讓”ProcessA:

P(Dmutex);

P(Emutex);ProcessB:

P(Emutex);

P(Dmutex);第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.5信號量集——AND型信號量集基本思想：將一段代碼同時需要的多個臨界資源，要么全部分配給它，要么一個都不分配Swait(S1,S2,…,Sn){while(true){if(S1>=1&&S2>=1&&…&&Sn>=1){for(i=1;i<=n;++i)--Si;break;}else{

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

阻塞調(diào)用進(jìn)程；

}}}SP第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.5信號量集——AND型信號量集基本思想：將一段代碼同時需要的多個臨界資源，要么全部分配給它，要么一個都不分配Ssignal(S1,S2,…,Sn){for(i=1;i<=n;++i){++Si;for(eachprocessPwaitinginSi.queue){

從等待隊列Sj.queue中取出進(jìn)程P;if(進(jìn)程P通過Swait中的測試)

進(jìn)程P進(jìn)入就緒隊列

else

進(jìn)程P進(jìn)入某等待隊列；

}}}SV第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.5信號量集——一般信號量集用于同時需要多種資源、每種占用的數(shù)目不同、且可分配的資源還存在一個臨界值時的處理；基本思想：在AND型信號量集的基礎(chǔ)上進(jìn)行擴(kuò)充：進(jìn)程對信號量Si的測試值為ti，占用值為diSwait(S1，t1，d1；…；Sn，tn，dn)(或SP)Ssignal(S1，d1；…；Sn，dn)(或SV)第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.5信號量集——一般信號量集Swait(S1，t1，d1；…；Sn，tn，dn)(或SP)If(s1>=t1ands2>=t2and…and

sn>=tn)thenFori=1tondosi:=si-diElse阻塞進(jìn)程；Ssignal(S1，d1；…；Sn，dn)(或SV)Fori=1tondoBegin

si:=si+di;Forall被阻塞的Pido喚醒進(jìn)程；End；第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.5信號量集——一般信號量集一般信號量集的幾種特定情況Swait(S,d,d)表示每次申請d個資源，當(dāng)少于d個時，便不分配SP(S,d,d)Swait(S,1,1)表示一般的記錄型信號量或互斥信號量SP(S,1,1)Swait(S,1,0)作為一個可控開關(guān)SP(S,1,0)當(dāng)S>=1時，允許多個進(jìn)程進(jìn)入臨界區(qū)當(dāng)S=0時，禁止任何進(jìn)程進(jìn)入臨界區(qū)第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.5信號量集——應(yīng)用利用AND信號量解決生產(chǎn)者——消費(fèi)者問題用SP(empty,mutex)代替P(empty)和P(mutex)，用SV(mutex,full)代替V(mutex)和V(full)消費(fèi)者：

SP(full,mutex)Oneunitbuffer

SV(mutex,empty)生產(chǎn)者：

SP(empty,mutex)Oneunitbuffer

SV(mutex,full)第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.5信號量集——應(yīng)用利用一般信號量集解決讀者——寫者問題增加一個限制，即最多允許RN個讀者同時讀。為此引入一信號量L，其初值為RN。讀者：

SP(L,1,1;mx,1,0)readSV(L,1)寫者：

SP(mx,1,1;L,RN,0)writeSV(mx,1)第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.5信號量集——應(yīng)用利用一般信號量集解決三個工人加工自行車問題Empty=N，s1=N-2，s2=N-1。工人1：加工一個車架；

SP(s1,1,1;empty,1,1);

車架放入箱中;SV(frame,1);工人2：加工一個車輪;SP(s2,1,1;empty,1,1);

車輪放入箱中;SV(wheel,1);工人3：

SP(frame,1,1;wheel,2,2);

取1個車架2個車輪;SV(empty,3;s1,1;s2,2);

加工一輛自行車;第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.6利用信號量實(shí)現(xiàn)前趨關(guān)系——前趨圖前趨圖是一個有向無循環(huán)圖，用于描述進(jìn)程之間執(zhí)行的前后關(guān)系；每個結(jié)點(diǎn)表示一個進(jìn)程、程序段或一條語句；結(jié)點(diǎn)間的有向邊表示兩結(jié)點(diǎn)間存在的偏序或前趨關(guān)系；Pi→PjPi是Pj的直接前趨，Pj是Pi的直接后繼，表示在Pj可能開始執(zhí)行前Pi必須執(zhí)行完成；給圖寫出所有的前趨關(guān)系。PiPj第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.6利用信號量實(shí)現(xiàn)前趨關(guān)系——前趨圖

P1→P2,P1→P3,P1→P4,P2→P5,P3→P5,P4→P6,P4→P7,P5→P8,P6→P8,P7→P9,P8→P9S1S2S3前趨圖中不能存在循環(huán)×P1P3P2P5P8P4P7P6P9第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.6利用信號量實(shí)現(xiàn)前趨關(guān)系S1S2進(jìn)程P1：…S1…進(jìn)程P2：…S2…若希望在S1執(zhí)行后再執(zhí)行S2，只需使進(jìn)程P1和P2共享一個公用信號量S，并賦初值0進(jìn)程P1：…S1；V(S)；…進(jìn)程P2：…P(S)；S2…第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.6利用信號量實(shí)現(xiàn)前趨關(guān)系Vara2,a3,a4,a5,a63,a64,a65:=semaphore:=0,0,0,0,0,0,0;Begin

ParbeginBeginS1;V(a2);V(a3);EndBeginP(a2);S2;V(a4);V(a5);EndBeginP(a3);S3;V(a63);EndBeginP(a4);S4;V(a64);EndBeginP(a5);S5;V(a65);EndBeginP(a63);P(a64);P(a65);S6;End

ParendEndS1S2S4S5S6S3a2a3a5a4a63a65a64第三章進(jìn)程管理3.5進(jìn)程互斥和同步

3.5.7管程(monitor)——信號量同步的缺點(diǎn)同步操作分散：信號量機(jī)制中，同步操作分散在各個進(jìn)程中，使用