第4章-進程同步與死鎖

1、 進程同步和互斥，臨界資源及臨界區(qū)進程同步和互斥，臨界資源及臨界區(qū)的概念的概念 實現進程互斥的方法實現進程互斥的方法 信號量機制與信號量機制與P、V操作操作 一些經典的進程同步問題一些經典的進程同步問題 利用管程實現進程同步利用管程實現進程同步 進程的死鎖及處理機制進程的死鎖及處理機制 Linux系統(tǒng)的進程同步及死鎖系統(tǒng)的進程同步及死鎖2 并發(fā)性并發(fā)性 操作系統(tǒng)基本特征，改善系統(tǒng)資源的利用率，操作系統(tǒng)基本特征，改善系統(tǒng)資源的利用率，提高系統(tǒng)的吞吐量提高系統(tǒng)的吞吐量 指一組進程執(zhí)行在時間點上相互交替，在時指一組進程執(zhí)行在時間點上相互交替，在時間段上重疊間段上重疊 與時間有關的錯誤與時間有關的錯誤

2、 多進程并發(fā)情況下，進程共享某些變量或硬多進程并發(fā)情況下，進程共享某些變量或硬件資源，進程的執(zhí)行具有不確定性，如果不件資源，進程的執(zhí)行具有不確定性，如果不對進程的執(zhí)行加以制約，執(zhí)行結果是錯誤的對進程的執(zhí)行加以制約，執(zhí)行結果是錯誤的3 進程的同步進程的同步 指當進程運行到某一點時，若其他進程已完成某種指當進程運行到某一點時，若其他進程已完成某種操作，使進程滿足了繼續(xù)運行的條件，進程才能夠操作，使進程滿足了繼續(xù)運行的條件，進程才能夠繼續(xù)運行，否則必須停下來等待繼續(xù)運行，否則必須停下來等待 相互協(xié)作的進程間經常存在數據或變量等共享資源，相互協(xié)作的進程間經常存在數據或變量等共享資源，進程受到特定條件的

3、限制，各進程需要嚴格按照固進程受到特定條件的限制，各進程需要嚴格按照固定的順序執(zhí)行，否則將導致程序的執(zhí)行錯誤定的順序執(zhí)行，否則將導致程序的執(zhí)行錯誤 進程的互斥進程的互斥 互斥共享資源是指在某段時間內，只能有一個進程互斥共享資源是指在某段時間內，只能有一個進程對該資源進行訪問，其他進程若想訪問該資源則必對該資源進行訪問，其他進程若想訪問該資源則必須停下來等待，直到該共享資源被前一進程釋放須停下來等待，直到該共享資源被前一進程釋放4 臨界資源臨界資源 只允許一個進程訪問的共享資源只允許一個進程訪問的共享資源 物理設備：打印機、繪圖儀物理設備：打印機、繪圖儀 變量、數據、文件、內存區(qū)變量、數據、文件

4、、內存區(qū) 臨界區(qū)臨界區(qū) 程序中對臨界資源訪問的代碼程序中對臨界資源訪問的代碼 臨界資源程序：入口區(qū)、臨界區(qū)、退出區(qū)、其余代臨界資源程序：入口區(qū)、臨界區(qū)、退出區(qū)、其余代碼區(qū)碼區(qū) 臨界區(qū)訪問準則：臨界區(qū)訪問準則：p 空閑讓進空閑讓進p 忙則等待忙則等待p 有限等待有限等待p 讓權等待讓權等待5 管理臨界區(qū)管理臨界區(qū)入口入口標志兩個操作標志兩個操作 查看標志以判斷臨界資源是否已被占用；查看標志以判斷臨界資源是否已被占用； 修改標志阻止其他進程進入臨界區(qū)；修改標志阻止其他進程進入臨界區(qū)； 并發(fā)進程交錯執(zhí)行時，可能會出現進程只執(zhí)行一個操作并發(fā)進程交錯執(zhí)行時，可能會出現進程只執(zhí)行一個操作就被另一個進程打斷

5、的情況，從而造成臨界資源訪問發(fā)就被另一個進程打斷的情況，從而造成臨界資源訪問發(fā)生錯誤；生錯誤； 主要思想主要思想 用一條指令來完成標志的檢查和修改兩個操作，保用一條指令來完成標志的檢查和修改兩個操作，保證兩個操作不被打斷；證兩個操作不被打斷； 通過禁止中斷的方式來保證檢查和修改作為一個整通過禁止中斷的方式來保證檢查和修改作為一個整體來執(zhí)行；體來執(zhí)行；6 禁止中斷禁止中斷 進程使用禁止中斷的方法構成臨界區(qū)的入口區(qū)，使進程使用禁止中斷的方法構成臨界區(qū)的入口區(qū)，使用打開中斷的方法構成臨界區(qū)退出區(qū)用打開中斷的方法構成臨界區(qū)退出區(qū) 不足：不足：u如果臨界區(qū)訪問時間過長，關中斷時間過長，限如果臨界區(qū)訪問時

6、間過長，關中斷時間過長，限制處理器交叉執(zhí)行程序的能力，影響系統(tǒng)效率；制處理器交叉執(zhí)行程序的能力，影響系統(tǒng)效率；u將關中斷的權利交給用戶進程，可能會引起計算將關中斷的權利交給用戶進程，可能會引起計算機響應不及時，使重要的中斷程序不能及時處理；機響應不及時，使重要的中斷程序不能及時處理；u在多處理器系統(tǒng)，通過關中斷阻止進程在臨界區(qū)在多處理器系統(tǒng)，通過關中斷阻止進程在臨界區(qū)執(zhí)行不被中斷沒有意義；執(zhí)行不被中斷沒有意義；7 專用機器指令：專門硬件指令，用一條指令完成檢查和專用機器指令：專門硬件指令，用一條指令完成檢查和改寫兩個操作改寫兩個操作 TS（Test-and-Set）指令：檢查指定標志后把該）指

