操作系統(tǒng) 第3章

1、第三章第三章 進程的同步與通信進程的同步與通信3.1 進程同步的基本概念3.2 信號量機制3.3 經(jīng)典進程同步問題3.4 管程機制3.5 進程通信*進程同步的任務(wù)：進程同步的任務(wù)： 使并發(fā)執(zhí)行的諸進程之間能有效地共享資源和相互合作，使并發(fā)執(zhí)行的諸進程之間能有效地共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性。從而使程序的執(zhí)行具有可再現(xiàn)性。*多道程序環(huán)境下，諸進程之間的關(guān)系：多道程序環(huán)境下，諸進程之間的關(guān)系： 相互獨立相互獨立 每個進程既不影響系統(tǒng)中其它進程的執(zhí)行，也不被其它進程影響。每個進程既不影響系統(tǒng)中其它進程的執(zhí)行，也不被其它進程影響。彼此有關(guān)彼此有關(guān) 具體表現(xiàn)為：具體表現(xiàn)為： 1 1）

2、進程之間由于共享資源而產(chǎn)生的間接制約關(guān)系。）進程之間由于共享資源而產(chǎn)生的間接制約關(guān)系。 2 2）進程之間由于相互合作而產(chǎn)生的直接制約關(guān)系。）進程之間由于相互合作而產(chǎn)生的直接制約關(guān)系。進程同步進程同步 解決解決1 1）的方法是：保證諸進程）的方法是：保證諸進程互斥互斥訪問臨界資源。訪問臨界資源。 解決解決2 2）的方法是：協(xié)調(diào)相互合作的諸進程的執(zhí)行次序。）的方法是：協(xié)調(diào)相互合作的諸進程的執(zhí)行次序。 -狹義的狹義的同步同步3.1 進程同步的基本概念進程同步的基本概念一、臨界資源一、臨界資源二、臨界區(qū)二、臨界區(qū)三、利用軟件方法解決進程互斥問題三、利用軟件方法解決進程互斥問題四、利用硬件方法解決進程互

3、斥問題四、利用硬件方法解決進程互斥問題臨界資源：臨界資源：一段時間內(nèi)只允許一個進程訪問的資源。一段時間內(nèi)只允許一個進程訪問的資源。要求：要求：共享臨界資源的諸進程必須共享臨界資源的諸進程必須互斥互斥訪問臨界資源。訪問臨界資源。原因：原因： 例：生產(chǎn)者例：生產(chǎn)者-消費者問題（消費者問題（P62） 生產(chǎn)者（生產(chǎn)者（producer） 放產(chǎn)品；放產(chǎn)品；counter:=counter+1; 消費者（消費者（consumer） 取產(chǎn)品；取產(chǎn)品；counter:=counter-1; 3.1 進程同步的基本概念進程同步的基本概念一、臨界資源一、臨界資源 生產(chǎn)者生產(chǎn)者counter:=counter+1;

4、-CS 1 register1:=counter;2 register1:= register1+1;3 counter:= register1; 消費者消費者counter:=counter-1;-CS 4 register2:=counter;5 register2:= register2-1;6 counter:= register2;機器語言形式為：機器語言形式為：由于生產(chǎn)者和消費者并發(fā)運行，且共享變量由于生產(chǎn)者和消費者并發(fā)運行，且共享變量 counter ，造成：，造成： 可能性可能性CPU執(zhí)行順序執(zhí)行順序counter的值的值（初值為（初值為5）A1234565正確正確B45612

5、35正確正確C1245364不正確不正確D4512366不正確不正確不是不是A、B 不正確不正確 3.1 進程同步的基本概念進程同步的基本概念一、臨界資源一、臨界資源結(jié)論：結(jié)論： counter是臨界資源，生產(chǎn)者和消費者應(yīng)互斥訪問。是臨界資源，生產(chǎn)者和消費者應(yīng)互斥訪問。 即：雖然生產(chǎn)者、消費者并發(fā)執(zhí)行，但在執(zhí)行即：雖然生產(chǎn)者、消費者并發(fā)執(zhí)行，但在執(zhí)行counter的的 加加1、減、減1的語句時，只能順序進行。的語句時，只能順序進行。 即：只能按可能性中即：只能按可能性中A或或B的順序進行，絕不能交替進行。的順序進行，絕不能交替進行。臨界資源實例：臨界資源實例： 硬件中的打印機、磁帶機等，軟件中

6、的變量、隊列、緩硬件中的打印機、磁帶機等，軟件中的變量、隊列、緩 沖區(qū)等。沖區(qū)等。 3.1 進程同步的基本概念進程同步的基本概念一、臨界資源一、臨界資源臨界區(qū)（臨界區(qū)（CS）：）：每個進程中訪問臨界資源的那段代碼。每個進程中訪問臨界資源的那段代碼。要求：要求：為實現(xiàn)對臨界資源的互斥訪問，應(yīng)保證諸進程為實現(xiàn)對臨界資源的互斥訪問，應(yīng)保證諸進程互斥互斥進入各自進入各自 的臨界區(qū)。（兩個互斥是一致的）的臨界區(qū)。（兩個互斥是一致的）模型：模型：準則：準則：1.空閑讓進空閑讓進 2.忙則等待忙則等待 3.有限等待有限等待 4.讓權(quán)等待讓權(quán)等待 repeat entry section 進入?yún)^(qū)：進入?yún)^(qū)：檢查

