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

1、第八講第八講 同步與互斥實(shí)現(xiàn)方法同步與互斥實(shí)現(xiàn)方法 目的與要求：目的與要求：理解互斥問(wèn)題的硬件實(shí)現(xiàn)方理解互斥問(wèn)題的硬件實(shí)現(xiàn)方法；掌握信號(hào)量機(jī)制及使用它解決進(jìn)程同法；掌握信號(hào)量機(jī)制及使用它解決進(jìn)程同步互斥問(wèn)題的方法。步互斥問(wèn)題的方法。 重點(diǎn)與難點(diǎn)重點(diǎn)與難點(diǎn)：信號(hào)量實(shí)現(xiàn)及使用。：信號(hào)量實(shí)現(xiàn)及使用。 作業(yè)：作業(yè)：1，2，4，13（沒(méi)做（沒(méi)做7題請(qǐng)補(bǔ)做）題請(qǐng)補(bǔ)做）實(shí)現(xiàn)臨界段的硬件方法利用處理機(jī)提供的特殊指令實(shí)現(xiàn)臨界區(qū)加鎖利用處理機(jī)提供的特殊指令實(shí)現(xiàn)臨界區(qū)加鎖單處理機(jī)系統(tǒng)常見(jiàn)硬件指令有單處理機(jī)系統(tǒng)常見(jiàn)硬件指令有: :一一. .屏蔽中斷屏蔽中斷Parbegin A(amount) disableInter

2、rupt(); R1=balance; R2=amount; R1=R1+R2; balance=R1; enableInterrupt(); ; B(amount) disableInterrupt(); R1=balance; R2=amount; R1=R1-R2; balance=R1; enableInterrupt(); ;Parend;多處理機(jī)系統(tǒng)硬件指令有多處理機(jī)系統(tǒng)硬件指令有: :一、一、“Test_and_SetTest_and_Set”指令。指令。該指令該指令功能功能描述為：描述為：Function Test_and_Set（Var target：boolean） :bo

3、olean；beginTest_and_Set = target；Target = true；end；二、二、“SwapSwap”指令。指令。該指令該指令功能功能描述為：描述為：Procedure SwapProcedure Swap（Var a,bVar a,b：booleanboolean）；）；Var tempVar temp：booleanboolean；beginbegintemp = atemp = a；a = ba = b；b = tempb = temp；endend；設(shè)設(shè)LockLock為全局布爾變量，利用為全局布爾變量，利用Test&SetTest&Set指

4、令，即可實(shí)現(xiàn)對(duì)臨界區(qū)的加鎖與解鎖：指令，即可實(shí)現(xiàn)對(duì)臨界區(qū)的加鎖與解鎖：Repeat while Test&Set (lock) do skip critical section lock = false; non-critical sectionUntil false;“test&settest&set” 讀后置讀后置1 1指令實(shí)例：指令實(shí)例：T&S Ri,Aj T&S Ri,Aj 解釋為將解釋為將(Aj)(Aj)地址所指內(nèi)地址所指內(nèi)存單元內(nèi)容讀到存單元內(nèi)容讀到RiRi寄存器中寄存器中, ,同時(shí)將同時(shí)將1 1置入置入AjAj所指的內(nèi)存單元中所指的內(nèi)存單元

5、中. .設(shè)設(shè)LockLock為臨界段鎖變量，則安排如下指令，為臨界段鎖變量，則安排如下指令，即可實(shí)現(xiàn)加鎖與解鎖：即可實(shí)現(xiàn)加鎖與解鎖：* *臨界段非臨界段非臨界段 A1A1&Lock;&Lock;（將（將LockLock單元地址送單元地址送A1A1寄存器。寄存器。LockLock單元初始值為單元初始值為0 0）Loop:T&S R1,A1;Loop:T&S R1,A1; JRN R1,Loop; (If (R1=1)then goto JRN R1,Loop; (If (R1=1)then goto Loop )Loop )A1 =&Lock;A1 =&a

6、mp;Lock;(A1) =0;(0(A1) =0;(0置置LockLock內(nèi)存單元內(nèi)存單元) )設(shè)設(shè)LockLock為全局布爾變量（初值為假），每個(gè)進(jìn)程為全局布爾變量（初值為假），每個(gè)進(jìn)程設(shè)一個(gè)局部布爾變量設(shè)一個(gè)局部布爾變量KeyKey。利用。利用SwapSwap指令，可實(shí)指令，可實(shí)現(xiàn)對(duì)臨界區(qū)的加鎖與解鎖?，F(xiàn)對(duì)臨界區(qū)的加鎖與解鎖。Repeat key = true; repeat Swap (lock, key); until key = false; critical section lock = false; non-critical sectionUntil false;信號(hào)量信號(hào)量機(jī)

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