7、令：檢查指定標志后把該標志置位標志置位TS(key)while(!TS(key);臨界區(qū)；臨界區(qū)；if(key = 1)key = 0；return 0;else key = 1;return 1;8 專用機器指令：專門硬件指令，用一條指令完成檢查和專用機器指令：專門硬件指令，用一條指令完成檢查和改寫兩個操作改寫兩個操作 Swap指令：交換兩個字節(jié)的內容指令：交換兩個字節(jié)的內容Swap(a,b)x = 1;while(x != 0)temp = a;swap(&key, &x);a = b;臨界區(qū)；臨界區(qū)；b = temp;key = 0;9 優(yōu)點：優(yōu)點： 適用范圍廣，可用于多

8、個并發(fā)進程及單處理器或多處理器環(huán)適用范圍廣，可用于多個并發(fā)進程及單處理器或多處理器環(huán)境；境； 方法簡單，只需要硬件指令即可實現；方法簡單，只需要硬件指令即可實現； 支持多個臨界區(qū)，可為每個臨界區(qū)設置單獨標志，在支持的支持多個臨界區(qū)，可為每個臨界區(qū)設置單獨標志，在支持的臨界區(qū)的個數上沒有限制；臨界區(qū)的個數上沒有限制； 缺點：缺點： 易出現忙等待，在進程無法進入臨界區(qū)時會對標志進行循環(huán)易出現忙等待，在進程無法進入臨界區(qū)時會對標志進行循環(huán)測試，耗費大量處理器資源；測試，耗費大量處理器資源； 可能產生進程饑餓現象，某個進程釋放臨界資源后，下一個可能產生進程饑餓現象，某個進程釋放臨界資源后，下一個進入臨

9、界區(qū)的進程不確定，從而可能會產生有的進程長期無進入臨界區(qū)的進程不確定，從而可能會產生有的進程長期無法進入臨界區(qū)的情況；法進入臨界區(qū)的情況；10 20世紀世紀60年代開始利用軟件方法解決臨界區(qū)互斥訪問問年代開始利用軟件方法解決臨界區(qū)互斥訪問問題研究；題研究； 方法主要基于內存級別的訪問互斥，通過內存中的標志方法主要基于內存級別的訪問互斥，通過內存中的標志位實現并發(fā)進程對臨界資源的順序訪問；位實現并發(fā)進程對臨界資源的順序訪問； 算法算法1：利用共享的標志位來表示哪個并發(fā)進程可以進：利用共享的標志位來表示哪個并發(fā)進程可以進入臨界區(qū)：設置標志變量，變量為入臨界區(qū)：設置標志變量，變量為0允許進程允許進程

10、A進入，變進入，變量為量為1允許進程允許進程B進入；進入；int turn = 0;進程進程A:進程進程B:while(turn != 0);while(turn != 1);臨界區(qū)臨界區(qū);臨界區(qū)臨界區(qū);turn = 1;turn = 0; 違反違反“空閑讓進空閑讓進”原則原則11算法算法2：利用雙標志法判斷進程是否進入臨界區(qū)：使用數組表示進：利用雙標志法判斷進程是否進入臨界區(qū)：使用數組表示進程是否希望進入臨界區(qū)，真正進入臨界區(qū)之前先查看一下對方標志，程是否希望進入臨界區(qū)，真正進入臨界區(qū)之前先查看一下對方標志，如果對方正在進入臨界區(qū)則進行等待，還需要通過一個變量避免兩如果對方正在進入臨界區(qū)則進

11、行等待，還需要通過一個變量避免兩個進程都無法進入臨界區(qū)個進程都無法進入臨界區(qū)int flag2 = 0,0;進程進程A:進程進程B:flag0 = 1;flag1 = 1;turn = 1;turn = 0;while(flag1&turn = 1);while(flag0&turn = 0);臨界區(qū)臨界區(qū);臨界區(qū)臨界區(qū);flag0 = 0;flag1 = 0;12信號量信號量 荷蘭科學家荷蘭科學家Dijkstra在在1965年提出，進程同步機制；年提出，進程同步機制； 概念上類似交通信號燈，通過信號量的狀態(tài)來決定并發(fā)概念上類似交通信號燈，通過信號量的狀態(tài)來決定并發(fā)進程對臨界資

12、源的訪問順序；進程對臨界資源的訪問順序； 多進程間傳遞簡單信號，使進程在某位置阻塞，直到收多進程間傳遞簡單信號，使進程在某位置阻塞，直到收到特定信號后繼續(xù)運行，達到多進程相互協(xié)作的目的；到特定信號后繼續(xù)運行，達到多進程相互協(xié)作的目的； 包含包含“檢測檢測”和和“歸還歸還”兩個操作：檢測操作稱為兩個操作：檢測操作稱為P操操作，查看是否可訪問臨界資源，若檢測通過，則開始訪作，查看是否可訪問臨界資源，若檢測通過，則開始訪問臨界資源，若檢測不通過，則進行等待，直到臨界資問臨界資源，若檢測不通過，則進行等待，直到臨界資源被歸還后才能進入臨界區(qū)訪問；歸還操作稱為源被歸還后才能進入臨界區(qū)訪問；歸還操作稱為V

13、操作，操作，通知等待進程臨界資源已經被釋放；通知等待進程臨界資源已經被釋放； P操作與操作與V操作都是原子操作，每個步驟不可分割，操作都是原子操作，每個步驟不可分割，“要要么都做，要么都不做么都做，要么都不做”；13信號量（續(xù)）信號量（續(xù)） 實現進程互斥訪問臨界資源的模型：實現進程互斥訪問臨界資源的模型：進程進程1：進程進程2：進程進程3：P(mutex);P(mutex);P(mutex);臨界區(qū)臨界區(qū);臨界區(qū)臨界區(qū);臨界區(qū)臨界區(qū);V(mutex);V(mutex);V(mutex); 實現進程間同步的模型：實現進程間同步的模型：進程進程1：進程進程2：讀入數據讀入數據;P(mutex);V

14、(mutex);處理數據處理數據;14整型信號量機制整型信號量機制 最簡單的一種信號量，通常是一個需要初最簡單的一種信號量，通常是一個需要初始化值的正整型量；始化值的正整型量； 操作原語如下：操作原語如下：P操作：操作：V操作：操作：P(x)V(x)while(x = 0);x = x + 1;x = x - 1;15記錄型信號量機制記錄型信號量機制 整型信號量在整型信號量在P操作不成功時需要進行循環(huán)等待，沒有操作不成功時需要進行循環(huán)等待，沒有放棄放棄CPU資源，違背讓權等待原則，造成系統(tǒng)資源浪費；資源，違背讓權等待原則，造成系統(tǒng)資源浪費； 記錄型信號量在整型信號量基礎上進行改進，包含整型記錄

15、型信號量在整型信號量基礎上進行改進，包含整型值外，還包含一個阻塞隊列；值外，還包含一個阻塞隊列； 操作原語如下：操作原語如下：P操作：操作：V操作：操作：P(x)V(x) x.value=x.value -1; x.value=x.value + 1; if(x.value 0) if(x.value =0&x2=0&.xn=0)for(i=0;in;+i)xi=xi-1;else在隊列中阻塞在隊列中阻塞;18AND型信號量機制（續(xù)型信號量機制（續(xù)2）SV(x1,x2,.,xn)for(i=0;in;+i)xi=xi+1;喚醒隊列中進程喚醒隊列中進程;19生產者生產者-消費者問

16、題消費者問題 最著名進程同步問題，一組生產者進程向一組消費者進最著名進程同步問題，一組生產者進程向一組消費者進程提供產品，共享一個環(huán)形緩沖池；程提供產品，共享一個環(huán)形緩沖池； 緩沖池每個緩沖區(qū)存放一個產品，生產者進程不斷生產緩沖池每個緩沖區(qū)存放一個產品，生產者進程不斷生產產品并放入緩沖池，消費者進程不斷從緩沖池取出產品產品并放入緩沖池，消費者進程不斷從緩沖池取出產品并消費；并消費； 進程滿足同步條件：進程滿足同步條件： 任一時刻所有生產者存放產品的單元數不能超過緩沖池的總任一時刻所有生產者存放產品的單元數不能超過緩沖池的總容量容量N； 所有消費者取出產品的總量不能超過所有生產者當前生產產所有消

17、費者取出產品的總量不能超過所有生產者當前生產產品的總量；品的總量；20生產者生產者-消費者問題（續(xù)消費者問題（續(xù)1） 同步關系：同步關系：當緩沖池滿時生產者進程需等待；當緩沖池滿時生產者進程需等待；當緩沖池空時消費者進程需等待；當緩沖池空時消費者進程需等待；各個進程應互斥使用緩沖池；各個進程應互斥使用緩沖池； 使用信號量解決問題。假設緩沖區(qū)編號使用信號量解決問題。假設緩沖區(qū)編號0（N-1），用），用in和和out作為生產者和消費者進程使用的指針，指向可用作為生產者和消費者進程使用的指針，指向可用的緩沖區(qū)，初值都是的緩沖區(qū)，初值都是0。設置。設置3個信號量：個信號量：full，表示放有產品的緩沖

18、區(qū)數，初值為，表示放有產品的緩沖區(qū)數，初值為0；empty，表示可供使用的緩沖區(qū)數，初值為，表示可供使用的緩沖區(qū)數，初值為N；mutex，互斥信號量，初值為，互斥信號量，初值為1，使各進程互斥進入臨界區(qū)，保證任何時候，使各進程互斥進入臨界區(qū)，保證任何時候只有一個進程使用緩沖區(qū)；只有一個進程使用緩沖區(qū)；21生產者生產者-消費者問題（續(xù)消費者問題（續(xù)2）算法描述：算法描述：/生產者進程生產者進程 /消費者進程消費者進程while(1) while(1) P(empty); P(full); P(mutex); P(mutex); 產品送往產品送往buffer(in); 從從buffer(out)取

19、出產品取出產品; in=(in+1)%N; out=(out+1)%N; V(mutex); V(mutex); V(full); V(empty); 生產者進程利用信號量生產者進程利用信號量empty保證在具有空閑的緩沖區(qū)時才將產品保證在具有空閑的緩沖區(qū)時才將產品放入緩沖池，消費者進程利用信號量放入緩沖池，消費者進程利用信號量full保證只有在緩沖區(qū)存在產保證只有在緩沖區(qū)存在產品時才會取出，信號量品時才會取出，信號量mutex保證生產者及消費者進程對緩沖池的保證生產者及消費者進程對緩沖池的互斥訪問?；コ庠L問。22讀者讀者-寫者問題寫者問題 一個數據對象（如文件或記錄）可以被多個并發(fā)進程共一個

20、數據對象（如文件或記錄）可以被多個并發(fā)進程共享，有些進程只要求讀取數據對象的內容，另一些進程享，有些進程只要求讀取數據對象的內容，另一些進程則要求修改數據對象的內容；則要求修改數據對象的內容； 允許多個讀進程同時訪問數據對象，但寫進程不能與其允許多個讀進程同時訪問數據對象，但寫進程不能與其他進程同時訪問數據對象；他進程同時訪問數據對象； 舉例，大型數據庫系統(tǒng)；舉例，大型數據庫系統(tǒng)； 根據寫者到來后是否仍允許新讀者進入分類：根據寫者到來后是否仍允許新讀者進入分類： 讀者優(yōu)先：當寫者提出存取共享對象的需求后，仍允許新讀讀者優(yōu)先：當寫者提出存取共享對象的需求后，仍允許新讀者進入；者進入； 寫者優(yōu)先：

21、當寫者提出存取共享對象的需求后，不允許新讀寫者優(yōu)先：當寫者提出存取共享對象的需求后，不允許新讀者進入；者進入；23讀者讀者-寫者問題（續(xù)寫者問題（續(xù)1） 使用信號量解決問題。需要設置兩個信號量和一個共享使用信號量解決問題。需要設置兩個信號量和一個共享變量：變量：讀互斥信號量讀互斥信號量rmutex，用于使讀進程互斥訪問共享變量，用于使讀進程互斥訪問共享變量readcount，其初，其初值為值為1；讀寫互斥信號量讀寫互斥信號量mutex，用于實現寫進程與讀進程的互斥以及寫進程與寫，用于實現寫進程與讀進程的互斥以及寫進程與寫進程的互斥，其初值為進程的互斥，其初值為1；讀共享變量讀共享變量readc

22、ount，用于記錄當前的讀進程數目，初值為，用于記錄當前的讀進程數目，初值為0；24讀者讀者-寫者問題（續(xù)寫者問題（續(xù)2）算法描述：（讀者優(yōu)先）算法描述：（讀者優(yōu)先）/讀者進程讀者進程 /寫者進程寫者進程while(1) while(1) P(rmutex); P(mutex); readcount=readcount+1; 執(zhí)行寫操作執(zhí)行寫操作; if(readcount=1) V(mutex); P(mutex); V(rmutex); 執(zhí)行讀操作執(zhí)行讀操作; P(rmutex); readcount=readcount-1; if(readcount=0) V(mutex); V(rmu

23、tex); 使用讀取的數據使用讀取的數據;25讀者讀者-寫者問題（續(xù)寫者問題（續(xù)3） 上述算法基礎上，增加上述算法基礎上，增加3個信號量和一個共享變量解決個信號量和一個共享變量解決寫者優(yōu)先的讀者寫者優(yōu)先的讀者-寫者問題：寫者問題：寫互斥信號量寫互斥信號量wmutex，用于使寫進程互斥訪問共享變量，用于使寫進程互斥訪問共享變量writecount，其初，其初值為值為1；讀寫阻塞信號量讀寫阻塞信號量rblock，用來在寫者到來后阻塞讀者，其初值為，用來在寫者到來后阻塞讀者，其初值為1；寫阻塞信號量寫阻塞信號量wblock，當有讀者被寫者阻塞時，阻塞其他新到來的讀者，當有讀者被寫者阻塞時，阻塞其他新

24、到來的讀者，其初值為其初值為1； 寫共享變量寫共享變量writecountwritecount，用來記錄當前寫進程的數目，初值為，用來記錄當前寫進程的數目，初值為0 0；26讀者讀者-寫者問題（續(xù)寫者問題（續(xù)4）算法描述：（寫者優(yōu)先）算法描述：（寫者優(yōu)先）/讀者進程讀者進程 /寫者進程寫者進程while(1) while(1) P(wblock); P(wmutex); P(rblock); writecount=writecount+1; P(rmutex); if(writecount=1) readcount=readcount+1; P(rblock); if(readcount=1)

25、 V(wmutex); P(mutex); P(mutex); V(rmutex); 執(zhí)行寫操作執(zhí)行寫操作; V(rblock); V(mutex); V(wblock); P(wmutex); 執(zhí)行讀操作執(zhí)行讀操作; writecount=writecount-1; P(rmutex); if(writecount=0) readcount=readcount-1; V(rblock); if(readcount=0) V(wmutex); V(mutex); V(rmutex);27哲學家進餐問題哲學家進餐問題 問題描述：有問題描述：有5個哲學家，生活方式就是交替地進行思個哲學家，生活方式

26、就是交替地進行思考和進餐，公用一張圓桌，分別坐在周圍的考和進餐，公用一張圓桌，分別坐在周圍的5張椅子上，張椅子上，在圓桌上有在圓桌上有5個碗和個碗和5支筷子，平時哲學家進行思考，饑支筷子，平時哲學家進行思考，饑餓時便試圖取其左右最靠近他的筷子，只有在拿到兩支餓時便試圖取其左右最靠近他的筷子，只有在拿到兩支筷子時才能進餐，進餐完畢，放下筷子又繼續(xù)思考；筷子時才能進餐，進餐完畢，放下筷子又繼續(xù)思考； 3種狀態(tài)：種狀態(tài)： THINKING：思考狀態(tài)，處于該狀態(tài)的哲學家正在思考；：思考狀態(tài)，處于該狀態(tài)的哲學家正在思考； HUNGRY：饑餓狀態(tài)，處于該狀態(tài)的哲學家已經停止思考，：饑餓狀態(tài)，處于該狀態(tài)的哲

27、學家已經停止思考，正在試圖取得身邊的兩根筷子；正在試圖取得身邊的兩根筷子； EATING：就餐狀態(tài)，處于該狀態(tài)的哲學家取得身邊的兩根：就餐狀態(tài)，處于該狀態(tài)的哲學家取得身邊的兩根筷子，正在就餐；筷子，正在就餐； 設定哲學家編號依次為設定哲學家編號依次為0到到4，數組，數組State表明哲學家所表明哲學家所處狀態(tài)；處狀態(tài)； 定義信號量數組定義信號量數組s，對應每個哲學家，初值為，對應每個哲學家，初值為0，在哲學，在哲學家得不到筷子時阻塞。定義信號量家得不到筷子時阻塞。定義信號量mutex，初值為，初值為1；28哲學家進餐問題（續(xù)）哲學家進餐問題（續(xù)）算法描述：算法描述：/哲學家進程哲學家進程i v

28、oid philosopher(int i) void test(int i) while(1) if(statei=HUNGRY & 思考問題思考問題; stateLEFT(i)!=EATING & take_chopstick(i); stateRIGHT(i)!=EATING) 就餐就餐; put_chopstick(i); statei=EATING; V(si); void take_chopstick(int i) void put_chopstick(int i) P(mutex); P(mutex); statei=HUNGRY; statei=THINKING

29、; test(i); test(LEFT(i); V(mutex); test(RIGHT(i); P(si); V(mutex); 29打瞌睡理發(fā)師問題打瞌睡理發(fā)師問題 問題描述：理發(fā)店有一位理發(fā)師、一把理發(fā)椅和問題描述：理發(fā)店有一位理發(fā)師、一把理發(fā)椅和5把供把供等候理發(fā)的顧客坐的座椅，如果沒有顧客，理發(fā)師便在等候理發(fā)的顧客坐的座椅，如果沒有顧客，理發(fā)師便在理發(fā)椅上睡覺。一個顧客到來時，必須叫醒理發(fā)師，如理發(fā)椅上睡覺。一個顧客到來時，必須叫醒理發(fā)師，如果理發(fā)師正在理發(fā)而且有空椅子可坐，就坐下來等待，果理發(fā)師正在理發(fā)而且有空椅子可坐，就坐下來等待，否則就離開；否則就離開； 設置變量設置變量wa

30、iting表示等待理發(fā)的顧客的數量，初值為表示等待理發(fā)的顧客的數量，初值為0。定義定義3個信號量：個信號量： customers：正待等待的顧客的數量，數值上與：正待等待的顧客的數量，數值上與waiting相同，初值相同，初值為為0； barbers：理發(fā)師的狀態(tài)，初值為：理發(fā)師的狀態(tài)，初值為1； mutex：用于互斥訪問變量：用于互斥訪問變量waiting，初值為，初值為1；30打瞌睡理發(fā)師問題（續(xù)）打瞌睡理發(fā)師問題（續(xù)）算法描述：算法描述：#define CHAIRS 5void barber(void) void customer(void) while(1) P(mutex); P(c

31、ustomers); if(waitingCHAIRS) P(mutex); waiting+; waiting-; V(customers); V(barbers); V(mutex); V(mutex); P(barbers); 給顧客理發(fā)給顧客理發(fā); 理發(fā)理發(fā); else V(mutex); 離開離開; 31使用信號的管程使用信號的管程Brinch Hansen和和Hoare提出，高級同步機制，管程提出，高級同步機制，管程Monitor；基本思想：利用數據抽象地表示系統(tǒng)中的共享資源，而把對該數據基本思想：利用數據抽象地表示系統(tǒng)中的共享資源，而把對該數據實施的操作定義為一組過程。代表共享資

32、源的數據，以及由對該共實施的操作定義為一組過程。代表共享資源的數據，以及由對該共享資源實施操作的一組過程所組成的資源管理程序，共同構成了一享資源實施操作的一組過程所組成的資源管理程序，共同構成了一個操作系統(tǒng)的資源管理模塊個操作系統(tǒng)的資源管理模塊-管程；管程；Hansen定義：一個管程定義了一個數據結構和能為并發(fā)進程在其定義：一個管程定義了一個數據結構和能為并發(fā)進程在其上執(zhí)行的一組操作，這組操作能使進程同步和改變管程中的數據；上執(zhí)行的一組操作，這組操作能使進程同步和改變管程中的數據；四部分組成：四部分組成：管程名稱；管程名稱；局部于管程的數據的說明；局部于管程的數據的說明；對數據進行操作的一組過

33、程；對數據進行操作的一組過程；對局部于管程內部的共享數據賦初值的語句；對局部于管程內部的共享數據賦初值的語句；32使用信號的管程（續(xù)）使用信號的管程（續(xù)）進程要想進入管程，必須調用管程中的過程；面向對象中對象的特進程要想進入管程，必須調用管程中的過程；面向對象中對象的特點；點；管程的過程體可以有局部數據；過程有兩種：由管程的過程體可以有局部數據；過程有兩種：由define定義的過程定義的過程可以被其他模塊引用，而未定義的則僅在管程內部使用；管程要引可以被其他模塊引用，而未定義的則僅在管程內部使用；管程要引用模塊外定義的過程，則必須用用模塊外定義的過程，則必須用use說明；說明；編譯器采用與其他

34、過程調用不同的方法來處理對管程的調用；典型編譯器采用與其他過程調用不同的方法來處理對管程的調用；典型處理方法：當一個進程調用管程過程時，該過程的前幾條指令將檢處理方法：當一個進程調用管程過程時，該過程的前幾條指令將檢查在管程中是否有其他活躍進程；查在管程中是否有其他活躍進程；進入管程時的互斥由編譯器負責，使用二值型信號量；進入管程時的互斥由編譯器負責，使用二值型信號量；條件變量和操作原語：條件變量和操作原語：wait，signal；生產者生產者-消費者問題使用管程的一種解決方案（消費者問題使用管程的一種解決方案（P96）；）；自動實現對臨界區(qū)的互斥，比信號量更容易保證程序的正確性；自動實現對臨

35、界區(qū)的互斥，比信號量更容易保證程序的正確性；缺點：程序設計語言概念，編譯器必須識別管程并用某種方式實現缺點：程序設計語言概念，編譯器必須識別管程并用某種方式實現互斥；互斥；33使用通知和廣播的管程使用通知和廣播的管程 Lampson和和Redell開發(fā)另一種管程方案，解決開發(fā)另一種管程方案，解決singal處理處理問題，并支持許多有用擴展；問題，并支持許多有用擴展； singal原語被原語被notify取代；取代； notify含義：當一個正在管程中的進程執(zhí)行含義：當一個正在管程中的進程執(zhí)行notify（x）時，時，x條件隊列得到通知，但發(fā)信號的進程繼續(xù)執(zhí)行；條件隊列得到通知，但發(fā)信號的進程繼

36、續(xù)執(zhí)行；通知的結果使得位于條件隊列頭的進程在將來方便時、通知的結果使得位于條件隊列頭的進程在將來方便時、當處理器可用時被恢復；不能保證之前沒有其他進程進當處理器可用時被恢復；不能保證之前沒有其他進程進入管程，等待進程必須重新檢查條件；入管程，等待進程必須重新檢查條件； 增加增加broadcast廣播原語，使所有在該條件上等待的進廣播原語，使所有在該條件上等待的進程都被置于就緒狀態(tài)；當不知道有多少別的進程將被激程都被置于就緒狀態(tài)；當不知道有多少別的進程將被激活時或難以準確斷定將激活哪個進程時，可使用廣播；活時或難以準確斷定將激活哪個進程時，可使用廣播； 使用通知和廣播的管程有助于程序結構中采用更

37、模塊化使用通知和廣播的管程有助于程序結構中采用更模塊化的方法；的方法；34死鎖的概念死鎖的概念 現實生活現象：兩人過獨木橋；現實生活現象：兩人過獨木橋； 進程死鎖問題描述：資源進程死鎖問題描述：資源R1和和R2是獨占性資源，進程是獨占性資源，進程A占有資源占有資源R1，進程，進程B占有資源占有資源R2，進程，進程A等待占有資源等待占有資源R2，進程等待占有資源，進程等待占有資源R1；結果兩個進程都處于阻塞狀；結果兩個進程都處于阻塞狀態(tài)，若不采取其他措施，這種循環(huán)等待狀況無限期持續(xù)。態(tài)，若不采取其他措施，這種循環(huán)等待狀況無限期持續(xù)。 信號量是共享資源，如果信號量是共享資源，如果P、V操作使用不當

38、，也會產生操作使用不當，也會產生死鎖；死鎖； 系統(tǒng)中資源分配不當也可引起死鎖；系統(tǒng)中資源分配不當也可引起死鎖； 死鎖：多個進程循環(huán)等待他方占有的獨占性資源而無限死鎖：多個進程循環(huán)等待他方占有的獨占性資源而無限期地僵持下去的局面。如果沒有外力作用，那么死鎖涉期地僵持下去的局面。如果沒有外力作用，那么死鎖涉及的各個進程都將永遠處于阻塞狀態(tài)；及的各個進程都將永遠處于阻塞狀態(tài)；35死鎖的概念（續(xù)）死鎖的概念（續(xù)） 同時具備如下同時具備如下4個必要條件時，發(fā)生死鎖：個必要條件時，發(fā)生死鎖： 互斥條件：每個資源每次只能分配給一個進程使用，某個進互斥條件：每個資源每次只能分配給一個進程使用，某個進程一旦獲得

39、資源，就不準其他進程使用；程一旦獲得資源，就不準其他進程使用； 部分分配（占有且等待）條件：進程由于申請不到所需要的部分分配（占有且等待）條件：進程由于申請不到所需要的資源而等待時，仍然占據著已經分配到的資源；資源而等待時，仍然占據著已經分配到的資源； 不可搶占（非剝奪）條件：任一個進程不能從另一個進程那不可搶占（非剝奪）條件：任一個進程不能從另一個進程那里搶占資源，即已被占有的資源，只能由占用進程自己來釋里搶占資源，即已被占有的資源，只能由占用進程自己來釋放；放； 循環(huán)等待條件：存在一個循環(huán)的等待序列，從而形成一個進循環(huán)等待條件：存在一個循環(huán)的等待序列，從而形成一個進程循環(huán)等待環(huán)；程循環(huán)等待

40、環(huán)； 資源分配圖示例（資源分配圖示例（P99）；）；36死鎖的處理策略死鎖的處理策略 產生死鎖的因素：系統(tǒng)擁有的資源數量、資源分配策略、產生死鎖的因素：系統(tǒng)擁有的資源數量、資源分配策略、進程對資源的使用要求、并發(fā)進程的速率；進程對資源的使用要求、并發(fā)進程的速率； 策略：策略： 預防死鎖：通過破壞預防死鎖：通過破壞4個必要條件之一，可以使系統(tǒng)不具備個必要條件之一，可以使系統(tǒng)不具備產生死鎖的條件；產生死鎖的條件； 避免死鎖：在為申請者分配資源前先測試系統(tǒng)狀態(tài)，若把資避免死鎖：在為申請者分配資源前先測試系統(tǒng)狀態(tài)，若把資源分配給申請者會產生死鎖，拒絕分配，否則接受申請，為源分配給申請者會產生死鎖，拒絕

41、分配，否則接受申請，為它分配資源；它分配資源； 檢測死鎖并恢復：允許系統(tǒng)出現死鎖，在死鎖發(fā)生后，通過檢測死鎖并恢復：允許系統(tǒng)出現死鎖，在死鎖發(fā)生后，通過一定方法加以恢復，并盡可能地減少損失；一定方法加以恢復，并盡可能地減少損失； 忽略死鎖：任憑死鎖的出現；當系統(tǒng)中出現死鎖時，將系統(tǒng)忽略死鎖：任憑死鎖的出現；當系統(tǒng)中出現死鎖時，將系統(tǒng)重新啟動；重新啟動；37死鎖的預防死鎖的預防 死鎖預防是排除死鎖的靜態(tài)策略，對進程申請資源的活死鎖預防是排除死鎖的靜態(tài)策略，對進程申請資源的活動加以限制，從而使產生死鎖的動加以限制，從而使產生死鎖的4個必要條件不能同時個必要條件不能同時具備，以保證死鎖不會發(fā)生；具備

42、，以保證死鎖不會發(fā)生； 策略：策略： 破壞互斥條件：由于資源獨占特征引起；一般來說，不采用該方法；破壞互斥條件：由于資源獨占特征引起；一般來說，不采用該方法； 破壞部分分配（占有而且等待）條件：破壞部分分配（占有而且等待）條件： 采用預分配策略，進程執(zhí)行前申請，靜態(tài)分配，申請資源系統(tǒng)調用采用預分配策略，進程執(zhí)行前申請，靜態(tài)分配，申請資源系統(tǒng)調用先于其他系統(tǒng)調用；先于其他系統(tǒng)調用； 僅當進程沒有占用資源時才允許它去申請資源，已經占用再申請資僅當進程沒有占用資源時才允許它去申請資源，已經占用再申請資源，應先釋放所占資源；源，應先釋放所占資源； 減低資源利用率，執(zhí)行前不知道所需全部資源；減低資源利用

43、率，執(zhí)行前不知道所需全部資源；38死鎖的預防（續(xù)）死鎖的預防（續(xù)） 策略：策略： 破壞不可搶占（非剝奪）條件：破壞不可搶占（非剝奪）條件： 允許在一些情況下，搶占其他進程占有的資源；允許在一些情況下，搶占其他進程占有的資源； 常用于資源狀態(tài)易于保留和恢復的環(huán)境，如常用于資源狀態(tài)易于保留和恢復的環(huán)境，如CPU寄存器和內存；寄存器和內存； 破壞循環(huán)條件：破壞循環(huán)條件： 實行資源按序（層次）分配策略，把全部資源事先分成多個層次，實行資源按序（層次）分配策略，把全部資源事先分成多個層次，排上序號，然后依次序分配；排上序號，然后依次序分配； 先釋放大，再申請??；先釋放大，再申請??； 證明（證明（P100

44、）；）； 資源利用率提高；進程使用資源次序和系統(tǒng)規(guī)定資源次序不同時，資源利用率提高；進程使用資源次序和系統(tǒng)規(guī)定資源次序不同時，提高不明顯；系統(tǒng)中所有資源合理排序號是難事，增加系統(tǒng)開銷；提高不明顯；系統(tǒng)中所有資源合理排序號是難事，增加系統(tǒng)開銷；39死鎖的避免死鎖的避免 動態(tài)策略，在為申請者分配資源前先測試系統(tǒng)裝他，若動態(tài)策略，在為申請者分配資源前先測試系統(tǒng)裝他，若把資源分配給申請者會產生死鎖，拒絕分配，否則接受把資源分配給申請者會產生死鎖，拒絕分配，否則接受申請，為它分配資源；申請，為它分配資源； Dijkstra，1965年，經典避免死鎖的算法年，經典避免死鎖的算法-銀行家算法；銀行家算法；模

45、型基于一個小城鎮(zhèn)的銀行家，向一群客戶分別承諾了模型基于一個小城鎮(zhèn)的銀行家，向一群客戶分別承諾了一定金額的貸款，而他知道不可能所有客戶同時都需要一定金額的貸款，而他知道不可能所有客戶同時都需要最大的貸款額。銀行家算法就是對每一個客戶的請求進最大的貸款額。銀行家算法就是對每一個客戶的請求進行檢查，檢查如果滿足它是否會引起不安全狀態(tài)；如果行檢查，檢查如果滿足它是否會引起不安全狀態(tài)；如果是，則不滿足該請求；否，則滿足請求；是，則不滿足該請求；否，則滿足請求； 系統(tǒng)安全，指系統(tǒng)中的所有進程能夠按照某一種次序分系統(tǒng)安全，指系統(tǒng)中的所有進程能夠按照某一種次序分配資源，并且依次運行完畢，這種進程序列就是安全序

46、配資源，并且依次運行完畢，這種進程序列就是安全序列；如果存在這樣一個安全序列，則系統(tǒng)是安全的；如列；如果存在這樣一個安全序列，則系統(tǒng)是安全的；如果系統(tǒng)不存在這個一個安全序列，則系統(tǒng)是不安全的；果系統(tǒng)不存在這個一個安全序列，則系統(tǒng)是不安全的；40死鎖的避免（續(xù)死鎖的避免（續(xù)1） 銀行家算法：系統(tǒng)給進程分配資源時，先檢查狀態(tài)是否銀行家算法：系統(tǒng)給進程分配資源時，先檢查狀態(tài)是否安全，方法是看它是否有足夠的剩余資源滿足一個距最安全，方法是看它是否有足夠的剩余資源滿足一個距最大需求最近的進程；如果有，那么分配資源給該進程，大需求最近的進程；如果有，那么分配資源給該進程，然后接著檢查下一個距最大需求最近的

47、進程，如此反復然后接著檢查下一個距最大需求最近的進程，如此反復下去。如果所有進程都能獲得所需資源，那么該狀態(tài)是下去。如果所有進程都能獲得所需資源，那么該狀態(tài)是安全的，最初的進程申請資源可以分配；安全的，最初的進程申請資源可以分配； 數據結構：向量數據結構：向量Availablej=k，表示，表示 類資源可用數類資源可用數量是量是k；矩陣；矩陣Claimi,j=x，表示進程，表示進程 最大需求最大需求 類類資源資源x個；矩陣個；矩陣Allocationi,j=y，表示進程，表示進程 此時占此時占有有y個個 類資源；矩陣類資源；矩陣Needi,j=z，表示進程，表示進程 還總還總共需要共需要z個個

48、 類資源才能完成任務；類資源才能完成任務； Needi,j=Claimi,j-Allocationi,j；41jriPjriPjriPjr死鎖的避免（續(xù)死鎖的避免（續(xù)2） 算法描述：設算法描述：設Request 是進程是進程P 的申請向量，如果的申請向量，如果Request j=m，表示，表示P 這次申請這次申請m個個r 類資源；當類資源；當P 發(fā)發(fā)出申請后，系統(tǒng)按下述步驟進行檢查：出申請后，系統(tǒng)按下述步驟進行檢查：if (Request =Need ) goto ;else error(進程對資源的申請量大于它說明的最大值進程對資源的申請量大于它說明的最大值);if (Request =Av

49、ailable ) goto ;else wait();系統(tǒng)試探性地把資源分配給系統(tǒng)試探性地把資源分配給P （類似回溯算法），并根據分配修改下（類似回溯算法），并根據分配修改下面數據結構中的值：面數據結構中的值：Available := Available - Request ;Allocation := Allocation + Request ;Need := Need - Request ;系統(tǒng)執(zhí)行安全性檢查，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)；系統(tǒng)執(zhí)行安全性檢查，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)；若安全，才正式將資源分配給進程以完成此次分配；若不安全，試探若安全，才正式將