7、是否可以進入臨界區(qū)檢查是否可以進入臨界區(qū) critical section 臨界區(qū)：臨界區(qū)：對臨界資源進行操作對臨界資源進行操作 exit section 退出區(qū)：退出區(qū)：釋放臨界資源以供其它進程使用釋放臨界資源以供其它進程使用 remainder section 剩余區(qū)：剩余區(qū)：until false 3.1 進程同步的基本概念進程同步的基本概念二、臨界區(qū)（二、臨界區(qū)（Critical Section）問題描述：問題描述： 兩個進程兩個進程P0和和P1，共享一個臨界資源，共享一個臨界資源R。算法算法1 （turn=j，表示允許進程，表示允許進程Pj進入臨界區(qū)）進入臨界區(qū)） 3.1 進程同步的

8、基本概念進程同步的基本概念三、利用軟件方法解決進程互斥問題三、利用軟件方法解決進程互斥問題Process P0 : repeat while turn 0 do no-op; critical section turn:=1; remainder section until false; Process P1 : repeat while turn 1 do no-op; critical section turn:=0; remainder section until false; 缺點：缺點：強制兩進程輪流進入臨界區(qū)；不能保證強制兩進程輪流進入臨界區(qū)；不能保證“空閑讓進空閑讓進”。算法算法

9、2 var flag:array0.1 of boolean; （flagi=true，Pi在臨界區(qū)）在臨界區(qū)）Process P0 : repeat while flag1 do no-op; flag0:=true; critical section flag0:=false; remainder section until false; 缺點：缺點：解決了解決了“空閑讓進空閑讓進”，但又違背了，但又違背了“忙則等待忙則等待”。Process P1 : repeat while flag0 do no-op; flag1:=true; critical section flag1:=fal

10、se; remainder section until false; 3.1 進程同步的基本概念進程同步的基本概念三、利用軟件方法解決進程互斥問題三、利用軟件方法解決進程互斥問題算法算法3 var flag:array0.1 of boolean;Process P0 : repeat flag0:=true; while flag1 do no-op; critical section flag0:=false; remainder section until false; 缺點：缺點：解決了解決了“忙則等待忙則等待”，但又違背了，但又違背了“空閑讓進空閑讓進”和和 “ “有限等待有限等待”

11、。Process P1 : repeat flag1:=true; while flag0 do no-op; critical section flag1:=false; remainder section until false; 3.1 進程同步的基本概念進程同步的基本概念三、利用軟件方法解決進程互斥問題三、利用軟件方法解決進程互斥問題算法算法4Process P0 : repeat flag0:=true; turn:=1; while (flag1 and turn=1) do no-op; critical section flag0:=false; remainder secti

12、on until false; 是算法是算法1 1和和3 3的組合，既實現(xiàn)了的組合，既實現(xiàn)了“空閑讓進空閑讓進”，又保證了，又保證了 “忙則等待忙則等待”。 3.1 進程同步的基本概念進程同步的基本概念三、利用軟件方法解決進程互斥問題三、利用軟件方法解決進程互斥問題Process P0 : repeat flag1:=true; turn:=0; while (flag0 and turn=0) do no-op; critical section flag1:=false; remainder section until false; 缺點：缺點： 四種算法全部屬于四種算法全部屬于“忙等待忙

13、等待”方式。方式。 現(xiàn)在已很少使用?，F(xiàn)在已很少使用。 3.1 進程同步的基本概念進程同步的基本概念三、利用軟件方法解決進程互斥問題三、利用軟件方法解決進程互斥問題利用利用Test-and-Set指令指令 1.Test-and-Set 指令指令 function TS(var. lock:boolean):boolean begin TS:=lock; lock:=true; endTS(lock)=lock lock=true結(jié)果結(jié)果 3.1 進程同步的基本概念進程同步的基本概念四、利用硬件方法解決進程互斥問題四、利用硬件方法解決進程互斥問題2. 利用利用TS指令實現(xiàn)進程互斥的模型指令實現(xiàn)進程

14、互斥的模型 repeat while TS(lock) do skip;-進入?yún)^(qū)進入?yún)^(qū) critical section; -臨界區(qū)臨界區(qū) lock:=false; -退出區(qū)退出區(qū) remainder section until false; 思路：思路： false 可以進入可以進入CSa)每個臨界資源每個臨界資源一個一個lock（初值（初值=false） true 不能進入不能進入CSb)在進入?yún)^(qū)測試是否在進入?yún)^(qū)測試是否 不能不能 (lock=true):忙等待忙等待 可以進入臨界區(qū)可以進入臨界區(qū)CS 可以可以 (lock=false)進入進入CS執(zhí)行執(zhí)行退出退出CS 3.1 進程同步的基

15、本概念進程同步的基本概念四、利用硬件方法解決進程互斥問題四、利用硬件方法解決進程互斥問題硬件指令的缺點：硬件指令的缺點： 1.1.雖可有效實現(xiàn)互斥，但屬于雖可有效實現(xiàn)互斥，但屬于“忙等待忙等待”方式，違背了方式，違背了 “ “讓權(quán)等待讓權(quán)等待”原則。原則。 2.2.很難用它解決復雜的同步問題。很難用它解決復雜的同步問題。 3.1 進程同步的基本概念進程同步的基本概念四、利用硬件方法解決進程互斥問題四、利用硬件方法解決進程互斥問題一、一、記錄型信號量機制記錄型信號量機制二、二、AND型信號量集機制型信號量集機制1965年，荷蘭科學家年，荷蘭科學家Dijkstra在在THE系統(tǒng)上提出。系統(tǒng)上提出。

