chapter3_進(jìn)程同步、通信與死鎖16-1

1、第第3章章進(jìn)程同步、通信與死鎖進(jìn)程同步、通信與死鎖n3.1 3.1 并發(fā)進(jìn)程并發(fā)進(jìn)程n3.2 3.2 臨界區(qū)管理臨界區(qū)管理n3.3 3.3 經(jīng)典的進(jìn)程同步問題經(jīng)典的進(jìn)程同步問題n3.4 3.4 管程和進(jìn)程通信管程和進(jìn)程通信n3.63.6死鎖死鎖n順序程序執(zhí)行、并發(fā)程序執(zhí)行順序程序執(zhí)行、并發(fā)程序執(zhí)行 輸入：輸入：計算：計算：輸出：輸出： t0 t1 t2 t3 t4 t5 t6tttI1三個程序并發(fā)執(zhí)行的前驅(qū)圖三個程序并發(fā)執(zhí)行的前驅(qū)圖I2I3C1C2C3P1P2P3時間時間:5個個t并行并行并行并行并行并行前驅(qū)關(guān)系前驅(qū)關(guān)系執(zhí)行順序執(zhí)行順序順序程序設(shè)計(2)n順序程序設(shè)計具有如下的特點：n 程序執(zhí)

2、行的順序性n 程序環(huán)境的封閉性n 程序執(zhí)行結(jié)果的確定性n 計算過程的可再現(xiàn)性順序程序設(shè)計(3) 順序程序設(shè)計的例順序程序設(shè)計的例 while(1) input，process，output 7878輸入機(jī)輸入機(jī)處理器處理器磁帶機(jī)磁帶機(jī)130130150150228228280280300300378378430430450450時時 間間處理器利用率：處理器利用率：52/(78+52+20)35%52/(78+52+20)35%順序程序設(shè)計(4)順序程序設(shè)計串行工作順序程序設(shè)計串行工作 i1p1o1i2p2o2順序程序設(shè)計(5)順序程序設(shè)計的優(yōu)缺點n順序程序設(shè)計的順序性、封閉性、確定性和再現(xiàn)性

3、給程序的編制、調(diào)試帶來很大方便，其缺點是計算機(jī)系統(tǒng)效率不高。進(jìn)程的并發(fā)性(1)n進(jìn)程執(zhí)行的并發(fā)性：一組進(jìn)程的執(zhí)行在時間上是重疊的n并發(fā)性舉例：例如：有兩個進(jìn)程A(a1、a2、a3)和B(b1、b2、b3)并發(fā)執(zhí)行 進(jìn)程的并發(fā)性(2)n從宏觀上看，并發(fā)性反映一個時間段中幾個進(jìn)程都在同一處理器上，處于運行還未運行結(jié)束狀態(tài)，n從微觀上看，任一時刻僅有一個進(jìn)程在處理器上運行。進(jìn)程的并發(fā)性(3)n并發(fā)的實質(zhì)是一個處理器在幾個進(jìn)程之間的多路復(fù)用，并發(fā)是對有限的物理資源強(qiáng)制行使多用戶共享，消除計算機(jī)部件之間的互等現(xiàn)象，以提高系統(tǒng)資源利用率。n并發(fā)程序設(shè)計:一個程序被分成若干可同時執(zhí)行的小程序,每個小程序及其

4、處理的數(shù)據(jù)組成一個進(jìn)程.并發(fā)進(jìn)程分類：無關(guān)的，交往的。n無關(guān)的并發(fā)進(jìn)程：一組并發(fā)進(jìn)程分別在不同的變量集合上操作，一個進(jìn)程的執(zhí)行與其他并發(fā)進(jìn)程的進(jìn)展無關(guān)。無關(guān)的并發(fā)進(jìn)程(2) 并發(fā)進(jìn)程的無關(guān)性是進(jìn)程的執(zhí)行與時間無關(guān)的一個充分條件，又稱為Bernstein條件。 無關(guān)的并發(fā)進(jìn)程(3) Bernstein條件：條件： R(pi)=a1,a2,an，程序pi在執(zhí)行期間引用的變量集 W(pi)=b1,b2,bm，程序pi在執(zhí)行期間改變的變量集 若 兩 個 程 序 的 變 量 集 交 集 之 和 為 空 集 ： R(p1)W(p2)R(p2)W(p1)W(p1)W(p2)= 則并發(fā)進(jìn)程的執(zhí)行與時間無關(guān)。無

5、關(guān)的并發(fā)進(jìn)程(4) 例如，有如下四條語句： S1: a := x + y S2: b := z + 1 S3: c := a b S4: w := c + 1 于是有：R(S1)=x,y ,R(S2)=z，R(S3)=a,b，R(S4)=c；W(S1)=a, W(S2)=b，W(S3)=c，W(S4)=w。 S1和S2可并發(fā)執(zhí)行，滿足Bernstein條件。其他語句并發(fā)執(zhí)行可能會產(chǎn)生與時間有關(guān)的錯誤。無關(guān)的并發(fā)進(jìn)程(5) 兩個無關(guān)的進(jìn)程并發(fā)執(zhí)行的例兩個無關(guān)的進(jìn)程并發(fā)執(zhí)行的例處理器利用率：處理器利用率：(52+42)/(78+52+20)63%(52+42)/(78+52+20)63%7878輸

6、入機(jī)輸入機(jī)處理器處理器磁帶機(jī)磁帶機(jī)130130150150228228280280300300378378430430450450時時 間間磁帶機(jī)磁帶機(jī)打印機(jī)打印機(jī)20206262170170320320交往的并發(fā)進(jìn)程(1)n交往的并發(fā)進(jìn)程：一組并發(fā)進(jìn)程共享某些變量，一個進(jìn)程的執(zhí)行可能影響其他并發(fā)進(jìn)程的結(jié)果。 并發(fā)程序設(shè)計的例子 while(1) input，send while(1) receive，process，send while(1) receive，output 處理器利用率處理器利用率：（52 * n） /（78*n+52+20）= 67%7878輸入機(jī)輸入機(jī)處理器處理器磁帶機(jī)磁

7、帶機(jī)130130150150228228306306208208286286384384364364時時 間間交往的并發(fā)進(jìn)程(2)并發(fā)程序設(shè)計n并發(fā)程序設(shè)計是：把一個程序設(shè)計成若干個可同時執(zhí)行的程序模塊的方法。n并發(fā)程序設(shè)計的特征： 并行性、 共享性、 制約性、 交互性。 交往的并發(fā)進(jìn)程交往的并發(fā)進(jìn)程(3)(3)并發(fā)程序設(shè)計的優(yōu)點并發(fā)程序設(shè)計的優(yōu)點對于單處理器系統(tǒng),可讓處理器和各I/O設(shè)備同時工作,發(fā)揮硬部件的并行能力。對于多處理器系統(tǒng),可讓各進(jìn)程在不同處理器上物理地并行，加快計算速度。簡化了程序設(shè)計任務(wù)。 交往的并發(fā)進(jìn)程(4)采用并發(fā)程序設(shè)計的目的n充分發(fā)揮硬件的并行性，提高系統(tǒng)效率。硬件能

8、并行工作僅有了提高效率的可能性，硬部件并行性的實現(xiàn)需要軟件技術(shù)去利用和發(fā)揮，這種軟件技術(shù)就是并發(fā)程序設(shè)計。n并發(fā)程序設(shè)計是多道程序設(shè)計的基礎(chǔ)，多道程序的實質(zhì)就是把并發(fā)程序設(shè)計引入到系統(tǒng)中。交往的并發(fā)進(jìn)程(5)與時間有關(guān)的錯誤與時間有關(guān)的錯誤n對于一組交往的并發(fā)進(jìn)程，執(zhí)行的相對速度無法相互控制，各種與時間有關(guān)的錯誤就可能出現(xiàn)。n與時間有關(guān)錯誤的表現(xiàn)形式：n結(jié)果不唯一n永遠(yuǎn)等待（結(jié)果不唯一）機(jī)票問題（結(jié)果不唯一）機(jī)票問題process Ti ( i = 1, 2 ) var Xi:integer;begin按旅客定票要求找到按旅客定票要求找到Aj；Xi := Aj;if Xi=1 then beg

9、in Xi:=Xi-1; Aj:=Xi;輸出一張票輸出一張票；endelse 輸出票已售完輸出票已售完；end;（永遠(yuǎn)等待）內(nèi)存管理問題（永遠(yuǎn)等待）內(nèi)存管理問題procedure borrow (var B:integer) begin if Bx then 申請進(jìn)程進(jìn)入等待隊列等主存資源申請進(jìn)程進(jìn)入等待隊列等主存資源 x:=x-B; 修改主存分配表，申請進(jìn)程獲得主存資源修改主存分配表，申請進(jìn)程獲得主存資源 end;procedure return (var B:integer) begin x:=x+B; 修改主存分配表修改主存分配表 釋放等主存資源的進(jìn)程釋放等主存資源的進(jìn)程 end;一一.

10、 .進(jìn)程同步的基本概念進(jìn)程同步的基本概念1.1.兩種形式的制約關(guān)系兩種形式的制約關(guān)系2.2.臨界資源、臨界區(qū)臨界資源、臨界區(qū)3.3.同步機(jī)制應(yīng)遵循的規(guī)則同步機(jī)制應(yīng)遵循的規(guī)則二二. .信號量機(jī)制與信號量機(jī)制與P P、V V操作操作1.1.整型信號量整型信號量2.2.記錄型信號量記錄型信號量返回目錄返回目錄3.2 3.2 進(jìn)程同步進(jìn)程同步進(jìn)程的交往：競爭與協(xié)作(1)n 并發(fā)進(jìn)程之間的競爭關(guān)系n 進(jìn)程的互斥n系統(tǒng)中的多個進(jìn)程之間彼此無關(guān)n 并發(fā)進(jìn)程之間的協(xié)作關(guān)系n 進(jìn)程的同步n系統(tǒng)中的多個進(jìn)程之間彼此相關(guān) 資源競爭的兩個控制問題：資源競爭的兩個控制問題： 一個是死鎖(Deadlock)問題， 一個是

11、饑餓(Starvation) 問題，既要解決饑餓問題，又要解決死鎖問題。進(jìn)程互斥進(jìn)程互斥(Mutual Exclusion)(Mutual Exclusion)進(jìn)程互斥：進(jìn)程互斥：進(jìn)程之間通過競爭系統(tǒng)某些資源產(chǎn)生的關(guān)進(jìn)程之間通過競爭系統(tǒng)某些資源產(chǎn)生的關(guān)系稱為間接制約關(guān)系系稱為間接制約關(guān)系，它們之間是通過某種“媒介”而產(chǎn)生了“關(guān)系”。(間接制約關(guān)系間接制約關(guān)系)進(jìn)程互斥進(jìn)程互斥指若干進(jìn)程要使用同一共享資源時，任何時刻最多允許一個進(jìn)程使用，其他進(jìn)程必須等待，直到占有資源的進(jìn)程釋放該資源。返回第二種是協(xié)作關(guān)系第二種是協(xié)作關(guān)系 進(jìn)程同步進(jìn)程同步指兩個以上進(jìn)程基于某個條件來協(xié)調(diào)它們的活動。一個進(jìn)程的執(zhí)行

12、依賴于協(xié)作進(jìn)程的消息或信號，當(dāng)一個進(jìn)程沒有得到來自于協(xié)作進(jìn)程的消息或信號時需等待，直到消息或信號到達(dá)才被喚醒。n進(jìn)程同步：進(jìn)程同步：進(jìn)程之間為了共同完成某項任務(wù)，或者協(xié)作完成，有意識彼此相互“交換信息”。如前分別將I、C和和P都看成是進(jìn)程都看成是進(jìn)程。(直接制約關(guān)系直接制約關(guān)系) 返回同同 步步互互 斥斥進(jìn)程進(jìn)程- -進(jìn)程進(jìn)程進(jìn)程進(jìn)程- -資源資源- -進(jìn)程進(jìn)程時間次序上受到某種限制時間次序上受到某種限制競爭到某一物理資源時競爭到某一物理資源時不允許進(jìn)程工作不允許進(jìn)程工作相互清楚對方的存在及作相互清楚對方的存在及作用，交換信息用，交換信息不一定清楚其進(jìn)程情況不一定清楚其進(jìn)程情況往往指有幾個進(jìn)程

