操作系統(tǒng)教程第5版第3章【PV】

第4章同步、通信與死鎖主要內(nèi)容并發(fā)進(jìn)程臨界區(qū)管理信號量與PV操作管程進(jìn)程通信死鎖14.1并發(fā)進(jìn)程4.1.1順序程序設(shè)計4.1.2進(jìn)程的并發(fā)性4.1.3進(jìn)程的交互：協(xié)作和競爭24.1.1順序程序設(shè)計進(jìn)程的順序性一個進(jìn)程在順序處理器上的執(zhí)行是嚴(yán)格按序的，一個進(jìn)程只有當(dāng)一個操作結(jié)束后，才能開始后繼操作。順序程序設(shè)計是把一個程序設(shè)計成一個順序執(zhí)行的程序模塊，順序的含義不但指一個程序模塊內(nèi)部，也指兩個程序模塊之間。3順序程序設(shè)計特點程序執(zhí)行的順序性程序環(huán)境的封閉性程序執(zhí)行結(jié)果的確定性計算過程的可再現(xiàn)性順序程序設(shè)計的缺點：計算機(jī)系統(tǒng)效率不高。44.1.2進(jìn)程的并發(fā)性1、并發(fā)程序設(shè)計進(jìn)程執(zhí)行的并發(fā)性：一組進(jìn)程的執(zhí)行在時間上是重疊的。并發(fā)性舉例：有兩個進(jìn)程A(a1、a2、a3)和B(b1、b2、b3)并發(fā)執(zhí)行。

a1、a2、a3、b1、b2、b3順序執(zhí)行

a1、b1、a2、b2、a3、b3并發(fā)執(zhí)行從宏觀上看，并發(fā)性反映一個時間段中幾個進(jìn)程都在同一處理器上，處于運(yùn)行還未運(yùn)行結(jié)束狀態(tài)。從微觀上看，任一時刻僅有一個進(jìn)程在處理器上運(yùn)行。5并行工作圖示進(jìn)程i1p1ipoo1i2p2o2i3p3o3t1t2t3時間并行工作i4t4i5P4t56并發(fā)的實質(zhì)并發(fā)的實質(zhì)是一個處理器在幾個進(jìn)程之間的多路復(fù)用，并發(fā)是對有限的物理資源強(qiáng)制行使多用戶共享，消除計算機(jī)部件之間的互等現(xiàn)象，以提高系統(tǒng)資源利用率。73、與時間有關(guān)的錯誤對于一組交往的并發(fā)進(jìn)程，執(zhí)行的相對速度無法相互控制，各種與時間有關(guān)的錯誤就可能出現(xiàn)。與時間有關(guān)錯誤的表現(xiàn)形式：結(jié)果不唯一永遠(yuǎn)等待83、與時間有關(guān)的錯誤（例子1）T1： …

read(x) ifx>=1000then x=x-1000write(x)…9T2： …

read(x) ifx>=2000then x=x-2000write(x)…某銀行業(yè)務(wù)系統(tǒng)，某客戶的賬戶有5000元，有兩個ATM機(jī)T1，T23、與時間有關(guān)的錯誤（例子2）10get、copy、put三個進(jìn)程并發(fā)執(zhí)行S緩沖區(qū)t緩沖區(qū)f緩沖區(qū)g緩沖區(qū)getcopyput（1）get把數(shù)據(jù)讀入s，但s中數(shù)據(jù)還未被copy取走，第二次get過來的進(jìn)程將s中數(shù)據(jù)覆蓋。（2）若put進(jìn)程先執(zhí)行，但t中數(shù)據(jù)未準(zhǔn)備好，可能將不需要的數(shù)據(jù)取走。11Stfggetcopyput當(dāng)前狀態(tài)fstg正誤（3，4，…,m）22(1,2)執(zhí)行順序假設(shè)g，c，p為getcopyput的一次循環(huán)g

c

p（4，5，…，m）33（1,2,3）√g

p

c（4，5，…，m）33（1,2,2）╳c

g

p（4，5，…，m）32（1,2,2）╳c

p

g（4，5，…，m）32（1,2,2）╳p

c

g（4，5，…，m）32（1,2,2）╳p

g

c（4，5，…，m）33（1,2,2）╳并發(fā)執(zhí)行分析12進(jìn)程前驅(qū)圖g1c1p1g2c2p2g3cipi…并發(fā)環(huán)境下進(jìn)程間的制約關(guān)系兩者先后順序任意Stfggetcopyput3、與時間有關(guān)的錯誤（例子3）//飛機(jī)票售票問題voidT1(){voidT2(){{按旅客訂票要求找到Aj};{按旅客訂票要求找到Aj};intX1=Aj;intX2=Aj;if(X1>=1){if(X2>=1){

