3.2臨界區(qū)管理3.2.1互斥與臨界區(qū)3.2.2實(shí)現(xiàn)臨界區(qū)管理的幾種嘗試3.2.3實(shí)現(xiàn)臨界區(qū)管理的軟件方法3.2.4實(shí)現(xiàn)臨界區(qū)管理的硬件設(shè)施3.2.1互斥與臨界區(qū)(1)并發(fā)進(jìn)程中與共享變量有關(guān)的程序段叫“臨界區(qū)”(CriticalSection)，共享變量代表的資源叫“臨界資源”(CriticalResource)?；コ馀c臨界區(qū)(2)

?與同一變量有關(guān)的臨界區(qū)分散在各進(jìn)程的程序段中，而各進(jìn)程的執(zhí)行速度不可預(yù)知。

?如果保證進(jìn)程在臨界區(qū)執(zhí)行時，不讓另一個進(jìn)程進(jìn)入臨界區(qū)，即各進(jìn)程對共享變量的訪問是互斥的，就不會造成與時間有關(guān)的錯誤?；コ馀c臨界區(qū)(3)

Dijkstra在1965年首先提出臨界區(qū)的概念?？梢杂门c一個共享變量相關(guān)的臨界區(qū)的語句結(jié)構(gòu)來書寫交互的并發(fā)進(jìn)程。

互斥與臨界區(qū)(4)

臨界區(qū)的調(diào)度原則：一次至多允許一個進(jìn)程進(jìn)入臨界區(qū)內(nèi)一個進(jìn)程不能無限地停留在臨界區(qū)內(nèi)一個進(jìn)程不能無限地等待進(jìn)入臨界區(qū)互斥與臨界區(qū)(5)

臨界區(qū)調(diào)度原則無空等待、有空讓進(jìn)、擇一而入、算法可行?；コ馀c臨界區(qū)(6)臨界區(qū)的描述sharedvariableregionvariabledostatement臨界區(qū)的嵌套使用regionxdo[…

regionydo[…]…]regionydo[…

regionxdo[…]…]臨界區(qū)管理的嘗試(1)inside1,inside2:Booleaninside1:=false;/*P1不在其臨界區(qū)內(nèi)*/inside2:=false;/*P2不在其臨界區(qū)內(nèi)*/cobeginprocessP1

Begin whileinside2dobeginend; inside1:=true;

臨界區(qū);

inside1:=false;

end;processP2begin whileinside1dobeginend; inside2=true;

臨界區(qū);

inside2:=false;end;coend臨界區(qū)管理的嘗試(2)inside1,inside2:boolean;inside1:=false;/*P1不在其臨界區(qū)內(nèi)*/inside2:=false;/*P2不在其臨界區(qū)內(nèi)*/cobeginprocessP1begin inside1:=true; whileinside2dobeginend;

臨界區(qū);

inside1:=false;end;processP2begin inside2:=true; whileinside1dobeginend;

臨界區(qū);

inside2:=false;end;

coendDekker算法(1)

Dekker算法用一個指示器turn來指示應(yīng)該哪一個進(jìn)程進(jìn)入臨界區(qū)。varinside:array[1..2]ofboolean;turn:integer;turn:=1or2;inside[1]:=false;inside[2]:=false;

cobegin

processP1begininside[1]:=true; whileinside[2]doifturn=2thenbegininside[1]:=false;whileturn=2dobeginend;inside[1]:=true;end

臨界區(qū);

turn=2；

inside[1]:=false;end;Dekker算法(2)

Dekker算法(3)

processP2begininside[2]:=true; whileinside[1]doifturn=1thenbegininside[2]:=false;whileturn=1dobeginend;inside[2]:=true;end

臨界區(qū);

turn=1；

inside[2]:=false;end;coend

Dekker算法的執(zhí)行過程描述(1)進(jìn)程P1(或P2)進(jìn)入自己的臨界區(qū)時，把自己的標(biāo)志位insidei置為true，并檢查對方標(biāo)志位如果對方不在也不想進(jìn)入臨界區(qū)，進(jìn)程Pi可立即進(jìn)入臨界區(qū)；如果雙方都想進(jìn)入，咨詢指示器turn，若turn為1(或?yàn)?)，P1(或P2)知道應(yīng)該自己進(jìn)入Dekker算法的執(zhí)行過程描述(2)

僅當(dāng)turn=i(i=1，2)時進(jìn)程Pi才有權(quán)力進(jìn)入臨界區(qū)，且在一個進(jìn)程退出臨界區(qū)之前，turn值不會改變，能保證互斥進(jìn)入臨界區(qū)的要求。turn的值不是1就是2，不可能同時出現(xiàn)兩個進(jìn)程均在while語句中等待而進(jìn)不了臨界區(qū)。Peterson算法(1)

varinside:array[1..2]ofboolean;turn:integer;turn:=1or2;inside[1]:=false;/*P1不在其臨界區(qū)內(nèi)*/inside[2]:=false;/*P2不在其臨界區(qū)內(nèi)*/Peterson算法(2)

cobeginprocessP1begin inside[1]:=true; turn:=2; while(inside[2]andturn=2)dobeginend;

臨界區(qū); inside[1]:=false;end;Peterson算法(3)

processP2begin inside[2]:=true; turn:=1; while(inside[1]andturn=1)dobeginend;

臨界區(qū);

inside[2]:=false;end;coendPeterson算法(4)

用對turn的置值和while語句來限制每次只有一個進(jìn)程進(jìn)入臨界區(qū)；進(jìn)程執(zhí)行完臨界區(qū)程序后，修改insidei狀態(tài)使等待進(jìn)入臨界區(qū)的進(jìn)程可在有限時間內(nèi)進(jìn)入。算法滿足臨界區(qū)管理的三個條件。實(shí)現(xiàn)臨界區(qū)管理的硬件設(shè)施

關(guān)中斷測試并建立指令對換指令關(guān)中斷實(shí)現(xiàn)互斥的最簡單方法之一關(guān)中斷方法的缺點(diǎn)測試并建立指令(1)

TS指令的處理過程

TS(x):若x=true，則x:=false；

returntrue；否則returnfalse；

TS指令管理臨界區(qū)時，可把一個臨界區(qū)與一個布爾變量s相連，由于變量s代表了臨界資源的狀態(tài)，可把它看成一把鎖。測試并建立指令(2)s:boolean;s:=true;processPi/*i=1,2,…,n*/

pi:boolean;begin repeatpi:=TS(s)untilpi；

臨界區(qū);

s:=true；end;對換指令(1)

對換（Swap）指令的功能是交換兩個字的內(nèi)容：

Swap(a,b):

temp:=a;

a:=b;b:=temp;對換指令(2)lock: