1、第第2章章 進程描述與控制（續(xù)）進程描述與控制（續(xù)）2.3 同步與互斥同步與互斥2.4 經(jīng)典同步問題經(jīng)典同步問題2.5 進程通信進程通信2.6 線程及線程及其其實現(xiàn)實現(xiàn) 12.3 同步與互斥同步與互斥2.3.1 同步和互斥的基本概念同步和互斥的基本概念2.3.2 進程間的互斥技術(shù)進程間的互斥技術(shù)2.3.3 信號量機制信號量機制2.3.4 信號量的應(yīng)用信號量的應(yīng)用2.3.5 管程機制管程機制2背景背景T1T2機票問題機票問題process Ti ( ) / i = 1, 2 按旅客訂票要求找到按旅客訂票要求找到A ； Xi = A; if (Xi=1) Xi=Xi-1; A=Xi;輸出一張票；輸

2、出一張票； else 輸出票已售完輸出票已售完 ； 3消費者消費者生產(chǎn)者生產(chǎn)者哲學(xué)家進餐問題哲學(xué)家進餐問題42.3.1 同步和互斥的基本概念同步和互斥的基本概念l多進程的并發(fā)執(zhí)行多進程的并發(fā)執(zhí)行n概念概念處理器同時交錯執(zhí)行多個進程；處理器同時交錯執(zhí)行多個進程；一組進程在一段時間內(nèi)同時存在。一組進程在一段時間內(nèi)同時存在。n特性特性間斷性：因運行環(huán)境的開放性，具體表現(xiàn)為間斷性：因運行環(huán)境的開放性，具體表現(xiàn)為n被動影響被動影響：資源競爭資源競爭。n主動合作主動合作：合作同步、數(shù)據(jù)交互、收發(fā)信號合作同步、數(shù)據(jù)交互、收發(fā)信號。失去封閉性失去封閉性不可再現(xiàn)性不可再現(xiàn)性結(jié)果的不確定性結(jié)果的不確定性5l進程間

3、的約束關(guān)系進程間的約束關(guān)系n間接的相互制約關(guān)系：間接的相互制約關(guān)系：資源競爭資源競爭( (共享共享) )需互斥地訪問臨界資源需互斥地訪問臨界資源n直接的相互制約關(guān)系：直接的相互制約關(guān)系：進程協(xié)作進程協(xié)作( (如數(shù)據(jù)共享、并行處理如數(shù)據(jù)共享、并行處理) )6l進程同步進程同步n是并發(fā)進程在執(zhí)行時序上進行相互制約，使并發(fā)進程是并發(fā)進程在執(zhí)行時序上進行相互制約，使并發(fā)進程能按一定的規(guī)則共享資源和相互合作的技術(shù)。（能按一定的規(guī)則共享資源和相互合作的技術(shù)。（廣義廣義上的同步）上的同步）。若兩個或兩個以上的進程要協(xié)作完成一個任務(wù)，則它們?nèi)魞蓚€或兩個以上的進程要協(xié)作完成一個任務(wù)，則它們之間就要互相配合，需在

4、某些動作之間進行同步（狹義之間就要互相配合，需在某些動作之間進行同步（狹義上的同步）。上的同步）。n如：計算進程和打印進程如：計算進程和打印進程若多個進程競爭某個資源，則也需同步（互斥）。若多個進程競爭某個資源，則也需同步（互斥）。7例如例如: 司機司機 P1 售票員售票員 P2 Repeat Repeat 啟動啟動 關(guān)門關(guān)門 正常運行正常運行 售票售票 到站停到站停 開門開門 Until False Until False8l互斥互斥n互斥是同步的一個特例?；コ馐峭降囊粋€特例。n兩個或兩個以上的進程兩個或兩個以上的進程競爭競爭/ /共享某資源共享某資源，而該資，而該資源在同一時刻只能被一個

5、進程使用。源在同一時刻只能被一個進程使用。n操作系統(tǒng)需要提供一種資源分配機制，來控制為操作系統(tǒng)需要提供一種資源分配機制，來控制為這些進程分配資源的順序，既保證各進程能夠使這些進程分配資源的順序，既保證各進程能夠使用資源，又能保證各進程互斥使用資源用資源，又能保證各進程互斥使用資源。9l例如：例如：n兩個進程共享一臺打印機，若讓他們隨意使用，兩個進程共享一臺打印機，若讓他們隨意使用，則很容易發(fā)生兩進程的輸出結(jié)果混淆在一起的情則很容易發(fā)生兩進程的輸出結(jié)果混淆在一起的情況。況。n解決辦法：解決辦法：當一個進程提出打印請求并得到許可當一個進程提出打印請求并得到許可后，打印機就一直為該進程所獨占；若在此

6、期間后，打印機就一直為該進程所獨占；若在此期間有另一進程也提出打印請求，則必須等待使用打有另一進程也提出打印請求，則必須等待使用打印機的那個進程釋放打印機后方可使用。印機的那個進程釋放打印機后方可使用。10l臨界資源臨界資源n一次僅允許一個進程訪問或使用的資源。臨界資一次僅允許一個進程訪問或使用的資源。臨界資源可能是硬件設(shè)備，也可能是軟件資源。源可能是硬件設(shè)備，也可能是軟件資源。n引起不可再現(xiàn)性是因為臨界資源沒有互斥訪問。引起不可再現(xiàn)性是因為臨界資源沒有互斥訪問?？刹l(fā)訪問可并發(fā)訪問不可并發(fā)訪問不可并發(fā)訪問硬件硬件內(nèi)存、顯示器、硬盤內(nèi)存、顯示器、硬盤打印機、繪圖儀、磁帶機打印機、繪圖儀、磁帶機

