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

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

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

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

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

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

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

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

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

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

11、行等待，還需要通過(guò)一個(gè)變量避免兩個(gè)進(jìn)程都無(wú)法進(jìn)入臨界區(qū)個(gè)進(jìn)程都無(wú)法進(jìn)入臨界區(qū)int flag2 = 0,0;進(jìn)程進(jìn)程A:進(jìn)程進(jìn)程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信號(hào)量信號(hào)量 荷蘭科學(xué)家荷蘭科學(xué)家Dijkstra在在1965年提出，進(jìn)程同步機(jī)制；年提出，進(jìn)程同步機(jī)制； 概念上類似交通信號(hào)燈，通過(guò)信號(hào)量的狀態(tài)來(lái)決定并發(fā)概念上類似交通信號(hào)燈，通過(guò)信號(hào)量的狀態(tài)來(lái)決定并發(fā)進(jìn)程對(duì)臨界資

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

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

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

15、型信號(hào)量在整型信號(hào)量基礎(chǔ)上進(jìn)行改進(jìn)，包含整型值外，還包含一個(gè)阻塞隊(duì)列；值外，還包含一個(gè)阻塞隊(duì)列； 操作原語(yǔ)如下：操作原語(yǔ)如下：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在隊(duì)列中阻塞在隊(duì)列中阻塞;18AND型信號(hào)量機(jī)制（續(xù)型信號(hào)量機(jī)制（續(xù)2）SV(x1,x2,.,xn)for(i=0;in;+i)xi=xi+1;喚醒隊(duì)列中進(jìn)程喚醒隊(duì)列中進(jìn)程;19生產(chǎn)者生產(chǎn)者-消費(fèi)者問

16、題消費(fèi)者問題 最著名進(jìn)程同步問題，一組生產(chǎn)者進(jìn)程向一組消費(fèi)者進(jìn)最著名進(jìn)程同步問題，一組生產(chǎn)者進(jìn)程向一組消費(fèi)者進(jìn)程提供產(chǎn)品，共享一個(gè)環(huán)形緩沖池；程提供產(chǎn)品，共享一個(gè)環(huán)形緩沖池； 緩沖池每個(gè)緩沖區(qū)存放一個(gè)產(chǎn)品，生產(chǎn)者進(jìn)程不斷生產(chǎn)緩沖池每個(gè)緩沖區(qū)存放一個(gè)產(chǎn)品，生產(chǎn)者進(jìn)程不斷生產(chǎn)產(chǎn)品并放入緩沖池，消費(fèi)者進(jìn)程不斷從緩沖池取出產(chǎn)品產(chǎn)品并放入緩沖池，消費(fèi)者進(jìn)程不斷從緩沖池取出產(chǎn)品并消費(fèi)；并消費(fèi)； 進(jìn)程滿足同步條件：進(jìn)程滿足同步條件： 任一時(shí)刻所有生產(chǎn)者存放產(chǎn)品的單元數(shù)不能超過(guò)緩沖池的總?cè)我粫r(shí)刻所有生產(chǎn)者存放產(chǎn)品的單元數(shù)不能超過(guò)緩沖池的總?cè)萘咳萘縉； 所有消費(fèi)者取出產(chǎn)品的總量不能超過(guò)所有生產(chǎn)者當(dāng)前生產(chǎn)產(chǎn)所有消

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

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

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

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

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