50、資源分配給進程以完成此次分配；若不安全，試探性分配作廢，恢復原資源分配表，讓進程性分配作廢，恢復原資源分配表，讓進程P 等待；等待；42iiiiijiiiiiiiiiiii死鎖的避免（續(xù)死鎖的避免（續(xù)3）安全性檢查算法描述：設置兩個向量安全性檢查算法描述：設置兩個向量Free、Finish；向量；向量Free表示表示系統(tǒng)可分配給進程的各類資源數組，含有元素個數等于資源數，執(zhí)系統(tǒng)可分配給進程的各類資源數組，含有元素個數等于資源數，執(zhí)行安全算法開始時，行安全算法開始時，Free := Available；標記向量；標記向量Finish表示進程表示進程在此次檢查中是否被滿足，初始值表示當前未滿足進程

51、申請，即在此次檢查中是否被滿足，初始值表示當前未滿足進程申請，即Finishi=false；當有足夠資源分配給進程（；當有足夠資源分配給進程（Need =Free）時，）時，Finishi=true，P 完成并釋放資源；完成并釋放資源；從進程集合中找一個能滿足下述條件的進程從進程集合中找一個能滿足下述條件的進程P ; Finishi=false，表示資源未分配給進程；，表示資源未分配給進程； Need =Free，表示資源夠分配給進程；，表示資源夠分配給進程；當當P 獲得資源后，認為獲得資源后，認為P 完成，釋放資源；完成，釋放資源；Free := Free + Allocation;Fini

