操作系統(tǒng)中進(jìn)程的同步與通信

1、 entry section exit section critical section remainder section 設(shè)置一個(gè)公用整型變量設(shè)置一個(gè)公用整型變量turnturn，用于指示被允許進(jìn)入臨界區(qū)，用于指示被允許進(jìn)入臨界區(qū) 的進(jìn)程的編號(hào)，即若的進(jìn)程的編號(hào)，即若turn=iturn=i，表示允許進(jìn)程，表示允許進(jìn)程Pi Pi 進(jìn)入臨界區(qū)。進(jìn)入臨界區(qū)。 Pi Pi進(jìn)程進(jìn)程: : PjPj進(jìn)程進(jìn)程: : repeat repeatrepeat repeat while turni do no op; while turni do no op; while turnj do no op;wh

2、ile turnj do no op; Critical section Critical section Critical section Critical section turn:=j; turn:=i; turn:=j; turn:=i; Remain Section Remain Section Remain Section Remain Section until false until false until false until false l該算法可確保每次只允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)。但是，強(qiáng)該算法可確保每次只允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)。但是，強(qiáng) 制兩個(gè)進(jìn)程輪流地進(jìn)入臨界區(qū)，很容

3、易造成資源利用不充制兩個(gè)進(jìn)程輪流地進(jìn)入臨界區(qū)，很容易造成資源利用不充 分。分。 l例如，當(dāng)進(jìn)程只退出臨界區(qū)后將例如，當(dāng)進(jìn)程只退出臨界區(qū)后將 turnturn置為置為j j，以便允許，以便允許 P P j j進(jìn)入臨界區(qū)。但如果進(jìn)程進(jìn)入臨界區(qū)。但如果進(jìn)程PjPj暫時(shí)并未要求訪問(wèn)該臨界資暫時(shí)并未要求訪問(wèn)該臨界資 源，而源，而PiPi又想再次訪問(wèn)該資源，但它卻無(wú)法進(jìn)入臨界區(qū)。又想再次訪問(wèn)該資源，但它卻無(wú)法進(jìn)入臨界區(qū)。 可見(jiàn)，此算法不能保證實(shí)現(xiàn)可見(jiàn)，此算法不能保證實(shí)現(xiàn)“空閑讓進(jìn)空閑讓進(jìn)”的準(zhǔn)則的準(zhǔn)則l l。 二二算法算法2 2：雙標(biāo)志先檢查：雙標(biāo)志先檢查 算法算法2 2的基本思想是：在每一個(gè)進(jìn)程訪問(wèn)臨界

4、資源之前，先去查看的基本思想是：在每一個(gè)進(jìn)程訪問(wèn)臨界資源之前，先去查看 一下臨界資源是否正被訪問(wèn)。若正被訪問(wèn)，該進(jìn)程需等待；否則才進(jìn)人一下臨界資源是否正被訪問(wèn)。若正被訪問(wèn)，該進(jìn)程需等待；否則才進(jìn)人 自己的臨界區(qū)。為此，設(shè)置了一個(gè)數(shù)組，使其中每個(gè)元素的初值為自己的臨界區(qū)。為此，設(shè)置了一個(gè)數(shù)組，使其中每個(gè)元素的初值為 falsefalse，表示所有進(jìn)程都未進(jìn)入臨界區(qū)；而當(dāng)其中的第，表示所有進(jìn)程都未進(jìn)入臨界區(qū)；而當(dāng)其中的第 i i個(gè)元素值個(gè)元素值truetrue 時(shí)，即若時(shí)，即若 flagi=trueflagi=true時(shí)，表示進(jìn)程時(shí)，表示進(jìn)程 PiPi正在臨界區(qū)內(nèi)執(zhí)行。正在臨界區(qū)內(nèi)執(zhí)行。 Pi:P

5、i: Pj Pj： repeat repeatrepeat repeat while flagj do no_op; while flagj do no_op; while flagi do no_op;while flagi do no_op; flagi:=true; flagi:=true; flagj:=true;flagj:=true; critical_section; critical_section; critical_section;critical_section; flagi:=false; flagi:=false; flagj:=false;flagj:=false;

6、 remainder section; remainder section; remainder section;remainder section; until false until falseuntil false until false 三三算法算法3 3：雙標(biāo)志、后檢查：雙標(biāo)志、后檢查 1.1.為了解決這一問(wèn)題，在算法為了解決這一問(wèn)題，在算法3 3中仍然使用了數(shù)中仍然使用了數(shù)flagnflagn ，但令但令flagi= trueflagi= true表示進(jìn)程表示進(jìn)程PiPi希望進(jìn)入臨界區(qū)，即每當(dāng)希望進(jìn)入臨界區(qū)，即每當(dāng) 進(jìn)程進(jìn)程PiPi要進(jìn)入臨界區(qū)前，先將要進(jìn)入臨界區(qū)前，先將flagi

7、 flagi 置為置為tureture，表示進(jìn)，表示進(jìn) 程程PiPi已要求進(jìn)入臨界區(qū)。已要求進(jìn)入臨界區(qū)。 2.2.然后再去查看然后再去查看PjPj的標(biāo)志。若此時(shí)的標(biāo)志。若此時(shí) flagj=trueflagj=true，則，則 pipi等待；否則，等待；否則，PiPi進(jìn)入臨界區(qū)。換言之，算法進(jìn)入臨界區(qū)。換言之，算法3 3是使要進(jìn)入是使要進(jìn)入 臨界區(qū)的進(jìn)程先設(shè)置其要求進(jìn)入的標(biāo)志，然后，再去查看臨界區(qū)的進(jìn)程先設(shè)置其要求進(jìn)入的標(biāo)志，然后，再去查看 其它進(jìn)程的標(biāo)志。其它進(jìn)程的標(biāo)志。 Pi:Pi: Pj: Pj: repeat repeatrepeat repeat flagi:=true; flagi:

8、=true; flagj:=true; flagj:=true; while flagj do no_op; while flagj do no_op; while flagi do no_op;while flagi do no_op; critical_section; critical_section; critical_section; critical_section; flagi:=false; flagj:=false;flagi:=false; flagj:=false; remainder section; remainder section;remainder sectio

9、n; remainder section; until false until falseuntil false until false Pi: repeat flagi:=true; turn:=j; while (flagj and turn=j) do no_op; critical_section; flagi:=false; remainder section; until false Pj: repeat flagj:=true; turn:=i; while (flagi and turn=i) do no_op; critical_section; flagj:=false;

10、remainder section; until false 完全利用軟件方法來(lái)解決諸進(jìn)程互斥進(jìn)入臨界區(qū)完全利用軟件方法來(lái)解決諸進(jìn)程互斥進(jìn)入臨界區(qū) 的問(wèn)題，有一定難度，且有很大局限性，因而現(xiàn)代已的問(wèn)題，有一定難度，且有很大局限性，因而現(xiàn)代已 很少采用此方法。很少采用此方法。 針對(duì)這一點(diǎn)，現(xiàn)在有許多計(jì)算機(jī)已提供了一些特針對(duì)這一點(diǎn)，現(xiàn)在有許多計(jì)算機(jī)已提供了一些特 殊的硬件指令，這些指令允許對(duì)一個(gè)字中的內(nèi)容進(jìn)行殊的硬件指令，這些指令允許對(duì)一個(gè)字中的內(nèi)容進(jìn)行 檢測(cè)和修正，或交換兩個(gè)字的內(nèi)容等?？衫眠@些特檢測(cè)和修正，或交換兩個(gè)字的內(nèi)容等?？衫眠@些特 殊的指令來(lái)解決臨界區(qū)問(wèn)題。殊的指令來(lái)解決臨界區(qū)問(wèn)題

11、。 下面介紹兩條特殊硬件指令，以及利用它們來(lái)解下面介紹兩條特殊硬件指令，以及利用它們來(lái)解 決臨界區(qū)問(wèn)題的方法。決臨界區(qū)問(wèn)題的方法。 一一利用利用TestTestandandSetSet指令實(shí)現(xiàn)互斥指令實(shí)現(xiàn)互斥 1.1.TestTestandandSetSet指令指令 在許多機(jī)器中都有這樣的指令，不同機(jī)器的相應(yīng)指令的在許多機(jī)器中都有這樣的指令，不同機(jī)器的相應(yīng)指令的 功能是相同的，因而我們不局限于某特定的機(jī)器去定義功能是相同的，因而我們不局限于某特定的機(jī)器去定義 TestTestandandsetset指令為指令為 function TS（var lock：boolean）：）：boolean；

12、begin TS:=lock； lock:= true； end 其中，其中，locklock有兩種狀態(tài)：當(dāng)有兩種狀態(tài)：當(dāng)lock= falselock= false時(shí)，表示該資時(shí)，表示該資 源空閑；當(dāng)源空閑；當(dāng)lock= truelock= true時(shí)，表示該資源正在被使用。時(shí)，表示該資源正在被使用。 2.2.利用利用TSTS實(shí)現(xiàn)進(jìn)程互斥實(shí)現(xiàn)進(jìn)程互斥 為了實(shí)現(xiàn)諸進(jìn)程對(duì)臨界資源的互斥訪問(wèn)，可為每個(gè)臨界為了實(shí)現(xiàn)諸進(jìn)程對(duì)臨界資源的互斥訪問(wèn)，可為每個(gè)臨界 資源設(shè)置一個(gè)布爾變量資源設(shè)置一個(gè)布爾變量 locklock，并賦予其初值為，并賦予其初值為falsefalse，以，以 表示資源空閑。表示資源空閑

13、。 利用利用TSTS指令實(shí)現(xiàn)互斥的指令實(shí)現(xiàn)互斥的PiPi進(jìn)程可描述為：進(jìn)程可描述為： repeat while TS(lock) do noloop； critical section; lock:= false; remainder section until false； 二二利用利用SwapSwap指令實(shí)現(xiàn)進(jìn)程互斥指令實(shí)現(xiàn)進(jìn)程互斥 1.1.SwapSwap指令指令 該指令稱(chēng)為交換指令。在微型機(jī)中該指令又稱(chēng)為該指令稱(chēng)為交換指令。在微型機(jī)中該指令又稱(chēng)為XCHGXCHG 指令，用于交換兩個(gè)字的內(nèi)容，可描述如下：指令，用于交換兩個(gè)字的內(nèi)容，可描述如下： Procedure Swap（var a,

14、b：boolean） var temp：boolean； begin temp:=a； a:=b； b:=temp； end 19651965年，荷蘭學(xué)者年，荷蘭學(xué)者DijkstraDijkstra提出的信號(hào)量機(jī)制是提出的信號(hào)量機(jī)制是 一種卓有成效的進(jìn)程同步工具。在長(zhǎng)期且廣泛的應(yīng)一種卓有成效的進(jìn)程同步工具。在長(zhǎng)期且廣泛的應(yīng) 用中，信號(hào)量機(jī)制又得到了很大的發(fā)展，它從整型用中，信號(hào)量機(jī)制又得到了很大的發(fā)展，它從整型 信號(hào)量經(jīng)記錄型信號(hào)量，進(jìn)而發(fā)展為信號(hào)量經(jīng)記錄型信號(hào)量，進(jìn)而發(fā)展為“信號(hào)量集信號(hào)量集” 機(jī)制?，F(xiàn)在信號(hào)量機(jī)制已被廣泛地應(yīng)用于單處理機(jī)機(jī)制?，F(xiàn)在信號(hào)量機(jī)制已被廣泛地應(yīng)用于單處理機(jī) 和多處理

15、機(jī)系統(tǒng)，以及計(jì)算機(jī)網(wǎng)絡(luò)中。和多處理機(jī)系統(tǒng)，以及計(jì)算機(jī)網(wǎng)絡(luò)中。 3.2.1 3.2.1 整型信號(hào)量機(jī)制整型信號(hào)量機(jī)制 3.2.2 3.2.2 記錄型信號(hào)量機(jī)制記錄型信號(hào)量機(jī)制 3.2.3 3.2.3 信號(hào)量集機(jī)制信號(hào)量集機(jī)制 一一整型信號(hào)量整型信號(hào)量 最初信號(hào)量最初信號(hào)量S S是一個(gè)整型變量，除初始化外，對(duì)信號(hào)量?jī)H是一個(gè)整型變量，除初始化外，對(duì)信號(hào)量?jī)H 能執(zhí)行兩個(gè)原子操作，即能執(zhí)行兩個(gè)原子操作，即wait(s)wait(s)和和signal(s),signal(s),這兩個(gè)原子操這兩個(gè)原子操 作以前多稱(chēng)為作以前多稱(chēng)為P P（s s）和）和V(s)V(s)操作。操作。 wait(s) while

16、s=0 do no-loop s:=s-1; signal(s) s:=s+1; 二二利用信號(hào)量實(shí)現(xiàn)互斥利用信號(hào)量實(shí)現(xiàn)互斥 進(jìn)程進(jìn)程P1P1 進(jìn)程進(jìn)程P2P2 wait（mutex）；）；wait（mutex）；）； critical section critical section signal（mutex）；）；signal（mutex）；）； remainder section remainder section 信號(hào)量信號(hào)量mutexmutex的初值為的初值為1 1，每個(gè)進(jìn)程在進(jìn)入臨界區(qū)時(shí)對(duì)信號(hào)，每個(gè)進(jìn)程在進(jìn)入臨界區(qū)時(shí)對(duì)信號(hào) 量執(zhí)行量執(zhí)行waitwait操作，待臨界區(qū)執(zhí)行完后執(zhí)行操作，