13、共同完往往指有幾個進(jìn)程共同完成一個任務(wù)成一個任務(wù)往往指多個任務(wù)多個進(jìn)往往指多個任務(wù)多個進(jìn)程間通訊制約程間通訊制約例：生產(chǎn)與消費之間，發(fā)例：生產(chǎn)與消費之間，發(fā)送與接受之間，作者與讀送與接受之間，作者與讀者之間，供者與用者之間者之間，供者與用者之間例：交通十字路口，單例：交通十字路口，單軌火車的撥道岔軌火車的撥道岔同步與互斥的比較返回2 2、臨界資源、臨界區(qū)、臨界資源、臨界區(qū)臨界資源臨界資源 (critical resource(critical resource） 系統(tǒng)中某些資源一次只允許一個進(jìn)程使用，系統(tǒng)中某些資源一次只允許一個進(jìn)程使用，稱這樣的資源為臨界資源或互斥資源或共享變量。稱這樣的資源

14、為臨界資源或互斥資源或共享變量。臨界區(qū)（互斥區(qū)）：臨界區(qū)（互斥區(qū)）：critical sectioncritical section 在進(jìn)程中涉及到臨界資源的程序段叫在進(jìn)程中涉及到臨界資源的程序段叫臨界區(qū)臨界區(qū)簡稱簡稱CSCS 多個進(jìn)程的臨界區(qū)稱為多個進(jìn)程的臨界區(qū)稱為相關(guān)臨界區(qū)相關(guān)臨界區(qū)2 2、臨界資源、臨界區(qū)、臨界資源、臨界區(qū) 進(jìn)程的互斥（間接作用）進(jìn)程的互斥（間接作用）a := a +1 print (a)P1 互斥互斥a := a -1 print (a)P2互斥互斥If a 0then a := a +1else a:= a-1 P3互斥互斥2 2、臨界資源、臨界區(qū)、臨界資源、臨界區(qū)程

15、序程序 段段1共享變量共享變量程序程序 段段2程序程序 段段3n例例：有兩個進(jìn)程：有兩個進(jìn)程A A和和B B，它們共享一個變量，它們共享一個變量x x，且兩個進(jìn)程按，且兩個進(jìn)程按以下方式對變量以下方式對變量X X進(jìn)行訪問和修改進(jìn)行訪問和修改: : 其中其中R1R1和和R2R2為處理機(jī)中的兩個為處理機(jī)中的兩個寄存器。寄存器。A A與與B B均對均對X+1X+1，即，即X+2X+2。若按另一順序?qū)ψ兞窟M(jìn)行修改：若按另一順序?qū)ψ兞窟M(jìn)行修改：結(jié)果結(jié)果x x只加了只加了1 1。A: R1=X;B: R2=X;A: R1=R1+1; X=R1;B: R2=R2+1; X=R2;A: R1=X; R1=R1

16、+1; X=R1;B: R2=X; R2=R2+1; X=R2;（1 1）變量）變量X X必必需按臨界資源需按臨界資源處理。處理。（2 2）每個進(jìn)）每個進(jìn)程中訪問臨界程中訪問臨界資源的那段代資源的那段代碼稱為臨界區(qū)碼稱為臨界區(qū)2 2、臨界資源、臨界區(qū)、臨界資源、臨界區(qū)實現(xiàn)各進(jìn)程互斥進(jìn)入臨界區(qū)實現(xiàn)各進(jìn)程互斥進(jìn)入臨界區(qū) 進(jìn)程須進(jìn)程須在臨界區(qū)前面增加一段用于進(jìn)行上述檢在臨界區(qū)前面增加一段用于進(jìn)行上述檢查的代碼，稱為查的代碼，稱為進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū)(entry section)(entry section)。在臨界區(qū)。在臨界區(qū)后面加上一段稱為后面加上一段稱為退出區(qū)退出區(qū)(exit section)(exit

17、 section)的代碼的代碼While (1)While (1) 進(jìn)入?yún)^(qū)代碼進(jìn)入?yún)^(qū)代碼; ; 臨界區(qū)代碼臨界區(qū)代碼; ; 退出區(qū)代碼退出區(qū)代碼; ; 其余代碼其余代碼 ; ; 進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū)臨界區(qū)臨界區(qū)退出區(qū)退出區(qū)剩余區(qū)剩余區(qū)n要進(jìn)入臨界區(qū)的若干進(jìn)程必須滿足如下三個條件要進(jìn)入臨界區(qū)的若干進(jìn)程必須滿足如下三個條件：（1 1）一次只允許一個進(jìn)程進(jìn)入臨界區(qū)）一次只允許一個進(jìn)程進(jìn)入臨界區(qū)（2 2）如果有進(jìn)程在臨界區(qū)）如果有進(jìn)程在臨界區(qū), ,試圖進(jìn)入此臨界區(qū)的其他進(jìn)程等待試圖進(jìn)入此臨界區(qū)的其他進(jìn)程等待（3 3）進(jìn)入臨界區(qū)的進(jìn)程要在有限的時間內(nèi)退出）進(jìn)入臨界區(qū)的進(jìn)程要在有限的時間內(nèi)退出, ,以便讓等待隊以