16、一個信號量一個信號量S是一個整型量，除對其初始化外，它只能是一個整型量，除對其初始化外，它只能 由兩個原子操作由兩個原子操作P和和V來訪問。來訪問。P和和V的名稱來源于荷蘭文的名稱來源于荷蘭文proberen（測試）和（測試）和verhogen （增量），它們的執(zhí)行具有不可中斷性。（增量），它們的執(zhí)行具有不可中斷性。本書中將本書中將P、V操作稱做操作稱做 wait 和和 signal 操作。操作。3.2 信號量機制信號量機制定義：定義： 3.2 信號量機制信號量機制一、記錄型信號量機制一、記錄型信號量機制信號量：信號量：type semaphore=record value:integer;

17、/*信號量的值 L:list of process; /*信號量等待隊列的隊首指針 end P(s): s.value:=s.value-1; if s.value0 then blocked(s.L); V(s): s.value:=s.value+1; if s.value 0 then wakeup(s.L);實現(xiàn)進程實現(xiàn)進程互斥互斥：模型：模型：一個臨界資源一個臨界資源一個互斥一個互斥信號量信號量mutex（初值（初值=1） 需互斥訪問該臨界需互斥訪問該臨界 P(mutex);-進入?yún)^(qū)進入?yún)^(qū) 資源的每個進程中資源的每個進程中 CS; V(mutex);-退出區(qū)退出區(qū)實例：實例：三個進程

18、執(zhí)行中要共享變量三個進程執(zhí)行中要共享變量count。分析：分析：count屬于臨界資源，對其應(yīng)互斥訪問。屬于臨界資源，對其應(yīng)互斥訪問。 提問：提問：1.mutex的取值范圍？的取值范圍？ 2.進程被喚醒后，執(zhí)行哪條語句？進程被喚醒后，執(zhí)行哪條語句？取值范圍：取值范圍：-2-2，11P P操作下一條語句操作下一條語句 3.2 信號量機制信號量機制一、記錄型信號量機制一、記錄型信號量機制var mutex:semaphore:=1; begin parbegin process1:begin repeat P(mutex); count:=count+1; V(mutex); until fals

19、e; end process2:begin repeat P(mutex); 1 count:=count+2; V(mutex); until false; end process3:begin repeat P(mutex); count:=count-1; V(mutex); until false; end parend end 2 3.2 信號量機制信號量機制一、記錄型信號量機制一、記錄型信號量機制實現(xiàn)進程實現(xiàn)進程同步同步： 模型：模型：一類資源一類資源一個公用一個公用信號量信號量s（初值（初值=0.n） 請求資源的進程中：請求資源的進程中：P(s); 釋放資源的進程中：釋放資源的進

20、程中：V(s);實例：實例：進程進程A和和B合作。合作。 A B 取數(shù)據(jù)；取數(shù)據(jù)； 計算數(shù)據(jù)；計算數(shù)據(jù)； 送數(shù)據(jù)；送數(shù)據(jù)； 3.2 信號量機制信號量機制一、記錄型信號量機制一、記錄型信號量機制 var s:semaphore:=0; parbegin processA:begin P(s); 取數(shù)據(jù)；取數(shù)據(jù)； 計算數(shù)據(jù)計算數(shù)據(jù); end processB:begin 送數(shù)據(jù)；送數(shù)據(jù)； V(s); end parend 執(zhí)行時兩種可能性：執(zhí)行時兩種可能性：1. 在進程在進程B還沒有送數(shù)據(jù)之前，進程還沒有送數(shù)據(jù)之前，進程 A先執(zhí)行了先執(zhí)行了P(s)，結(jié)果會怎樣？，結(jié)果會怎樣？2. 進程進程B的的V

21、(s)操作已經(jīng)完成，進程操作已經(jīng)完成，進程A 才執(zhí)行了才執(zhí)行了P(s)，結(jié)果會怎樣？，結(jié)果會怎樣？ 1.進程進程A執(zhí)行執(zhí)行P(s)，會使自己進入阻，會使自己進入阻 塞狀態(tài)，直至進程塞狀態(tài)，直至進程B送數(shù)據(jù)后執(zhí)行送數(shù)據(jù)后執(zhí)行 V(s) ，才能將它喚醒。，才能將它喚醒。2. 若進程若進程B的的V(s)操作已經(jīng)完成，進操作已經(jīng)完成，進 程程A才執(zhí)行了才執(zhí)行了P(s)，則進程，則進程A不會不會 阻塞。它可以順利地取到數(shù)據(jù)，完阻塞。它可以順利地取到數(shù)據(jù)，完 成下面的操作。成下面的操作。 3.2 信號量機制信號量機制一、記錄型信號量機制一、記錄型信號量機制實例實例：Var a,b,c,d,e:semaph

22、ore:=0,0,0,0,0;begin parbegin process p1: begin ; V(a); V(b); end; process p2: begin P(a); ; V(c); end; process p3: begin P(b); ; V(d); end; process p4: begin P(c); P(d); ; V(e); end; process p5: begin P(e); ; end; parendendp1p2p3p4p5描述進程描述進程前趨關(guān)系前趨關(guān)系：e ea ab bc cd d 3.2 信號量機制信號量機制一、記錄型信號量機制一、記錄型信號量機

23、制描述進程描述進程前趨關(guān)系前趨關(guān)系：模型：模型： 與進程同步類似；不同點：與進程同步類似；不同點： 1.信號量信號量s的初值的初值=0； 2.若等信號，則在開始處執(zhí)行若等信號，則在開始處執(zhí)行P(s)； 3.若發(fā)信號，則在最后處執(zhí)行若發(fā)信號，則在最后處執(zhí)行V(s)； 3.2 信號量機制信號量機制一、記錄型信號量機制一、記錄型信號量機制物理含義：物理含義：信號量的值信號量的值s.value： 表示系統(tǒng)中某類可用資源的數(shù)目。表示系統(tǒng)中某類可用資源的數(shù)目。s.values.value 0 0，表示還有，表示還有 此類資源可供分配；此類資源可供分配；s.values.value 0 0，表示資源已分配完

24、畢，表示資源已分配完畢， 其絕對值表示其絕對值表示s.Ls.L鏈表中阻塞進程的數(shù)目。鏈表中阻塞進程的數(shù)目。P(s)：請求一個單位的資源。請求一個單位的資源。V(s)：釋放一個單位的資源。釋放一個單位的資源。注：注：對一個信號量的對一個信號量的P P、V V操作必是成對出現(xiàn)的，有可能操作必是成對出現(xiàn)的，有可能 集中在一個進程中，也有可能分布在不同進程中。集中在一個進程中，也有可能分布在不同進程中。 3.2 信號量機制信號量機制一、記錄型信號量機制一、記錄型信號量機制定義：定義：swait (s1,s2, ,sn ) if s1 1 and and sn 1 then for i:=1 to n

25、do si:=si-1; endfor else place the process in the waiting queue associated with the first si found with si 1,and set the PC of this process to the beginning of swait operation. endif;ssignal (s1,s2, ,sn ) for i:=1 to n do si:=si+1; remove all the process waiting in the queue associated with si into

26、the ready queue. endfor; 3.2 信號量機制信號量機制二、二、AND型信號量集機制型信號量集機制與記錄型信號量的區(qū)別：與記錄型信號量的區(qū)別： 1. 一次同時對多個信號量進行判定；一次同時對多個信號量進行判定； 2. 所處阻塞隊列是第一個不滿足條件的信號量的阻塞隊列；所處阻塞隊列是第一個不滿足條件的信號量的阻塞隊列； 3. 阻塞后其程序計數(shù)器被撥回到阻塞后其程序計數(shù)器被撥回到swait開始位置；開始位置； 4. ssignal時，將全部信號量阻塞隊列中的全部阻塞進程時，將全部信號量阻塞隊列中的全部阻塞進程 喚醒。喚醒?；舅枷耄夯舅枷耄?資源一次性分配（要么全分配，要么

27、一個也不分配），資源一次性分配（要么全分配，要么一個也不分配）， 進程用完后再一起釋放。進程用完后再一起釋放。 3.2 信號量機制信號量機制二、二、AND型信號量集機制型信號量集機制一、生產(chǎn)者一、生產(chǎn)者-消費者問題消費者問題二、二、讀者讀者-寫者問題寫者問題三、哲學家就餐問題三、哲學家就餐問題3.3 經(jīng)典進程同步問題經(jīng)典進程同步問題問題描述：問題描述： 一群生產(chǎn)者進程在生產(chǎn)消息，并將此消息提供給消費者進一群生產(chǎn)者進程在生產(chǎn)消息，并將此消息提供給消費者進程去消費。為使生產(chǎn)者進程和消費者進程能并發(fā)執(zhí)行，在它們程去消費。為使生產(chǎn)者進程和消費者進程能并發(fā)執(zhí)行，在它們之間設(shè)置了一個具有個之間設(shè)置了一個具

28、有個n緩沖區(qū)的緩沖池，生產(chǎn)者進程可以將緩沖區(qū)的緩沖池，生產(chǎn)者進程可以將它所生產(chǎn)的消息放入一個緩沖區(qū)中，消費者進程可以從一個緩它所生產(chǎn)的消息放入一個緩沖區(qū)中，消費者進程可以從一個緩沖區(qū)中取得一個消息消費。規(guī)定：不允許消費者進程到一個空沖區(qū)中取得一個消息消費。規(guī)定：不允許消費者進程到一個空緩沖區(qū)中取消息，也不允許生產(chǎn)者進程向一個已裝有消息且尚緩沖區(qū)中取消息，也不允許生產(chǎn)者進程向一個已裝有消息且尚未被取走消息的緩沖區(qū)中投放消息。未被取走消息的緩沖區(qū)中投放消息。 3.3 經(jīng)典進程同步問題經(jīng)典進程同步問題一、生產(chǎn)者一、生產(chǎn)者- -消費者問題消費者問題一組生產(chǎn)者一組生產(chǎn)者一組消費者一組消費者 1 10 0

29、n-1n-1inin順序放順序放順序取順序取outout利用記錄型信號量解決利用記錄型信號量解決 3.3 經(jīng)典進程同步問題經(jīng)典進程同步問題一、生產(chǎn)者一、生產(chǎn)者- -消費者問題消費者問題1.1.基本工作：基本工作：生產(chǎn)者：生產(chǎn)消息；放消息。生產(chǎn)者：生產(chǎn)消息；放消息。 消費者：取消息；消費消息。消費者：取消息；消費消息。3.3.同步同步：生產(chǎn)者：放生產(chǎn)者：放 有空緩沖區(qū)：放有空緩沖區(qū)：放 無空緩沖區(qū)：阻塞無空緩沖區(qū)：阻塞 消費者：取消費者：取 有滿緩沖區(qū)：取有滿緩沖區(qū)：取 無滿緩沖區(qū)：阻塞無滿緩沖區(qū)：阻塞 喚醒喚醒設(shè)兩個公用信號量設(shè)兩個公用信號量 empty：空緩沖區(qū)的數(shù)目（初值：空緩沖區(qū)的數(shù)目（

30、初值= =n） full： 滿緩沖區(qū)的數(shù)目（初值滿緩沖區(qū)的數(shù)目（初值= =0）2.2.互斥：互斥：臨界資源（緩沖池）臨界資源（緩沖池）一個互斥信號量一個互斥信號量mutex（初值（初值=1）Var mutex, empty, full:semaphore:=1, n, 0; buffer:array0.n-1 of item; in, out:integer:=0, 0;begin parbegin producer: begin repeat until false; end consumer: begin repeat until false end parendendproduce an

31、 item in nextp;buffer(in):=nextp;in:=(in+1) mod n; P(mutex); V(mutex);P(empty);V(full);nextc:=buffer(out);out:=(out+1) mod n; consume an item in nextc;P(mutex); V(mutex);P(full);V(empty);注意：注意：要先對公用信號量執(zhí)行要先對公用信號量執(zhí)行P P操作，再對互斥信號量執(zhí)行操作，再對互斥信號量執(zhí)行 P P操作，否則可能引起死鎖操作，否則可能引起死鎖! 3.3 經(jīng)典進程同步問題經(jīng)典進程同步問題一、生產(chǎn)者一、生產(chǎn)者-

32、-消費者問題消費者問題例：分別交換生產(chǎn)者進程中以及消費例：分別交換生產(chǎn)者進程中以及消費者進程中的兩個者進程中的兩個P P操作的順序。當操作的順序。當mutex=1，empty=0，full=n 時，生產(chǎn)時，生產(chǎn)者先占用者先占用CPU執(zhí)行，結(jié)果會怎樣？執(zhí)行，結(jié)果會怎樣？ 生產(chǎn)者：生產(chǎn)者： 消費者：消費者： P(mutex); P(mutex); P(empty); P(full); 放消息；放消息； 取消息；取消息； V(mutex); V(mutex); V(full); V(empty);交換兩個交換兩個V操作不操作不 會有任何問題。會有任何問題。還有一種引發(fā)死鎖還有一種引發(fā)死鎖的可能性，是

33、什么？的可能性，是什么？利用利用AND型信號量解決：型信號量解決：（不會引發(fā)死鎖）（不會引發(fā)死鎖） 3.3 經(jīng)典進程同步問題經(jīng)典進程同步問題一、生產(chǎn)者一、生產(chǎn)者- -消費者問題消費者問題begin parbegin producer: begin repeat produce an item in nextp; swait(empty, mutex); buffer(in):=nextp; in:=(in+1) mod n; ssignal(mutex, full); until false; end consumer: begin repeat swait(full, mutex); nex

34、tc:=buffer(out); out:=(out+1) mod n; ssignal(mutex, empty); consume an item in nextc; until false end parend end 問題描述：問題描述： 一個數(shù)據(jù)對象可被多個進程共享。其中有些進程要求讀；一個數(shù)據(jù)對象可被多個進程共享。其中有些進程要求讀；另一些進程要求寫或修改。我們把只要求讀的進程稱為另一些進程要求寫或修改。我們把只要求讀的進程稱為 “reader進程進程”，其它稱為，其它稱為“writer進程進程”。允許多個。允許多個reader進進程同時讀共享的數(shù)據(jù)對象，但絕不允許一個程同時讀共享

35、的數(shù)據(jù)對象，但絕不允許一個 writer進程和其它進程和其它writer進程或進程或reader進程同時訪問該共享的數(shù)據(jù)對象。（多個進程同時訪問該共享的數(shù)據(jù)對象。（多個讀者和多個寫者間的關(guān)系）讀者和多個寫者間的關(guān)系） 3.3 經(jīng)典進程同步問題經(jīng)典進程同步問題二、讀者二、讀者- -寫者問題寫者問題利用記錄型信號量解決利用記錄型信號量解決1.1.基本工作：基本工作： reader（讀者）：讀數(shù)據(jù)對象。讀者）：讀數(shù)據(jù)對象。 writer（寫者）：寫數(shù)據(jù)對象。寫者）：寫數(shù)據(jù)對象。3.3.互斥：互斥： 數(shù)據(jù)對象數(shù)據(jù)對象互斥信號量互斥信號量wmutex（初值（初值=1），用于讀者進程，用于讀者進程 和寫者

36、進程互斥訪問數(shù)據(jù)對象。和寫者進程互斥訪問數(shù)據(jù)對象。 寫者寫者-與其它寫者、所有讀者都要互斥。與其它寫者、所有讀者都要互斥。 讀者讀者-可與其它讀者同時讀（不互斥），但要與所有寫者可與其它讀者同時讀（不互斥），但要與所有寫者 互斥?；コ?。 2.2.同步：同步：無，因要求中沒有說明讀者和寫者要合作無，因要求中沒有說明讀者和寫者要合作。 3.3 經(jīng)典進程同步問題經(jīng)典進程同步問題二、讀者二、讀者- -寫者問題寫者問題利用記錄型信號量解決利用記錄型信號量解決 某個讀者：想進入讀某個讀者：想進入讀 寫者正在寫，該讀者阻塞寫者正在寫，該讀者阻塞 其它讀者在讀，該讀者可進入其它讀者在讀，該讀者可進入 正在讀正

37、在讀 寫者想進入寫，該寫者阻塞寫者想進入寫，該寫者阻塞 其它讀者想進入讀，可以進入其它讀者想進入讀，可以進入 故讀者：進入時判斷寫者是否在內(nèi)，讀完后要釋放數(shù)據(jù)對象。故讀者：進入時判斷寫者是否在內(nèi)，讀完后要釋放數(shù)據(jù)對象。 第一個要求進入的讀者第一個要求進入的讀者 最后一個離開的讀者最后一個離開的讀者 增加變量增加變量readcount，來表示正在讀的讀者數(shù)目。，來表示正在讀的讀者數(shù)目。由于多個讀者共享由于多個讀者共享readcount ，故也應(yīng)作為臨界資源處理。，故也應(yīng)作為臨界資源處理。 設(shè)互斥信號量設(shè)互斥信號量rmutex（初值（初值=1），用于讀者互斥訪問，用于讀者互斥訪問readcount

38、。 3.3 經(jīng)典進程同步問題經(jīng)典進程同步問題二、讀者二、讀者- -寫者問題寫者問題Var rmutex, wmutex:semaphore:=1, 1; readcount:integer:=0;begin parbegin reader: begin repeat P(rmutex); if readcount=0 then P(wmutex); readcount:=readcount+1; V(rmutex); perform read operation; P(rmutex); readcount:=readcount-1; if readcount=0 then V(wmutex);

39、 V(rmutex); until false end writer:begin repeat P(wmutex); perform write operation; V(wmutex); until false; end parendend提問：提問：1.1.reader中的第一個中的第一個signal(rmutex)和第二個和第二個 wait(rmutex) 能否去掉？能否去掉？2.2.若一個寫者進程正在寫數(shù)據(jù)對象，問每個讀者進程和若一個寫者進程正在寫數(shù)據(jù)對象，問每個讀者進程和 其它寫者進程所在位置？（要求從狀態(tài)、所在隊列及其它寫者進程所在位置？（要求從狀態(tài)、所在隊列及 執(zhí)行到哪個語句三方

40、面來說明）執(zhí)行到哪個語句三方面來說明） 3.3 經(jīng)典進程同步問題經(jīng)典進程同步問題二、讀者二、讀者- -寫者問題寫者問題問題描述：問題描述： 有有5位位哲學家，他們的生活方哲學家，他們的生活方式是交替進行思考和就餐。哲學式是交替進行思考和就餐。哲學家們共用一張圓桌，分別坐在周家們共用一張圓桌，分別坐在周圍的五張椅子上。在圓桌上有五圍的五張椅子上。在圓桌上有五支筷子，每個哲學家饑餓時必須支筷子，每個哲學家饑餓時必須拿到其左、右最靠近他的各一支拿到其左、右最靠近他的各一支筷子時才能就餐。進餐畢，放下筷子時才能就餐。進餐畢，放下筷子又繼續(xù)思考?？曜佑掷^續(xù)思考。 3.3 經(jīng)典進程同步問題經(jīng)典進程同步問題

41、三、哲學家就餐問題三、哲學家就餐問題1203401234示意圖示意圖利用記錄型信號量解決利用記錄型信號量解決1.1.基本工作基本工作：哲學家：思考；就餐。哲學家：思考；就餐。2.2.同步同步：無。無。3.3.互斥互斥：臨界資源是筷子臨界資源是筷子 一支筷子一支筷子( (編號為編號為i) )一個互斥信號量一個互斥信號量chopsticki（初值（初值=1）。）。 提問：此算法有無問題？如何解決？提問：此算法有無問題？如何解決？ 3.3 經(jīng)典進程同步問題經(jīng)典進程同步問題三、哲學家就餐問題三、哲學家就餐問題var chopstick: array 0.4 of semaphore:=1, 1, 1,

42、 1, 1; begin parbegin process i ( i=0, 1, 2, 3, 4): begin repeat think; P(chopsticki); P(chopsticki+1 mod 5); eat; V(chopsticki); V(chopsticki+1 mod 5); until false; end parend end 3.3 經(jīng)典進程同步問題經(jīng)典進程同步問題三、哲學家就餐問題三、哲學家就餐問題一、管程的定義一、管程的定義二、互斥和同步二、互斥和同步三、利用管程解決生產(chǎn)者三、利用管程解決生產(chǎn)者-消費者問題消費者問題信號量機制為互斥、同步問題的解決提供了有

43、效和靈活信號量機制為互斥、同步問題的解決提供了有效和靈活 的工具，但用信號量編寫一個正確的程序比較困難。的工具，但用信號量編寫一個正確的程序比較困難。Hoare(1974)和和Hansen(1975)提出了一種高級的同步原語，提出了一種高級的同步原語， 稱為管程。它與信號量機制功能等價，且更容易控制。稱為管程。它與信號量機制功能等價，且更容易控制。3.4 管程機制管程機制管程：管程：管程是一個由一或多個過程、初始化代碼及局部變管程是一個由一或多個過程、初始化代碼及局部變 量組成的集合。其主要特性如下：量組成的集合。其主要特性如下： 1. 局部于管程的變量僅能被管程內(nèi)部的過程訪問，而不能局部于管

44、程的變量僅能被管程內(nèi)部的過程訪問，而不能 被任何外部過程訪問。被任何外部過程訪問。 2. 一個進程通過調(diào)用管程內(nèi)的一個過程而進入管程。一個進程通過調(diào)用管程內(nèi)的一個過程而進入管程。 3. 任一時刻管程中只能有一個活躍進程。即任一時刻只能任一時刻管程中只能有一個活躍進程。即任一時刻只能 有一個進程在管程中執(zhí)行，其它想進入管程的進程阻塞，有一個進程在管程中執(zhí)行，其它想進入管程的進程阻塞， 等待管程可用。等待管程可用。 3.4 管程機制管程機制一、管程的定義一、管程的定義管程的描述：管程的描述：type monitor-name=monitor variable declaration; proced

45、ure entry p1(); begin end; procedure entry p2(); begin end; procedure entry pn(); begin end; begin initialization code; end 管程的示意圖：管程的示意圖：共享數(shù)據(jù)共享數(shù)據(jù)操作過程操作過程初始化代碼初始化代碼進入隊列進入隊列xy相應(yīng)于條件變相應(yīng)于條件變量量x x和和y y的隊列的隊列 3.4 管程機制管程機制一、管程的定義一、管程的定義互斥：互斥： 3.4 管程機制管程機制二、互斥與同步二、互斥與同步管程的第管程的第3 3個特性，使它們能有效的完成互斥。個特性，使它們能有效的

46、完成互斥。進入管程時的互斥由編譯器負責，寫管程的人無需關(guān)心。進入管程時的互斥由編譯器負責，寫管程的人無需關(guān)心。同步：同步：條件變量條件變量及兩個相關(guān)操作及兩個相關(guān)操作wait和和signal 條件變量（條件變量（condition variables） x ：表示等待原因。表示等待原因。 x.wait：執(zhí)行該操作的進程阻塞，直至其它進程執(zhí)行執(zhí)行該操作的進程阻塞，直至其它進程執(zhí)行x.signal。 x.signal：喚醒喚醒x等待等待隊列中的一個進程。如果隊列中的一個進程。如果x等待隊列中無進等待隊列中無進 程阻塞，該操作不產(chǎn)生任何作用。程阻塞，該操作不產(chǎn)生任何作用。 3.4 管程機制管程機制二

47、、互斥與同步二、互斥與同步說明：說明： 進程進程Q因執(zhí)行因執(zhí)行x.wait處于處于阻塞狀態(tài)，后來進程阻塞狀態(tài)，后來進程P執(zhí)行了執(zhí)行了x.signal而而將進程將進程Q喚醒。為了避免管程中同時有兩個活躍進程，需要有喚醒。為了避免管程中同時有兩個活躍進程，需要有一條規(guī)則來決定讓一條規(guī)則來決定讓P和和Q誰執(zhí)行、誰阻塞。誰執(zhí)行、誰阻塞。 處理方式處理方式1：P執(zhí)行；執(zhí)行；Q等待。等待。 處理方式處理方式2：Q執(zhí)行；執(zhí)行；P等待。（等待。（Hoare采用）采用） 處理方式處理方式3：執(zhí)行：執(zhí)行signal的進程必須立即退出管程，即的進程必須立即退出管程，即signal語語 句只可能作為一個管程過程的最后

48、一條語句。句只可能作為一個管程過程的最后一條語句。 （Hansen建議）建議） 3.4 管程機制管程機制三、利用管程解決生產(chǎn)者三、利用管程解決生產(chǎn)者- -消費者問題消費者問題type producer-consumer=monitor var in,out,count: integer; buffer: array0.n-1 of item; notfull,notempty: condition; procedure entry put(item) begin if count n then notfull.wait; buffer(in):=item; in:=(in+1) mod n;

49、count:=count+1; if count=1then notempty.signal; endprocedure entry get(item) begin if count 0 then notempty.wait; item:=buffer(out); out:=(out+1) mod n; count:=count-1; if count=n-1then notfull.signal; end begin in:=out:=0; count:=0; end管程管程定義定義 3.4 管程機制管程機制三、利用管程解決生產(chǎn)者三、利用管程解決生產(chǎn)者- -消費者問題消費者問題produce

50、r: begin repeat produce an item in nextp; producer-consumer.put(nextp); until false; endconsumer: begin repeat producer-consumer.get(nextc); consume the item in nextc; until false; end進程調(diào)用進程調(diào)用 進程通信進程通信IPC（Inter Process Communication） 指合作進程之間的信息交換。指合作進程之間的信息交換。方式：方式： 1. 低級通信方式：信號量和管程低級通信方式：信號量和管程 信號量

51、的缺點：一次只傳遞一個信號量，大量信息的傳遞需借信號量的缺點：一次只傳遞一個信號量，大量信息的傳遞需借 助共享數(shù)據(jù)結(jié)構(gòu)進行，而共享數(shù)據(jù)結(jié)構(gòu)的定義助共享數(shù)據(jù)結(jié)構(gòu)進行，而共享數(shù)據(jù)結(jié)構(gòu)的定義 和操作以及同步控制均要由程序員自己實現(xiàn)。和操作以及同步控制均要由程序員自己實現(xiàn)。 管程的缺點：管程在少數(shù)幾種編程語言以外無法使用。管程的缺點：管程在少數(shù)幾種編程語言以外無法使用。 2. 高級通信方式：例如消息傳遞系統(tǒng)高級通信方式：例如消息傳遞系統(tǒng) 優(yōu)勢：一次可以傳遞大量信息；進程中使用通信命令即可通信；優(yōu)勢：一次可以傳遞大量信息；進程中使用通信命令即可通信； 通信過程由通信過程由OS實現(xiàn)。實現(xiàn)。 3.5 進程通

52、信進程通信作為同步工具有效，作為通信工具低級說明：說明： 3.5 進程通信進程通信一、消息傳遞系統(tǒng)（一、消息傳遞系統(tǒng)（Message Passing System）消息傳遞系統(tǒng)至少要提供兩個操作：發(fā)送消息消息傳遞系統(tǒng)至少要提供兩個操作：發(fā)送消息send(message) 和接收消息和接收消息receive(message)。如果進程如果進程P和和Q想要通信，它們必須互相發(fā)送消息和接收消想要通信，它們必須互相發(fā)送消息和接收消 息；并且在它們之間一定存在著一條通信鏈路（息；并且在它們之間一定存在著一條通信鏈路（communication link）。）。 通信鏈路和通信鏈路和send/receiv

53、e操作的邏輯實現(xiàn)方法：操作的邏輯實現(xiàn)方法： 直接或間接通信直接或間接通信對稱或非對稱地址對稱或非對稱地址有容量或無容量的緩沖區(qū)有容量或無容量的緩沖區(qū)定長或變長消息定長或變長消息 直接通信：直接通信： 要通信的每個進程必須明確指出發(fā)送進程或接收進程的標識符。要通信的每個進程必須明確指出發(fā)送進程或接收進程的標識符。send和和receive原語的格式原語的格式： send ( P, message )-發(fā)送消息給進程發(fā)送消息給進程P； receive ( Q, message)-接收來自進程接收來自進程Q的消息。的消息。通信鏈路的性質(zhì)：通信鏈路的性質(zhì)： 1. 要通信的一對進程之間的通信鏈路是自動建

54、立的。進程只需要通信的一對進程之間的通信鏈路是自動建立的。進程只需 知道彼此的標識符。知道彼此的標識符。 2. 一條鏈路只連接一對進程。（點到點連接）一條鏈路只連接一對進程。（點到點連接） 3. 每對進程之間只存在一條鏈路。每對進程之間只存在一條鏈路。 3.5 進程通信進程通信一、消息傳遞系統(tǒng)（一、消息傳遞系統(tǒng)（Message Passing System）這種這種send/receive原語展示的是原語展示的是對稱地址對稱地址。即發(fā)送進程和接收。即發(fā)送進程和接收 進程都要指出對方的標識符。進程都要指出對方的標識符。非對稱地址方式下非對稱地址方式下send和和receive原語的格式原語的格式

55、： send ( P, message )-發(fā)送消息給進程發(fā)送消息給進程P； receive ( id, message)-接收從任一進程發(fā)來的消息。接收從任一進程發(fā)來的消息。id是是 receive操作操作的返回值，表示本次接收的返回值，表示本次接收 來的消息的發(fā)送者是誰。來的消息的發(fā)送者是誰。直接通信的缺點：直接通信的缺點： 一個進程的標識符發(fā)生改變，則與之通信的所有進程都要修改一個進程的標識符發(fā)生改變，則與之通信的所有進程都要修改 通信原語中的相應(yīng)標識符。通信原語中的相應(yīng)標識符。 3.5 進程通信進程通信一、消息傳遞系統(tǒng)（一、消息傳遞系統(tǒng)（Message Passing System）間

56、接通信：間接通信： 通信進程利用通信進程利用信箱信箱傳遞消息。但只有在獲得一個可共享的信箱傳遞消息。但只有在獲得一個可共享的信箱 的前提下，進程間才可通信。的前提下，進程間才可通信。send和和receive原語的格式：原語的格式： send ( A, message )-將消息發(fā)送到信箱將消息發(fā)送到信箱A； receive ( A, message)-從信箱從信箱A接收消息。接收消息。通信鏈路的性質(zhì)：通信鏈路的性質(zhì)： 1. 僅當要通信的一對進程具有可以共享的信箱時，通信鏈路僅當要通信的一對進程具有可以共享的信箱時，通信鏈路 才能建立。才能建立。 2. 一條鏈路可以連接多個進程。（多點連接）一

57、條鏈路可以連接多個進程。（多點連接） 3. 每對通信進程之間可以存在多條鏈路，但每條鏈路上只有每對通信進程之間可以存在多條鏈路，但每條鏈路上只有 一個信箱。一個信箱。 3.5 進程通信進程通信一、消息傳遞系統(tǒng)（一、消息傳遞系統(tǒng)（Message Passing System）信箱：信箱： 每個信箱的標識符是唯一的。每個信箱的標識符是唯一的。 信箱的擁有者可以是信箱的擁有者可以是OS，也可以是用戶進程。歸也可以是用戶進程。歸OS所有的信箱是所有的信箱是 獨立的，它不附屬于任何進程。獨立的，它不附屬于任何進程。 如果如果OS提供了有關(guān)信箱的創(chuàng)建、撤消及通過信箱發(fā)送和接收消息的提供了有關(guān)信箱的創(chuàng)建、撤

58、消及通過信箱發(fā)送和接收消息的 原語，則一個用戶進程可為自己建立一個信箱，它就是該信箱的擁原語，則一個用戶進程可為自己建立一個信箱，它就是該信箱的擁 有者。當它終止時，該信箱自動消失。有者。當它終止時，該信箱自動消失。 進一步說明：進一步說明： 1. 要區(qū)分信箱的擁有者（只能從該信箱接收消息）和使用者（只能要區(qū)分信箱的擁有者（只能從該信箱接收消息）和使用者（只能 向該信箱發(fā)消息）。向該信箱發(fā)消息）。 2. 信箱創(chuàng)建后，其所有權(quán)和接收權(quán)可以通過系統(tǒng)調(diào)用命令傳遞給其信箱創(chuàng)建后，其所有權(quán)和接收權(quán)可以通過系統(tǒng)調(diào)用命令傳遞給其 它進程，這就可能導致一個信箱有多個接收者。它進程，這就可能導致一個信箱有多個接收者。 3.5 進