第3章 進(jìn)程的同步與通信

1、lChap.3 進(jìn)程的同步與通信進(jìn)程的同步與通信1 1、如何控制和協(xié)調(diào)并發(fā)進(jìn)程異步執(zhí)行、如何控制和協(xié)調(diào)并發(fā)進(jìn)程異步執(zhí)行 的時(shí)序？的時(shí)序？ 2 2、進(jìn)程之間如何互相聯(lián)系，傳遞信息？、進(jìn)程之間如何互相聯(lián)系，傳遞信息？ 本章討論的主要問題本章討論的主要問題3.1 3.1 進(jìn)程間的相互作用進(jìn)程間的相互作用n進(jìn)程間的聯(lián)系進(jìn)程間的聯(lián)系n進(jìn)程的同步機(jī)制進(jìn)程的同步機(jī)制信號(hào)量及信號(hào)量及P.VP.V操操作（解決進(jìn)程同步互斥問題）作（解決進(jìn)程同步互斥問題）1.1.進(jìn)程間的聯(lián)系進(jìn)程間的聯(lián)系相交進(jìn)程與無關(guān)進(jìn)程相交進(jìn)程與無關(guān)進(jìn)程相交進(jìn)程：指多個(gè)并發(fā)進(jìn)程在邏輯上有相交進(jìn)程：指多個(gè)并發(fā)進(jìn)程在邏輯上有某種聯(lián)系某種聯(lián)系無關(guān)進(jìn)程（

2、不相交進(jìn)程）：在邏輯上無無關(guān)進(jìn)程（不相交進(jìn)程）：在邏輯上無任何聯(lián)系的進(jìn)程任何聯(lián)系的進(jìn)程直接作用和間接作用直接作用和間接作用直接作用：直接作用：進(jìn)程間的相互聯(lián)系是進(jìn)程間的相互聯(lián)系是有意識(shí)的安排的有意識(shí)的安排的，直接作用只發(fā)生在相交進(jìn)程間直接作用只發(fā)生在相交進(jìn)程間間接作用：間接作用：進(jìn)程間要通過進(jìn)程間要通過某種中介某種中介發(fā)生聯(lián)系，是無發(fā)生聯(lián)系，是無意識(shí)安排的，可發(fā)生在相交進(jìn)程之間，意識(shí)安排的，可發(fā)生在相交進(jìn)程之間，也可發(fā)生在無關(guān)進(jìn)程之間也可發(fā)生在無關(guān)進(jìn)程之間進(jìn)程的同步（直接作用）進(jìn)程的同步（直接作用）進(jìn)程的同步：進(jìn)程的同步：synchronism指系統(tǒng)中多個(gè)進(jìn)程中發(fā)生的事件存在某種指系統(tǒng)中多個(gè)進(jìn)

3、程中發(fā)生的事件存在某種時(shí)序關(guān)系，需要相互合作，共同完成一項(xiàng)時(shí)序關(guān)系，需要相互合作，共同完成一項(xiàng)任務(wù)。任務(wù)。具體說，一個(gè)進(jìn)程運(yùn)行到某一點(diǎn)時(shí)具體說，一個(gè)進(jìn)程運(yùn)行到某一點(diǎn)時(shí)要求另一伙伴進(jìn)程為它提供消息，在未獲要求另一伙伴進(jìn)程為它提供消息，在未獲得消息之前，該進(jìn)程處于等待狀態(tài)，獲得得消息之前，該進(jìn)程處于等待狀態(tài)，獲得消息后被喚醒進(jìn)入就緒態(tài)消息后被喚醒進(jìn)入就緒態(tài)同步問題同步問題1nA race between two or more teams, in which each team member runs only a set part of the race and is then relieved

4、 by another member of the team.緩沖區(qū)鍵盤鍵盤計(jì)算計(jì)算緩沖區(qū)緩沖區(qū)緩沖區(qū)B進(jìn)程A進(jìn)程 A A進(jìn)程只有當(dāng)緩沖區(qū)為空時(shí)，才能將數(shù)據(jù)輸入緩沖區(qū)，進(jìn)程只有當(dāng)緩沖區(qū)為空時(shí)，才能將數(shù)據(jù)輸入緩沖區(qū)， B B進(jìn)程只有當(dāng)緩沖區(qū)有數(shù)據(jù)時(shí)，才能從緩沖區(qū)取數(shù)進(jìn)行計(jì)算。進(jìn)程只有當(dāng)緩沖區(qū)有數(shù)據(jù)時(shí)，才能從緩沖區(qū)取數(shù)進(jìn)行計(jì)算。 進(jìn)程的同步與互斥雖然是兩個(gè)既有區(qū)別又有聯(lián)系的概念，進(jìn)程的同步與互斥雖然是兩個(gè)既有區(qū)別又有聯(lián)系的概念，但從本質(zhì)上看并發(fā)進(jìn)程的異步執(zhí)行都必須按一定的相互約束但從本質(zhì)上看并發(fā)進(jìn)程的異步執(zhí)行都必須按一定的相互約束的時(shí)序進(jìn)行，因此統(tǒng)稱為的時(shí)序進(jìn)行，因此統(tǒng)稱為“進(jìn)程同步進(jìn)程同步”。

5、顯然，必須解決好進(jìn)程的同步問題，才能保證并發(fā)進(jìn)程顯然，必須解決好進(jìn)程的同步問題，才能保證并發(fā)進(jìn)程的正常執(zhí)行。的正常執(zhí)行。同步問題同步問題2進(jìn)程的互斥（間接作用）進(jìn)程的互斥（間接作用）由于各進(jìn)程要求共享資源，而有些資源需由于各進(jìn)程要求共享資源，而有些資源需要互斥使用，因此各進(jìn)程間競(jìng)爭(zhēng)使用這要互斥使用，因此各進(jìn)程間競(jìng)爭(zhēng)使用這些資源，進(jìn)程的這種關(guān)系為進(jìn)程的互斥些資源，進(jìn)程的這種關(guān)系為進(jìn)程的互斥臨界資源：臨界資源：critical resource 系統(tǒng)中某些資源一次只允許一個(gè)進(jìn)程使系統(tǒng)中某些資源一次只允許一個(gè)進(jìn)程使用，稱這樣的資源為臨界資源或互斥資用，稱這樣的資源為臨界資源或互斥資源或共享變量源或共

6、享變量臨界區(qū)（互斥區(qū)）：臨界區(qū)（互斥區(qū)）：critical section一個(gè)程序片段的集合，這些程序片段分散一個(gè)程序片段的集合，這些程序片段分散在不同的進(jìn)程中，對(duì)某個(gè)共享的數(shù)據(jù)結(jié)在不同的進(jìn)程中，對(duì)某個(gè)共享的數(shù)據(jù)結(jié)構(gòu)（共享資源）進(jìn)行操作構(gòu)（共享資源）進(jìn)行操作 在進(jìn)程中涉及到臨界資源的程序段叫在進(jìn)程中涉及到臨界資源的程序段叫臨臨界區(qū)界區(qū) 多個(gè)進(jìn)程的臨界區(qū)稱為多個(gè)進(jìn)程的臨界區(qū)稱為相關(guān)臨界區(qū)相關(guān)臨界區(qū) 每個(gè)進(jìn)程每個(gè)進(jìn)程 互斥訪問互斥訪問臨界資源臨界資源的那段代碼稱為的那段代碼稱為臨界區(qū)臨界區(qū)。代。代碼構(gòu)成如下碼構(gòu)成如下： repeatrepeat entry section entry sectio

7、n 進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) 申請(qǐng)進(jìn)入臨界區(qū)申請(qǐng)進(jìn)入臨界區(qū) critical section critical section 臨界區(qū)臨界區(qū) 訪問臨界資源訪問臨界資源 exit section exit section 退出區(qū)退出區(qū) 退出對(duì)臨界資源的訪退出對(duì)臨界資源的訪問問 remainder section remainder section 剩留區(qū)剩留區(qū) 進(jìn)程的其他代碼進(jìn)程的其他代碼 until false until false 1 1。什么是臨界資源。什么是臨界資源 凡是以互斥方式使用的共享資源都稱為臨界資源。臨界凡是以互斥方式使用的共享資源都稱為臨界資源。臨界資源具有一次只允許一個(gè)進(jìn)程使用的屬性

8、資源具有一次只允許一個(gè)進(jìn)程使用的屬性。2 2。臨界區(qū)。臨界區(qū) （critical section）使用互斥區(qū)的原則使用互斥區(qū)的原則有空讓進(jìn)：有空讓進(jìn)：當(dāng)無進(jìn)程在互斥區(qū)時(shí)，任何有權(quán)使用當(dāng)無進(jìn)程在互斥區(qū)時(shí)，任何有權(quán)使用互斥區(qū)的進(jìn)程可進(jìn)入互斥區(qū)的進(jìn)程可進(jìn)入無空等待：無空等待：不允許兩個(gè)以上的進(jìn)程同時(shí)進(jìn)入互斥不允許兩個(gè)以上的進(jìn)程同時(shí)進(jìn)入互斥區(qū)區(qū)多中擇一：多中擇一：當(dāng)沒有進(jìn)程在臨界區(qū)，而同時(shí)有多個(gè)當(dāng)沒有進(jìn)程在臨界區(qū)，而同時(shí)有多個(gè)進(jìn)程要求進(jìn)入臨界區(qū)，只能讓其中之一進(jìn)入臨進(jìn)程要求進(jìn)入臨界區(qū)，只能讓其中之一進(jìn)入臨界區(qū)，其他進(jìn)程必須等待界區(qū)，其他進(jìn)程必須等待有限等待：有限等待：任何進(jìn)入互斥區(qū)的要求應(yīng)在有限的時(shí)任

9、何進(jìn)入互斥區(qū)的要求應(yīng)在有限的時(shí)間內(nèi)得到滿足間內(nèi)得到滿足讓權(quán)等待：讓權(quán)等待：處于等待狀態(tài)的進(jìn)程應(yīng)放棄占用處于等待狀態(tài)的進(jìn)程應(yīng)放棄占用CPUCPU，以使其他進(jìn)程有機(jī)會(huì)得到以使其他進(jìn)程有機(jī)會(huì)得到CPUCPU的使用權(quán)的使用權(quán)前提：任何進(jìn)程無權(quán)停止其它進(jìn)程的運(yùn)行前提：任何進(jìn)程無權(quán)停止其它進(jìn)程的運(yùn)行 進(jìn)程之間相對(duì)運(yùn)行速度無硬性規(guī)定進(jìn)程之間相對(duì)運(yùn)行速度無硬性規(guī)定進(jìn)程互斥的解決有兩種做法進(jìn)程互斥的解決有兩種做法: :n由競(jìng)爭(zhēng)各方平等協(xié)商由競(jìng)爭(zhēng)各方平等協(xié)商n引入進(jìn)程管理者，由管理者來協(xié)調(diào)競(jìng)爭(zhēng)引入進(jìn)程管理者，由管理者來協(xié)調(diào)競(jìng)爭(zhēng)各方對(duì)互斥資源的使用各方對(duì)互斥資源的使用具體方法：具體方法：n硬件硬件n軟件軟件使用互斥

10、區(qū)的原則（續(xù)）使用互斥區(qū)的原則（續(xù)）軟件解法軟件解法 (1)(1)free: free: 表示臨界區(qū)標(biāo)志表示臨界區(qū)標(biāo)志 true: true: 有進(jìn)程在臨界區(qū)有進(jìn)程在臨界區(qū) false:false:無進(jìn)程在臨界區(qū)無進(jìn)程在臨界區(qū)( (初值初值) ) . . while (free); while (free); free = true; free = true; 臨界區(qū)臨界區(qū) free = false;free = false;空循環(huán)空循環(huán)軟件解法軟件解法 (2)(2)turn: true turn: true P P進(jìn)入臨界區(qū)進(jìn)入臨界區(qū) false false Q Q進(jìn)入臨界區(qū)進(jìn)入臨界區(qū) .P

