互斥同步與通訊

1、第四章第四章 互斥、同步與通訊互斥、同步與通訊n并發(fā)進程并發(fā)進程(concurrent processes)n進程互斥進程互斥(mutual exclusion)n進程同步進程同步(synchronization)n進程高級通訊進程高級通訊(communication)4.1并發(fā)進程并發(fā)進程n4.1.1前驅(qū)圖的定義前驅(qū)圖的定義 前驅(qū)圖(precedence graph)是一個有向無環(huán)圖，圖中的每個結(jié)點表示一條語句、一個計算步驟或一個進程。結(jié)點間的有向邊表示偏序或前驅(qū)關(guān)系（precedence relation）“”，=（pi，pj） pi必須在pj啟動之前完成。 （pi，pj） 可記為pi p

2、j，稱pi是pj的前驅(qū)， pj是pi的后繼。4.1并發(fā)進程并發(fā)進程n在前驅(qū)圖中沒有前驅(qū)的結(jié)點稱為初始結(jié)點，沒有后繼的結(jié)點稱為終止結(jié)點。每個結(jié)點可以有一個權(quán)重（weight），它表示該結(jié)點所包含的程序量或計算時間。n前驅(qū)關(guān)系滿足傳遞性，即若p1 p2，p2 p3，則必有p1 p3。4.1 并發(fā)進程并發(fā)進程n4.1.2 順序程序及其特性順序程序及其特性n順序性順序性n內(nèi)部順序性：對于一個進程來說，它的所有指令是按順序執(zhí)行的。內(nèi)部順序性：對于一個進程來說，它的所有指令是按順序執(zhí)行的。P1: a1,a2,a3; P2: b1,b2,b3n外部順序性：對于多個進程來說，所有進程的活動是依次執(zhí)行的。外部順

3、序性：對于多個進程來說，所有進程的活動是依次執(zhí)行的。a1,a2,a3,b1,b2,b3; b1,b2,b3,a1,a2,a3n順序程序特性順序程序特性:n (1)順序性順序性: 指令逐條執(zhí)行指令逐條執(zhí)行n (2)封閉性封閉性: 不受其它程序及外界因素影響不受其它程序及外界因素影響n (3)可再現(xiàn)性可再現(xiàn)性: 結(jié)果與推進速度無關(guān)結(jié)果與推進速度無關(guān)4.1 并發(fā)進程并發(fā)進程n4.1.3 并發(fā)程序及其特性并發(fā)程序及其特性n并發(fā)性并發(fā)性n內(nèi)部并發(fā)性：指程序內(nèi)部的并發(fā)性。例如：內(nèi)部并發(fā)性：指程序內(nèi)部的并發(fā)性。例如：S1：a:=x+2;S2: b:=y+4;S3: c:=a+b;S4: d:=c-6;S5:

4、 e:=c+6;S6: f:=c-e;經(jīng)分析知道經(jīng)分析知道S3必須在必須在S1和和S2之后執(zhí)行，之后執(zhí)行，S4和和S5必須在必須在S3之后執(zhí)行，之后執(zhí)行，S6必須在必須在S3和和S5之后執(zhí)行；而之后執(zhí)行；而S1和和S2可以并發(fā)執(zhí)行，可以并發(fā)執(zhí)行，S4和和S5可以并發(fā)可以并發(fā)執(zhí)行，執(zhí)行，S4和和S6可以并發(fā)執(zhí)行?？梢圆l(fā)執(zhí)行。4.1并發(fā)進程并發(fā)進程n外部并發(fā)性：外部并發(fā)性是指多個程序的并發(fā)性。例如外部并發(fā)性：外部并發(fā)性是指多個程序的并發(fā)性。例如P1: a1,a2,a3; P2: b1,b2,b3 執(zhí)行次序可以是如下情況：執(zhí)行次序可以是如下情況：a1,b1,b2,a2,a3,b3; b1,b2,a

5、1,b3,a2,a3n并發(fā)程序特性并發(fā)程序特性:n(1)間斷性間斷性:多個程序是交叉執(zhí)行的，處理器在執(zhí)行一個程序的過程中有多個程序是交叉執(zhí)行的，處理器在執(zhí)行一個程序的過程中有可能被中斷，并轉(zhuǎn)而執(zhí)行另一個程序，有些交叉可能導(dǎo)致錯誤結(jié)果可能被中斷，并轉(zhuǎn)而執(zhí)行另一個程序，有些交叉可能導(dǎo)致錯誤結(jié)果n(2)非封閉性非封閉性:一個進程的運行環(huán)境受其他程序影響一個進程的運行環(huán)境受其他程序影響n(3)不可再現(xiàn)性不可再現(xiàn)性:由于交叉的隨機性，并發(fā)程序的多次執(zhí)行可能對應(yīng)不同由于交叉的隨機性，并發(fā)程序的多次執(zhí)行可能對應(yīng)不同的交叉，從而使得兩次運行結(jié)果可能不同即不能期望從新運行的程序能的交叉，從而使得兩次運行結(jié)果可能

6、不同即不能期望從新運行的程序能夠再現(xiàn)上次運行時產(chǎn)生的結(jié)果。夠再現(xiàn)上次運行時產(chǎn)生的結(jié)果。4.1并發(fā)進程并發(fā)進程n4.1.4程序并發(fā)執(zhí)行的條件程序并發(fā)執(zhí)行的條件 并發(fā)是人們所期望的，但并發(fā)帶來一個明顯的問題就是程序執(zhí)行的非封閉性，而人們卻要求在非封閉性的條件下保持可再現(xiàn)性，因為只有可再現(xiàn)的結(jié)果才是正確的。令：令： R(pi)=a1,a2,am表示程序pi在執(zhí)行期間所讀取的所有變量的集合，稱為“讀集”。 W(pi)=b1,b2,bn表示程序pi在執(zhí)行期間所修改的所有變量的集合，稱為“寫集”。Bernstein條件（1966年由Bernstein提出）： 若兩個程序p1、p2滿足以下條件，則能夠保持可

7、再現(xiàn)性，可以并發(fā)執(zhí)行，條件是： R(p1) W(p2) R(p2) W(p1) W(p1) W(p2) = 4.1并發(fā)進程并發(fā)進程n并發(fā)程序的表示 并發(fā)程序常用并發(fā)語cobegin(concurrent begin)coend(concurrent end)來表示，令S1、S2、Sn為n條語句，它們可以并發(fā)執(zhí)行，則用并發(fā)語句表示為： cobegin S1；S2； Sn coend； 有時也用并行語parallelbegin(parallel begin)parallelend(parallel end)來表示 當(dāng)遇到并發(fā)或并行語句時，同時n創(chuàng)建個進程（線程），分別執(zhí)行S1、S2、Sn 。當(dāng)它們

8、都結(jié)束時，并發(fā)和并行語句結(jié)束。4.1.6 與時間有關(guān)的錯誤與時間有關(guān)的錯誤例：圖書借閱系統(tǒng)例：圖書借閱系統(tǒng) （x: :某種某種書冊數(shù)，設(shè)當(dāng)前書冊數(shù)，設(shè)當(dāng)前x=1.=1.）終端終端1： 終端終端2：do do 等待借書者；等待借書者； 等待借書者；等待借書者； if x=1 if x=1 _ _ x:=x-1; x:=x-1; _ _ 借書借書 借書借書 else 無書無書 else 無書無書 while(1) while(1) (a)CR1 (b)CR2 12344.1.6 與時間有關(guān)的錯誤與時間有關(guān)的錯誤(Cont.)錯誤原因之錯誤原因之1： 進程執(zhí)行交叉進程執(zhí)行交叉(interleave)

9、;錯誤原因之錯誤原因之2： 涉及公共變量涉及公共變量(x)。Remarks: 某些交叉結(jié)果不正確某些交叉結(jié)果不正確; 必須去掉導(dǎo)致不正確結(jié)果的交叉。必須去掉導(dǎo)致不正確結(jié)果的交叉。4.2 進程互斥進程互斥(mutual exclusion)n4.2.1 共享變量與臨界區(qū)共享變量與臨界區(qū)n4.2.2 臨界區(qū)域與進程互斥臨界區(qū)域與進程互斥n4.2.3 進程互斥的實現(xiàn)進程互斥的實現(xiàn)n4.2.4 多處理機環(huán)境下的互斥多處理機環(huán)境下的互斥4.2.1 共享變量與臨界區(qū)域共享變量與臨界區(qū)域n共享變量共享變量（shared variable）或公共變量n多個進程都需要訪問的變量。多個進程都需要訪問的變量。n臨界

10、區(qū)域臨界區(qū)域（critical region）或臨界段(critical section)n訪問共享變量的程序段訪問共享變量的程序段。 一組公共變量一組公共變量CR1CR2CRn.4.2.1 共享變量與臨界區(qū)域共享變量與臨界區(qū)域n臨界區(qū)是于1965年首先提出的。在上例中的CR1和CR2。臨界區(qū)可能有多個。為了清晰起見，通常把臨界區(qū)與所對應(yīng)的共享變量聯(lián)系起來，稱為關(guān)于某一組共享變量的臨界區(qū)。如上例CR1和CR2是關(guān)于共享變量x的臨界區(qū)。n關(guān)于同一組共享變量的臨界區(qū)可能有一個也可能有多個，它們的關(guān)系可以用上圖表示。n共享變量既可能屬于操作系統(tǒng)空間，也可能屬于用戶空間。對于前者，其臨界區(qū)也屬于操作系

11、統(tǒng)空間；同樣后者對應(yīng)的臨界區(qū)也屬于用戶空間。共享變量和臨界區(qū)的表示共享變量和臨界區(qū)的表示共享變量共享變量: shared 臨界區(qū)域臨界區(qū)域: region do 語句語句臨界資源：一次只允許一個進程使用的資源臨界資源：一次只允許一個進程使用的資源例子：例子：shared x1,x2; region x1,x2 do region x1,x2 do (訪問訪問B） （訪問（訪問B） 4.2.2 臨界區(qū)域與進程互斥臨界區(qū)域與進程互斥定義定義：多個進程不能同時進入關(guān)于同一組共享變量的臨多個進程不能同時進入關(guān)于同一組共享變量的臨界區(qū)域，否則可能發(fā)生與時間有關(guān)的錯誤，這種現(xiàn)象稱界區(qū)域，否則可能發(fā)生與時間

12、有關(guān)的錯誤，這種現(xiàn)象稱為進程互斥為進程互斥二層涵義：二層涵義： （1）任何時刻最多只能有一個進程處于同一組共）任何時刻最多只能有一個進程處于同一組共享變量的相同的臨界區(qū)域；享變量的相同的臨界區(qū)域； （2）任何時刻最多只能有一個進程處于同一組共）任何時刻最多只能有一個進程處于同一組共享變量的不同的臨界區(qū)域享變量的不同的臨界區(qū)域。Remarks: 互斥是相對于公共變量而言的?；コ馐窍鄬τ诠沧兞慷缘?。嵌套臨界區(qū)域嵌套臨界區(qū)域 shared x; shared y; region x do region y do _ _ region y do region x do . . 一個臨界區(qū)程序段可能

13、調(diào)用另一個臨界區(qū)程序段，稱發(fā)生了臨界區(qū)的嵌套。一個臨界區(qū)程序段可能調(diào)用另一個臨界區(qū)程序段，稱發(fā)生了臨界區(qū)的嵌套。4.2.3 進程互斥的實現(xiàn)進程互斥的實現(xiàn)nframeworkdo critical section remainder section while(1)entry sectionexit section4.2.3 進程互斥的實現(xiàn)進程互斥的實現(xiàn)nRequirements:nmutual exclusion: 一次只允許一個進程活動在關(guān)一次只允許一個進程活動在關(guān)于同一組公共變量的臨界區(qū)中于同一組公共變量的臨界區(qū)中；nprogress: 臨界區(qū)空閑時，多個競爭者在有限時間臨界區(qū)空閑時，多個

14、競爭者在有限時間內(nèi)確定下一個進入者內(nèi)確定下一個進入者；nbounded waiting: 一個想要進入臨界區(qū)的進程在等一個想要進入臨界區(qū)的進程在等待有限個進程進入并離開臨界區(qū)后獲得進入臨界區(qū)待有限個進程進入并離開臨界區(qū)后獲得進入臨界區(qū)的機會的機會。4.2.3 進程互斥的實現(xiàn)進程互斥的實現(xiàn)n調(diào)度原則： 1.關(guān)于同一組共享變量的所有臨界區(qū)均為空閑時，一個要求進入改組共享變量某一臨界區(qū)的進程應(yīng)當(dāng)能夠立即進入。 2.當(dāng)關(guān)于某一組共享變量的某一臨界區(qū)被占用時，一個要求進入改組共享變量某一臨界區(qū)的進程應(yīng)當(dāng)?shù)却?3.當(dāng)某一進程離開關(guān)于某一組共享變量的某一臨界區(qū)時，應(yīng)當(dāng)允許某一個等待進入該組共享變量某一臨界

15、區(qū)的進程進入。4.2.3.1 進程互斥的軟件實現(xiàn)進程互斥的軟件實現(xiàn)n完全用程序?qū)崿F(xiàn)，不需特殊硬件指令支完全用程序?qū)崿F(xiàn)，不需特殊硬件指令支持。持。n可用于單可用于單CPU和多和多CPU環(huán)境中。環(huán)境中。n有忙式等待問題。有忙式等待問題。Busy waiting“運行運行”或或“就緒就緒”Dekker互斥算法n是由荷蘭數(shù)學(xué)家T.Dekker給出的第一個正確實現(xiàn)互斥的軟件算法，算法針對兩個進程P0和P1定義的兩個數(shù)據(jù)結(jié)構(gòu)： int flag2;/初值為0 int turn;/初值為0或1算法：Dekker互斥算法nP0: do flag0=1; while flag1 do if (turn=1) f

16、lag0=0; while turn=1 do skip; flag0=1;Dekker互斥算法 臨界區(qū) turn=1; flag0=0; 其余代碼 while(1)Dekker互斥算法nP1: do flag1=1; while flag0 do if (turn=0) flag1=0; while turn=0 do skip; flag1=1;Dekker互斥算法 臨界區(qū) turn=0; flag1=0; 其余代碼 while(1)Lamport面包店算法面包店算法算法思想算法思想：算法的基本思想源于顧客在面包店中購買面包：算法的基本思想源于顧客在面包店中購買面包時的排隊原理。設(shè)置一個發(fā)

17、號者，按時的排隊原理。設(shè)置一個發(fā)號者，按0,1,2, 發(fā)號。想進發(fā)號。想進入臨界區(qū)（面包店）的進程先抓號，抓到號之后按由小到入臨界區(qū)（面包店）的進程先抓號，抓到號之后按由小到大的次序依次進入大的次序依次進入。Problem: 兩個進程可能抓到相同的號。兩個進程可能抓到相同的號。Why? 為保證抓到不同的號，需要互斥機制。為保證抓到不同的號，需要互斥機制。Resolution: 若抓到相同的號，按進程編號若抓到相同的號，按進程編號由小到大由小到大依次依次進入。進入。Definition: (a,b)(c,d) iff (ac)or(a=c and bd)Lamport面包店算法面包店算法n算法需

18、要以下兩個數(shù)據(jù)結(jié)構(gòu) int choosingn; int numbern; 前者表示進程是否正在抓號choosingi=1表示進程正在抓號，否則為0，其初值為0.后者用來表示進程抓到號碼，初值也為0.n算法描述方便需要定義以下表示方法 (a,b)(c,d),如果 ac or(a=c and bd)成立。Lamport面包店算法面包店算法doPi 進入進入：1. choosingi=1;2. numberi=maxnumber0,numbern-1+1;3. choosingi=0;4. for(j=0;jn; j+)5. While choosingj skip;6. While (numbe

19、rj0)&7. (numberj,j)(numberi,i) skip8. (1)P0抓到1未賦值(2)P1抓到1進入臨界區(qū)(3)P2抓到2進入臨界區(qū) Lamport面包店算法面包店算法(Cont.) 臨界區(qū)；臨界區(qū)； numberi=0；while(1);變量變量choosing的的作用：作用：P0：抓到：抓到1; P1：抓到：抓到1; 正確次序：正確次序：P0，P1，P2P2：抓到：抓到2; 可能按可能按P1,P2,P0次序進入次序進入！滿足臨界區(qū)管理原則滿足臨界區(qū)管理原則n互斥性互斥性(mutual exclusion)n如果進程如果進程pi在臨界區(qū)內(nèi)在臨界區(qū)內(nèi),且進程且進程pk