8、通過(guò)硬件實(shí)現(xiàn)不可中斷性；或通過(guò)實(shí)現(xiàn)臨界段的元方法達(dá)到不被中斷。過(guò)實(shí)現(xiàn)臨界段的元方法達(dá)到不被中斷。實(shí)現(xiàn)臨界段的元方法實(shí)現(xiàn)臨界段的元方法: :屏蔽中斷屏蔽中斷( (只用于單機(jī)只用于單機(jī)) )加硬鎖。加硬鎖。下面我們用屏蔽中斷方法實(shí)現(xiàn)下面我們用屏蔽中斷方法實(shí)現(xiàn)P P（s s）和）和V V（s s）的原子性。）的原子性。P P（s s） DisableInterrupt();DisableInterrupt();while while （s0s0）do do enableInterrupt();enableInterrupt();DisableInterrupt();DisableInterrupt(

9、); ；s = s - 1s = s - 1；enableInterrupt();enableInterrupt(); V V（s s） DisableInterrupt();DisableInterrupt(); s = s +1s = s +1；enableInterrupt();enableInterrupt(); 二、信號(hào)量的使用(互斥與同步)互斥：互斥：用于用于n n個(gè)進(jìn)程的臨界段互斥，個(gè)進(jìn)程的臨界段互斥，n n進(jìn)程共享一進(jìn)程共享一個(gè)信號(hào)量個(gè)信號(hào)量mutex,mutex,初值為初值為1 1，任一進(jìn)程，任一進(jìn)程PiPi的結(jié)構(gòu)為：的結(jié)構(gòu)為： P(mutex)V(mutex)臨界段非臨界段

10、repeatUntil false同步：同步：有有P1P1、P2 P2 兩進(jìn)程，必須在兩進(jìn)程，必須在P P1 1執(zhí)行完執(zhí)行完S1S1語(yǔ)句后，語(yǔ)句后，P2P2才能執(zhí)行才能執(zhí)行S2S2。需同步的兩進(jìn)程共享。需同步的兩進(jìn)程共享信號(hào)量信號(hào)量synchsynch，初值為，初值為0 0。Parbegin P2: begin P1: beginS1;V(synch);end; P(synch);S2;end;Parend;S1S2S3S4S5S6S7請(qǐng)用并行語(yǔ)句和PV操作描述操作系統(tǒng)實(shí)現(xiàn)信號(hào)量時(shí)與進(jìn)程調(diào)度相結(jié)合，操作系統(tǒng)實(shí)現(xiàn)信號(hào)量時(shí)與進(jìn)程調(diào)度相結(jié)合，消除忙等待現(xiàn)象。消除忙等待現(xiàn)象。原則是：原則是：在在P P

11、操作循環(huán)等待的地方加入放棄操作循環(huán)等待的地方加入放棄處理機(jī)處理機(jī)/ /掛入等待隊(duì)列動(dòng)作，在掛入等待隊(duì)列動(dòng)作，在V V操作時(shí)，操作時(shí)，從等待隊(duì)列中摘取進(jìn)程變?yōu)榫途w態(tài)。從等待隊(duì)列中摘取進(jìn)程變?yōu)榫途w態(tài)。（P P、V V原語(yǔ)本身的互斥操作通過(guò)屏敝中斷原語(yǔ)本身的互斥操作通過(guò)屏敝中斷或?yàn)樾盘?hào)量加硬鎖實(shí)現(xiàn)）或?yàn)樾盘?hào)量加硬鎖實(shí)現(xiàn)）三.信號(hào)量的具體實(shí)現(xiàn)1 1、信號(hào)量定義、信號(hào)量定義 type Semaphore=recordtype Semaphore=record value:integer; value:integer; 一個(gè)數(shù)型變量一個(gè)數(shù)型變量 L:List of process;L:List of process;一個(gè)一個(gè)PCBPCB隊(duì)列隊(duì)列 end;end;2 2、P P操作操作 P(S):S.Value=S.value P(S):S.Value=S.value 1;1; If S.value0 then If S.value0