7、軟件軟件共享程序段共享程序段共享變量等共享變量等11l臨界區(qū)臨界區(qū)（ Dijkstra在在1965年首先提出）年首先提出）n是每個進程中訪問臨界資源的那段代碼。是每個進程中訪問臨界資源的那段代碼。當一個進程進入自身的這段代碼時，不允許其他進程當一個進程進入自身的這段代碼時，不允許其他進程進入自己對應(yīng)的臨界區(qū)。進入自己對應(yīng)的臨界區(qū)。n若保證進程在臨界區(qū)執(zhí)行時，不讓另一個進程進若保證進程在臨界區(qū)執(zhí)行時，不讓另一個進程進入自身對應(yīng)的臨界區(qū)，即各進程對臨界資源的訪入自身對應(yīng)的臨界區(qū)，即各進程對臨界資源的訪問是互斥的，則不會造成與時間有關(guān)的錯誤。問是互斥的，則不會造成與時間有關(guān)的錯誤。n同一臨界資源的臨

8、界區(qū)個數(shù)同一臨界資源的臨界區(qū)個數(shù) = 共享該臨界資源的共享該臨界資源的進程數(shù)。進程數(shù)。12兩個進程兩個進程 P1和和P2存在存在共享變量共享變量countP1： P2： R1=count R2=count R1=R1+1 R2=R2+1 count=R1 count=R2 臨界區(qū)示例臨界區(qū)示例本意本意: count初值為初值為0，結(jié)果：，結(jié)果：count = 2。13l在并發(fā)系統(tǒng)中，進程可能并發(fā)交叉執(zhí)行，兩個進程在并發(fā)系統(tǒng)中，進程可能并發(fā)交叉執(zhí)行，兩個進程可能的相對執(zhí)行次序：可能的相對執(zhí)行次序： P1：R1=count R1=R1+1 P2：R2=count R2=R2+1 count=R2

9、P1：count=R1l結(jié)果：結(jié)果：count = 1l原因？原因？14l臨界區(qū)的訪問模型臨界區(qū)的訪問模型while( true ) Entry section 進入?yún)^(qū)（檢查有無進程進入）進入?yún)^(qū)（檢查有無進程進入） Critical section 臨界區(qū)臨界區(qū) Exit section 退出區(qū)（將訪問標志復(fù)位）退出區(qū)（將訪問標志復(fù)位） Remainder section剩余區(qū)剩余區(qū)15l使用臨界區(qū)時，同步機制應(yīng)遵循的準則使用臨界區(qū)時，同步機制應(yīng)遵循的準則n前提前提任何進程無權(quán)停止其它進程的運行任何進程無權(quán)停止其它進程的運行對進程速度和處理器的數(shù)量沒有任何要求和限制對進程速度和處理器的數(shù)量沒有

10、任何要求和限制n使用臨界區(qū)的準則使用臨界區(qū)的準則空閑讓進空閑讓進忙則等待忙則等待有限等待有限等待讓權(quán)等待讓權(quán)等待162.3.2 進程間的互斥技術(shù)進程間的互斥技術(shù)l臨界區(qū)互斥的實現(xiàn)方法臨界區(qū)互斥的實現(xiàn)方法n平等協(xié)商平等協(xié)商硬件方法硬件方法n互斥鎖互斥鎖n特殊指令法（特殊指令法（test&set指令、交換指令指令、交換指令exchange）n中斷禁用法中斷禁用法n組合法組合法軟件方法軟件方法n引入進程管理者引入進程管理者17l互斥的互斥的硬件方法硬件方法1 1互斥鎖互斥鎖n通過鎖的狀態(tài)來表示是否有進程在臨界區(qū)通過鎖的狀態(tài)來表示是否有進程在臨界區(qū)X=0：打開狀態(tài)：打開狀態(tài)X=1：關(guān)閉狀態(tài)：關(guān)

11、閉狀態(tài)n進程要進入臨界區(qū)前，必須要測試鎖的狀態(tài)，只進程要進入臨界區(qū)前，必須要測試鎖的狀態(tài)，只有打開狀態(tài)時，才能進入臨界區(qū)有打開狀態(tài)時，才能進入臨界區(qū)n進程在進入臨界區(qū)的那一刻立即關(guān)鎖進程在進入臨界區(qū)的那一刻立即關(guān)鎖n進程在離開臨界區(qū)時要立即開鎖進程在離開臨界區(qū)時要立即開鎖例：在火車上如廁例：在火車上如廁18鎖機制不安全性分析鎖機制不安全性分析l安全性問題安全性問題n鎖的關(guān)閉操作包含鎖的關(guān)閉操作包含測試鎖的狀態(tài)測試鎖的狀態(tài)和和關(guān)鎖關(guān)鎖兩個步驟。兩個步驟。n問題描述問題描述若進程若進程A測試鎖狀態(tài)為開，但在測試鎖狀態(tài)為開，但在關(guān)鎖前被剝奪關(guān)鎖前被剝奪CPU;被調(diào)度的進程被調(diào)度的進程B發(fā)現(xiàn)鎖狀態(tài)為開

12、，可能關(guān)鎖并進入臨發(fā)現(xiàn)鎖狀態(tài)為開，可能關(guān)鎖并進入臨界區(qū)。界區(qū)。A恢復(fù)執(zhí)行后，以為鎖狀態(tài)仍為開，于是關(guān)鎖并進入恢復(fù)執(zhí)行后，以為鎖狀態(tài)仍為開，于是關(guān)鎖并進入臨界區(qū)。臨界區(qū)。n可能出現(xiàn)兩個進程同時進入臨界區(qū)可能出現(xiàn)兩個進程同時進入臨界區(qū)l安全性保證條件安全性保證條件n把測試鎖狀態(tài)和關(guān)鎖兩個步驟把測試鎖狀態(tài)和關(guān)鎖兩個步驟實現(xiàn)為不可分割的原實現(xiàn)為不可分割的原子性操作子性操作。19 boolean testset (boolean *lock) /testset指令語義指令語義boolean ts=*lock;*lock=TRUE;return ts;互斥的硬件方法互斥的硬件方法2 test &s