X1--;

X2--; Aj=X1; Aj=X2; {輸出一張票};{輸出一張票};}}elseelse{輸出信息"票已售完"};{輸出信息"票已售完"};}}13T1、T2并發(fā)執(zhí)行，可能出現(xiàn)如下交叉情況：T1:X1=Aj;//X1=mT2:X2=Aj;//X2=mT2:X2--;Aj=X2;{輸出一張票};//Aj=m-1T1:X1--;Aj=X1;{輸出一張票};//Aj=m-1同一張票賣給兩位旅客143、與時間有關(guān)的錯誤（例子3）（永遠(yuǎn)等待）主存管理問題申請和歸還主存資源問題intX=memory;//memory為初始主存容量void

borrow(intB){voidreturn(intB){while(B>X)X=X+B;{進(jìn)程進(jìn)入等待主存資源隊列};{修改主存分配表};X=X-B;{釋放等主存資源進(jìn)程};{修改主存分配表，進(jìn)程獲得主存資源};}}153、與時間有關(guān)的錯誤（例子4）122若對borrow和return的并發(fā)執(zhí)行不加限制將會導(dǎo)致錯誤，例如：Borrow:while(B>X);Return:X=X+B;{修改主存分配表};{釋放等待主存資源的進(jìn)程}；此時，因為borrow還沒有進(jìn)入等待隊列，因此，return的釋放操作是空操作，當(dāng)borrow進(jìn)入等待隊列時，可能沒有進(jìn)程再來歸還，處于永遠(yuǎn)等待狀態(tài)。163、與時間有關(guān)的錯誤（例子4）3.1.3進(jìn)程的交互：競爭與協(xié)作(1)

第一種是競爭關(guān)系進(jìn)程互斥：若干個進(jìn)程因相互爭奪獨(dú)占型資源時所產(chǎn)生的競爭制約關(guān)系。資源競爭的兩個控制問題：一個是死鎖(Deadlock)問題，一個是饑餓(Starvation)問題

既要解決饑餓問題，又要解決死鎖問題。17進(jìn)程的交往：競爭與協(xié)作(2)