17、待臨界區(qū)執(zhí)行完后執(zhí)行signalsignal操作。操作。 3.2.13.2.1整型信號(hào)量機(jī)制整型信號(hào)量機(jī)制 三三利用信號(hào)量來(lái)描述前趨關(guān)系利用信號(hào)量來(lái)描述前趨關(guān)系 信號(hào)量信號(hào)量s s的初值為的初值為0 0，當(dāng)進(jìn)程，當(dāng)進(jìn)程P2P2先執(zhí)行必定阻塞，只有先執(zhí)行必定阻塞，只有 在在P1P1執(zhí)行完執(zhí)行完S1S1； signal(s)signal(s) ， P2P2 才被喚醒。才被喚醒。 進(jìn)程進(jìn)程P1P1 進(jìn)程進(jìn)程P2P2 S1;S1; wait(s) wait(s) signal(s)signal(s) S2;S2; S1S1 S2S2 S4S4 S6S6 S5S5 S3S3 a a b b c cd d

18、 e e f f g g var a,b,c,d,e,f,g:semaphore=0; begin parbegin begin s1；signal(a)；signal(b)；end； begin wait(a)；s2；signal(c)；signal(d)；end； begin wait(b)；s3；signal(e)；end； begin wait(c)；s4；signal(f)；end； begin wait(d)；s5；signal(g)；end； begin wait(e)； wait(f)； wait(g)；s6；end； parend end 習(xí)題（習(xí)題（P94-8P94-8）：

19、我們?yōu)槟撑R界區(qū)設(shè)置一把鎖）：我們?yōu)槟撑R界區(qū)設(shè)置一把鎖W W，當(dāng)，當(dāng)W=1W=1時(shí)，表時(shí)，表 示關(guān)鎖；示關(guān)鎖； W=0W=0表示鎖已打開(kāi)。試寫(xiě)出開(kāi)鎖原語(yǔ)和關(guān)鎖原語(yǔ)，并表示鎖已打開(kāi)。試寫(xiě)出開(kāi)鎖原語(yǔ)和關(guān)鎖原語(yǔ)，并 利用它們?nèi)?shí)現(xiàn)互斥。利用它們?nèi)?shí)現(xiàn)互斥。 3.2.13.2.1整型信號(hào)量機(jī)制整型信號(hào)量機(jī)制 解：解： 開(kāi)鎖原語(yǔ)開(kāi)鎖原語(yǔ) unlock(W):unlock(W):W:=0;W:=0; 關(guān)鎖原語(yǔ)關(guān)鎖原語(yǔ) lock(W):lock(W):while W=1 do no_op;while W=1 do no_op; W=1;W=1; 利用開(kāi)關(guān)鎖原語(yǔ)實(shí)現(xiàn)互斥利用開(kāi)關(guān)鎖原語(yǔ)實(shí)現(xiàn)互斥: : var W:

20、 semaphore:=0;var W: semaphore:=0; beginbegin parbeginparbegin process : process : beginbegin repeatrepeat lock(W);lock(W); critical sectioncritical section unlock(W);unlock(W); remainder sectionremainder section until false;until false; procedure wait(s) begin s.count:=s.count-1; if s.count0 then B

21、lock(s. queue) end procedure signal(s) begin s.count:=s. count+1; if s. count=0 then Wakeup(s. queue); end if s. count buffer; V(mutex); V(full);/退出區(qū) P(full); P(mutex);/進(jìn)入?yún)^(qū) one unit =1表示讀者數(shù)不滿表示讀者數(shù)不滿RN個(gè)，本讀者可讀個(gè)，本讀者可讀*/ Swait (mx , 1 , 0 ) ; /*mx=1表示無(wú)寫(xiě)者在寫(xiě)，本讀者可讀表示無(wú)寫(xiě)者在寫(xiě)，本讀者可讀*/ perform read operation Ssignal (L , 1) ; until false ; end A正文 A數(shù)據(jù) A棧 共享 存 儲(chǔ) 器 B正文 B數(shù)據(jù) B棧 CreateFile