13、et指令指令n每個臨界資源對應(yīng)一個每個臨界資源對應(yīng)一個lock，其初值為，其初值為FALSE，表示臨界資源空閑；表示臨界資源空閑；n用用test&set指令測試指令測試lock狀態(tài)，并加鎖；狀態(tài)，并加鎖；n由于由于test&set是一條完整是一條完整的指令的指令，執(zhí)行中是不會被，執(zhí)行中是不會被“中斷中斷” 的，故保證了鎖的，故保證了鎖的測試和關(guān)閉操作的原子的測試和關(guān)閉操作的原子性（即不可分解的特性）。性（即不可分解的特性）。20test &set指令的應(yīng)用指令的應(yīng)用boolean lock;void P(int i)while(true)while(testset(&a

14、mp;lock); /循環(huán)測試循環(huán)測試critical section;lock=FALSE;remainder section;void main()lock=FALSE;parbegin(P(1), P(2), , P(n);21void exchange(boolean *key, boolean *lock) boolean temp;temp = *lock;*lock = *key;*key = temp;互斥的硬件方法互斥的硬件方法3交換指令交換指令exchange（swap）22lexchange指令能夠?qū)崿F(xiàn)兩個變量之間的內(nèi)容交換。指令能夠?qū)崿F(xiàn)兩個變量之間的內(nèi)容交換。l基本思想

15、基本思想n交換的同時進行加鎖交換的同時進行加鎖l具體實現(xiàn)具體實現(xiàn)n設(shè)置：測試變量設(shè)置：測試變量key、鎖變量、鎖變量lockn進入臨界區(qū)前進入臨界區(qū)前A.先置測試變量的值為先置測試變量的值為TRUE，再對測試變量和鎖變量執(zhí)，再對測試變量和鎖變量執(zhí)行交換指令。行交換指令。B.若測試變量值為若測試變量值為FALSE：進入臨界區(qū)：進入臨界區(qū)C.若測試變量值為若測試變量值為TRUE ：重新轉(zhuǎn)向：重新轉(zhuǎn)向A。n離開臨界區(qū)離開臨界區(qū)設(shè)置鎖變量值為設(shè)置鎖變量值為FALSE23void Pi( )while(true)keyi=TURE;doexchage(&keyi , &lock); /循

16、環(huán)測試循環(huán)測試 while(keyi!=FALSE) critical section;lock=FALSE;remainder section;24l硬件硬件方法的不足方法的不足n忙等，不能實現(xiàn)忙等，不能實現(xiàn)“讓權(quán)等待讓權(quán)等待”（循環(huán)測試）；（循環(huán)測試）；n硬件實現(xiàn)代價較大硬件實現(xiàn)代價較大；n可移植性差，依賴具體的硬件平臺可移植性差，依賴具體的硬件平臺；n在多處理環(huán)境下有些硬件實現(xiàn)方式不適用在多處理環(huán)境下有些硬件實現(xiàn)方式不適用。25l實現(xiàn)進程互斥的軟件方法實現(xiàn)進程互斥的軟件方法n基本思路基本思路：在進入?yún)^(qū)檢查和設(shè)置一些標志，若：在進入?yún)^(qū)檢查和設(shè)置一些標志，若已有進程在臨界區(qū)，則在進入?yún)^(qū)通過循

17、環(huán)檢查已有進程在臨界區(qū)，則在進入?yún)^(qū)通過循環(huán)檢查進行等待；在退出區(qū)修改標志。進行等待；在退出區(qū)修改標志。n主要問題是設(shè)置什么標志和如何檢查標志？主要問題是設(shè)置什么標志和如何檢查標志？26l軟件方法軟件方法1：單標志單標志n設(shè)立一個公用整型變量設(shè)立一個公用整型變量 turn，描述允許進入臨界描述允許進入臨界區(qū)的進程標識；區(qū)的進程標識；n假設(shè)有兩個進程假設(shè)有兩個進程Pi, Pj ，其中，其中Pi：在進入臨界區(qū)前，循環(huán)檢查是否允許本進程進入在進入臨界區(qū)前，循環(huán)檢查是否允許本進程進入nturn為為i時，進程時，進程Pi可進入；可進入；在退出臨界區(qū)時，修改允許進入進程標識在退出臨界區(qū)時，修改允許進入進程標

18、識n進程進程Pi退出時，改退出時，改turn為進程為進程Pj的標識的標識j；27n單標志的缺點單標志的缺點強制輪流進入臨界區(qū)強制輪流進入臨界區(qū)，未考慮進程的實際需要。容易，未考慮進程的實際需要。容易造成資源利用不充分：在造成資源利用不充分：在Pi讓出臨界區(qū)之后，讓出臨界區(qū)之后，Pj使用使用臨界區(qū)之前，臨界區(qū)之前，Pi不可能再次使用臨界區(qū)。不可能再次使用臨界區(qū)。while (turn != i);critical sectionturn = j;remainder sectionPi28l軟件算法軟件算法2：雙標志、先檢查：雙標志、先檢查n設(shè)立一個標志數(shù)組設(shè)立一個標志數(shù)組flag0.1：描述進程

19、是否在臨界：描述進程是否在臨界區(qū)，初值均為區(qū)，初值均為FALSE。先檢查，后修改先檢查，后修改：在進入?yún)^(qū)檢查另一進程是否在臨：在進入?yún)^(qū)檢查另一進程是否在臨界區(qū)，界區(qū)，若不在若不在，則修改本進程在臨界區(qū)的標志；，則修改本進程在臨界區(qū)的標志；在退出區(qū)修改本進程在臨界區(qū)的標志。在退出區(qū)修改本進程在臨界區(qū)的標志。Pi29n雙標志、先檢查的優(yōu)點：雙標志、先檢查的優(yōu)點：不用交替進入，可連續(xù)使用；n缺點：缺點：Pi、Pj可能同時進入臨界區(qū)可能同時進入臨界區(qū)。如：按下面序列執(zhí)行時：如：按下面序列執(zhí)行時：“Pi Pj Pi Pj”。即在檢查對方。即在檢查對方flag之后和切換自己之后和切換自己flag之前之前有