第二種是協(xié)作關(guān)系進(jìn)程同步：為完成共同任務(wù)的并發(fā)進(jìn)程基于某個條件來協(xié)調(diào)它們的活動，因為需要在某些位置上排定執(zhí)行的先后次序而等待、傳遞信號或消息所產(chǎn)生的協(xié)作制約關(guān)系。進(jìn)程互斥關(guān)系是一種特殊的進(jìn)程同步關(guān)系，即逐次使用互斥共享資源，是對進(jìn)程使用資源次序上的一種協(xié)調(diào)。184.2臨界區(qū)管理4.2.1互斥與臨界區(qū)4.2.2實現(xiàn)臨界區(qū)管理的幾種嘗試4.2.3實現(xiàn)臨界區(qū)管理的軟件方法4.2.4實現(xiàn)臨界區(qū)管理的硬件設(shè)施1920競爭條件（空閑區(qū)域7）打印目錄…4abc5Prog.c6Hi.c7out=4in=7ProcessAProcessB進(jìn)程A和B都申請把要打印的文件名放入7，然后打印21競爭條件（空閑區(qū)域7）打印目錄…4abc5Prog.c6Hi.c7out=4in=7ProcessAProcessB進(jìn)程A讀取到in=7，將文件名放入7，即將修改in時，進(jìn)程A被切換下CPU，進(jìn)程B上CPU。22打印目錄…4abc5Prog.c6Hi.c7out=4in=7ProcessAProcessB進(jìn)程B讀取到in=7，將文件名放入7，修改in=8結(jié)果：進(jìn)程A中文件未能打印，因為被進(jìn)程B覆蓋了。競爭條件（空閑區(qū)域7）4.2.1互斥與臨界區(qū)(1)并發(fā)進(jìn)程中，與共享變量有關(guān)的程序段叫“臨界區(qū)”，共享變量代表的資源叫“臨界資源”。與同一變量有關(guān)的臨界區(qū)分散在各進(jìn)程的程序段中，而各進(jìn)程的執(zhí)行速度不可預(yù)知。如果保證進(jìn)程在臨界區(qū)執(zhí)行時，不讓另一個進(jìn)程進(jìn)入臨界區(qū)，即各進(jìn)程對共享變量的訪問是互斥的，就不會造成與時間有關(guān)的錯誤。2324競爭互斥由于各個進(jìn)程要求使用共享資源（變量、文件）而這些資源需要排他性使用，各進(jìn)程之間競爭使用這些資源——這一關(guān)系稱為進(jìn)程互斥臨界資源系統(tǒng)中某些資源一次只允許一個進(jìn)程使用，稱這樣的資源為臨界資源或互斥資源或共享變量臨界區(qū)（互斥區(qū)）各個進(jìn)程對某個臨界資源（共享變量）實施操作的程序片段互斥與臨界區(qū)(2)臨界區(qū)調(diào)度原則：一次至多一個進(jìn)程能夠進(jìn)入臨界區(qū)內(nèi)執(zhí)行；如果已有進(jìn)程在臨界區(qū)，其他試圖進(jìn)入的進(jìn)程應(yīng)等待；進(jìn)入臨界區(qū)內(nèi)的進(jìn)程應(yīng)在有限時間內(nèi)退出，以便讓等待進(jìn)程中的一個進(jìn)入。臨界區(qū)調(diào)度原則總結(jié)：互斥使用、有空讓進(jìn)；忙則等待、有限等待；擇一而入，算法可行。2526臨界區(qū)（互斥區(qū)）的使用原則B要進(jìn)入臨界區(qū)被阻塞B進(jìn)入臨界區(qū)t1t2t3t4A進(jìn)入臨界區(qū)A出臨界區(qū)進(jìn)程A進(jìn)程B時間（1）若沒有進(jìn)程在臨界區(qū)，想進(jìn)入臨界區(qū)的進(jìn)程可進(jìn)入（2）不允許兩個進(jìn)程同時處于其臨界區(qū)（3）臨界區(qū)外運(yùn)行的進(jìn)程不能阻塞其他進(jìn)程進(jìn)入臨界區(qū)（4）不得使進(jìn)程無限期等待進(jìn)入臨界區(qū)軟件方案Dekker解法、Peterson解法硬件方案屏蔽中斷、TSL（XCHG）指令27實現(xiàn)進(jìn)程互斥的方法28軟件方法1P：……while(free);free=true;臨界區(qū)free=false；……Q：……while(free);free=true;臨界區(qū)free=false；……1CPUStep1:P先上CPUfree:臨界區(qū)空閑標(biāo)志true:有進(jìn)程在臨界區(qū)；false:無進(jìn)程在臨界區(qū)初值：free為false29軟件方法1P：……while(free);free=true;臨界區(qū)free=false；……Q：……while(free);free=true;臨界區(qū)free=false；……1CPUStep2:P下CPU，Q上CPU2CPUfree:臨界區(qū)空閑標(biāo)志true:有進(jìn)程在臨界區(qū)；false:無進(jìn)程在臨界區(qū)初值：free為false30軟件方法1P：……while(free);free=true;臨界區(qū)free=false；……Q：……while(free);free=true;臨界區(qū)free=false；……1CPUStep3:Q下CPU，P上CPU；此時兩個進(jìn)程都在臨界區(qū)！該方法有問題。2CPU3free:臨界區(qū)空閑標(biāo)志true:有進(jìn)程在臨界區(qū)；false:無進(jìn)程在臨界區(qū)初值：free為false31軟件方法1P：……while(free);free=true;臨界區(qū)free=false；……Q：……while(free);free=true;臨界區(qū)free=false；……free:臨界區(qū)空閑標(biāo)志true:有進(jìn)程在臨界區(qū)；false:無進(jìn)程在臨界區(qū)初值：free為false改進(jìn)方法:設(shè)置原語lock()unlock()32軟件方法2P：……while(notturn);臨界區(qū)turn=false；……Q：……while(turn);臨界區(qū)turn=ture；……turn：誰進(jìn)臨界區(qū)的標(biāo)志

true:P進(jìn)程進(jìn)臨界區(qū)；false:Q進(jìn)程進(jìn)臨界區(qū)初值任意若P想進(jìn)臨界區(qū)，由于turn=false；進(jìn)不了；同時Q進(jìn)程始終不準(zhǔn)備進(jìn)臨界區(qū)，即使臨界區(qū)一直沒有進(jìn)程，但P一直無法進(jìn)入臨界區(qū)該方法，違反了使用臨界區(qū)的原則33軟件方法3P：……pturn=ture;while(qturn);臨界區(qū)pturn=false；……Q：……qturn=ture;while(pturn);臨界區(qū)qturn=false；……pturn,qturn的初值為falseP進(jìn)入臨界區(qū)的條件：pturn

^notqturn（與）Q進(jìn)入臨界區(qū)的條件：notpturn^