52、shi ：=true；goto step1如此試探分配，若可以達到如此試探分配，若可以達到Finish0,.,n=true成立，則表示系統(tǒng)處于安全成立，則表示系統(tǒng)處于安全狀態(tài)；否則系統(tǒng)處于不安全狀態(tài)；狀態(tài)；否則系統(tǒng)處于不安全狀態(tài)；43iiiiiii44 資源資源進程進程AllocationClaimNeedAvailableR1R2R3R4R1R2R3R4R1R2R3R4R1R2R3R4P13011411111001020P2010002120112P3111042103100P4110111210020P5000021102110 資資源源進程進程FreeNeedAllocationFree

53、+AllocationFinishR1R2R3R4R1R2R3R4R1R2R3R4R1R2R3R4死鎖的檢測與恢復死鎖的檢測與恢復 對資源的分配加以限制可以預防和避免死鎖的發(fā)生，但對資源的分配加以限制可以預防和避免死鎖的發(fā)生，但不利于各進程對系統(tǒng)資源的充分共享；不利于各進程對系統(tǒng)資源的充分共享； 死鎖檢測方法，對資源的分配不加以限制，系統(tǒng)周期性死鎖檢測方法，對資源的分配不加以限制，系統(tǒng)周期性地運行一個地運行一個“死鎖檢測死鎖檢測”程序，判斷系統(tǒng)內是否存在死程序，判斷系統(tǒng)內是否存在死鎖，若檢測到，則設法加以解除；鎖，若檢測到，則設法加以解除； 檢測頻率取決于發(fā)生死鎖的可能性，申請資源時檢測可檢測