20、一段時間，結(jié)果都檢查通過，同時進入臨界區(qū)，有一段時間，結(jié)果都檢查通過，同時進入臨界區(qū)，顯然顯然違背了違背了“忙則等待忙則等待”的原則的原則。這里的問題出在。這里的問題出在檢查和修改操作不能連續(xù)進行。檢查和修改操作不能連續(xù)進行。30l軟件算法軟件算法3：雙標志、后檢查雙標志、后檢查n類似于算法類似于算法2，與算法，與算法2的區(qū)別在于先修改后檢的區(qū)別在于先修改后檢查。查。可防止兩個進程同時進入臨界區(qū)可防止兩個進程同時進入臨界區(qū)。31l雙標志、后檢查的缺點雙標志、后檢查的缺點nPi、Pj可能都進不了臨界區(qū)可能都進不了臨界區(qū)如：按下面序列執(zhí)行時：如：按下面序列執(zhí)行時：“Pi Pj Pi Pj”。即在切

21、換自己。即在切換自己flag之后和檢查對方之后和檢查對方flag之之前有一段時間，結(jié)果都切換前有一段時間，結(jié)果都切換flag，都檢查不通過。，都檢查不通過。因而，因而，這又違背了這又違背了“空閑讓進空閑讓進”和和“有限等待有限等待”原則原則。32練習(xí)題練習(xí)題l兩個旅行社甲和乙為旅客到某航空公司訂飛機票，形成互斥兩個旅行社甲和乙為旅客到某航空公司訂飛機票，形成互斥資源的是（）。資源的是（）。A. 旅行社旅行社 B.航空公司航空公司 C.飛機票飛機票 D.旅行社與航空公司旅行社與航空公司l臨界區(qū)是指并發(fā)進程訪問共享資源的（）。臨界區(qū)是指并發(fā)進程訪問共享資源的（）。A. 管理信息管理信息 B.信息存

22、儲信息存儲 C.數(shù)據(jù)數(shù)據(jù) D.代碼代碼l以下（）不是同步機制遵循的準則。以下（）不是同步機制遵循的準則。A. 讓權(quán)等待讓權(quán)等待B.空閑讓進空閑讓進C.忙則等待忙則等待 D.無限等待無限等待l進程進程A和和B通過共享緩沖區(qū)協(xié)作完成數(shù)據(jù)處理，通過共享緩沖區(qū)協(xié)作完成數(shù)據(jù)處理，A負責(zé)產(chǎn)生負責(zé)產(chǎn)生數(shù)據(jù)并放入緩沖區(qū)，數(shù)據(jù)并放入緩沖區(qū)，B負責(zé)從緩沖區(qū)讀數(shù)據(jù)并輸出，負責(zé)從緩沖區(qū)讀數(shù)據(jù)并輸出，A和和B之間是（）關(guān)系。之間是（）關(guān)系。nA. 互斥互斥 B.同步同步 C.同步與互斥同步與互斥 D.沒有沒有332.3.3 信號量機制信號量機制l前面的互斥算法都是平等進程間的一種協(xié)商機制，前面的互斥算法都是平等進程間的

23、一種協(xié)商機制，但存在的問題是平等協(xié)商無法解決的。但存在的問題是平等協(xié)商無法解決的。l需要引入一個地位高于進程的管理者來解決公有需要引入一個地位高于進程的管理者來解決公有資源的使用問題。資源的使用問題。lOS可從進程管理者的角度來處理進程同步問題，可從進程管理者的角度來處理進程同步問題，信號量信號量就是就是OS提供的管理公有資源的有效手段。提供的管理公有資源的有效手段。n信號量信號量 代表代表 可用資源實體的數(shù)量可用資源實體的數(shù)量。34信號量機制：信號量機制：信號量的基本原理和思想信號量的基本原理和思想l進程間通過信號實現(xiàn)互斥、協(xié)作。進程間通過信號實現(xiàn)互斥、協(xié)作。n信號在邏輯意義上對應(yīng)于資源，信

24、號可以類似于短消息，信號在邏輯意義上對應(yīng)于資源，信號可以類似于短消息，可以緩存在某個地方?？梢跃彺嬖谀硞€地方。l進程要申請互斥資源，必須等待信號的到來。進程要申請互斥資源，必須等待信號的到來。n若有信號到來，則消耗一個信號后，占有資源。若有信號到來，則消耗一個信號后，占有資源。n若沒有信號，則把自己阻塞在這個信號上。若沒有信號，則把自己阻塞在這個信號上。l進程在釋放資源時，發(fā)出釋放資源的信號。進程在釋放資源時，發(fā)出釋放資源的信號。35l若在阻塞過程中收到信號，則消耗掉該信號后，若在阻塞過程中收到信號，則消耗掉該信號后，進程被喚醒。進程被喚醒。l若多個進程阻塞在一個信號上，有信號到來，會若多個進

25、程阻塞在一個信號上，有信號到來，會根據(jù)調(diào)度原則，決定哪個進程真正收到該信號。根據(jù)調(diào)度原則，決定哪個進程真正收到該信號。信號量機制：信號量機制：信號量的基本原理和思想信號量的基本原理和思想信號量機制是一種卓有成效的進程同步工信號量機制是一種卓有成效的進程同步工具，被廣泛應(yīng)用于單處理機和多處理機系具，被廣泛應(yīng)用于單處理機和多處理機系統(tǒng)以及計算機網(wǎng)絡(luò)中。統(tǒng)以及計算機網(wǎng)絡(luò)中。36信號量機制：信號量機制：信號量的具體實現(xiàn)信號量的具體實現(xiàn)l1、整型信號量、整型信號量 和和 P、V原語原語n一個整型量一個整型量s，僅通過原子操作，僅通過原子操作P(s)和和V(s)訪問。訪問。nP(s)： while( s=

26、 0 ) ; s-;nV(s)： s+;P: Wait V: signal37l整型信號量整型信號量在邏輯上在邏輯上表示可分配的資源數(shù)量表示可分配的資源數(shù)量。n初始值為該類資源的總數(shù)量。初始值為該類資源的總數(shù)量。lP(s)表示表示資源申請資源申請操作（進入臨界區(qū)前調(diào)用該操作）操作（進入臨界區(qū)前調(diào)用該操作）n信號量的值減信號量的值減1lV(s)表示表示資源釋放資源釋放操作操作(離開臨界區(qū)前調(diào)用該操作離開臨界區(qū)前調(diào)用該操作)n信號量的值增信號量的值增1l對信號量只能執(zhí)行對信號量只能執(zhí)行P、V操作，操作， P、V操作不可中斷。操作不可中斷。l信號量必須置一次且信號量必須置一次且只能置一次初值，初值不