qturn（與）Step1:p執(zhí)行到pturn=ture，被撤下CPU1CPU34軟件方法3P：……pturn=ture;while(qturn);臨界區(qū)pturn=false；……Q：……qturn=ture;while(pturn);臨界區(qū)qturn=false；……pturn,qturn的初值為falseP進(jìn)入臨界區(qū)的條件：pturn^notqturnQ進(jìn)入臨界區(qū)的條件：notpturn^qturnStep2:Q進(jìn)程上CPU執(zhí)行到qturn=ture1CPU2CPU35軟件方法3P：……pturn=ture;while(qturn);臨界區(qū)pturn=false；……Q：……qturn=ture;while(pturn);臨界區(qū)qturn=false；……pturn,qturn的初值為falseP進(jìn)入臨界區(qū)的條件：pturn^notqturnQ進(jìn)入臨界區(qū)的條件：notpturn^qturnStep3:Q進(jìn)程上一直測試pturn，無法通過，始終不能進(jìn)入臨界區(qū)1CPU2CPU3此處不斷循環(huán)36軟件方法3P：……pturn=ture;while(qturn);臨界區(qū)pturn=false；……Q：……qturn=ture;while(pturn);臨界區(qū)qturn=false；……pturn,qturn的初值為falseP進(jìn)入臨界區(qū)的條件：pturn^notqturnQ進(jìn)入臨界區(qū)的條件：notpturn^qturnStep3:時間片結(jié)束，Q進(jìn)程被撤下CPU，P進(jìn)程上CPU，一直測試qturn，無法通過，始終不能進(jìn)入臨界區(qū)P進(jìn)程和Q進(jìn)程都無法進(jìn)入空閑著的臨界區(qū)（該方法不滿足臨界區(qū)的使用原則）1CPU2CPU3437軟件方法4dekker算法對解法3的改進(jìn)1965年第一個用軟件的方法解決了臨界區(qū)保護(hù)問題P：……pturn=ture;while(qturn){ if(turn==2){ pturn=false; while(turn==2); pturn=turn； }}臨界區(qū)turn=2;pturn=false；……Q：……qturn=ture;while(pturn){ if(turn==2){ qturn=false; while(turn==1); qturn=turn； }}臨界區(qū)turn=1;qturn=false；……引入turn變量：turn=1P上cpu；turn=2Q上cpu38P：……pturn=ture;while(qturn){ if(turn==2){ pturn=false; while(turn==2); pturn=turn； }}臨界區(qū)turn=2;pturn=false；……Q：……qturn=ture;while(pturn){ if(turn==1){ qturn=false; while(turn==1); qturn=turn； }}臨界區(qū)turn=2;qturn=false；……1CPU2CPUStep1:P上CPUStep2：P被撤下CPU，Q上CPU39P：……pturn=ture;while(qturn){ if(turn==2){ pturn=false; while(turn==2); pturn=turn； }}臨界區(qū)turn=2;pturn=false；……Q：……qturn=ture;while(pturn){ if(turn==1){ qturn=false; while(turn==1); qturn=turn； }}臨界區(qū)turn=2;qturn=false；……1CPU2CPU此時pturn=ture，qturn=true；根據(jù)turn的值決定誰進(jìn)CPU340P：……pturn=ture;while(qturn){ if(turn==2){ pturn=false; while(turn==2); pturn=turn； }}臨界區(qū)turn=2;pturn=false；……Q：……qturn=ture;while(pturn){ if(turn==1){ qturn=false; while(turn==1); qturn=turn； }}臨界區(qū)turn=2;qturn=false；……1CPU2CPUStep3:根據(jù)turn的值，判斷誰進(jìn)臨界區(qū)，Q將自己的qturn設(shè)為false，讓P進(jìn)入臨界區(qū)，并用while一直查詢turn是否=1，即輪到Q進(jìn)入臨界區(qū)3441軟件方法5peterson算法進(jìn)程i：…enter_region(i);//進(jìn)程想進(jìn)臨界區(qū)調(diào)用該函數(shù)，看是否能 //安全進(jìn)入，i是進(jìn)程號;臨界區(qū)；lever_region（i）