11、: while (not turn);P: while (not turn); 臨界區(qū)臨界區(qū) turn = true;turn = true;Q: while (turn);Q: while (turn); 臨界區(qū)臨界區(qū) turn = false;turn = false;軟件解法的缺點(diǎn)：軟件解法的缺點(diǎn)： 1. 1. 忙等待忙等待 2. 2. 實(shí)現(xiàn)過于復(fù)雜，需要高的編程技巧實(shí)現(xiàn)過于復(fù)雜，需要高的編程技巧硬件解法：提供專門的硬件指令，允許對(duì)一個(gè)字的硬件解法：提供專門的硬件指令，允許對(duì)一個(gè)字的內(nèi)容進(jìn)行檢測(cè)和修正，或交換兩個(gè)字的內(nèi)容內(nèi)容進(jìn)行檢測(cè)和修正，或交換兩個(gè)字的內(nèi)容目的：解決共享變量的目的：解決

12、共享變量的完整性和正確性完整性和正確性 簡(jiǎn)單、有效，特別簡(jiǎn)單、有效，特別適用于多處理機(jī)適用于多處理機(jī)缺點(diǎn)：忙等待缺點(diǎn)：忙等待硬件解法硬件解法 (1)(1) “測(cè)試并設(shè)置測(cè)試并設(shè)置”指令指令 TSTS指令執(zhí)行過程不可分割。指令執(zhí)行過程不可分割。 為臨界資源設(shè)置一個(gè)布爾量為臨界資源設(shè)置一個(gè)布爾量 LOCKLOCK：實(shí)現(xiàn)的基本思想是：對(duì)實(shí)現(xiàn)的基本思想是：對(duì)臨界資源臨界資源“加鎖加鎖” 進(jìn)程的同步機(jī)制可以用軟件實(shí)現(xiàn)，也可以用硬件實(shí)現(xiàn)。進(jìn)程的同步機(jī)制可以用軟件實(shí)現(xiàn)，也可以用硬件實(shí)現(xiàn)。（1 1）用）用T TestandestandS Set et 指令實(shí)現(xiàn)互斥指令實(shí)現(xiàn)互斥LOCK LOCK = false

13、 false 沒有進(jìn)程在臨界區(qū)沒有進(jìn)程在臨界區(qū)true true 有進(jìn)程進(jìn)入臨界區(qū)有進(jìn)程進(jìn)入臨界區(qū) TSTS指令的形式指令的形式： function function tsts（varvar lock lock：booleanboolean）：）：booleanboolean； begin begin tsts：=lock=lock； locklock：=true=true； endend；以兩進(jìn)程以兩進(jìn)程P1P1、P2P2并發(fā)執(zhí)行為例，如果并發(fā)執(zhí)行為例，如果P1P1先執(zhí)行：先執(zhí)行：若若P1P1先進(jìn)入臨界區(qū)，則先進(jìn)入臨界區(qū)，則P2P2循環(huán)執(zhí)行循環(huán)執(zhí)行TSTS指令，直到指令，直到P1P1退出臨界

14、區(qū)。退出臨界區(qū)。調(diào)用TS指令p1TS=true進(jìn)入P1臨界區(qū)Lock：=false進(jìn)入剩余區(qū)調(diào)用TS指令p2TS=true進(jìn)入P2臨界區(qū)Lock：=false進(jìn)入剩余區(qū)進(jìn)入剩余區(qū)調(diào)用調(diào)用TS指令指令TS=trueNY進(jìn)入進(jìn)入P1臨界區(qū)臨界區(qū)調(diào)用TS指令TS=trueYN調(diào)用TS指令調(diào)用調(diào)用TS指令指令TS=trueTS=trueLock：=false進(jìn)入進(jìn)入P2臨界區(qū)臨界區(qū)進(jìn)入剩余區(qū)進(jìn)入剩余區(qū) 如果如果P2P2先執(zhí)行：若先執(zhí)行：若P2P2先進(jìn)入臨界區(qū)，則先進(jìn)入臨界區(qū)，則P1P1循環(huán)執(zhí)行循環(huán)執(zhí)行TSTS指令，直指令，直到到P2P2退出臨界區(qū)。退出臨界區(qū)。 結(jié)論：結(jié)論： TSTS指令有效實(shí)現(xiàn)互斥（

15、空閑讓進(jìn)、忙則等待）指令有效實(shí)現(xiàn)互斥（空閑讓進(jìn)、忙則等待） 循環(huán)測(cè)試，處于循環(huán)測(cè)試，處于“忙等待忙等待”（未讓權(quán)等待）（未讓權(quán)等待）調(diào)用TS指令p2TS=true進(jìn)入P1臨界區(qū)Lock：=false進(jìn)入剩余區(qū)調(diào)用調(diào)用TS指令指令TS=trueNY進(jìn)入進(jìn)入P2臨界區(qū)臨界區(qū)Lock：=false進(jìn)入剩余區(qū)進(jìn)入剩余區(qū)調(diào)用TS指令p1TS=true進(jìn)入P2臨界區(qū)Lock：=false進(jìn)入剩余區(qū)進(jìn)入剩余區(qū)調(diào)用TS指令TS=trueYN調(diào)用TS指令調(diào)用調(diào)用TS指令指令TS=trueTS=true進(jìn)入進(jìn)入P1臨界區(qū)臨界區(qū)Lock：=false進(jìn)入剩余區(qū)進(jìn)入剩余區(qū)2.2.進(jìn)程的同步機(jī)制進(jìn)程的同步機(jī)制信號(hào)量及信

16、號(hào)量及P.VP.V操作操作 以上介紹的各種算法都存在問題，它們是以上介紹的各種算法都存在問題，它們是平平等進(jìn)程等進(jìn)程間的一種間的一種協(xié)商機(jī)制協(xié)商機(jī)制，需要一個(gè)地位高，需要一個(gè)地位高于進(jìn)程的于進(jìn)程的管理者管理者來解決公有資源的使用問題來解決公有資源的使用問題 操作系統(tǒng)操作系統(tǒng)可從進(jìn)程管理者的角度來處理互斥可從進(jìn)程管理者的角度來處理互斥的問題，的問題，信號(hào)量信號(hào)量就是操作系統(tǒng)提供的管理公就是操作系統(tǒng)提供的管理公有資源的有效手段有資源的有效手段進(jìn)程的同步機(jī)制（續(xù)）進(jìn)程的同步機(jī)制（續(xù)）同步機(jī)制：同步機(jī)制： 信號(hào)量信號(hào)量及及P P、V V操作；管程；操作；管程；條件臨條件臨界域；路徑表達(dá)式等（用于集中式