20、(ki)已抓到號已抓到號numberk0, 則有則有(numberi,i)(numberk,k). 進進程程Pk將在第二個將在第二個while循環(huán)處等待循環(huán)處等待, 直到直到pi離開該臨界區(qū)離開該臨界區(qū).n有限等待性有限等待性(bounded waiting)n競爭進程按競爭進程按FIFO的次序進入臨界區(qū)的次序進入臨界區(qū), 而進程個數(shù)是有限的而進程個數(shù)是有限的, 因因而進程不會無限期等待進入臨界區(qū)而進程不會無限期等待進入臨界區(qū).n進展性進展性(progress)n多個進程競爭進入臨界區(qū)時多個進程競爭進入臨界區(qū)時, 下述條件之一成立下述條件之一成立: (1)一個進程一個進程抓到最小號抓到最小號,

21、 (2)若干進程抓到最小號若干進程抓到最小號. 情形情形(1)抓到最小號的抓到最小號的進程獲準進入臨界區(qū)進程獲準進入臨界區(qū); 情形情形(2)編號最小抓到最小號的進程獲編號最小抓到最小號的進程獲準進入臨界區(qū)準進入臨界區(qū), 因而確定進入臨界區(qū)進程的決策將在有限時間因而確定進入臨界區(qū)進程的決策將在有限時間內(nèi)確定內(nèi)確定.Eisenberg/Mcguire算法算法enum flagn (idle, want_in, in_cs);初值初值idle int turn;/in the range of (0,n-1); 初始任意初始任意0 i turnn-1先于先于i先于先于iflagi=idle: 進程進

22、程Pi不想進入臨界區(qū)不想進入臨界區(qū)flagi=want_in: 進程進程Pi想進入臨界區(qū)想進入臨界區(qū)flagi=in_cs: 進程進程Pi想進入或已進入臨界區(qū)想進入或已進入臨界區(qū)Eisenberg/Mcguire算法算法Pi進入進入:do do flagi=want_in; j=turn; While (j!=i) if (flagj!=idle) j=turn; else j=(j+1)% n; flagi=in_cs; j=0; While (jn)&(j=i flagj!=in_cs) j+; while(j!=n); turn=i;Eisenberg/Mcguire算法算法Pi

23、離開：離開：j=(turn+1)% n;While (flagj=idle) j=(j+1)% n;turn=j;flagi=idle;while(1)CS滿足臨界區(qū)管理原則滿足臨界區(qū)管理原則n互斥性互斥性n僅當(dāng)對所有僅當(dāng)對所有ji, flagj in_cs時時, 進程進程Pi才進入臨界區(qū)域才進入臨界區(qū)域, 因而滿足互斥性因而滿足互斥性.n進展性進展性n如果沒有進程正處于臨界區(qū)或離開臨界區(qū)如果沒有進程正處于臨界區(qū)或離開臨界區(qū), turn值不變值不變, 競爭競爭進程將按進程將按turn, turn+1, , n-1, 1, turn-1的次序進入臨界的次序進入臨界區(qū)區(qū), 因而滿足進展性原則因而滿

24、足進展性原則.n有限等待性有限等待性n進程離開臨界區(qū)時進程離開臨界區(qū)時,按循環(huán)次序確定唯一一個競爭進程為其后按循環(huán)次序確定唯一一個競爭進程為其后繼繼, 所以一個進程最多等待所以一個進程最多等待n-1個進程進入并離開臨界區(qū)后一個進程進入并離開臨界區(qū)后一定能進入臨界區(qū)定能進入臨界區(qū), 因而滿足有限等待性因而滿足有限等待性.4.2.3.2 進程互斥的硬件實現(xiàn)進程互斥的硬件實現(xiàn)1. 硬件提供硬件提供“測試并建立測試并建立”指令指令 int test_and_set(int &target) int temp; temp=target; &target=1; return(temp) 對

25、一組公共變量，對一組公共變量，int lock（初始（初始=0); Pi進入：進入：While test_and_set(lock) skip; Pi離開：離開：lock=0;4.2.3.2 進程互斥的硬件實現(xiàn)進程互斥的硬件實現(xiàn)n基于“測試并設(shè)置”指令的公平性硬件互斥算法 定義全局變量為： int waitingn; int lock; 其中變量的初值都為0. 每個進程定義的局部變量為： int j; int key;4.2.3.2 進程互斥的硬件實現(xiàn)進程互斥的硬件實現(xiàn)do waitingi=1; key=1; while ( waitingi & key) key=test_and_

26、set(&lock); waitingi=0; CR j=(i+1)% n; while (j!=i) & (! waitingj) j=(j+1)% n; if (j=i) lock=0; else waitingj=0; REMAIN while (1)4.2.3.2 進程互斥的硬件實現(xiàn)進程互斥的硬件實現(xiàn)2. 硬件提供硬件提供“交換交換”指令指令 void swap(int &a,&b) int temp; temp=*a; *a=b; *b=temp ; 對一組公共變量對一組公共變量：int lock (初始初始=0); 對一個進程空間對一個進程空間：in