;//進(jìn)程離開臨界區(qū)調(diào)用該函數(shù)，Peterson算法解決了互斥訪問的問題，而且克服了（Dekker算法）強(qiáng)制輪流法的缺點，可以完全正常的工作42軟件方法5peterson算法#defineFALSE0#defineTRUE1#defineN2//進(jìn)程的個數(shù)intturn;//輪到誰？intinterested[N];//興趣數(shù)組，初始值均為FALSEvoidenter_region(intprocess){//process=0或1intother;//另外一個進(jìn)程的進(jìn)程號other=1-process;interested[process]=TRUE;//表明本進(jìn)程感興趣turn=process;//設(shè)置標(biāo)志位while(turn==process&&interested[other]==TRUE);}voidleave_region(intprocess){ interested[process]=FALSE;//本進(jìn)程已離開臨界區(qū)}表明哪個進(jìn)程要進(jìn)臨界區(qū)43軟件方法5peterson算法#defineFALSE0#defineTRUE1#defineN2//進(jìn)程的個數(shù)intturn;//輪到誰？intinterested[N];//興趣數(shù)組，初始值均為FALSEvoidenter_region(intprocess){//process=0或1intother;//另外一個進(jìn)程的進(jìn)程號other=1-process;interested[process]=TRUE;//表明本進(jìn)程感興趣turn=process;//設(shè)置標(biāo)志位while(turn==process&&interested[other]==TRUE);}voidleave_region(intprocess){ interested[process]=FALSE;//本進(jìn)程已離開臨界區(qū)}用進(jìn)程號調(diào)用，表明哪一個進(jìn)程要進(jìn)入臨界區(qū)44軟件方法5peterson算法#defineFALSE0#defineTRUE1#defineN2//進(jìn)程的個數(shù)intturn;//輪到誰？intinterested[N];//興趣數(shù)組，初始值均為FALSEvoidenter_region(intprocess){//process=0或1intother;//另外一個進(jìn)程的進(jìn)程號other=1-process;interested[process]=TRUE;//表明本進(jìn)程感興趣turn=process;//設(shè)置標(biāo)志位while(turn==process&&interested[other]==TRUE);}voidleave_region(intprocess){ interested[process]=FALSE;//本進(jìn)程已離開臨界區(qū)}想進(jìn)臨界區(qū)的進(jìn)程，將進(jìn)程號賦給turn45軟件方法5peterson算法#defineFALSE0#defineTRUE1#defineN2//進(jìn)程的個數(shù)intturn;//輪到誰？intinterested[N];//興趣數(shù)組，初始值均為FALSEvoidenter_region(intprocess){//process=0或1intother;//另外一個進(jìn)程的進(jìn)程號other=1-process;interested[process]=TRUE;//表明本進(jìn)程感興趣turn=process;//設(shè)置標(biāo)志位while(turn==process&&interested[other]==TRUE);}voidleave_region(intprocess){ interested[process]=FALSE;//本進(jìn)程已離開臨界區(qū)}若進(jìn)程0先調(diào)用enter_regionturn的值為0之后，進(jìn)程1調(diào)用enter_regionturn的值為1問題：如何保證先執(zhí)行進(jìn)程0?46軟件方法5peterson算法#defineFALSE0#defineTRUE1#defineN2//進(jìn)程的個數(shù)intturn;//輪到誰？intinterested[N];//興趣數(shù)組，初始值均為FALSEvoidenter_region(intprocess){//process=0或1intother;//另外一個進(jìn)程的進(jìn)程號other=1-process;interested[process]=TRUE;//表明本進(jìn)程感興趣turn=process;//設(shè)置標(biāo)志位while(turn==process&&interested[other]==TRUE);}voidleave_region(intprocess){ interested[process]=FALSE;//本進(jìn)程已離開臨界區(qū)}進(jìn)程0先調(diào)用enter_region()，進(jìn)程1后調(diào)用進(jìn)程0調(diào)用enter_region()， process=0；turn=0；turn被改為1之后，進(jìn)程1調(diào)用enter_region()，

process=1；turn=1，0被覆蓋；那么，對于進(jìn)程0，turn！=process條件不成立，進(jìn)入臨界區(qū)。對于進(jìn)程1，turn==process，進(jìn)程1的turn=1，條件成立，進(jìn)程1陷入循環(huán)Peterson算法cobeginprocessP0(){inside[0]=true;turn=1;while(inside[1]&&turn==1); {臨界區(qū)}; inside[0]=false;}

coend

47processP1(){inside[1]=true;turn=0;while(inside[0]&&turn==0); {臨界區(qū)};inside[1]=false;}4.2.4實現(xiàn)臨界區(qū)管理的硬件設(shè)施關(guān)中斷測試并建立指令對換指令48“開關(guān)中斷”指令（特權(quán)指令）可實現(xiàn)原語操作