27、能只能置一次初值，初值不能為負為負。38void P( semaphore s )s.value - - ; if (s.value 0 ) 調(diào)用調(diào)用block原語自我阻塞原語自我阻塞, 即將即將進程放入阻塞隊列進程放入阻塞隊列s.queue; 并進行調(diào)度并進行調(diào)度; typedef struct semaphore int value; /可用資源數(shù)可用資源數(shù) Queue queue; /被阻塞進被阻塞進程隊列程隊列 semaphore ；由于整型信號量機制中的由于整型信號量機制中的P操作，只要操作，只要s=0就會不斷測試，就會不斷測試，不滿足不滿足“讓權(quán)等待讓權(quán)等待”，因此，引入，因此，引

28、入記錄型信號量記錄型信號量。l2、記錄型信號量、記錄型信號量39void V(semaphore s)s.value +; if (s.value = 0 ) 從阻塞隊列從阻塞隊列s.queue取出一進程，調(diào)用取出一進程，調(diào)用wakeup喚醒該進程；喚醒該進程；40l3、AND型信號量型信號量n基本思想：將進程在整個運行過程中需要的所有基本思想：將進程在整個運行過程中需要的所有資源，一次性全部分配給進程，待進程使用完后資源，一次性全部分配給進程，待進程使用完后再一起釋放。只要有一個資源未能分配給進程，再一起釋放。只要有一個資源未能分配給進程，其它所有可能分配給它的資源也不分配給它。其它所有可能

29、分配給它的資源也不分配給它。n當不用它時，有可能發(fā)生當不用它時，有可能發(fā)生死鎖死鎖。41process A: P(Dmutex); P(Emutex);process B: P(Emutex); P(Dmutex);若這若這2個進程交替執(zhí)行，則個進程交替執(zhí)行，則死鎖死鎖。用用and型信號量機制可避免上述死鎖情況型信號量機制可避免上述死鎖情況的發(fā)生。的發(fā)生。如：如：42Swait(S1, S2, , Sn) while(true) if (Si1& & Sn1) for (i=1; i=n; i+) Si-; break; else 將進程放入相應(yīng)的等待隊列將進程放入相應(yīng)的等待隊

30、列; Ssignal(S1, S2, , Sn) while(true) for (i=1; i1）或互斥型信）或互斥型信號量（號量（S=1）。）。P (S, 1, 0)，可控開關(guān)，當，可控開關(guān)，當 S=1 時，允許多個進程進入某特時，允許多個進程進入某特定區(qū)，定區(qū)，S=0時，阻止進入。時，阻止進入。44資源分配資源分配的下限的下限資源需求資源需求量量2.3.4 信號量的應(yīng)用信號量的應(yīng)用l用信號量實現(xiàn)互斥用信號量實現(xiàn)互斥l用信號量實現(xiàn)同步用信號量實現(xiàn)同步45信號量的應(yīng)用信號量的應(yīng)用：用信號量實現(xiàn)互斥用信號量實現(xiàn)互斥l基本思想基本思想n用信號量用信號量S表示可分配的某類資源數(shù)量。表示可分配的某類

31、資源數(shù)量。n用用P原語表示申請資源，原語表示申請資源，V原語表示釋放原語表示釋放資源。資源。nP、V原語原語必須在臨界區(qū)前后成對出現(xiàn)必須在臨界區(qū)前后成對出現(xiàn)。n互斥信號量的初值互斥信號量的初值一般為一般為1。46l信號量的取值含義：信號量的取值含義：nS 0：某類資源當前可用的數(shù)量，表示還某類資源當前可用的數(shù)量，表示還能有能有S個進程可分配到該資源。個進程可分配到該資源。nS=0：表示沒有待分配資源，但也沒有進表示沒有待分配資源，但也沒有進程在等待資源。程在等待資源。nS0表示有表示有S個資源可用個資源可用nS=0表示無資源可用表示無資源可用nS0則則| S |表示阻塞隊列中的阻塞進程個數(shù)表示

32、阻塞隊列中的阻塞進程個數(shù)n信號量的初值應(yīng)該大于等于信號量的初值應(yīng)該大于等于095lP/V操作操作nP(S):表示申請一個資源表示申請一個資源 nV(S):表示釋放一個資源表示釋放一個資源n必須成對出現(xiàn)必須成對出現(xiàn)n當為互斥操作時，它們同處于同一進程當為互斥操作時，它們同處于同一進程n當為同步操作時，則在不同進程中出現(xiàn)當為同步操作時，則在不同進程中出現(xiàn)n一個同步一個同步P操作與一個互斥操作與一個互斥P操作在一起時，同操作在一起時，同步步P操作在互斥操作在互斥P操作前。而兩個操作前。而兩個V操作順序無關(guān)操作順序無關(guān)緊要。緊要。96信號量機制的優(yōu)缺點信號量機制的優(yōu)缺點l優(yōu)點優(yōu)點n簡單，而且表達能力強

33、（用信號量機制可解決任何同步簡單，而且表達能力強（用信號量機制可解決任何同步互斥問題）互斥問題）l缺點缺點n同步操作分散：同步操作分散：信號量機制中，同步操作分散在各個進信號量機制中，同步操作分散在各個進程中，使用不當就可能導(dǎo)致各進程程中，使用不當就可能導(dǎo)致各進程死鎖、饑餓和不公平。死鎖、饑餓和不公平。不適合實時系統(tǒng)。不適合實時系統(tǒng)。n可讀性差：可讀性差：要了解對于一組共享變量及信號量的操作是要了解對于一組共享變量及信號量的操作是否正確，必須通讀整個系統(tǒng)或者并發(fā)程序；否正確，必須通讀整個系統(tǒng)或者并發(fā)程序；n不利于修改和維護：不利于修改和維護：各模塊的獨立性差，任一組變量或各模塊的獨立性差，任一

34、組變量或一段代碼的修改都可能影響全局；一段代碼的修改都可能影響全局；n正確性難以保證：正確性難以保證：操作系統(tǒng)或并發(fā)程序通常很大，很難操作系統(tǒng)或并發(fā)程序通常很大，很難保證這樣一個復(fù)雜的系統(tǒng)沒有邏輯錯誤。保證這樣一個復(fù)雜的系統(tǒng)沒有邏輯錯誤。97作業(yè)作業(yè)對于前面例題對于前面例題2，若司機和售票員的工作流程如下，若司機和售票員的工作流程如下（司機：啟動開車、正常行車、到站停車；售票員司機：啟動開車、正常行車、到站停車；售票員：開車門、關(guān)車門、售票：開車門、關(guān)車門、售票），），則用則用PV操作如何實現(xiàn)操作如何實現(xiàn)司機和售票員之間的同步（提示，此時初始狀態(tài)為司機和售票員之間的同步（提示，此時初始狀態(tài)為停

35、車而還沒開門狀態(tài)，即乘客還沒下車）。停車而還沒開門狀態(tài)，即乘客還沒下車）。有一個倉庫，可以存放有一個倉庫，可以存放A和和B 兩種產(chǎn)品。要求：兩種產(chǎn)品。要求：1)每次只能存入一種產(chǎn)品每次只能存入一種產(chǎn)品(A或或B)；2)NA產(chǎn)品產(chǎn)品數(shù)量數(shù)量B產(chǎn)品數(shù)量產(chǎn)品數(shù)量0）個單元的緩沖區(qū)。個單元的緩沖區(qū)。P1每次用每次用produce( )生成一個正生成一個正整數(shù)并用整數(shù)并用put( )送入緩沖區(qū)某一空單元中；送入緩沖區(qū)某一空單元中；P2每次每次用用getodd( )從該緩沖區(qū)中取出一個奇數(shù)并用從該緩沖區(qū)中取出一個奇數(shù)并用countodd( )統(tǒng)計奇數(shù)個數(shù)；統(tǒng)計奇數(shù)個數(shù)；P3每次用每次用geteven( )