22、ount，用于記錄當(dāng)前的讀進(jìn)程數(shù)目，初值為，用于記錄當(dāng)前的讀進(jìn)程數(shù)目，初值為0；24讀者讀者-寫者問題（續(xù)寫者問題（續(xù)2）算法描述：（讀者優(yōu)先）算法描述：（讀者優(yōu)先）/讀者進(jìn)程讀者進(jìn)程 /寫者進(jìn)程寫者進(jìn)程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); 使用讀取的數(shù)據(jù)使用讀取的數(shù)據(jù);25讀者讀者-寫者問題（續(xù)寫者問題（續(xù)3） 上述算法基礎(chǔ)上，增加上述算法基礎(chǔ)上，增加3個(gè)信號(hào)量和一個(gè)共享變量解決個(gè)信號(hào)量和一個(gè)共享變量解決寫者優(yōu)先的讀者寫者優(yōu)先的讀者-寫者問題：寫者問題：寫互斥信號(hào)量寫互斥信號(hào)量wmutex，用于使寫進(jìn)程互斥訪問共享變量，用于使寫進(jìn)程互斥訪問共享變量writecount，其初，其初值為值為1；讀寫阻塞信號(hào)量讀寫阻塞信號(hào)量rblock，用來(lái)在寫者到來(lái)后阻塞讀者，其初值為，用來(lái)在寫者到來(lái)后阻塞讀者，其初值為1；寫阻塞信號(hào)量寫阻塞信號(hào)量wblock，當(dāng)有讀者被寫者阻塞時(shí)，阻塞其他新到來(lái)的讀者，當(dāng)有讀者被寫者阻塞時(shí)，阻塞其他新

24、到來(lái)的讀者，其初值為其初值為1； 寫共享變量寫共享變量writecountwritecount，用來(lái)記錄當(dāng)前寫進(jìn)程的數(shù)目，初值為，用來(lái)記錄當(dāng)前寫進(jìn)程的數(shù)目，初值為0 0；26讀者讀者-寫者問題（續(xù)寫者問題（續(xù)4）算法描述：（寫者優(yōu)先）算法描述：（寫者優(yōu)先）/讀者進(jìn)程讀者進(jìn)程 /寫者進(jìn)程寫者進(jìn)程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哲學(xué)家進(jìn)餐問題哲學(xué)家進(jìn)餐問題 問題描述：有問題描述：有5個(gè)哲學(xué)家，生活方式就是交替地進(jìn)行思個(gè)哲學(xué)家，生活方式

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

27、學(xué)家已經(jīng)停止思考，正在試圖取得身邊的兩根筷子；正在試圖取得身邊的兩根筷子； EATING：就餐狀態(tài)，處于該狀態(tài)的哲學(xué)家取得身邊的兩根：就餐狀態(tài)，處于該狀態(tài)的哲學(xué)家取得身邊的兩根筷子，正在就餐；筷子，正在就餐； 設(shè)定哲學(xué)家編號(hào)依次為設(shè)定哲學(xué)家編號(hào)依次為0到到4，數(shù)組，數(shù)組State表明哲學(xué)家所表明哲學(xué)家所處狀態(tài)；處狀態(tài)； 定義信號(hào)量數(shù)組定義信號(hào)量數(shù)組s，對(duì)應(yīng)每個(gè)哲學(xué)家，初值為，對(duì)應(yīng)每個(gè)哲學(xué)家，初值為0，在哲學(xué)，在哲學(xué)家得不到筷子時(shí)阻塞。定義信號(hào)量家得不到筷子時(shí)阻塞。定義信號(hào)量mutex，初值為，初值為1；28哲學(xué)家進(jìn)餐問題（續(xù)）哲學(xué)家進(jìn)餐問題（續(xù)）算法描述：算法描述：/哲學(xué)家進(jìn)程哲學(xué)家進(jìn)程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ā)椅上睡覺。一個(gè)顧客到來(lái)時(shí)，必須叫醒理發(fā)師，如理發(fā)椅上睡覺。一個(gè)顧客到來(lái)時(shí)，必須叫醒理發(fā)師，如果理發(fā)師正在理發(fā)而且有空椅子可坐，就坐下來(lái)等待，果理發(fā)師正在理發(fā)而且有空椅子可坐，就坐下來(lái)等待，否則就離開；否則就離開； 設(shè)置變量設(shè)置變量wa

30、iting表示等待理發(fā)的顧客的數(shù)量，初值為表示等待理發(fā)的顧客的數(shù)量，初值為0。定義定義3個(gè)信號(hào)量：個(gè)信號(hào)量： customers：正待等待的顧客的數(shù)量，數(shù)值上與：正待等待的顧客的數(shù)量，數(shù)值上與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使用信號(hào)的管程使用信號(hào)的管程Brinch Hansen和和Hoare提出，高級(jí)同步機(jī)制，管程提出，高級(jí)同步機(jī)制，管程Monitor；基本思想：利用數(shù)據(jù)抽象地表示系統(tǒng)中的共享資源，而把對(duì)該數(shù)據(jù)基本思想：利用數(shù)據(jù)抽象地表示系統(tǒng)中的共享資源，而把對(duì)該數(shù)據(jù)實(shí)施的操作定義為一組過(guò)程。代表共享資

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