操作步驟如下：Step1：執(zhí)行“關(guān)中斷”指令Step2：臨界區(qū)操作Step3：執(zhí)行“開中斷”指令49簡單，有效較高的代價，限制CPU并發(fā)能力（臨界區(qū)大?。┎贿m用于多處理器關(guān)中斷實現(xiàn)互斥的最簡單方法關(guān)中斷適用場合簡單有效，對操作系統(tǒng)自身有用，可在更新共享變量或列表的幾條指令期間禁止中斷。關(guān)中斷方法的缺點不適合作為通用的互斥機(jī)制，關(guān)中斷時間過長會影響性能和系統(tǒng)效率；不適應(yīng)于多處理器計算機(jī)系統(tǒng)，因為一個處理器關(guān)中斷，并不能防止進(jìn)程在其它處理器上執(zhí)行相同的臨界段代碼；若將這項權(quán)力賦予用戶會存在危險，若用戶未開中斷，則系統(tǒng)可能因此而終止。50測試并建立指令TS指令的處理過程boolTS(bool&x){if(x){

x=false; returntrue; }else returnfalse;}

TS指令管理臨界區(qū)時，可把一個臨區(qū)與一個布爾變量s相連，由于變量s代表了臨界資源的狀態(tài)，可把它看成一把鎖。51測試并建立指令TS指令實現(xiàn)進(jìn)程互斥bools=true;cobeginprocessPi(){//i=1,2,...,n

while(!TS(s));//上鎖

{臨界區(qū)};

s=true;//開鎖}coend52boolTS(bool&x){if(x){x=false;returntrue;}elsereturnfalse;}反復(fù)測試直到值為真對換指令(1)voidSWAP(bool&a,bool&b){

booltemp=a; a=b; b=temp; }53對換指令(2)對換指令實現(xiàn)進(jìn)程互斥布爾型鎖變量boollock=false;cobeginProcessPi(){//i=1,2,...,n boolkeyi=true; do{SWAP(keyi,lock);}while(keyi);//上鎖

{臨界區(qū)};

SWAP(keyi,lock);//開鎖}coend54軟件方法：開銷，編程技巧硬件方法忙等待（busywaiting）進(jìn)程在得到臨界區(qū)訪問權(quán)之前，持續(xù)測試而不做其他事情（單處理器避免使用）自旋鎖Spinlock（多處理器）55小結(jié)4.3信號量與PV操作4.3.1同步與同步機(jī)制4.3.2信號量與PV操作4.3.3信號量實現(xiàn)互斥4.3.4信號量解決五個哲學(xué)家吃通心面問題4.3.5信號量解決生產(chǎn)者-消費(fèi)者問題4.3.6記錄型信號量解決讀者-寫者問題4.3.7記錄型信號量解決理發(fā)師問題56進(jìn)程同步：指系統(tǒng)中多個進(jìn)程中發(fā)生的事件存在某種時序關(guān)系，需要相互合作，共同完成一項任務(wù)57進(jìn)程的同步一個進(jìn)程運(yùn)行到某一個點時，要求另一伙伴進(jìn)程為它提供消息在未獲得消息之前，該進(jìn)程進(jìn)入阻塞態(tài)；獲得消息后被喚醒進(jìn)入就緒態(tài)4.3.1同步和同步機(jī)制著名的生產(chǎn)者--消費(fèi)者問題是計算機(jī)操作系統(tǒng)中并發(fā)進(jìn)程內(nèi)在關(guān)系的一種抽象，是典型的進(jìn)程同步問題。在操作系統(tǒng)中:生產(chǎn)者進(jìn)程可以是計算進(jìn)程、發(fā)送進(jìn)程；而消費(fèi)者進(jìn)程可以是打印進(jìn)程、接收進(jìn)程等等。解決好生產(chǎn)者--消費(fèi)者問題就解決好了一類并發(fā)進(jìn)程的同步問題。58生產(chǎn)者--消費(fèi)者問題表述59緩沖區(qū)生產(chǎn)者進(jìn)程消費(fèi)者進(jìn)程問題描述：一個或多個生產(chǎn)者生產(chǎn)某種類型的數(shù)據(jù)放在緩沖區(qū)有消費(fèi)者從緩沖區(qū)中取數(shù)據(jù)，每次取一項只能有一個生產(chǎn)者或消費(fèi)者對緩沖區(qū)進(jìn)行操作需要解決的問題緩沖區(qū)滿，生產(chǎn)者添加數(shù)據(jù)到緩沖區(qū)緩沖區(qū)空，消費(fèi)者不會從緩沖區(qū)取數(shù)據(jù)生產(chǎn)者-消費(fèi)者問題算法描述(1)processproducer(void){while(true){//無限循環(huán)

{produceaniteminnextp};//生產(chǎn)一個產(chǎn)品

if(counter==k)//緩沖滿時，生產(chǎn)者睡眠

sleep(producer); buffer[in]=nextp;//將一個產(chǎn)品放入緩沖區(qū)

in=(in+1)%k;//指針推進(jìn)

counter++;//緩沖內(nèi)產(chǎn)品數(shù)加1 if(counter==1)//緩沖為空，加進(jìn)一件產(chǎn)品

wakeup(consumer);//并喚醒消費(fèi)者

}}60檢查共享變量的值會產(chǎn)生錯誤嗎？生產(chǎn)者-消費(fèi)者問題算法描述(2)processconsumer(void){ while(true){//無限循環(huán)

if(counter==0)//緩沖區(qū)空，消費(fèi)者睡眠

sleep(consumer); nextc=buffer[out];//取一個產(chǎn)品到nextc out=(out+1)%k;//指針推進(jìn)

counter--;//取走一個產(chǎn)品，計數(shù)減1 if(counter==k-1)//緩沖滿了，取走一件產(chǎn)品并喚

wakeup(producer);//醒生產(chǎn)者

{consumetheiteminnextc};//消耗產(chǎn)品

}}61檢查共享變量的值會產(chǎn)生錯誤嗎？62processproducer(void){while(true){{produceaniteminnextp

if(counter==k)

sleep(producer); buffer[in]=nextp

in=(in+1)%k;

counter++; if(counter==1)

wakeup(consumer);

}}processconsumer(void){while(true){ if(counter==0) sleep(consumer); nextc=buffer[out]; out=(out+1)%k; counter--; if(counter==k-1) wakeup(producer); {consumetheiteminnextc}; }}1使用共享變量count可能會產(chǎn)生的錯誤Step1：count==0，進(jìn)程counsumer上cpu2363processproducer(void){while(true){{produceaniteminnextp

if(counter==k)

sleep(producer); buffer[in]=nextp

in=(in+1)%k;

counter++; if(counter==1)

wakeup(consumer);

}}processconsumer(void){while(true){ if(counter==0) sleep(consumer); nextc=buffer[out]; out=(out+1)%k; counter--; if(counter==k-1) wakeup(producer); {consumetheiteminnextc}; }}1使用共享變量count可能會產(chǎn)生的錯誤Step2：進(jìn)程consumer被撤下CPU，producer上CPUStep3：producer執(zhí)行wakeup(consumer)，由于進(jìn)程consumer執(zhí)行sleep之前被撤下，所以wakeup(consumer)相當(dāng)于是空操作。2364processproducer(void){while(true){{produceaniteminnextp

if(counter==k)

sleep(producer); buffer[in]=nextp

in=(in+1)%k;

counter++; if(counter==1)

wakeup(consumer);

}}processconsumer(void){while(true){ if(counter==0) sleep(consumer); nextc=buffer[out]; out=(out+1)%k; counter--; if(counter==k-1) wakeup(producer); {consumetheiteminnextc}; }}1使用共享變量count可能會產(chǎn)生的錯誤Step4：producer被撤下，進(jìn)程consumer繼續(xù)執(zhí)行，執(zhí)行sleep(consumer);由于step3操作已經(jīng)執(zhí)行wakeup(consumer)，所以consumer就不會被喚醒。234生產(chǎn)者-消費(fèi)者問題解決方法的不足生產(chǎn)者和消費(fèi)者進(jìn)程對counter的交替執(zhí)行會使其結(jié)果不唯一生產(chǎn)者和消費(fèi)者進(jìn)程的交替執(zhí)行會導(dǎo)致進(jìn)程永遠(yuǎn)等待654.3.2信號量與PV操作661965年E.W.Dijkstra提出了新的同步工具--信號量和P、V操作。信號量：用于進(jìn)程間傳遞信息的一個整數(shù)值Structsemaphore{ intcount； queueTypequeue；//允許進(jìn)程掛接到該隊列上}

信號量聲明：semaphores；

對信號量可以實施的操作，初始化、P和V操作信號量與PV操作(3)實現(xiàn)時，信號量是一種記錄型數(shù)據(jù)結(jié)構(gòu)，有兩個分量：一個是信號量的值，另一個是信號量隊列的隊列指針。信號量的值信號量隊列指針6768PV操作定義P(s){s.count--;if(s.count<0){

該進(jìn)程狀態(tài)為阻塞狀態(tài)將該進(jìn)程插入相等的等待隊列s.queue末尾；（表示讓出CPU）重新調(diào)度；}}V(s){s.count++;if(s.count<=0){

喚醒相應(yīng)等待隊列 s.queue等待的一個進(jìn)程，改變其狀態(tài)為就緒態(tài)，并將其插入就緒隊列}}down，semwaitup，semsignal信號量與PV操作信號量：一種軟件資源原語操作：內(nèi)核中執(zhí)行時不可被中斷的過程P操作原語和V操作原語最初提出的是二元信號量（解決互斥）之后，推廣到一般信號量（多值）或計數(shù)信號量（解決同步）6970用PV操作解決進(jìn)程間的互斥問題分析并發(fā)進(jìn)程的關(guān)鍵活動，劃定臨界區(qū)設(shè)置信號量mutex，初值為1在臨界區(qū)錢實施P(mutex)在臨界區(qū)之后實施V(mutex)臨界區(qū)P(mutex)V(mutex)P(mutex)P(mutex)V(mutex)V(mutex)P1P2P371臨界區(qū)P(mutex)V(mutex)P(mutex)P(mutex)V(mutex)V(mutex)P1P2P3設(shè)置信號量mutex，初值為1案例解析Step1：P1上CPU，執(zhí)行P操作，mutex=mutex-1=0，此時mutex不小于0，所以P1進(jìn)程進(jìn)入臨界區(qū)。Step2：P1被中斷，P1被撤下CPU，P2上CPU，執(zhí)行P操作，mutex=mutex-1=0-1=-1，此時mutex小于0，P2無法進(jìn)入臨界區(qū)，P2進(jìn)程進(jìn)入等待隊列。72臨界區(qū)P(mutex)V(mutex)P(mutex)P(mutex)V(mutex)V(mutex)P1P2P3設(shè)置信號量mutex，初值為1案例解析Step3：P2被中斷，P2被撤下CPU，P3上CPU，執(zhí)行P操作，mutex=mutex-1=-1-1=-2，此時mutex小于0，P3無法進(jìn)入臨界區(qū)，P3進(jìn)程進(jìn)入等待隊列。73臨界區(qū)P(mutex)V(mutex)P(mutex)P(mutex)V(mutex)V(mutex)P1P2P3設(shè)置信號量mutex，初值為1案例解析Step4：P3被中斷，P3被撤下CPU，P1上CPU，執(zhí)行V操作，mutex=mutex+1=-2+1=-1，此時mutex小于0，去等待隊列中喚醒P2，P2進(jìn)入就緒隊列，P1進(jìn)程繼續(xù)執(zhí)行自己的工作。74臨界區(qū)P(mutex)V(mutex)P(mutex)P(mutex)V(mutex)V(mutex)P1P2P3設(shè)置信號量mutex，初值為1案例解析Step4：P1被中斷，P1被撤下CPU，P2上CPU，直接進(jìn)入臨界區(qū)，執(zhí)行V操作，mutex=mutex+1=-1+1=0，此時mutex等于0，去等待隊列中喚醒P3，P3進(jìn)入就緒隊列，P2進(jìn)程繼續(xù)執(zhí)行自己的工作。75臨界區(qū)P(mutex)V(mutex)P(mutex)P(mutex)V(mutex)V(mutex)P1P2P3設(shè)置信號量mutex，初值為1案例解析Step4：P2被中斷，P2被撤下CPU，P3上CPU，直接進(jìn)入臨界區(qū)，執(zhí)行V操作，mutex=mutex+1=0+1=1，此時mutex大于0，表示無等待的進(jìn)程，P3進(jìn)程繼續(xù)執(zhí)行自己的工作。76用信號量解決生產(chǎn)者/消費(fèi)者問題voidproducer（void）{intitem;while(true){item=produce_item();

p(&empty);

insert_item(item);v(&full);}}voidconsumer（void）{intitem;while(true){item=remove_item();

p(&full);

consume_item(item);

v(&empty);}}#defineN

100//緩沖區(qū)的個數(shù)typedefintsemaphore;//信號量是一種特殊的整型數(shù)據(jù)Semaphoremutex=1;//互斥信號量，控制對臨界區(qū)的訪問Semaphoreempty=N；//空緩沖區(qū)的個數(shù)Semaphorefull=0；//滿緩沖區(qū)的個數(shù)77用信號量解決生產(chǎn)者/消費(fèi)者問題voidproducer（void）{intitem;while(true){item=produce_item();p(&empty);p(&mutex);insert_item(item);v(&mutex);v(&full);}}voidconsumer（void）{intitem;while(true){item=remove_item();p(&full);p(&mutex);consume_item(item);

v(&mutex);v(&empty);}}78是否可以改變順序voidproducer（void）{intitem;while(true){item=produce_item();p(&empty);p(&mutex);inse