36、從從該緩沖區(qū)中取出一個偶數(shù)并用該緩沖區(qū)中取出一個偶數(shù)并用counteven( )統(tǒng)計偶統(tǒng)計偶數(shù)個數(shù)。請用信號量機制實現(xiàn)這三個進程的同步與數(shù)個數(shù)。請用信號量機制實現(xiàn)這三個進程的同步與互斥活動，并說明所定義的信號量的含義。互斥活動，并說明所定義的信號量的含義。 992.5 進程通信進程通信100l并發(fā)進程之間的交互必須滿足兩個基本要求：并發(fā)進程之間的交互必須滿足兩個基本要求：同同步和通信步和通信。n例如，進程同步可通過信號量，建立進程之間的聯(lián)系，例如，進程同步可通過信號量，建立進程之間的聯(lián)系，相互協(xié)調(diào)運行和協(xié)同工作。相互協(xié)調(diào)運行和協(xié)同工作。l進程協(xié)同工作時，需要互相交換信息，有些情況進程協(xié)同工作時

37、，需要互相交換信息，有些情況下進程間交換少量信息，有些情況下進程間交換下進程間交換少量信息，有些情況下進程間交換大量數(shù)據(jù)。大量數(shù)據(jù)。l進程通信進程通信(Inter-Process Communication, IPC)：是指進程之間的信息交換。：是指進程之間的信息交換。101l低級進程通信低級進程通信n只能傳遞狀態(tài)和控制信息，如：信號量和管程。只能傳遞狀態(tài)和控制信息，如：信號量和管程。優(yōu)點是速度快，缺點：優(yōu)點是速度快，缺點：傳送傳送信息量小、效率低信息量小、效率低。通信對用戶不透明，編程復(fù)雜、容易出錯。通信對用戶不透明，編程復(fù)雜、容易出錯。l高級進程通信高級進程通信n用戶直接使用用戶直接使用O

38、S提供的一組通信命令高效地傳送提供的一組通信命令高效地傳送大量數(shù)據(jù)大量數(shù)據(jù)。nOS屏蔽了通信細節(jié)，即通信過程屏蔽了通信細節(jié)，即通信過程對用戶透明對用戶透明，減，減少了通信程序編制的復(fù)雜性。少了通信程序編制的復(fù)雜性。進程通信的分類進程通信的分類102l（1）共享存儲器系統(tǒng)）共享存儲器系統(tǒng)n基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式（是低級通信）基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式（是低級通信）如：如：producer-consumer中的有界緩沖區(qū)。中的有界緩沖區(qū)。低效、不透明、適于少量數(shù)據(jù)的傳遞。低效、不透明、適于少量數(shù)據(jù)的傳遞。n基于共享存儲區(qū)的通信方式基于共享存儲區(qū)的通信方式共享存儲區(qū)（從內(nèi)存中劃分）共享存儲區(qū)（從

39、內(nèi)存中劃分） 。通信過程：通信過程：n向系統(tǒng)申請一個或多個分區(qū)向系統(tǒng)申請一個或多個分區(qū)n獲得分區(qū)后即可讀獲得分區(qū)后即可讀/寫寫 特點：高效、速度快、可傳輸大量數(shù)據(jù)。特點：高效、速度快、可傳輸大量數(shù)據(jù)。進程通信的分類進程通信的分類103l（3）消息傳遞系統(tǒng)）消息傳遞系統(tǒng) n信息單位：消息（報文）；信息單位：消息（報文）；n是目前主要的通信方式，分為是目前主要的通信方式，分為直接通信、間接通信直接通信、間接通信；n實現(xiàn)：一組通信命令（原語），具有透明性；實現(xiàn)：一組通信命令（原語），具有透明性；n可用于多處理機系統(tǒng)、分布式系統(tǒng)和計算機網(wǎng)絡(luò)?？捎糜诙嗵幚頇C系統(tǒng)、分布式系統(tǒng)和計算機網(wǎng)絡(luò)。l（2）管道（）