17、系界域；路徑表達(dá)式等（用于集中式系統(tǒng)中）統(tǒng)中）同步機(jī)制應(yīng)滿足的基本要求：同步機(jī)制應(yīng)滿足的基本要求：* * 描述能力描述能力* * 可以實(shí)現(xiàn)可以實(shí)現(xiàn)* * 效率高效率高* * 使用方便使用方便n1965年，由荷蘭學(xué)者年，由荷蘭學(xué)者Dijkstra提出（所以提出（所以P、V分別是荷蘭語的分別是荷蘭語的test(proberen)和和increment(verhogen)）n一種卓有成效的進(jìn)程同步機(jī)制一種卓有成效的進(jìn)程同步機(jī)制n最初提出的是二元信號(hào)量（互斥）最初提出的是二元信號(hào)量（互斥） 推廣到一般信號(hào)量（多值）（同步）推廣到一般信號(hào)量（多值）（同步）n廣泛應(yīng)用于存在臨界資源和臨界區(qū)控制廣泛應(yīng)用于存

18、在臨界資源和臨界區(qū)控制的場(chǎng)合的場(chǎng)合信號(hào)量及信號(hào)量及P、V操作操作Semaphores (proposed by Dijkstra in 1965)nWhat a Semaphore is?nAn integer variablenRepresent the number of resources available (when it is greater than or equals to 0)nRepresent the number of processes waiting for the resources( when it is less than 0)nOperations on a

19、 semaphorenInitializationnP operation - to testnV operation - to increment信號(hào)量：信號(hào)量：semaphoresemaphoren是一個(gè)數(shù)據(jù)結(jié)構(gòu)是一個(gè)數(shù)據(jù)結(jié)構(gòu)n定義如下：定義如下： strucstruc semaphore semaphore intint value; value;pointer_PCB queue;pointer_PCB queue; n信號(hào)量說明：信號(hào)量說明： semaphore s;semaphore s; S.value ：= S.Value + 1； 若 S.Value 0 進(jìn)程繼續(xù)執(zhí)行。 若

20、S.Value 0 則釋放S等待隊(duì)列中的一個(gè)進(jìn)程 ， 使之轉(zhuǎn)為就緒狀態(tài)。P P、V V操作原語操作原語 定義：定義：VARVAR S S：SemaphoreSemaphore； 1 1。P P操作（操作（wait wait 原語）原語） 每作一次每作一次P P操作，申請(qǐng)分配一個(gè)單位的資源。操作，申請(qǐng)分配一個(gè)單位的資源。 P P（S S） 對(duì)信號(hào)量對(duì)信號(hào)量S S 進(jìn)行進(jìn)行P P操作。操作。 2 2。V V操作（操作（SignalSignal原語）原語） V V（S S） 對(duì)信號(hào)量對(duì)信號(hào)量S S 進(jìn)行進(jìn)行V V操作，釋放一個(gè)單位的資源。操作，釋放一個(gè)單位的資源。 S.value ：= S.Valu

21、e - 1； 若若 S.Value 0 進(jìn)程繼續(xù)執(zhí)行。進(jìn)程繼續(xù)執(zhí)行。 若若 S.Value 0 0 時(shí)，其值表示某類資源可用數(shù)量。時(shí)，其值表示某類資源可用數(shù)量。 S.ValueS.Value 0 0 時(shí)，其絕對(duì)值表示在信號(hào)量隊(duì)列中等待時(shí)，其絕對(duì)值表示在信號(hào)量隊(duì)列中等待 該資源的進(jìn)程數(shù)。該資源的進(jìn)程數(shù)。 P P、V V操作有嚴(yán)格的不可分割性；執(zhí)行過程不允許中斷；操作有嚴(yán)格的不可分割性；執(zhí)行過程不允許中斷； P P、V V操作成對(duì)出現(xiàn)。操作成對(duì)出現(xiàn)。 （根據(jù)同步機(jī)制的原則，分析P、V操作的特點(diǎn)，）？問題？問題？如何使用如何使用P P、V V操作實(shí)現(xiàn)同步機(jī)制？操作實(shí)現(xiàn)同步機(jī)制？ 考慮：考慮： 如何控

22、制互斥地使用臨界資源？如何控制互斥地使用臨界資源？ 如何控制進(jìn)程并發(fā)執(zhí)行的時(shí)序？如何控制進(jìn)程并發(fā)執(zhí)行的時(shí)序？實(shí)現(xiàn)同步機(jī)制實(shí)現(xiàn)同步機(jī)制基本思想是：加基本思想是：加鎖、解鎖鎖、解鎖Another Meaning from SemaphorenP to request resourcesnV to release resources1、利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥、利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥n共享某個(gè)公有資源共享某個(gè)公有資源 定義一個(gè)互斥信號(hào)量，初定義一個(gè)互斥信號(hào)量，初值為值為1P(S)V(S)臨界區(qū)Mutual Exclusion Achieved by Using Semaphoreshared sema

23、phore S = 1;/P(S);/ Critical SectionV(S);The Bounded-Buffer Problem 1PAPAPBPBbuf設(shè) mutex 公共互斥信號(hào)量 初值：mutex.Value = 1利用P、V操作實(shí)現(xiàn)互斥的模型實(shí)現(xiàn)進(jìn)程互斥實(shí)現(xiàn)進(jìn)程互斥 以兩個(gè)進(jìn)程并發(fā)執(zhí)行為例以兩個(gè)進(jìn)程并發(fā)執(zhí)行為例進(jìn)程進(jìn)程P1P1.P P（mutexmutex）；）；進(jìn)入進(jìn)入P1P1臨界區(qū)；臨界區(qū)；V V（mutexmutex）；）；.值值0 0 進(jìn)程進(jìn)程P2P2.P P（mutexmutex）；）； 進(jìn)入進(jìn)入P2P2臨界區(qū)；臨界區(qū)； V（mutex）；）；.值值0 0 值值-1-1