54、頻率取決于發(fā)生死鎖的可能性，申請資源時檢測可以使算法相對比較簡單，但頻繁的檢測消耗相當多的系以使算法相對比較簡單，但頻繁的檢測消耗相當多的系統(tǒng)資源；統(tǒng)資源；45死鎖的檢測與恢復（續(xù)死鎖的檢測與恢復（續(xù)1） 檢測常見算法：使用檢測常見算法：使用Available向量、向量、Allocation矩陣、矩陣、Request矩陣；算法只調查尚待完成的各個進程所有可矩陣；算法只調查尚待完成的各個進程所有可能的分配序列；初始化臨時向量能的分配序列；初始化臨時向量Free:=Available；如；如果果Allocation 0(i=1,2,.,n)，則，則Finishi=false；否；否則則Finish

55、=true； 算法描述：算法描述： 從進程集合中找一個能滿足下述條件的進程從進程集合中找一個能滿足下述條件的進程P ； Finishi=false，表示資源未分配給進程；，表示資源未分配給進程； Request =Free，表示資源夠分配給進程；，表示資源夠分配給進程； 當當P 獲得資源后，認為獲得資源后，認為P 完成，釋放資源；完成，釋放資源；Free := Free + Allocation;Finishi := true;goto step1; 存在某些存在某些i，使得，使得Finishi=false，則系統(tǒng)處于死鎖狀態(tài)，進，則系統(tǒng)處于死鎖狀態(tài)，進程程P 處于死鎖之中；處于死鎖之中；46

56、iiiiii死鎖的檢測與恢復（續(xù)死鎖的檢測與恢復（續(xù)2） 按照檢測算法，序列按照檢測算法，序列P1，P3，P2，P4，對于所有，對于所有i都都有有Finishi=true，因此，在，因此，在T0時刻沒有死鎖；時刻沒有死鎖；47 資源資源進程進程AllocationRequestAvailableR1R2R3R1R2R3R1R2R3P1110000000P2200202P3313000P4212102死鎖的檢測與恢復（續(xù)死鎖的檢測與恢復（續(xù)3） 進程進程P3申請一個申請一個R3資源，進程資源，進程P3等待；等待； 對于對于i=1,2,3,4，Allocation 0，則，則Finishi=False； P1 Request1=Free，標記，標記Finish1=true，釋放資源，釋放資源，Free=（1,1,0），此時不能滿足其余進程中任何一個需），此時不能滿足其余進程中任何一個需要，要，Finishi=false，出現死鎖，出現死鎖48 資源資源進程進程AllocationRequestAvailableR1R2R3R1R2R3R1R2R3P1110000000P2200202P3313001P42