40、管道（pipe）通信）通信n管道：用于連接一個讀進程和一個寫進程之間通信的管道：用于連接一個讀進程和一個寫進程之間通信的共享文件（共享文件（pipe文件）。文件）。n功能：大量的數(shù)據(jù)發(fā)收。功能：大量的數(shù)據(jù)發(fā)收。n注意：互斥地使用管道、同步、對方是否存在。注意：互斥地使用管道、同步、對方是否存在。進程通信的分類進程通信的分類104l（4）客戶機）客戶機-服務(wù)器系統(tǒng)服務(wù)器系統(tǒng)n是網(wǎng)絡(luò)環(huán)境中的主流通信機制。是網(wǎng)絡(luò)環(huán)境中的主流通信機制。n主要的實現(xiàn)方法：主要的實現(xiàn)方法：套接字套接字遠程過程調(diào)用和遠程方法調(diào)用遠程過程調(diào)用和遠程方法調(diào)用消息傳遞通信的實現(xiàn)方式消息傳遞通信的實現(xiàn)方式105l(1)直接通信方式

41、直接通信方式nsend(Receiver, message)nreceive(Sender, message)l(2)間接通信方式（可實現(xiàn)非實時通信）間接通信方式（可實現(xiàn)非實時通信）n優(yōu)點：優(yōu)點：在讀在讀/寫時間上的隨機性寫時間上的隨機性n寫進程寫進程-信箱信箱（中間實體）（中間實體）-讀進程讀進程n信箱的創(chuàng)建與撤消信箱的創(chuàng)建與撤消信箱名、屬性（公用、私用、共享）、共享者名字信箱名、屬性（公用、私用、共享）、共享者名字n消息的發(fā)送和接收消息的發(fā)送和接收Send (mailbox, message)Receive (mailbox, message)消息傳遞通信的實現(xiàn)方式消息傳遞通信的實現(xiàn)方式1

42、06n信箱類型信箱類型私用：擁有者有讀私用：擁有者有讀/寫權(quán)，其它只有寫權(quán)，存在期寫權(quán)，其它只有寫權(quán)，存在期進程存在期。進程存在期。公用：系統(tǒng)創(chuàng)建，雙向，存在期公用：系統(tǒng)創(chuàng)建，雙向，存在期=系統(tǒng)存在期。系統(tǒng)存在期。共享信箱：創(chuàng)建時指明其共享者，雙向。共享信箱：創(chuàng)建時指明其共享者，雙向。n利用郵箱通信時，發(fā)送、接收進程之間的關(guān)系利用郵箱通信時，發(fā)送、接收進程之間的關(guān)系一對一關(guān)系；一對一關(guān)系；多對一關(guān)系多對一關(guān)系(C/S交互交互)；一對多關(guān)系一對多關(guān)系(廣播方式廣播方式)；多對多關(guān)系多對多關(guān)系(公用信箱公用信箱)。消息傳遞系統(tǒng)實現(xiàn)中的幾個問題消息傳遞系統(tǒng)實現(xiàn)中的幾個問題107l(1)(1)通信鏈路

43、通信鏈路n顯式建立：（多用于網(wǎng)絡(luò)）顯式建立：（多用于網(wǎng)絡(luò)）利用建立鏈路的原語利用建立鏈路的原語n隱式建立：（多用于單機系統(tǒng)）隱式建立：（多用于單機系統(tǒng)）使用發(fā)送命令時，系統(tǒng)自動建立使用發(fā)送命令時，系統(tǒng)自動建立n鏈路類型：鏈路類型：由通信方式分：單向鏈路、雙向鏈路由通信方式分：單向鏈路、雙向鏈路消息傳遞系統(tǒng)實現(xiàn)中的幾個問題消息傳遞系統(tǒng)實現(xiàn)中的幾個問題108l(2)消息格式消息格式 n消息頭消息頭含控制信息，如收含控制信息，如收/發(fā)進程名、消息長度、類型、發(fā)進程名、消息長度、類型、編號編號n消息正文消息正文n定長消息定長消息系統(tǒng)開銷小，對傳長消息的用戶不便系統(tǒng)開銷小，對傳長消息的用戶不便n變長消息

44、變長消息開銷大，對用戶方便。開銷大，對用戶方便。消息傳遞系統(tǒng)實現(xiàn)中的幾個問題消息傳遞系統(tǒng)實現(xiàn)中的幾個問題109l(3)進程同步方式進程同步方式進程間的通信需要同步進程間的通信需要同步n發(fā)送和接收進程阻塞發(fā)送和接收進程阻塞用于緊密同步，無緩沖區(qū)時。用于緊密同步，無緩沖區(qū)時。n發(fā)送進程不阻塞，接收進程阻塞發(fā)送進程不阻塞，接收進程阻塞（多個）（多個）相當于接收進程（可能是多個）一直等待發(fā)送進相當于接收進程（可能是多個）一直等待發(fā)送進程，如：打印進程等待打印任務(wù)。程，如：打印進程等待打印任務(wù)。n發(fā)送發(fā)送/ /接收進程均不阻塞接收進程均不阻塞一般在發(fā)、收進程間有多個緩沖區(qū)時。一般在發(fā)、收進程間有多個緩沖

45、區(qū)時。消息傳遞系統(tǒng)實例消息傳遞系統(tǒng)實例110l消息緩沖隊列通信機制消息緩沖隊列通信機制n是直接消息傳遞系統(tǒng)是直接消息傳遞系統(tǒng)n數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)消息緩沖區(qū)消息緩沖區(qū)typedef struct message_bufferint sender; /發(fā)送者的標識符發(fā)送者的標識符int size; /消息長度消息長度char *text; /消息正文消息正文struct message_buffer *next; /指向下一個消息緩沖區(qū)指向下一個消息緩沖區(qū)PCB中有關(guān)通信的數(shù)據(jù)項中有關(guān)通信的數(shù)據(jù)項struct message_buffer *mq; /消息隊列隊首指針消息隊列隊首指針semaphor

