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

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

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

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

4、l section,Until false;,,算法2：設(shè)一個表示進程狀態(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è)一個表示進程狀態(tài)

5、的數(shù)組 Var flag：array[0..1] of boolean,不滿足準則4,Repeat,flag[i] = false；,Critical section,Non-ritical section,Until false;,,算法4：在標志置true的時候注意一下 對方的狀態(tài),不滿足準則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è)一個表示進程狀態(tài)的數(shù)組和一個令牌 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 實現(xiàn)臨界段的硬件方法,利用處理機提供的特殊指令實現(xiàn)臨界區(qū)加鎖。常見硬件指令有:,一、“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指令，即可實現(xiàn)對臨界區(qū)的加鎖與解鎖：,設(shè)Lock為全局布爾變量（初值為假），每個進程設(shè)一個局部布爾變量Key。利用Swap指令，可實現(xiàn)對臨界區(qū)的加鎖與解鎖。,Repeat key = true; repeat Swap (lock, key); until key = false; critical section lock = false; non-criti

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

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

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

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