27、t key; Pi進入進入：key=1; do swap(&lock,&key)while (key=1); Pi離開離開：lock=0;4.2.3.2進程互斥的硬件實現(xiàn)進程互斥的硬件實現(xiàn)Remarks：(1) test_and_set指令和指令和swap指令是原子的，指令是原子的，不可中斷的不可中斷的(在單在單CPU情況下情況下)。(2) test_and_set實際上是：將內(nèi)存中一個單實際上是：將內(nèi)存中一個單元的內(nèi)容取出，再送一個新值。元的內(nèi)容取出，再送一個新值。(3) swap實際上是：交換內(nèi)存兩個單元的內(nèi)容實際上是：交換內(nèi)存兩個單元的內(nèi)容。4.2.3.2進程互斥的硬件實

28、現(xiàn)進程互斥的硬件實現(xiàn)n基于“交換”指令的公平性硬件互斥算法 定義全局變量為： int waitingn; int lock; 其中變量的初值都為0. 每個進程定義的局部變量為： int j; int key;4.2.3.2進程互斥的硬件實現(xiàn)進程互斥的硬件實現(xiàn)do waitingi=1; key=1; while ( waitingi & key) key=swap(&lock, &key); waitingi=0; CR j=(i+1)% n; while (j!=i) & (! waitingj) j=(j+1)% n; if (j=i) lock=0; el

29、se waitingj=0; REMAIN while (1)4.2.3.2進程互斥的硬件實現(xiàn)進程互斥的硬件實現(xiàn)3. 硬件提供硬件提供“關(guān)中斷關(guān)中斷”和和“開中斷開中斷”指指令令 關(guān)中斷關(guān)中斷 Critical Region 開中斷開中斷Remarks: (1) 開關(guān)中斷只在單開關(guān)中斷只在單CPU系統(tǒng)中有效系統(tǒng)中有效;(why?) (2) 影響并發(fā)性。影響并發(fā)性。Assignment #11. 進程切換時需要保存哪些現(xiàn)場信息？請盡量考慮完全。2. 進程切換時，現(xiàn)場信息為何不能保存在下降進程的系統(tǒng)棧中,而必須傳送到PCB中？Assignment #2Consider the following

30、program:var blocked: array0.1of boolean; turn:0.1;procedure P(id:integer);begin repeat blockedid:=true; while turnid do begin while blocked1-id do nothing turn:=id end; blockedid:=false; until falseend;begin blocked0:=false; blocked1:=false; turn:=0; parbegin P(0); P(1) parend;end.This is a software

31、 solution to the mutual exclusion problem proposed by Hyman. Find a counter example to demonstrate that this solution is incorrect. It is interesting to note that even the Communication of the ACM was fooled on this one.4.3 進程同步進程同步4.3.1 進程同步的概念進程同步的概念例：司機例：司機-售票員問題售票員問題 司機活動：司機活動： 售票員活動：售票員活動： do d

32、o 啟動車輛啟動車輛 關(guān)車門關(guān)車門 正常行駛正常行駛 售售 票票 到站停車到站停車 開車門開車門 while( (1) ) while( (1) )4.3.1 進程同步的概念進程同步的概念定義：定義：一組進程，為協(xié)調(diào)其推進速度，在某些關(guān)一組進程，為協(xié)調(diào)其推進速度，在某些關(guān)鍵點處需要相互等待與相互喚醒，進程之間這種鍵點處需要相互等待與相互喚醒，進程之間這種相互制約的關(guān)系稱為進程同步相互制約的關(guān)系稱為進程同步(synchronization)。P1:P2:synchronize后先4.3.2 進程同步機制進程同步機制n定義：定義：用于實現(xiàn)進程同步的工具稱為同用于實現(xiàn)進程同步的工具稱為同步機制步機制

33、（synchronization mechanism）又稱同步設(shè)施。n同步機制要求：同步機制要求：n描述能力夠用描述能力夠用;n可實現(xiàn)可實現(xiàn);n高效高效;n使用方便使用方便.典型同步機制典型同步機制 n信號燈與信號燈與PV操作操作( (semaphore and PV operations) )n管程管程( (monitor) )n會合會合( (rendezvous) )n條件臨界區(qū)條件臨界區(qū)( (conditional critical region) )n路徑表達式路徑表達式( (path expression) )n事件事件( (traditional UNIX) )4.3.3 信號量與

34、信號量與PV操作操作E.W.Dijkstra, 1965.4.3.3.1 信號量信號量0與與PV操作的定義操作的定義 struct semaphore int value; point_to_PCB queue; ; semaphore s;Remarks:(1) semaphore is pre-defined data type,(2) s can be declared as needed, eg. var s1,s2:semaphore; 信號量信號量S-valueS-queueS-valueS-queuePCBPCBPCBSemaphore s;FIFOP操作原語操作原語P操作原語操

35、作原語：void P(semaphore *s) s-value-; if (s-valuequeue) asleep(s-queue)是標準函數(shù):(1) 執(zhí)行此操作進程的執(zhí)行此操作進程的PCB入入s-queue尾（狀態(tài)改為等尾（狀態(tài)改為等待）；待）；(2) 轉(zhuǎn)處理機調(diào)度程序。轉(zhuǎn)處理機調(diào)度程序。 Primitive: a piece of code un-interruptibleV操作原語操作原語V操作原語：操作原語：void V(semaphore *s) s-value+; if (s-valuequeue); wakeup(s-queue)是標準函數(shù)：是標準函數(shù)：（1）執(zhí)行次操作系統(tǒng)將