24、 進(jìn)程進(jìn)程P1P1先執(zhí)行先執(zhí)行 P P（mutexmutex）；）；進(jìn)程進(jìn)程P1P1進(jìn)入臨界區(qū)；進(jìn)入臨界區(qū)； 進(jìn)程進(jìn)程P2P2開始執(zhí)行開始執(zhí)行 P P（mutexmutex）；）；進(jìn)程進(jìn)程P2P2阻塞，插入阻塞隊(duì)列。阻塞，插入阻塞隊(duì)列。 若進(jìn)程若進(jìn)程P1P1再次執(zhí)行再次執(zhí)行 V V（mutexmutex）；）；mutex.Valuemutex.Value=0 =0 釋放資源。釋放資源。 2、實(shí)現(xiàn)進(jìn)程間的同步、實(shí)現(xiàn)進(jìn)程間的同步nPA：需要空緩沖區(qū)資源，該資源由需要空緩沖區(qū)資源，該資源由PB取取數(shù)后產(chǎn)生，空緩沖區(qū)資源用信號(hào)量數(shù)后產(chǎn)生，空緩沖區(qū)資源用信號(hào)量Sempty表示表示nPB：需要滿緩沖區(qū)資源

25、，該資源由需要滿緩沖區(qū)資源，該資源由PA送送數(shù)后產(chǎn)生，滿緩沖區(qū)資源用信號(hào)量數(shù)后產(chǎn)生，滿緩沖區(qū)資源用信號(hào)量Sfull表表示示PAPAPBPBbuf實(shí)現(xiàn)進(jìn)程間的同步實(shí)現(xiàn)進(jìn)程間的同步PA:P(Sempty);V(Sfull);Goto PA;PB:P(Sfull);V(Sempty);Goto PB;Shared Semaphore Sempty := 1Shared Semaphore Sfull := 0 分析：打印進(jìn)程與計(jì)算進(jìn)程之間有兩個(gè)約束： 1）計(jì)算進(jìn)程只有當(dāng)緩沖區(qū)為空時(shí)，才能放入計(jì)算結(jié)果。 2）打印進(jìn)程只有當(dāng)緩沖區(qū)有結(jié)果時(shí)，才能從緩沖區(qū)取 計(jì)算結(jié)果打印。定義兩個(gè)信號(hào)量：Sempty、 S

26、full ，用于控制這兩個(gè)約束：Sfull 控制打印進(jìn)程從緩沖區(qū)取計(jì)算結(jié)果打印。Sempty 控制計(jì)算進(jìn)程向緩沖區(qū)送計(jì)算結(jié)果。2 2、實(shí)現(xiàn)進(jìn)程同步、實(shí)現(xiàn)進(jìn)程同步 實(shí)例：實(shí)例： 打印進(jìn)程與計(jì)算進(jìn)程的同步問題。打印進(jìn)程與計(jì)算進(jìn)程的同步問題。緩沖區(qū)計(jì)算計(jì)算打印機(jī)打印機(jī)緩沖區(qū)緩沖區(qū)緩沖區(qū)打印打印進(jìn)程進(jìn)程計(jì)算進(jìn)程計(jì)算進(jìn)程SfullSempty設(shè)：設(shè)： Sempty 初值為初值為1 1 Sfull初值為初值為0 0 表示緩沖區(qū)為空。表示緩沖區(qū)為空。 當(dāng)當(dāng) Sfull 0 0 表示可以打印表示可以打印 當(dāng)當(dāng) Sempty 0 0 表示可以表示可以放入計(jì)算結(jié)果。放入計(jì)算結(jié)果。信號(hào)量機(jī)制的基本原理信號(hào)量機(jī)制的基

27、本原理n兩個(gè)或兩個(gè)或多個(gè)進(jìn)程可以通過簡(jiǎn)單的信號(hào)進(jìn)行合作，一多個(gè)進(jìn)程可以通過簡(jiǎn)單的信號(hào)進(jìn)行合作，一個(gè)進(jìn)程被迫在某個(gè)指定位置停止，直到它收到一個(gè)個(gè)進(jìn)程被迫在某個(gè)指定位置停止，直到它收到一個(gè)特定的信號(hào)才繼續(xù)。特定的信號(hào)才繼續(xù)。n通過合適的信號(hào)結(jié)構(gòu)可以滿足任何復(fù)雜的協(xié)作要求。通過合適的信號(hào)結(jié)構(gòu)可以滿足任何復(fù)雜的協(xié)作要求。n為了發(fā)信號(hào)，使用特殊的變量為了發(fā)信號(hào)，使用特殊的變量信號(hào)量。信號(hào)量。n進(jìn)程執(zhí)行原語進(jìn)程執(zhí)行原語 signal(S) / V(S)發(fā)出信號(hào)，通過執(zhí)行發(fā)出信號(hào)，通過執(zhí)行 wait(S) / P(S)接收信號(hào)；如果沒有相應(yīng)的信號(hào)到達(dá)，接收信號(hào)；如果沒有相應(yīng)的信號(hào)到達(dá)，該進(jìn)程將被掛起直到所需

28、信號(hào)到達(dá)。該進(jìn)程將被掛起直到所需信號(hào)到達(dá)。Another Meaning from SemaphorenP wait nTo wait for a signalnV signal nTo give a signal to somebody.The Bounded-Buffer Problem 2PAPAPBPBbufbufbuf.bufThe buffer is finite and consists of a linear array of elementsQ: How to describe ? Mutual Exclusion Needed!Synchronization Between

29、 Producer and ConsumernProducer:repeatproduce P(Sempty); V(Sfull);forevernConsumer:repeat P(Sfull); V(Sempty);consumeforeverSempty, Sfull : Semaphore;Sempty := n;Sfull := 0;Classical Synchronization Problemsn生產(chǎn)者生產(chǎn)者消費(fèi)者問題消費(fèi)者問題( the Producer-Consumer Problem )n讀者與寫者問題讀者與寫者問題( the Readers and Writers Pr

30、oblem )經(jīng)典的生產(chǎn)者經(jīng)典的生產(chǎn)者消費(fèi)者問題消費(fèi)者問題消費(fèi)者消費(fèi)者生產(chǎn)者生產(chǎn)者生產(chǎn)者生產(chǎn)者消費(fèi)者問題分析消費(fèi)者問題分析n生產(chǎn)者與消費(fèi)者間的同步關(guān)系生產(chǎn)者與消費(fèi)者間的同步關(guān)系n生產(chǎn)者之間互斥訪問緩沖區(qū)生產(chǎn)者之間互斥訪問緩沖區(qū)n消費(fèi)者之間互斥訪問緩沖區(qū)消費(fèi)者之間互斥訪問緩沖區(qū)n生產(chǎn)者與消費(fèi)者之間互斥訪問緩沖區(qū)生產(chǎn)者與消費(fèi)者之間互斥訪問緩沖區(qū) P P進(jìn)程不能往進(jìn)程不能往“滿滿”的緩沖區(qū)中放產(chǎn)品，的緩沖區(qū)中放產(chǎn)品，設(shè)置信號(hào)量為設(shè)置信號(hào)量為Sempty Q Q進(jìn)程不能從進(jìn)程不能從“空空”的緩沖區(qū)中取產(chǎn)品，的緩沖區(qū)中取產(chǎn)品，設(shè)置信號(hào)量設(shè)置信號(hào)量Sfull Synchronization Between

