同步與互斥實(shí)現(xiàn)方法

1、第八講 同步與互斥實(shí)現(xiàn)方法,目的與要求：理解互斥問(wèn)題的軟硬件實(shí)現(xiàn)方法；掌握信號(hào)量機(jī)制及使用它解決進(jìn)程同步互斥問(wèn)題的方法。重點(diǎn)與難點(diǎn)：信號(hào)量實(shí)現(xiàn)及使用。作業(yè)：1，2，4，7，13。,解決臨界段問(wèn)題的軟件算法必須遵循：準(zhǔn)則1：不能虛設(shè)硬件指令或假設(shè)處理機(jī)數(shù)目。準(zhǔn)則2：不能假設(shè)n個(gè)進(jìn)程的相對(duì)速度。準(zhǔn)則3：當(dāng)一個(gè)進(jìn)程未處于其臨界段時(shí)，不應(yīng)阻止其他進(jìn)程進(jìn)入臨界段。準(zhǔn)則4：當(dāng)若干進(jìn)程欲進(jìn)入臨界段時(shí)，應(yīng)能在有限時(shí)間內(nèi)選出一個(gè)進(jìn)程進(jìn)

2、入其臨界段。,4.2.2 實(shí)現(xiàn)互斥的軟件算法,進(jìn)入臨界段之前要申請(qǐng)，獲得批準(zhǔn)方可進(jìn)入； 退出臨界段之后要聲明，以便其他進(jìn)程進(jìn)入。,協(xié)調(diào)各進(jìn)程入臨界段的調(diào)度原則： 當(dāng)無(wú)進(jìn)程處于臨界段時(shí)，允許一個(gè)進(jìn)程立即進(jìn)入臨界段。 當(dāng)已有進(jìn)程進(jìn)入臨界段時(shí)， 其他試圖進(jìn)入的進(jìn)程必須等待。 當(dāng)某進(jìn)程退出臨界段時(shí)，若有等待進(jìn)入臨界段的進(jìn)程，則應(yīng)選取一個(gè)進(jìn)入臨界段。軟件算法舉例:,Pi 表示一個(gè)進(jìn)程Pj 表示另一個(gè)進(jìn)程（i=0, 1； j=1

3、- i ）,Repeat,While turn≠i do skip ;,turn= j ;,Critical section,Non-ritical section,Until false;,,算法1：設(shè)一個(gè)共享的整型變量turn（0，1）,不滿足準(zhǔn)則3,Repeat,While flag[j] do skip flag[i] = true；,flag[i] = false；,Critical section,Non-ritica

4、l section,Until false;,,算法2：設(shè)一個(gè)表示進(jìn)程狀態(tài)的數(shù)組 Var flag：array[0..1] of boolean,不滿足互斥要求,Repeat,flag[i] = true； While flag[j] do skip；,flag[i] = false；,Critical section,Non-ritical section,Until false;,,算法3：設(shè)一個(gè)表示進(jìn)程狀態(tài)

5、的數(shù)組 Var flag：array[0..1] of boolean,不滿足準(zhǔn)則4,Repeat,flag[i] = false；,Critical section,Non-ritical section,Until false;,,算法4：在標(biāo)志置true的時(shí)候注意一下 對(duì)方的狀態(tài),不滿足準(zhǔn)則4,flag[i] = true；,While flag[j] do,begin,flag[

6、i] = false；,While flag[j] do skip；,flag[i] = true；,end,,turn = j; flag[i] = false；,算法5：設(shè)一個(gè)表示進(jìn)程狀態(tài)的數(shù)組和一個(gè)令牌 Var flag：array[0..1] of boolean turn：0..1,flag[i] = true；,Wh

7、ile flag[j] do,begin,flag[i] = false；,While turn==j do skip；,flag[i] = true；,End;,,if turn==j then,Dekker算法 OK！,4.2.3 實(shí)現(xiàn)臨界段的硬件方法,利用處理機(jī)提供的特殊指令實(shí)現(xiàn)臨界區(qū)加鎖。常見(jiàn)硬件指令有:,一、“Test_and_Set”指令該指令功能描述為：Function Test_and_Set（V

8、ar target：boolean） :boolean；beginTest_and_Set = target；Target = true；end；,二、“Swap”指令該指令功能描述為：Procedure Swap（Var a,b：boolean）；Var temp：boolean；begintemp = a；a = b；b = temp；end；,設(shè)Lock為全局布爾變量，利用Test&a

9、mp;Set指令，即可實(shí)現(xiàn)對(duì)臨界區(qū)的加鎖與解鎖：,設(shè)Lock為全局布爾變量（初值為假），每個(gè)進(jìn)程設(shè)一個(gè)局部布爾變量Key。利用Swap指令，可實(shí)現(xiàn)對(duì)臨界區(qū)的加鎖與解鎖。,Repeat key = true; repeat Swap (lock, key); until key = false; critical section lock = false; non-criti

10、cal sectionUntil false;,,,4.2.4 信號(hào)量,信號(hào)量機(jī)構(gòu)：“信號(hào)量”、“P，V操作”。 信號(hào)量S為一整型變量： P(S): While S≤0 do skip ； S = S-1 ； V（S）：S = S＋1；P,V操作是兩條原語(yǔ)，即保證P,V操作對(duì)變量S的訪問(wèn)是互斥操作。,一、原語(yǔ)概念與實(shí)現(xiàn)原語(yǔ)：指完成某種功能且不被分割或不被中斷執(zhí)行的操作序列。原語(yǔ)可通過(guò)硬件實(shí)現(xiàn)不

11、可中斷性；或通過(guò)實(shí)現(xiàn)臨界段的元方法達(dá)到不被中斷。實(shí)現(xiàn)臨界段的元方法:屏蔽中斷(只用于單機(jī))；加硬鎖。,二、信號(hào)量的使用(互斥與同步)互斥：用于n個(gè)進(jìn)程的臨界段互斥，n個(gè)進(jìn)程共享一個(gè)信號(hào)量mutex,初值為1，任一進(jìn)程Pi的結(jié)構(gòu)為：,P(mutex),V(mutex),臨界段,非臨界段,repeat,Until false,同步：有P1,P2 兩進(jìn)程，必須在P1執(zhí)行完S1語(yǔ)句后，P2才能執(zhí)行S2。需同步的兩進(jìn)程共享信號(hào)量sync

12、h，初值為0。,Parbegin,P2: begin,P1: begin,……,S1;,V(synch);,……,end;,……,P(synch);,S2;,……,end;,Parend;,操作系統(tǒng)實(shí)現(xiàn)信號(hào)量時(shí)與進(jìn)程調(diào)度相結(jié)合，消除忙等待現(xiàn)象。原則是：在P操作循環(huán)等待的地方加入放棄處理機(jī)/掛入等待隊(duì)列動(dòng)作，在V操作時(shí)，從等待隊(duì)列中摘取進(jìn)程變?yōu)榫途w態(tài)。（P,V原語(yǔ)本身的互斥操作通過(guò)屏敝中斷或?yàn)樾盘?hào)量加硬鎖實(shí)現(xiàn)）。,三、信號(hào)量的具體實(shí)

13、現(xiàn),1.信號(hào)量定義 type Semaphore=record value:integer; 一個(gè)數(shù)型變量 L:List of process;一個(gè)PCB隊(duì)列 end;2.P操作 P(S):S.Value=S.value –1; If S.value<0 then 保存現(xiàn)場(chǎng)， 將本進(jìn)程掛入S.L隊(duì)列，重新調(diào)度。3.V操作 V（S):S.v