33、程；對(duì)數(shù)據(jù)進(jìn)行操作的一組過(guò)程；對(duì)局部于管程內(nèi)部的共享數(shù)據(jù)賦初值的語(yǔ)句；對(duì)局部于管程內(nèi)部的共享數(shù)據(jù)賦初值的語(yǔ)句；32使用信號(hào)的管程（續(xù)）使用信號(hào)的管程（續(xù)）進(jìn)程要想進(jìn)入管程，必須調(diào)用管程中的過(guò)程；面向?qū)ο笾袑?duì)象的特進(jìn)程要想進(jìn)入管程，必須調(diào)用管程中的過(guò)程；面向?qū)ο笾袑?duì)象的特點(diǎn)；點(diǎn)；管程的過(guò)程體可以有局部數(shù)據(jù)；過(guò)程有兩種：由管程的過(guò)程體可以有局部數(shù)據(jù)；過(guò)程有兩種：由define定義的過(guò)程定義的過(guò)程可以被其他模塊引用，而未定義的則僅在管程內(nèi)部使用；管程要引可以被其他模塊引用，而未定義的則僅在管程內(nèi)部使用；管程要引用模塊外定義的過(guò)程，則必須用用模塊外定義的過(guò)程，則必須用use說(shuō)明；說(shuō)明；編譯器采用與其他

34、過(guò)程調(diào)用不同的方法來(lái)處理對(duì)管程的調(diào)用；典型編譯器采用與其他過(guò)程調(diào)用不同的方法來(lái)處理對(duì)管程的調(diào)用；典型處理方法：當(dāng)一個(gè)進(jìn)程調(diào)用管程過(guò)程時(shí)，該過(guò)程的前幾條指令將檢處理方法：當(dāng)一個(gè)進(jìn)程調(diào)用管程過(guò)程時(shí)，該過(guò)程的前幾條指令將檢查在管程中是否有其他活躍進(jìn)程；查在管程中是否有其他活躍進(jìn)程；進(jìn)入管程時(shí)的互斥由編譯器負(fù)責(zé)，使用二值型信號(hào)量；進(jìn)入管程時(shí)的互斥由編譯器負(fù)責(zé)，使用二值型信號(hào)量；條件變量和操作原語(yǔ)：條件變量和操作原語(yǔ)：wait，signal；生產(chǎn)者生產(chǎn)者-消費(fèi)者問題使用管程的一種解決方案（消費(fèi)者問題使用管程的一種解決方案（P96）；）；自動(dòng)實(shí)現(xiàn)對(duì)臨界區(qū)的互斥，比信號(hào)量更容易保證程序的正確性；自動(dòng)實(shí)現(xiàn)對(duì)臨

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

51、申請(qǐng)，即在此次檢查中是否被滿足，初始值表示當(dāng)前未滿足進(jìn)程申請(qǐng)，即Finishi=false；當(dāng)有足夠資源分配給進(jìn)程（；當(dāng)有足夠資源分配給進(jìn)程（Need =Free）時(shí)，）時(shí)，F(xiàn)inishi=true，P 完成并釋放資源；完成并釋放資源；從進(jìn)程集合中找一個(gè)能滿足下述條件的進(jìn)程從進(jìn)程集合中找一個(gè)能滿足下述條件的進(jìn)程P ; Finishi=false，表示資源未分配給進(jìn)程；，表示資源未分配給進(jìn)程； Need =Free，表示資源夠分配給進(jìn)程；，表示資源夠分配給進(jìn)程；當(dāng)當(dāng)P 獲得資源后，認(rèn)為獲得資源后，認(rèn)為P 完成，釋放資源；完成，釋放資源；Free := Free + Allocation;Fini

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

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

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

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

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