36、隊列）執(zhí)行次操作系統(tǒng)將隊列s-queue頭部的進程的頭部的進程的PCB移移出等待隊列，出等待隊列，并將其插并將其插入就緒隊列入就緒隊列。（2）將移出進程的）將移出進程的狀態(tài)改為就緒。狀態(tài)改為就緒。 Primitive: a piece of code un-interruptible規(guī)定和結(jié)論規(guī)定和結(jié)論n對于信號量變量的規(guī)定：對于信號量變量的規(guī)定：n必須置一次初值，只能置一次初值，初值必須置一次初值，只能置一次初值，初值=0;n只能執(zhí)行只能執(zhí)行P操作和操作和V操作，所有其它操作非法。操作，所有其它操作非法。n幾個有用的結(jié)論幾個有用的結(jié)論：n當(dāng)當(dāng)s-value0時，時，s-queue為空；為空；

37、n當(dāng)當(dāng)s-valuevalue|為隊列為隊列s-queue的長度；的長度；n當(dāng)當(dāng)s.value初=1時，可以實現(xiàn)進程互斥；時，可以實現(xiàn)進程互斥；n當(dāng)當(dāng)s.value初=非1正整數(shù)時，可以時，可以用來管理同種組合資源，申請用來管理同種組合資源，申請資源執(zhí)行一次資源執(zhí)行一次P操作，歸還資源執(zhí)行一次操作，歸還資源執(zhí)行一次V操作；操作；n當(dāng)當(dāng)s.value初=0時，可以實現(xiàn)進程同步。時，可以實現(xiàn)進程同步。semaphore mutex; (初值初值=1） shared int x,y,z; CR1 CR2 CRn用信號量實現(xiàn)進程互斥用信號量實現(xiàn)進程互斥semaphore mutex; (初值初值=1）

38、 shared int x,y,z;P(mutex) P(mutex) P(mutex) CR1 CR2 CRnV(mutex) V(mutex) V(mutex)互斥例子：借書系統(tǒng)互斥例子：借書系統(tǒng)(revisited)nsemaphore mutex=1; n終端終端1： 終端終端2：ndo don 等待借書者等待借書者； 等待借書者等待借書者；n if x1 if x1 n x=x-1; x=x-1;n n 借書借書 借書借書n n else 無書無書; else 無書無書; n while(1) while(1)互斥例子：借書系統(tǒng)互斥例子：借書系統(tǒng)(revisited)semaphor

39、e mutex=1; 終端終端1： 終端終端2：do do 等待借書者等待借書者； 等待借書者等待借書者； P(mutex) P(mutex) if x1 if x 1 x=x-1; x=x-1; V(mutex) V(mutex) 借書借書 借書借書 else V(mutex);無書無書; else V(mutex);無書無書; while(1) while(1)用信號燈實現(xiàn)進程同步用信號燈實現(xiàn)進程同步 后動作后動作先動作先動作 P1:P2:用信號量實現(xiàn)進程同步用信號量實現(xiàn)進程同步 P(S)后動作后動作先動作先動作 V(S)P1:P2:用信號量實現(xiàn)進程同步用信號量實現(xiàn)進程同步n例子：司機例子

40、：司機-售票員問題：售票員問題：n司機活動：司機活動： 售票員活動：售票員活動：n Do Don 關(guān)車門關(guān)車門n 啟動車輛啟動車輛 n 正常行駛正常行駛 售售 票票n 到站停車到站停車 n 開車門開車門n While(1) While(1)用信號量實現(xiàn)進程同步用信號量實現(xiàn)進程同步例子：司機例子：司機-售票員問題：售票員問題：semaphore s1=0,s2=0; 司機活動：司機活動： 售票員活動：售票員活動： Do Do P(S1) 關(guān)車門關(guān)車門 啟動車輛啟動車輛 V(S1) 正常行駛正常行駛 售售 票票 到站停車到站停車 P(S2) V(S2) 開車門開車門 While(1) While(

41、1)用開關(guān)中斷實現(xiàn)用開關(guān)中斷實現(xiàn)P、V操作操作void P(semaphore *s) disable interrupt; s-value-; if (s-valuequeue) enable interrupt; goto CPU dispatcher; else enable interrupt; 用開關(guān)中斷實現(xiàn)用開關(guān)中斷實現(xiàn)P、V操作操作void V(semaphore *s) disable interrupt; s-value+; if (s-value0) wakeup(s-queue) else enable interrupt; 用開關(guān)中斷實現(xiàn)用開關(guān)中斷實現(xiàn)P、V操作操作na

42、sleep(s-queue):set this process status to blocked;place this process in s-queue.nwakeup(s-queue):remove a process from s-queue;place the process in ready list.用用TS、swap指令實現(xiàn)指令實現(xiàn)P、V操作操作void P(semaphore *s) while(TS(s-flag); s-value-; if (s-valuequeue) s-flag=0; goto CPU dispatcher; else s-flag=0; 用用TS

43、、swap指令實現(xiàn)指令實現(xiàn)P、V操作操作void V(semaphore *s) while(TS(s-flag); s-value+; if (s-value0) wakeup(s-queue) else s-flag=0;Classical synchronization problems1. Producers and consumers problem2. Readers and writers problem3. Dining philosophers problem4. Cigarette smokers problem5. Sleepy barbers problemetc. 例

44、例1. 生產(chǎn)者生產(chǎn)者/消費者問題消費者問題預(yù)備知識：預(yù)備知識：組合資源組合資源：若干相對獨立的資源構(gòu)成的資源集合，其中：若干相對獨立的資源構(gòu)成的資源集合，其中每個相對獨立的資源稱為子資源。每個相對獨立的資源稱為子資源。同種組合資源同種組合資源：相同類型子資源構(gòu)成的組合資源。：相同類型子資源構(gòu)成的組合資源。管理：管理：semaphore s; (初值初值=子資源個數(shù)）子資源個數(shù)）例子：例子：2臺打印機臺打印機 semaphore s=2; 申請：申請：P（S）；）； 釋放：釋放：V（S）；）；自動機描述自動機描述210-1-2P(S)P(S)P(S)P(S)P(S)V(S) V(S) V(S)

45、V(S) V(S) S-value=空閑資源數(shù)空閑資源數(shù) S-queue=空空|S-value|=等待進程數(shù)等待進程數(shù) 空閑資源數(shù)空閑資源數(shù)=0.P(S): 申請一臺打印機申請一臺打印機, 分配分配, 空閑打印機減空閑打印機減1P(S): 申請一臺打印機申請一臺打印機, 等待等待, 等待進程數(shù)加等待進程數(shù)加1 2自動機描述自動機描述10-1-2P(S)P(S)P(S)P(S)P(S)V(S) V(S) V(S) V(S) V(S) S-value=空閑資源數(shù)空閑資源數(shù) S-queue=空空|S-value|=等待進程數(shù)等待進程數(shù) 空閑資源數(shù)空閑資源數(shù)=0.V(S): 釋放一臺打印機釋放一臺打印

46、機, 喚醒一個等待者喚醒一個等待者, 打印機分給被喚醒進程打印機分給被喚醒進程, 等待進程數(shù)減等待進程數(shù)減1V(S): 釋放一臺打印機釋放一臺打印機, 空閑打印機數(shù)量增空閑打印機數(shù)量增1 例例1. 生產(chǎn)者生產(chǎn)者/消費者問題消費者問題 0 1 k-1箱子，容量箱子，容量k itemType bufferk生產(chǎn)者生產(chǎn)者消費者消費者生產(chǎn)物品生產(chǎn)物品放入放入B中中B中取物品中取物品消費之消費之環(huán)形緩沖區(qū)環(huán)形緩沖區(qū)10K-1in(in+1)% kout(out+1)% k問題分析生產(chǎn)者活動生產(chǎn)者活動： 消費者活動消費者活動： do do 加工一件物品加工一件物品 箱中取一物品箱中取一物品 物品放入箱中物

47、品放入箱中 消耗這件物品消耗這件物品 while(1) while(1)資源：箱子（同種組合）資源：箱子（同種組合） 資源：物品（同種組合）資源：物品（同種組合） semaphore s1; semaphore s2; s1.value=k; s2.value=0;放前：放前：P（S1） 取前：取前：P（S2）放后：放后：V（S2） 取后：取后：V（S1）同步同步生產(chǎn)者活動生產(chǎn)者活動： 消費者活動消費者活動： Do Do 加工一件物品加工一件物品 P(S2) P(S1) 箱中取一物品箱中取一物品 物品放入箱中物品放入箱中 V(S1) V(S2) 消耗這件物品消耗這件物品 While(1) Wh

48、ile(1)對對B和和in,out的互斥的互斥：semaphore mutex=1; 考慮互斥的生產(chǎn)者和消費者問題考慮互斥的生產(chǎn)者和消費者問題生產(chǎn)者活動：生產(chǎn)者活動： 消費者活動：消費者活動： do do 加工一件物品加工一件物品 P(S2) P(S1) P(mutex) P(mutex) 箱中取一物品箱中取一物品 物品放入箱中物品放入箱中 V(mutex) V(mutex) V(S1) V(S2) 消耗這件物品消耗這件物品 while(1) while(1)程序void producers_consumers; itemType bufferk; semaphore s1=k,s2=0,mu

49、tex=1; int in=0; int out=0;void producer() while(1) produceitem(&item) P(S1); P(mutex); bufferin=item; in=(in+1)%k; V(mutex); V(S2) void consumer() while(1) P(s2); P(mutex); x=bufferout; out=(out+1)%k; V(mutex); V(S1); consumeitem(x); 程序程序Cobegin fork(producer,0); ;fork(producer,m-1); fork(consu

50、mer,0); ;fork(consumer,n-1);Coend;并發(fā)性提高策略并發(fā)性提高策略生產(chǎn)者和消費者：不操作生產(chǎn)者和消費者：不操作buffer的相同分的相同分量量生產(chǎn)者的共享變量生產(chǎn)者的共享變量： Bin, in消費者的共享變量消費者的共享變量： Bout, outin=out: 滿或空,semaphore mutex1=1,mutex2=1; 并發(fā)性提高策略并發(fā)性提高策略生產(chǎn)者活動：生產(chǎn)者活動： 消費者活動：消費者活動： do do 加工一件物品加工一件物品 P(S2) P(S1) P(mutex2) P(mutex1) 箱中取一物品箱中取一物品 物品放入箱中物品放入箱中 V(mu

51、tex2) V(mutex1) V(S1) V(S2) 消耗這件物品消耗這件物品 while(1) while(1)P、V順序不當(dāng)會發(fā)生死鎖順序不當(dāng)會發(fā)生死鎖生產(chǎn)者活動：生產(chǎn)者活動： 消費者活動：消費者活動： do do 加工一件物品加工一件物品 P(S2) P(mutex) P(mutex) P(S1) 箱中取一物品箱中取一物品 物品放入箱中物品放入箱中 V(mutex) V(mutex) V(S1) V(S2) 消耗這件物品消耗這件物品 while(1) while(1)例例2. 讀者讀者/寫者問題寫者問題P. J. Courtois 1971首先提出并解決的問題首先提出并解決的問題Com

52、munication of the ACM, Vol.14, 667-669.ACM: Association for Computing Machinery解法解法1：寫者可能餓死：寫者可能餓死解法解法2：寫者優(yōu)先：寫者優(yōu)先例例2. 讀者讀者/寫者問題寫者問題Problem Statement: 一組公共數(shù)據(jù)一組公共數(shù)據(jù)DB R1 Rm W1 . Wn要求要求：（：（1）R-R可以同時可以同時 （2）R-W不可同時不可同時 （3）W-W不可同時不可同時accessingSolution1: 不考慮不考慮R-R不互斥不互斥semaphore r_w_w=1; Reader： Writer: P

53、(r_w_w); P(r_w_w) 讀操作讀操作 寫操作寫操作 V(r_w_w); V(r_w_w)分析：（分析：（1）寫者活動正確；（）寫者活動正確；（2）R-R不能同時。不能同時。改進：最先進入的改進：最先進入的R執(zhí)行執(zhí)行P；最后離開的；最后離開的R執(zhí)行執(zhí)行V；Solution2: 考慮考慮R-R不互斥不互斥int read_count=0; Reader: read_count=read_count+1; If (read_count=1) P(r_w_w); 讀操作讀操作 read_count=read_count-1; If (read_count=0) V(r_w_w);問題：對問

54、題：對Read_count操作的互斥問題。操作的互斥問題。Solution3: 正確解法正確解法semaphore mutex=1; Reader: P(mutex); read_count=read_count+1; If(read_count=1) P(r_w_w); V(mutex); 讀操作讀操作 P(mutex); read_count=read_count-1; If(read_count=0) V(r_w_w); V(mutex); 讀者等待在何處？讀者等待在何處？ 讀者如何被喚醒？讀者如何被喚醒？程序程序semaphore r_w_w=1; semaphore mutex=1;

55、int read_count=0;viod writer(0) while(1) P(r_w_w); write ops V(r_w_w) 程序（程序（Cont.）viod reader()While(1) P(&mutex); read_count=read_count+1; If(read_count=)1 P(&r_w_w); V(&mutex); read operations P(&mutex); read_count=read_count-1; If(read_count=0) V(&r_w_w); V(mutex); 程序（程序（Cont.

56、）cobegin fork(reader,0); ;fork(reader,m-1); fork(writer,0); ; fork(writer,n-1) coend分析：問題問題：讀者源源不斷，：讀者源源不斷，read_count不歸不歸0，寫者，寫者會被餓死。會被餓死。策略策略：一旦有寫者等待，新到達讀者等待，正在：一旦有寫者等待，新到達讀者等待，正在讀的讀者都結(jié)束后，寫者進入。讀的讀者都結(jié)束后，寫者進入。 Further improvement is left to interested students.寫者優(yōu)先算法寫者優(yōu)先算法 Reader: writer: p(m) 1 p(k)

57、 p(w) 2 if(wc=0) p(w) 4 p(mutex) wc=wc+1 if(rc=0) p(s) v(k) rc=rc+1 p(s) 5 v(mutex) v(w) 3 v(s) v(m) p(k) wc=wc-1 p(mutex) if(wc=0) v(w) 6 rc=rc-1 v(k) if(rc=0) v(s) 7 v(mutex)程序程序int readcount=0, writecount=0; semaphore m=1,w=1,s=1,k=1,mutex=1; reader() writer( ) while(1) while(1) p(m); p(k); p(w);

58、 if writecount= =0 then p(w); p(mutex); writecount= writecount+1; if readcount= =0 then p(s); v(k); readcount=readcount+1; p(s); v(mutex); v(w); v(s); V(m); p(k); writecount=writecount-1; P(mutex); if writecount = =0 then v(w); Readcount=readcount-1; v(k); If readcount= =0 then v(s); V(mutex); 例例4.

59、3臺打印機管理臺打印機管理n設(shè)有3臺類型相同的打印機，其編號分別為1、2、3，編寫一個申請函數(shù)require和一個釋放函數(shù)return。前者要求當(dāng)有打印機空閑時，返回分的的打印機的編號；當(dāng)無打印機空閑時則等待，但被喚醒后返回分得的打印機的編號。后者用于釋放指定編號的打印機，并當(dāng)有申請者等待時將其喚醒。例例4. 3臺打印機管理臺打印機管理enum lp1.3of (free,used); /initial value is freesemaphore s; /initial value is 3semaphore mutex; /initial value is 1void require; v

60、oid return(i:1.3); P(S); P(mutex); P(mutex); lpi:=free; for(i=1,i=t1 & & Sn=tn ) for(i=1;i=n;i+) Si=Si-di;else (1) place the executing process in the waiting queue for the first Si with Siti, (2)and set the program counter to the beginning of the SP operation so that all conditions will be reexamined when the process is reactivated. Simultaneous V-operationSV(S1,d1;Sn,dn);