31、 Producer and ConsumernProducer:repeatproduce P(Sempty);V(Sfull);forevernConsumer:repeat P(Sfull);V(Sempty);consumeforeverSempty, Sfull : Semaphore;Sempty := n;Sfull := 0;.PQ放 消 息取 消 息nn個(gè) 緩 沖 區(qū)(Buffer)ijMutual Exclusion Among Producers/ConsumersnProducer:RepeatproduceP(mutex);V(mutex);forevernConsum

32、er:repeatP(mutex);V(mutex);consumeforevermutex: Semaphore;mutex := 1;A Solution to the Bounded-Buffer Producer/Consumer ProblemSemaphores:Sempty: Semaphore := n;Sfull: Semaphore := 0;Mutex: Semaphore := 1;A Solution to the Bounded-Buffer Producer/Consumer ProblemnProducer:RepeatproduceP(Sempty);P(mu

33、tex);V(Sfull);V(mutex);forevernConsumer:repeatP(Sfull);P(mutex);V(Sempty);V(mutex);consumeforeverV操作出現(xiàn)的次序能否顛倒？P操作出現(xiàn)的次序能否顛倒？得出結(jié)論：得出結(jié)論：生產(chǎn)一種產(chǎn)品P（S n）V（S 0)V(S)P（S ）產(chǎn)品送入緩沖區(qū)P(S0)P(S)V(S)消耗該產(chǎn)品從緩沖區(qū)取一產(chǎn)品V(Sn)生產(chǎn)者消費(fèi)者ProducerConsumerProblem 1n桌上有一空盤，只允許放入一個(gè)水果。桌上有一空盤，只允許放入一個(gè)水果。爸爸專向盤中放蘋果，媽媽專向盤中入爸爸專向盤中放蘋果，媽媽專向盤中入桔子

34、，女兒專等吃盤中的蘋果，兒子專桔子，女兒專等吃盤中的蘋果，兒子專等吃盤中的桔子。試用等吃盤中的桔子。試用P、V原語實(shí)現(xiàn)爸原語實(shí)現(xiàn)爸爸、媽媽、兒子和女兒間能同步的程序。爸、媽媽、兒子和女兒間能同步的程序。 The Readers / Writers Problem There is a data area shared among a number of processes. The data area could be a file, a block of main memory, or even a bank of processor registers. There are a numbe

35、r of processes that only read the data area(readers) and a number that only write to the data area(writers).The Readers / Writers ProblemThe following conditions must be satisfied:1.Any number of reader may simultaneously read the file.2.Only one writer at a time may write to the file.3.If a writer

36、is writing to the file, no reader may read it.讀者與寫者問題讀者與寫者問題n讀者：只能讀取數(shù)據(jù)區(qū)中的數(shù)據(jù)讀者：只能讀取數(shù)據(jù)區(qū)中的數(shù)據(jù)n寫者：只能往數(shù)據(jù)區(qū)中寫入數(shù)據(jù)寫者：只能往數(shù)據(jù)區(qū)中寫入數(shù)據(jù)n滿足的要求：滿足的要求：1、同時(shí)可以有任意多個(gè)讀者讀取數(shù)據(jù)、同時(shí)可以有任意多個(gè)讀者讀取數(shù)據(jù)2、在某個(gè)時(shí)候只能有一個(gè)寫者往里寫數(shù)據(jù)、在某個(gè)時(shí)候只能有一個(gè)寫者往里寫數(shù)據(jù)3、在寫的時(shí)候不能讀，讀的時(shí)候不能寫、在寫的時(shí)候不能讀，讀的時(shí)候不能寫 與生產(chǎn)者與生產(chǎn)者/消費(fèi)者問題的區(qū)別？消費(fèi)者問題的區(qū)別？A Solution to Readers/Writers Proble

37、mnSemaphores:nreadcount: integer;/ number of readersnrmutex: semaphores := 1;/ mutual exclusionnwmutex: Semaphores := 1;/ mutual exclusion among writersA Solution to Readers/Writers ProblemnReader:repeatP(rmutex);readcount := readcount + 1;if readcount =1 then P(wmutex);V(rmutex);READUNIT;P(rmutex);

38、readcount := readcount - 1;if readcount = 0 then V(wmutex);V(rmutex);foreverlWriter:repeatP(wmutex);WRITEUNIT;V(wmutex);forever本講內(nèi)容本講內(nèi)容nP、V操作小結(jié)操作小結(jié)n信號(hào)量集信號(hào)量集n進(jìn)程間通信進(jìn)程間通信回顧回顧經(jīng)典的進(jìn)程同步問題：經(jīng)典的進(jìn)程同步問題：n生產(chǎn)者生產(chǎn)者消費(fèi)者問題消費(fèi)者問題n讀者讀者寫者問題寫者問題Problem 2n有一閱覽室，共有有一閱覽室，共有100個(gè)座位。讀者進(jìn)入個(gè)座位。讀者進(jìn)入前必須先在一張登記表上登記，該表為前必須先在一張登記表上登記，該表為