46、e mutex; /消息隊列互斥信號量消息隊列互斥信號量semaphore sm; /消息隊列資源信號量（消息數(shù)）消息隊列資源信號量（消息數(shù)）消息傳遞系統(tǒng)實例消息傳遞系統(tǒng)實例111l消息緩沖隊列通信機制消息緩沖隊列通信機制n發(fā)送原語發(fā)送原語void send(receiver, a) getbuf( a.size,i ); /申請緩沖區(qū)申請緩沖區(qū) i.sender=a.sender; i.size=a.size; copy( i.text, a.text ); i.next=0; getid( PCBset, receiver.j ); wait(j.mutex); insert(j.mq,

47、i); signal(j.mutex); signal(j.sm); 112n接收原語接收原語void receive(b) j=internal name; wait(j.sm); wait(j.mutex); remove(j.mq, i); signal(j.mutex); b.sender=i.sender; b.size=i.size; copy( b.text, i.text ); releasebuf(i);1132.6 線程及其實現(xiàn)線程及其實現(xiàn)114l由于進程是一個資源的擁有者，因而在創(chuàng)建、撤由于進程是一個資源的擁有者，因而在創(chuàng)建、撤消和切換中，系統(tǒng)必須為之付出較大的時空開銷。

48、消和切換中，系統(tǒng)必須為之付出較大的時空開銷。n在系統(tǒng)中設(shè)置的進程數(shù)目不宜過多，進程切換的頻率在系統(tǒng)中設(shè)置的進程數(shù)目不宜過多，進程切換的頻率也不宜過高，這限制了并發(fā)程度。也不宜過高，這限制了并發(fā)程度。l引入線程引入線程，作為獨立調(diào)度和分派的單位，作為獨立調(diào)度和分派的單位，而而不獨不獨立擁有資源立擁有資源（僅有少量基本資源），與其它線程（僅有少量基本資源），與其它線程共享同一進程的資源，減少了系統(tǒng)的時空開銷。共享同一進程的資源，減少了系統(tǒng)的時空開銷。l實質(zhì)：把進程的任務(wù)劃分為更小、不能再分的、實質(zhì)：把進程的任務(wù)劃分為更小、不能再分的、具有獨立功能的單位，以提高程序的并發(fā)度。具有獨立功能的單位，以提

49、高程序的并發(fā)度。線程的屬性線程的屬性l輕型實體輕型實體 n只擁有一點必不可少的資源，如：只擁有一點必不可少的資源，如：TCB、寄存器上下文、寄存器上下文和棧和棧l獨立調(diào)度和分派的基本單位獨立調(diào)度和分派的基本單位 n具有具有就緒、阻塞、執(zhí)行就緒、阻塞、執(zhí)行三種基本狀態(tài)三種基本狀態(tài)n線程的創(chuàng)建、終止時間比進程短線程的創(chuàng)建、終止時間比進程短n同進程內(nèi)線程切換時間短，系統(tǒng)開銷小同進程內(nèi)線程切換時間短，系統(tǒng)開銷小l可并發(fā)執(zhí)行可并發(fā)執(zhí)行n同一進程的線程并發(fā)執(zhí)行；不同進程間的線程并發(fā)執(zhí)行同一進程的線程并發(fā)執(zhí)行；不同進程間的線程并發(fā)執(zhí)行l(wèi)共享進程資源共享進程資源 n由于同進程內(nèi)線程間共享內(nèi)存和文件資源，可直接

50、進行由于同進程內(nèi)線程間共享內(nèi)存和文件資源，可直接進行不通過內(nèi)核的通信不通過內(nèi)核的通信115116/64l單線程與多線程的進程單線程與多線程的進程被進程內(nèi)的被進程內(nèi)的線程共享線程共享線程線程資源資源線程與進程的比較線程與進程的比較l(1)(1)調(diào)度。調(diào)度。無線程時，獨立調(diào)度、分派的基本單位是無線程時，獨立調(diào)度、分派的基本單位是進程。而引入線程后，把線程作為調(diào)度和分派的基進程。而引入線程后，把線程作為調(diào)度和分派的基本單位，本單位，而進程而進程只只是資源的擁有者。是資源的擁有者。n同一進程中的線程之間切換，不會引起進程切換同一進程中的線程之間切換，不會引起進程切換，不不同同進進程程中中的線程之間切換

51、，會引起進程切換。的線程之間切換，會引起進程切換。l(2)(2)并發(fā)性。并發(fā)性。引入線程后，進程間可以并發(fā)執(zhí)行，一引入線程后，進程間可以并發(fā)執(zhí)行，一個進程中的多個線程間亦可并發(fā)執(zhí)行，不同進程中個進程中的多個線程間亦可并發(fā)執(zhí)行，不同進程中的線程也能并發(fā)，因而，使的線程也能并發(fā)，因而，使OSOS具有更好的并發(fā)性，具有更好的并發(fā)性，從而能更有效地使用系統(tǒng)資源和提高系統(tǒng)吞吐量。從而能更有效地使用系統(tǒng)資源和提高系統(tǒng)吞吐量。117線程與進程的比較線程與進程的比較l(3)(3)擁有資源。擁有資源。進程是擁有資源的獨立單位。線程自進程是擁有資源的獨立單位。線程自己一般不擁有系統(tǒng)資源，僅有一點必不可少的資源己一般不擁有系統(tǒng)資源，僅有一點必不可少的資源，但它可以訪問其隸屬進程的資源。，但它可以訪問其隸屬進程的資源。l(4)(4)獨立性。獨立性。同一進程中的線程間的獨立性要低于不同一進程中的線程間的獨立性要低于不同進程之間的獨立性。同進程之間的獨