18、便讓等待隊列中的一個進(jìn)程進(jìn)入列中的一個進(jìn)程進(jìn)入. .n解決臨界區(qū)（互斥）問題的原則：解決臨界區(qū)（互斥）問題的原則： 2 2、臨界資源、臨界區(qū)、臨界資源、臨界區(qū)3 3、同步機(jī)制應(yīng)遵循的規(guī)則、同步機(jī)制應(yīng)遵循的規(guī)則q有空讓進(jìn)有空讓進(jìn)( (空閑讓進(jìn)）空閑讓進(jìn)）: :當(dāng)無進(jìn)程處于臨界區(qū)時，當(dāng)無進(jìn)程處于臨界區(qū)時，表明臨界資源處于空閑狀態(tài)，應(yīng)允許一個請求進(jìn)表明臨界資源處于空閑狀態(tài)，應(yīng)允許一個請求進(jìn)入臨界區(qū)的進(jìn)程立即進(jìn)入自己的臨界區(qū)，以有效入臨界區(qū)的進(jìn)程立即進(jìn)入自己的臨界區(qū)，以有效地利用臨界資源。地利用臨界資源。q互斥（忙則等待）互斥（忙則等待）: :當(dāng)已有進(jìn)程進(jìn)入臨界區(qū)時，表當(dāng)已有進(jìn)程進(jìn)入臨界區(qū)時，表明臨界

19、資源正在被訪問，因而其他試圖進(jìn)入臨界明臨界資源正在被訪問，因而其他試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待，以保證對臨界資源的互斥訪區(qū)的進(jìn)程必須等待，以保證對臨界資源的互斥訪問。問。一、進(jìn)程同步的基本概念一、進(jìn)程同步的基本概念q算法可行算法可行: :對要求訪問臨界資源的進(jìn)程，應(yīng)保證在對要求訪問臨界資源的進(jìn)程，應(yīng)保證在有限時間內(nèi)能進(jìn)入自己的臨界區(qū)，以免陷入有限時間內(nèi)能進(jìn)入自己的臨界區(qū)，以免陷入“死等死等”狀態(tài)狀態(tài); ;當(dāng)進(jìn)程不能進(jìn)入自己的臨界區(qū)時，應(yīng)立即釋當(dāng)進(jìn)程不能進(jìn)入自己的臨界區(qū)時，應(yīng)立即釋放處理機(jī)，以免進(jìn)程陷入放處理機(jī)，以免進(jìn)程陷入“忙等忙等”。q擇一而入擇一而入: :一次只能進(jìn)入一個一次只能進(jìn)入一個一

20、、進(jìn)程同步的基本概念一、進(jìn)程同步的基本概念3 3、同步機(jī)制應(yīng)遵循的規(guī)則、同步機(jī)制應(yīng)遵循的規(guī)則返回返回解決臨界區(qū)（互斥）問題的方法：解決臨界區(qū)（互斥）問題的方法：n1. 軟件n2利用硬件方法解決進(jìn)程互斥問題（1）禁止中斷（2）專用機(jī)器指令n3信號量及原語 是機(jī)器指令的延伸，往往是為完成某些特定的功能而編制的一段系統(tǒng)程序。原語操作也稱做“原子操作”（atomic action），即一個操作中的所有動作要么全做，要么全不做。n執(zhí)行原語操作時，要屏蔽中斷，以保證其操作的不可分割性。臨界區(qū)管理的嘗試 (1)ninside1,inside2:Booleaninside1,inside2:Booleanni

21、nside1 := false; /inside1 := false; /* * P1 P1不在其臨界區(qū)內(nèi)不在其臨界區(qū)內(nèi) * */ /ninside2 := false; /inside2 := false; /* * P2 P2不在其臨界區(qū)內(nèi)不在其臨界區(qū)內(nèi) * */ /ncobegincobeginnprocess P1process P1n Begin Beginnwhile inside2 do begin end; while inside2 do begin end; * * * *ninside1 := true;inside1 := true;n臨界區(qū)臨界區(qū); ;ninside1

22、 := false;inside1 := false;n end; end;nprocess P2process P2n begin beginnwhile inside1 do begin end;while inside1 do begin end;ninside2 = true;inside2 = true;n臨界區(qū)臨界區(qū); ;ninside2 := false;inside2 := false;n end; end;ncoendcoend臨界區(qū)管理的嘗試 (2)ninside1,inside2:boolean;inside1,inside2:boolean;ninside1 := fa

23、lse; /inside1 := false; /* * P1 P1不在其臨界區(qū)內(nèi)不在其臨界區(qū)內(nèi) * */ /ninside2 := false; /inside2 := false; /* * P2 P2不在其臨界區(qū)內(nèi)不在其臨界區(qū)內(nèi) * */ /ncobegincobeginnprocess P1process P1n begin beginninside1 := true;inside1 := true;nwhile inside2 do begin end;while inside2 do begin end;n臨界區(qū)臨界區(qū); ;ninside1 := false;inside1 :=

24、false;n end; end;nprocess P2process P2n begin beginninside2 := true;inside2 := true;nwhile inside1 do begin end;while inside1 do begin end;n臨界區(qū)臨界區(qū); ;ninside2 := false;inside2 := false;n end; end; coend coendPeterson算法(1)nvar inside:array1.2 of boolean;var inside:array1.2 of boolean;nturn:integer;tur

25、n:integer;nturn := 1 or 2; turn := 1 or 2; ninside1 := false;inside1 := false;/ /* * P1 P1不在其臨界區(qū)內(nèi)不在其臨界區(qū)內(nèi) * */ /ninside2 := false;inside2 := false;/ /* * P2 P2不在其臨界區(qū)內(nèi)不在其臨界區(qū)內(nèi) * */ /Peterson算法(2)ncobegincobeginnprocess P1process P1n begin beginninside1:= true;inside1:= true;nturn := 2;turn := 2;nwhile

26、(inside2 and turn=2)while (inside2 and turn=2)n do begin end; do begin end;n臨界區(qū)臨界區(qū); ;ninside1 := false;inside1 := false;n end; end;Peterson算法(3)nprocess P2process P2n begin beginninside2 := true;inside2 := true;nturn := 1;turn := 1;nwhile (inside1 and turn=1)while (inside1 and turn=1)n do begin end;

27、 do begin end;n臨界區(qū)臨界區(qū); ;ninside2 := false;inside2 := false;n end; end;ncoendcoendPeterson算法(4)n用對turn的置值和while語句來限制每次只有一個進(jìn)程進(jìn)入臨界區(qū)；n進(jìn)程執(zhí)行完臨界區(qū)程序后，修改insidei 狀態(tài)使等待進(jìn)入臨界區(qū)的進(jìn)程可在有限時間內(nèi)進(jìn)入。n算法滿足臨界區(qū)管理的三個條件。實現(xiàn)臨界區(qū)實現(xiàn)臨界區(qū)管理的硬件設(shè)施的硬件設(shè)施n 關(guān)中斷n 測試并建立指令n 對換指令測試并建立指令(1) TS指令的處理過程: TS(x): 若x=true， 則x:=false； return true； 否則 re

28、turn false； TS指令管理臨界區(qū)時，可把一個臨界區(qū)與一個布爾變量s相連，由于變量s代表了臨界資源的狀態(tài)，可把它看成一把鎖。 測試并建立指令(2)s : boolean;s : boolean;s := true;beginbeginprocess Pi() /process Pi() /* * i = 1,2, i = 1,2,n ,n * */ / while(!TS(S) while(!TS(S)；/上鎖上鎖 臨界區(qū)臨界區(qū); s := true s := true；/開鎖開鎖 coendcoend;對換指令(1) 對換（對換（SwapSwap）指令）指令的功能是交換兩個字的內(nèi)容：

29、 Swap (a,b): temp:=a; a:=b; b:=temp;對換指令(2)lock : boolean;lock := false;process Pi /* i = 1,2,n */ pi : boolean;begin pi := true; do swap(lock, pi); while( pi )；臨界區(qū);swap(lock, pi);end;關(guān)中斷n實現(xiàn)互斥的最簡單方法之一n關(guān)中斷方法的缺點返回三、信號量機(jī)制n信號量機(jī)制是荷蘭科學(xué)家信號量機(jī)制是荷蘭科學(xué)家E.W.DijkstraE.W.Dijkstra在在19651965年提出的一種同步機(jī)制，也稱為年提出的一種同步機(jī)制，

30、也稱為P P、V V操作。由操作。由最初的整型信號量發(fā)展為記錄型信號量，進(jìn)而最初的整型信號量發(fā)展為記錄型信號量，進(jìn)而發(fā)展為信號量集。發(fā)展為信號量集。n整型信號量整型信號量n記錄型信號量記錄型信號量1 1、整型信號量、整型信號量n整型信號量整型信號量非負(fù)整數(shù)，除了初始化外，只能通過兩個非負(fù)整數(shù)，除了初始化外，只能通過兩個原子操作原子操作waitwait和和signalsignal（P P，V V）來訪問。）來訪問。nwaitwait和和signalsignal操作描述操作描述： wait(S)wait(S)： while Swhile S 0 do no-op 0 do no-op 測試有無可用

31、資源測試有無可用資源 S:=S-1; S:=S-1; 可用資源數(shù)減一個單位可用資源數(shù)減一個單位 signal(S): S:=S+1;signal(S): S:=S+1;n主要問題主要問題：只要：只要S S 0 0， waitwait操作就不斷地測試（盲等），操作就不斷地測試（盲等），因而，未做到因而，未做到“讓權(quán)等待讓權(quán)等待”。 2 2、記錄型信號量、記錄型信號量n基本思想基本思想 1、設(shè)置一個代表資源數(shù)目的整型變量、設(shè)置一個代表資源數(shù)目的整型變量value（資源（資源信號量）信號量） 2、設(shè)置一鏈表、設(shè)置一鏈表L用于鏈接所有等待的進(jìn)程用于鏈接所有等待的進(jìn)程n記錄型信號量的數(shù)據(jù)結(jié)構(gòu)記錄型信號量

32、的數(shù)據(jù)結(jié)構(gòu) Type semaphore=record value:integer; L: list of process; end2 2、記錄型信號量、記錄型信號量n P P、V V操作操作 除初始化外，僅能通過兩個標(biāo)準(zhǔn)的原子操除初始化外，僅能通過兩個標(biāo)準(zhǔn)的原子操作作wait(S)wait(S)和和signal(S)signal(S)來訪問。很長時間以來訪問。很長時間以來，這兩個操作一直被稱為來，這兩個操作一直被稱為P P、V V操作。操作。 原子操作原子操作（atomic actionatomic action）或簡稱）或簡稱“原原語語”(primitive)(primitive)：在執(zhí)行

33、上不可中斷的操作。：在執(zhí)行上不可中斷的操作。 2 2、記錄型信號量、記錄型信號量n P P、V V操作定義操作定義P(s) P(s) / /* *= wait(s)= wait(s)）* */ / s.value=s.value s.value=s.value; ; if (s.value 0) if (s.value 0) block(s.queue) block(s.queue) 該進(jìn)程狀態(tài)置為等待狀該進(jìn)程狀態(tài)置為等待狀態(tài)態(tài)將該進(jìn)程的將該進(jìn)程的PCBPCB插入相的插入相的等待隊列末尾等待隊列末尾s.queue;s.queue;2 2、記錄型信號量、記錄型信號量V(s) V(s) / /*

34、*=signal(s) =signal(s) * */ / s.value=s.value+; s.value=s.value+; if (s.value = 0) if (s.value 0 S0 表示有表示有S S個資源可用個資源可用S=0 S=0 表示無資源可用表示無資源可用S0 S0 則則 |S| |S| 表示表示S S等待隊列中的進(jìn)程個數(shù)等待隊列中的進(jìn)程個數(shù)2)2) P P、V V操作的含義操作的含義P(S):P(S):表示申請一個資源表示申請一個資源 V(S)V(S)：表示釋放一個資源。信號量的初值應(yīng)：表示釋放一個資源。信號量的初值應(yīng)0 0使用使用P, V操作實現(xiàn)互斥時應(yīng)注意兩點：

35、操作實現(xiàn)互斥時應(yīng)注意兩點： 在每個程序中用于實現(xiàn)互斥的P(mutex)和V(mutex)必須成對出現(xiàn)，即先做P，進(jìn)入臨界區(qū)；后做V，退出臨界區(qū)。 互斥信號量mutex的初值一般為1。三、信號量的應(yīng)用三、信號量的應(yīng)用n利用信號量實現(xiàn)進(jìn)程互斥利用信號量實現(xiàn)進(jìn)程互斥Process1:while (true) P(mutex); critical section; V(mutex); remainder section; while (true) P(mutex); critical section; V(mutex); remainder section; Process2:三、信號量的應(yīng)用三、信號

36、量的應(yīng)用例例: :三個進(jìn)程共用兩個三個進(jìn)程共用兩個I/OI/O緩沖區(qū)。緩沖區(qū)。n解：設(shè)用信號量解：設(shè)用信號量S S表示共享資源，表示共享資源，S S初始值為初始值為2 2 P(mutex)V(mutex)P1P2P3互斥區(qū)互斥區(qū)P(mutex)P(mutex)V(mutex)V(mutex)三、信號量的應(yīng)用三、信號量的應(yīng)用n利用信號量實現(xiàn)前驅(qū)關(guān)系利用信號量實現(xiàn)前驅(qū)關(guān)系P1P2三、信號量的應(yīng)用三、信號量的應(yīng)用設(shè)置一個信號量設(shè)置一個信號量S S，其，其初值為初值為0 0, ,P1；V(S);P(S)；P2;如此即可實現(xiàn)先執(zhí)行如此即可實現(xiàn)先執(zhí)行P1P1，再執(zhí)行，再執(zhí)行P2P2三、信號量的應(yīng)用三、信號

37、量的應(yīng)用Eg: Eg: 設(shè)設(shè)S1,S2,S3,S4S1,S2,S3,S4為一組合作進(jìn)程，其前趨圖如為一組合作進(jìn)程，其前趨圖如圖所示，用圖所示，用P P、V V操作實現(xiàn)其同步。操作實現(xiàn)其同步。 var a,b,c,d:semaphore:=0,0,0,0; /*表示進(jìn)程是否執(zhí)行完表示進(jìn)程是否執(zhí)行完*/ main() cobegin s1(); s2(); s3(); s4(); coend s1s2s3s4abcdS1() v(a); S2() v(b); v(c); S3() p(a); p(b); v(d); S4() p(c); p(d); . n利用信號量實現(xiàn)前驅(qū)關(guān)系（同步例子）利用信號

38、量實現(xiàn)前驅(qū)關(guān)系（同步例子）三、信號量的應(yīng)用三、信號量的應(yīng)用思考：思考：已知一個求值公式（已知一個求值公式（A2/3BA2/3B）/ /（B+5AB+5A），），若若A A、B B已賦值，畫出該公式求值過程的前趨圖已賦值，畫出該公式求值過程的前趨圖 n利用信號量實現(xiàn)前驅(qū)關(guān)系（同步例子）利用信號量實現(xiàn)前驅(qū)關(guān)系（同步例子）三、信號量的應(yīng)用三、信號量的應(yīng)用n利用信號量實現(xiàn)同步利用信號量實現(xiàn)同步n有有A A、B B兩進(jìn)程，兩進(jìn)程，A A進(jìn)程從卡片機(jī)讀信息入緩沖進(jìn)程從卡片機(jī)讀信息入緩沖區(qū)，區(qū)，B B進(jìn)程負(fù)責(zé)加工讀進(jìn)緩沖區(qū)的卡片進(jìn)程負(fù)責(zé)加工讀進(jìn)緩沖區(qū)的卡片n解：設(shè)信號量解：設(shè)信號量S1S1：緩沖區(qū)中有否可供

39、加工的：緩沖區(qū)中有否可供加工的信息，初始值為信息，初始值為0 0；信號量；信號量S2S2：緩沖區(qū)是否為：緩沖區(qū)是否為空，初始值為空，初始值為1 1。三、信號量的應(yīng)用三、信號量的應(yīng)用n利用信號量實現(xiàn)同步舉例利用信號量實現(xiàn)同步舉例返回返回3.3 3.3 經(jīng)典進(jìn)程的同步問題經(jīng)典進(jìn)程的同步問題 在多道程序環(huán)境下，進(jìn)程同步問題十分在多道程序環(huán)境下，進(jìn)程同步問題十分重要，出現(xiàn)一系列經(jīng)典的進(jìn)程同步問題，其中重要，出現(xiàn)一系列經(jīng)典的進(jìn)程同步問題，其中有代表性有有代表性有：生產(chǎn)者生產(chǎn)者消費者問題消費者問題哲學(xué)家進(jìn)餐問題哲學(xué)家進(jìn)餐問題讀者讀者寫者問題寫者問題返回目錄返回目錄1 1、“生產(chǎn)者生產(chǎn)者消費者消費者”問問題

40、題 單緩沖區(qū)單緩沖區(qū)：生產(chǎn)者進(jìn)程：生產(chǎn)者進(jìn)程P P和消費者進(jìn)程和消費者進(jìn)程C C共用一個共用一個緩沖區(qū)，緩沖區(qū)，P P生產(chǎn)產(chǎn)品放入緩沖區(qū)，生產(chǎn)產(chǎn)品放入緩沖區(qū)，C C從緩沖區(qū)取產(chǎn)從緩沖區(qū)取產(chǎn)品來消費。品來消費。 消費者消費者生產(chǎn)者生產(chǎn)者1 1、“生產(chǎn)者生產(chǎn)者消費者消費者”問問題題u單緩沖區(qū)的同步問題單緩沖區(qū)的同步問題 P P進(jìn)程不能往進(jìn)程不能往“滿滿”的緩沖區(qū)中放產(chǎn)品，設(shè)置信的緩沖區(qū)中放產(chǎn)品，設(shè)置信號量為號量為emptyemptyC C進(jìn)程不能從進(jìn)程不能從“空空”的緩沖區(qū)中取產(chǎn)品，設(shè)置信的緩沖區(qū)中取產(chǎn)品，設(shè)置信號量號量fullfullu單緩沖區(qū)的互斥問題單緩沖區(qū)的互斥問題P P、C C進(jìn)程不能同

41、時使用緩沖區(qū)進(jìn)程不能同時使用緩沖區(qū)1 1、“生產(chǎn)者生產(chǎn)者消費者消費者”問問題題u單緩沖區(qū)的生產(chǎn)者單緩沖區(qū)的生產(chǎn)者消費者問題解消費者問題解P： C：while (true) while (true) 生產(chǎn)一個產(chǎn)品生產(chǎn)一個產(chǎn)品; P(full); P(empty) ; 從緩沖區(qū)取產(chǎn)品從緩沖區(qū)取產(chǎn)品; 送產(chǎn)品到緩沖區(qū)送產(chǎn)品到緩沖區(qū); V(empty); V(full); 消費產(chǎn)品消費產(chǎn)品; ;empty初值為初值為1，full初值為初值為01 1、“生產(chǎn)者生產(chǎn)者消費者消費者”問問題題 多個緩沖區(qū)多個緩沖區(qū)：若干個生產(chǎn)者進(jìn)程：若干個生產(chǎn)者進(jìn)程P1, P2, , Pn，若干個消費者進(jìn)程若干個消費者進(jìn)程C

42、l，C2，Cm。它們通過。它們通過一個有界緩沖池一個有界緩沖池(k個個)聯(lián)系。聯(lián)系。 .PC生產(chǎn)者生產(chǎn)者消費者消費者k kk k個個 BufferBuffern nm m1 1、“生產(chǎn)者生產(chǎn)者消費者消費者”問問題題u多緩沖區(qū)的同步互斥問題多緩沖區(qū)的同步互斥問題 n同步同步：當(dāng)緩沖池已放滿了產(chǎn)品時：當(dāng)緩沖池已放滿了產(chǎn)品時( (供過于求供過于求) )，生產(chǎn)者進(jìn)程必須等待；當(dāng)緩沖池已空時生產(chǎn)者進(jìn)程必須等待；當(dāng)緩沖池已空時( (供供不應(yīng)求不應(yīng)求) )，消費者進(jìn)程應(yīng)等待。，消費者進(jìn)程應(yīng)等待。n互斥互斥：所有進(jìn)程應(yīng)互斥使用緩沖池這一臨界：所有進(jìn)程應(yīng)互斥使用緩沖池這一臨界資源。資源。u多緩沖區(qū)的生產(chǎn)者多緩沖

43、區(qū)的生產(chǎn)者消費者問題解法消費者問題解法1 1、“生產(chǎn)者生產(chǎn)者消費者消費者”問問題題 設(shè)置兩個同步信號量及一個互斥信號量設(shè)置兩個同步信號量及一個互斥信號量nempty：說明空緩沖單元的數(shù)目，其初值為有界緩沖區(qū)的說明空緩沖單元的數(shù)目，其初值為有界緩沖區(qū)的 大小大小n。nfull：說明滿緩沖單元的數(shù)目（即產(chǎn)品數(shù)目），其初值為說明滿緩沖單元的數(shù)目（即產(chǎn)品數(shù)目），其初值為0。nmutex: 說明該有界緩沖區(qū)是一臨界資源，必須互斥使用，說明該有界緩沖區(qū)是一臨界資源，必須互斥使用，其初值為其初值為1。1 1、“生產(chǎn)者生產(chǎn)者消費者消費者”問問題題u多緩沖區(qū)的生產(chǎn)者多緩沖區(qū)的生產(chǎn)者消費者問題解法消費者問題解法思

44、考：思考：P操作的順序可換嗎？操作的順序可換嗎？u“生產(chǎn)者生產(chǎn)者消費者消費者”問題的算法描述問題的算法描述 semaphore full=0; /*表示滿緩沖區(qū)的數(shù)目表示滿緩沖區(qū)的數(shù)目*/ semaphore empty=n; /*表示空緩沖區(qū)的數(shù)目表示空緩沖區(qū)的數(shù)目*/ semaphore mutex=1; /*表示對緩沖區(qū)進(jìn)程操作的互斥表示對緩沖區(qū)進(jìn)程操作的互斥信號量信號量*/Main() cobegin producer(); consumer(); coend 1 1、“生產(chǎn)者生產(chǎn)者消費者消費者”問問題題 while(true) 生產(chǎn)一個產(chǎn)品生產(chǎn)一個產(chǎn)品; P(empty); P(mu

45、tex); 將一個產(chǎn)品送入緩沖將一個產(chǎn)品送入緩沖區(qū)；區(qū)； V(mutex); V(full);Producer() while(true) p(full); P(mutex); 從緩沖區(qū)取走一個產(chǎn)品從緩沖區(qū)取走一個產(chǎn)品; V(mutex);V(empty); 消費一個產(chǎn)品；消費一個產(chǎn)品； Consumer()1 1、“生產(chǎn)者生產(chǎn)者消費者消費者”問問題題u“生產(chǎn)者生產(chǎn)者消費者消費者”問題的算法描述問題的算法描述u “生產(chǎn)者生產(chǎn)者- -消費者消費者”問題中應(yīng)注意問題中應(yīng)注意1.1.互斥信號量的互斥信號量的P,VP,V操作在每一程序中必須成對出現(xiàn)操作在每一程序中必須成對出現(xiàn). .1 1、“生產(chǎn)者生產(chǎn)

46、者消費者消費者”問問題題2.2.資源信號量資源信號量(full,empty)(full,empty)也必須成對出現(xiàn)也必須成對出現(xiàn), ,但可分但可分別處于不同的程序中別處于不同的程序中. .3.3.多個多個P P操作順序不能顛倒操作順序不能顛倒. .4.4.先執(zhí)行資源信號量的先執(zhí)行資源信號量的P P操作操作, ,再執(zhí)行互斥信號量的再執(zhí)行互斥信號量的P P操作操作, ,否則可能引起進(jìn)程死鎖否則可能引起進(jìn)程死鎖. .1 1、“生產(chǎn)者生產(chǎn)者消費者消費者”問問題題5.5.它是一個同步問題：它是一個同步問題： （1 1）消費者想要取產(chǎn)品，有界緩沖區(qū)中至少有一個）消費者想要取產(chǎn)品，有界緩沖區(qū)中至少有一個單元

47、是滿的。單元是滿的。 （2 2）生產(chǎn)者想要放產(chǎn)品，有界緩沖區(qū)中至少有一個）生產(chǎn)者想要放產(chǎn)品，有界緩沖區(qū)中至少有一個是空的。是空的。u “生產(chǎn)者生產(chǎn)者- -消費者消費者”問題中應(yīng)注意問題中應(yīng)注意返回返回6.6.它是一互斥問題它是一互斥問題 有界緩沖區(qū)是臨界資源，因此，各生產(chǎn)者進(jìn)程和各有界緩沖區(qū)是臨界資源，因此，各生產(chǎn)者進(jìn)程和各消費者進(jìn)程必須互斥執(zhí)行。消費者進(jìn)程必須互斥執(zhí)行。2 2、“哲學(xué)家進(jìn)餐哲學(xué)家進(jìn)餐”問問題題n5 5個哲學(xué)家圍坐在圓桌旁，個哲學(xué)家圍坐在圓桌旁，每人面前有一只空盤子，每每人面前有一只空盤子，每2 2人之間放一只筷子，如圖所人之間放一只筷子，如圖所示。示。n為了就餐，每個哲學(xué)家為

48、了就餐，每個哲學(xué)家必須拿到兩只筷子，并且只必須拿到兩只筷子，并且只能直接從自己的左邊或右邊能直接從自己的左邊或右邊去取筷子。去取筷子。 問題描述問題描述 semaphore stick5=1,1,1,1,1; /*分別表示分別表示5支筷子支筷子*/ Main() cobegin philosopher(0); philosopher(1); philosopher(2); philosopher(3); philosopher(4); coend 哲學(xué)家進(jìn)餐問題的解決哲學(xué)家進(jìn)餐問題的解決2 2、“哲學(xué)家進(jìn)餐哲學(xué)家進(jìn)餐”問問題題2 2、“哲學(xué)家進(jìn)餐哲學(xué)家進(jìn)餐”問問題題哲學(xué)家哲學(xué)家i i的活動為：

49、的活動為： void philosopher (int i) while (true) 思考；思考； P(chopsticki) ； /取左邊筷子取左邊筷子 P(chopstick(i+1) % 5) ； /取右邊筷子取右邊筷子 進(jìn)食；進(jìn)食； V(chopsticki) ； /放左邊筷子放左邊筷子 V(chopstick(i+1) % 5) ； /放右邊筷子放右邊筷子 哲學(xué)家進(jìn)餐問題的解決哲學(xué)家進(jìn)餐問題的解決2 2、“哲學(xué)家進(jìn)餐哲學(xué)家進(jìn)餐”問問題題如果：如果：5 5人同時拿起左邊筷子，再企圖人同時拿起左邊筷子，再企圖拿起右邊的筷子時，會如何？拿起右邊的筷子時，會如何？死鎖！死鎖！ 2 2、“哲

50、學(xué)家進(jìn)餐哲學(xué)家進(jìn)餐”問問題題 為防止死鎖發(fā)生可采取的措施：為防止死鎖發(fā)生可采取的措施：n最多允許最多允許4 4個哲學(xué)家同時坐在桌子周圍個哲學(xué)家同時坐在桌子周圍n僅當(dāng)一個哲學(xué)家左右兩邊的筷子都可用時，才僅當(dāng)一個哲學(xué)家左右兩邊的筷子都可用時，才允許他拿筷子允許他拿筷子n給所有哲學(xué)家編號，奇數(shù)號的哲學(xué)家必須首先給所有哲學(xué)家編號，奇數(shù)號的哲學(xué)家必須首先拿左邊的筷子，偶數(shù)號的哲學(xué)家則反之拿左邊的筷子，偶數(shù)號的哲學(xué)家則反之返回返回3 3、“讀者讀者寫者寫者”問題問題問題描述：問題描述： 多個進(jìn)程訪問一個共享數(shù)據(jù)對象（如數(shù)據(jù)文件或記錄以及內(nèi)存和多個進(jìn)程訪問一個共享數(shù)據(jù)對象（如數(shù)據(jù)文件或記錄以及內(nèi)存和寄存器）

51、寄存器）, ,為該類問題建立一個通用模型。其中，為該類問題建立一個通用模型。其中，readerreader進(jìn)程只能讀，進(jìn)程只能讀，writer writer 進(jìn)程要求寫或修改。允許多個讀進(jìn)程同時讀數(shù)據(jù)，但絕不允進(jìn)程要求寫或修改。允許多個讀進(jìn)程同時讀數(shù)據(jù)，但絕不允許一個許一個writerwriter進(jìn)程與其它的進(jìn)程與其它的readerreader進(jìn)程或進(jìn)程或writerwriter進(jìn)程同時訪問，即進(jìn)程同時訪問，即writerwriter進(jìn)程必須與其它進(jìn)程互斥訪問共享對象。進(jìn)程必須與其它進(jìn)程互斥訪問共享對象。 如一個聯(lián)網(wǎng)售票系統(tǒng)如一個聯(lián)網(wǎng)售票系統(tǒng): :數(shù)據(jù)的查詢和更新非常頻繁數(shù)據(jù)的查詢和更新非常頻

52、繁, ,必然有多個進(jìn)必然有多個進(jìn)程試圖查詢或修改同一條記錄的情況程試圖查詢或修改同一條記錄的情況, ,多個進(jìn)程同時查詢多個進(jìn)程同時查詢( (讀讀) )是允許是允許的的, ,但是不允許一個正在修改更新數(shù)據(jù)庫但是不允許一個正在修改更新數(shù)據(jù)庫( (寫寫) )的進(jìn)程工作的同時其他的進(jìn)程工作的同時其他修改修改( (寫寫) )或查詢或查詢( (讀讀) )發(fā)生發(fā)生, ,否則可能一票多售否則可能一票多售. .3 3、“讀者讀者寫者寫者”問題問題分析分析: :n有兩組并發(fā)進(jìn)程有兩組并發(fā)進(jìn)程: : 讀者和寫者讀者和寫者，共享一組數(shù)據(jù)區(qū)共享一組數(shù)據(jù)區(qū) 要求：要求：n允許多個讀者同時執(zhí)行讀操作允許多個讀者同時執(zhí)行讀操

53、作n不允許讀者、寫者同時操作不允許讀者、寫者同時操作n不允許多個寫者同時操作不允許多個寫者同時操作如果用生產(chǎn)者消費者的方法來嚴(yán)格互斥任何如果用生產(chǎn)者消費者的方法來嚴(yán)格互斥任何讀者寫者進(jìn)程讀者寫者進(jìn)程, ,可以保證數(shù)據(jù)更新的正確性可以保證數(shù)據(jù)更新的正確性. .但對查詢不利但對查詢不利. . (與生產(chǎn)與生產(chǎn)-消費的異同消費的異同)3 3、“讀者讀者寫者寫者”問題問題讀者讀者-寫者問題有兩種類型：寫者問題有兩種類型：n解法解法1 1：讀者優(yōu)先讀者優(yōu)先 只要有一個讀者存在，不管只要有一個讀者存在，不管有否寫者請求，后續(xù)讀者都可以執(zhí)行讀過程。有否寫者請求，后續(xù)讀者都可以執(zhí)行讀過程。 n解法解法2 2：讀

54、寫平等讀寫平等 即一旦有寫者到達(dá)，后續(xù)的即一旦有寫者到達(dá)，后續(xù)的讀者必須等待，無論是否有讀者在讀。讀者必須等待，無論是否有讀者在讀。s寫者優(yōu)先寫者優(yōu)先。只要有一個寫者請求，讀者就要等。只要有一個寫者請求，讀者就要等待，直到所有寫者退出。待，直到所有寫者退出。返回返回設(shè)置一個共享變量和兩個信號量：設(shè)置一個共享變量和兩個信號量：n共享變量共享變量ReadcountReadcount：記錄當(dāng)前正在讀數(shù)據(jù)集的：記錄當(dāng)前正在讀數(shù)據(jù)集的讀進(jìn)程數(shù)目，初值為讀進(jìn)程數(shù)目，初值為0 0。n讀互斥信號量讀互斥信號量Rmutex Rmutex ：表示讀進(jìn)程互斥地訪問：表示讀進(jìn)程互斥地訪問共享變量共享變量readcou

55、ntreadcount，初值為，初值為1.1.n寫互斥信號量寫互斥信號量wmutexwmutex：表示寫進(jìn)程與其它進(jìn)程：表示寫進(jìn)程與其它進(jìn)程（讀、寫）互斥地訪問數(shù)據(jù)集，初值為（讀、寫）互斥地訪問數(shù)據(jù)集，初值為1.1.3 3、“讀者讀者寫者寫者”問題問題讀者優(yōu)讀者優(yōu)先先semaphore rmutex=1; semaphore wmutex=1; int readcount=0; Main() cobegin reader(); writer(); coend 3 3、“讀者讀者寫者寫者”問題問題讀者優(yōu)讀者優(yōu)先先 while(true) while(true) p(rmutex);p(rmute

56、x); if(readcount= =1) if(readcount= =1) p(wmutexp(wmutex);/);/* *第一位讀者阻止寫者第一位讀者阻止寫者* */ / readcount+; readcount+; V(rmutex);V(rmutex); 讀數(shù)據(jù)集；讀數(shù)據(jù)集； p(rmutex);p(rmutex); readcount-; readcount-; if(readcount= =0) if(readcount= =0) v(wmutexv(wmutex);/);/* *第末位讀者允許寫者進(jìn)第末位讀者允許寫者進(jìn)* */ / V(rmutex);V(rmutex);

57、reader() while(true) p(wmutex); / /* *阻止其它進(jìn)程（讀、寫）進(jìn)阻止其它進(jìn)程（讀、寫）進(jìn)* */ / 寫數(shù)據(jù)集；寫數(shù)據(jù)集； V(wmutex); / /* *允許其它進(jìn)程（讀、寫）進(jìn)允許其它進(jìn)程（讀、寫）進(jìn)* */ /writer()3 3、“讀者讀者寫者寫者”問題問題讀寫平讀寫平等等為了提高寫者的優(yōu)先級為了提高寫者的優(yōu)先級，我們增加一個信號量，我們增加一個信號量w w，用，用以在寫進(jìn)程到達(dá)時封鎖后續(xù)的讀者進(jìn)程。相應(yīng)的以在寫進(jìn)程到達(dá)時封鎖后續(xù)的讀者進(jìn)程。相應(yīng)的控制算法如下：控制算法如下： BEGINBEGIN integer rmutex, wmutex,

58、rc, integer rmutex, wmutex, rc, w;w; rmutex:=1; rmutex:=1; wmutex:=1; wmutex:=1; rc:=0; rc:=0; w:=1; w:=1; BEGINBEGIN P(w);P(w); P(rmutex); P(rmutex); rc:=rc+1; rc:=rc+1; IF rc=1 THEN P(wmutex); IF rc=1 THEN P(wmutex); V(rmutex); V(rmutex); V(w);V(w); Reading the FILE; Reading the FILE; P(rmutex); P

59、(rmutex); rc:=rc-1; rc:=rc-1; IF rc=0 THEN V(wmutex); IF rc=0 THEN V(wmutex); V(rmutex); V(rmutex);END; END; readerBEGINBEGIN P(w);P(w); P(wmutex); P(wmutex); Writeing the FILE; Writeing the FILE; V(wmutex); V(wmutex); V(w);V(w);END;END;COEND COEND Writer返回返回3、“讀者讀者寫者寫者”問題問題寫者優(yōu)先寫者優(yōu)先Const readcount,w

60、ritecount:integerVar x,y,z,rsem,wrem:=semaphoreReader:BeginRepeat P(z); P(rsem);P(x); Readcount:= Readcount+1; If Readcount=1 then P(wsem);V(x); V(rsem); V(z);讀數(shù)據(jù)讀數(shù)據(jù);P(x);Readcount:=readcount-1;If readcount=0 then V(wsem);V(x);Forever;End;Writer:BeginRepeatP(y); Writecount:=writecount+1; If writecou