39、每一座位列一表目，包括座號(hào)和讀者姓每一座位列一表目，包括座號(hào)和讀者姓名。讀者離開時(shí)要消掉登記內(nèi)容。試用名。讀者離開時(shí)要消掉登記內(nèi)容。試用某一種語言（或類語言）和某一種語言（或類語言）和P、V操作描操作描述讀者進(jìn)程的同步結(jié)構(gòu)。述讀者進(jìn)程的同步結(jié)構(gòu)。 n【分析分析】n本例是考查操作系統(tǒng)中信號(hào)量的應(yīng)用本例是考查操作系統(tǒng)中信號(hào)量的應(yīng)用. 讀者要申請(qǐng)座讀者要申請(qǐng)座位，首先要獲得登記表以便在上面進(jìn)行登記；該讀位，首先要獲得登記表以便在上面進(jìn)行登記；該讀者在登記過程中是不允許其他讀者進(jìn)行登記的；因者在登記過程中是不允許其他讀者進(jìn)行登記的；因此，需要引入一個(gè)初值為此，需要引入一個(gè)初值為1的信號(hào)的信號(hào)量量mut

40、ex以實(shí)現(xiàn)讀以實(shí)現(xiàn)讀者間對(duì)登記表的互斥使用；者間對(duì)登記表的互斥使用；n讀者要在登記表上進(jìn)行登記，前提是登記表要有空讀者要在登記表上進(jìn)行登記，前提是登記表要有空表目；為此，需要引入一個(gè)信號(hào)表目；為此，需要引入一個(gè)信號(hào)量量S，其初值其初值為為100，表示有空表目表示有空表目100項(xiàng)；項(xiàng)；n讀者在完成登記后，放下登記表給其他讀者使用，讀者在完成登記后，放下登記表給其他讀者使用，然后在申請(qǐng)到的座位上進(jìn)行閱讀活動(dòng)；然后在申請(qǐng)到的座位上進(jìn)行閱讀活動(dòng)； n在完成閱讀后讀者需刪除登記表上的內(nèi)容，在他進(jìn)在完成閱讀后讀者需刪除登記表上的內(nèi)容，在他進(jìn)行刪除的同時(shí)是不允許其他讀者進(jìn)行刪除的。行刪除的同時(shí)是不允許其他讀

41、者進(jìn)行刪除的。n讀者進(jìn)程：讀者進(jìn)程：nmutex, S: Semaphore;mutex := 1;S := 100;Process Readeri begin P( S ); /查找空表目查找空表目 P( mutex ); /申請(qǐng)登記申請(qǐng)登記 ; V( mutex ); /允許其他讀者填寫登記表允許其他讀者填寫登記表 ; P( mutex );V( mutex );V( S );end;Problem 3n設(shè)有四個(gè)進(jìn)程設(shè)有四個(gè)進(jìn)程A、X、Y、Z共享一個(gè)緩共享一個(gè)緩沖區(qū)，進(jìn)程沖區(qū)，進(jìn)程A負(fù)責(zé)循環(huán)地從文件讀一個(gè)整負(fù)責(zé)循環(huán)地從文件讀一個(gè)整數(shù)并放入緩沖區(qū)，進(jìn)程數(shù)并放入緩沖區(qū)，進(jìn)程X從緩沖區(qū)中循環(huán)從緩

42、沖區(qū)中循環(huán)地讀入地讀入MOD 3為為0的整數(shù)并累計(jì)求和；的整數(shù)并累計(jì)求和；Y從緩沖區(qū)中循環(huán)地讀入從緩沖區(qū)中循環(huán)地讀入MOD 3為為1的整數(shù)的整數(shù)并累計(jì)求和；并累計(jì)求和；Z從緩沖區(qū)中循環(huán)地讀入從緩沖區(qū)中循環(huán)地讀入MOD 3為為2的整數(shù)并累計(jì)求和。請(qǐng)用的整數(shù)并累計(jì)求和。請(qǐng)用PV操作寫出能夠正確執(zhí)行的程序。操作寫出能夠正確執(zhí)行的程序。 緩沖區(qū)AZYXnum MOD 3 = 0numnum MOD 3 = 1num MOD 3 = 2Sempty, SX, SY, SZ: Semaphore = 1, 0, 0, 0;num: integer; Process PABeginP(Sempty);if(

43、 num MOD 3 = 0 )V( SX )Else if ( num MOD 3 = 1 )V( SY )Else V( SZ );End;Process PXBeginP( SX );V( Sempty );End;Process PYBeginP( SY );V( Sempty );End;Process PZBeginP( SZ );V( Sempty );End;1) 信號(hào)量的物理含義信號(hào)量的物理含義：S0表示有表示有S個(gè)資源可用個(gè)資源可用S=0表示無資源可用表示無資源可用S=1 & S2 = 1 & & Sn = 1)/滿足資源要求時(shí)的處理；滿足資源要求時(shí)

44、的處理； for (i = 1; i = n; +i) -Si; /注：注：與與P的處理不同，這里是在確信可滿足的處理不同，這里是在確信可滿足 / / 資源要求時(shí)，才進(jìn)行減資源要求時(shí)，才進(jìn)行減1操作；操作；break;else /某些資源不夠時(shí)的處理；某些資源不夠時(shí)的處理； 調(diào)用進(jìn)程進(jìn)入第一個(gè)小于調(diào)用進(jìn)程進(jìn)入第一個(gè)小于1信號(hào)量的等待隊(duì)列信號(hào)量的等待隊(duì)列Sj.queue; 阻塞調(diào)用進(jìn)程阻塞調(diào)用進(jìn)程; 信號(hào)量集信號(hào)量集AND型信號(hào)量集（續(xù)）型信號(hào)量集（續(xù)） Ssignal(S1, S2, , Sn)for (i = 1; i = ti；即當(dāng)資源數(shù)量低于即當(dāng)資源數(shù)量低于ti時(shí)，便不予時(shí)，便不予分配）

45、分配）占用占用值為值為di（表示資源的申請(qǐng)量，即表示資源的申請(qǐng)量，即Si = Si - di）對(duì)應(yīng)的對(duì)應(yīng)的P、V原語格式為：原語格式為：nSwait(S1, t1, d1; .; Sn, tn, dn);nSsignal(S1, d1; .; Sn, dn);一般一般“信號(hào)量集信號(hào)量集”（續(xù)）（續(xù)）一般一般“信號(hào)量集信號(hào)量集”可以用于各種情況可以用于各種情況的資源分配和釋放，幾種特殊情況的資源分配和釋放，幾種特殊情況：nSwait(S, d, d)表示每次申請(qǐng)表示每次申請(qǐng)d個(gè)資源，當(dāng)少個(gè)資源，當(dāng)少于于d個(gè)時(shí)，便不分配個(gè)時(shí)，便不分配nSwait(S, 1, 1)表示互斥信號(hào)量表示互斥信號(hào)量nSw

46、ait(S, 1, 0)可作為一個(gè)可控開關(guān)（當(dāng)可作為一個(gè)可控開關(guān)（當(dāng)S 1時(shí)，允許多個(gè)進(jìn)程進(jìn)入臨界區(qū)；時(shí)，允許多個(gè)進(jìn)程進(jìn)入臨界區(qū)；當(dāng)當(dāng)S=0時(shí)，時(shí)，禁止任何進(jìn)程進(jìn)入臨界區(qū)）禁止任何進(jìn)程進(jìn)入臨界區(qū)）管程的引入管程的引入n信號(hào)量機(jī)制中信號(hào)量機(jī)制中P、V操作使用不當(dāng)會(huì)造成操作使用不當(dāng)會(huì)造成與時(shí)間有關(guān)的錯(cuò)誤與時(shí)間有關(guān)的錯(cuò)誤P、V操作不當(dāng)?shù)睦硬僮鞑划?dāng)?shù)睦?V(mutex)P(mutex)P(mutex)V(mutex)P、V操作不當(dāng)?shù)睦硬僮鞑划?dāng)?shù)睦?V(mutex)V(mutex)P(mutex)V(mutex)P、V操作不當(dāng)?shù)睦硬僮鞑划?dāng)?shù)睦?P(mutex)P(mutex)V(mutex)

47、管程管程n1971年年, Dijkstra：把所有進(jìn)程對(duì)某一種把所有進(jìn)程對(duì)某一種臨界資源的同步操作集成起來構(gòu)成臨界資源的同步操作集成起來構(gòu)成“秘秘書書”進(jìn)程；凡要訪問該資源的進(jìn)程都需進(jìn)程；凡要訪問該資源的進(jìn)程都需先報(bào)告先報(bào)告“秘書秘書”，由其實(shí)現(xiàn)諸進(jìn)程的同，由其實(shí)現(xiàn)諸進(jìn)程的同步步n1973年，年，Hansan和和Hoare：管程概念管程概念管程概念管程概念n一個(gè)管程定義了一個(gè)數(shù)據(jù)結(jié)構(gòu)和能為并一個(gè)管程定義了一個(gè)數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進(jìn)程所執(zhí)行（在該數(shù)據(jù)結(jié)構(gòu)上）的一發(fā)進(jìn)程所執(zhí)行（在該數(shù)據(jù)結(jié)構(gòu)上）的一組操作，這組操作能同步進(jìn)程和改變管組操作，這組操作能同步進(jìn)程和改變管程中的數(shù)據(jù)程中的數(shù)據(jù)Hansan M

48、onitors - high level synchronization constructsnSemaphores and event-counters are too primitive (low level) and are hard to programn Monitors are a special package of proceduresn Mutual exclusion constructs are generated by the compiler. Internal data structures are invisiblenOnly one process is act

49、ive in a monitor at the same time - high level mutual exclusionmonitor sharedData int *buffer;public:writeData(int byteNum) ;readData(int byteNum) ; ;type monitor-name = monitorvariable declarationsprocedure entry P1 ();begin end;procedure entry P2 ();begin end;.procedure entry Pn ();begin end; begi

50、ninitialization code endFigure 6.20 Monitor with Condition VariableShared dataxyQueues associated with x, y conditionsoperationsInitialization codeEntry queueMonitors - Condition variablesn Only one process is active in a monitor at the same time - high level mutual exclusionn To enable synchronizat

51、ion: Condition variables and operations on them: and n the monitor provides queuing for proceduresn When one procedure and another , the signaling procedure is inside the monitor ! n Operation signal must be either followed by or , so that only one procedure is active at one timeBounded-Buffer with

52、Monitorsmonitor ProducerConsumerconditionnotfull, notempty;integercount;procedure enter;beginif count = N then notfull.wait;enter_item;count := count + 1;if count = 1 then notempty.signal; endprocedure remove;beginif count = 0 then notempty.wait;remove_item;count := count - 1;if count = N - 1 then n

53、otfull.signal; endcount := 0;end monitorBounded-Buffer with Monitors (II)procedure producer;beginwhile true dobeginproduce_item;ProducerConsumer.enter;endend;procedure consumer;beginwhile true dobeginProducerConsumer.remove;consume_item;endend;Interprocess Communication (進(jìn)程間通信進(jìn)程間通信)n低級(jí)通信低級(jí)通信 交換的數(shù)據(jù)量較

54、小的情況，常常指的交換的數(shù)據(jù)量較小的情況，常常指的是控制信息的交換，往往用來控制進(jìn)程是控制信息的交換，往往用來控制進(jìn)程執(zhí)行的速度，如鎖或信號(hào)量執(zhí)行的速度，如鎖或信號(hào)量n高級(jí)通信高級(jí)通信 傳送的數(shù)據(jù)量大，只是為了交換信息，傳送的數(shù)據(jù)量大，只是為了交換信息，而不是為了控制進(jìn)程的執(zhí)行速度而不是為了控制進(jìn)程的執(zhí)行速度進(jìn)程間高級(jí)通信進(jìn)程間高級(jí)通信類型類型n共享存儲(chǔ)區(qū)方式共享存儲(chǔ)區(qū)方式n共享文件方式（管道方式）共享文件方式（管道方式）n郵箱通信郵箱通信n消息緩沖機(jī)制消息緩沖機(jī)制共享存儲(chǔ)區(qū)方式共享存儲(chǔ)區(qū)方式n在內(nèi)存中開辟一塊供多個(gè)進(jìn)程共享使用在內(nèi)存中開辟一塊供多個(gè)進(jìn)程共享使用的區(qū)域的區(qū)域n基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式n由程序員完成同步處理n基于共享存儲(chǔ)區(qū)的通信方式基于共享存儲(chǔ)區(qū)的通信方式共享文件方式（管道方式共享文件方式（管道方式, Pipe）WriteReadFI