操作系統(tǒng)原理第4章進程同步與死鎖內(nèi)容摘要進程同步和互斥，臨界資源及臨界區(qū)的概念實現(xiàn)進程互斥的方法信號量機制與P、V操作一些經(jīng)典的進程同步問題利用管程實現(xiàn)進程同步進程的死鎖及處理機制Linux系統(tǒng)的進程同步及死鎖2進程同步的基本概念并發(fā)性操作系統(tǒng)基本特征，改善系統(tǒng)資源的利用率，提高系統(tǒng)的吞吐量

指一組進程執(zhí)行在時間點上相互交替，在時間段上重疊與時間有關(guān)的錯誤多進程并發(fā)情況下，進程共享某些變量或硬件資源，進程的執(zhí)行具有不確定性，如果不對進程的執(zhí)行加以制約，執(zhí)行結(jié)果是錯誤的3進程同步的基本概念（續(xù)1）進程的同步指當(dāng)進程運行到某一點時，若其他進程已完成某種操作，使進程滿足了繼續(xù)運行的條件，進程才能夠繼續(xù)運行，否則必須停下來等待

相互協(xié)作的進程間經(jīng)常存在數(shù)據(jù)或變量等共享資源，進程受到特定條件的限制，各進程需要嚴(yán)格按照固定的順序執(zhí)行，否則將導(dǎo)致程序的執(zhí)行錯誤進程的互斥互斥共享資源是指在某段時間內(nèi)，只能有一個進程對該資源進行訪問，其他進程若想訪問該資源則必須停下來等待，直到該共享資源被前一進程釋放4進程同步的基本概念（續(xù)2）臨界資源只允許一個進程訪問的共享資源物理設(shè)備：打印機、繪圖儀變量、數(shù)據(jù)、文件、內(nèi)存區(qū)臨界區(qū)程序中對臨界資源訪問的代碼臨界資源程序：入口區(qū)、臨界區(qū)、退出區(qū)、其余代碼區(qū)

臨界區(qū)訪問準(zhǔn)則：空閑讓進忙則等待有限等待讓權(quán)等待5互斥實現(xiàn)方法-硬件方法管理臨界區(qū)入口標(biāo)志兩個操作查看標(biāo)志以判斷臨界資源是否已被占用；修改標(biāo)志阻止其他進程進入臨界區(qū)；并發(fā)進程交錯執(zhí)行時，可能會出現(xiàn)進程只執(zhí)行一個操作就被另一個進程打斷的情況，從而造成臨界資源訪問發(fā)生錯誤；主要思想用一條指令來完成標(biāo)志的檢查和修改兩個操作，保證兩個操作不被打斷；通過禁止中斷的方式來保證檢查和修改作為一個整體來執(zhí)行；6互斥實現(xiàn)方法-硬件方法（續(xù)1）禁止中斷進程使用禁止中斷的方法構(gòu)成臨界區(qū)的入口區(qū)，使用打開中斷的方法構(gòu)成臨界區(qū)退出區(qū)

不足：如果臨界區(qū)訪問時間過長，關(guān)中斷時間過長，限制處理器交叉執(zhí)行程序的能力，影響系統(tǒng)效率；將關(guān)中斷的權(quán)利交給用戶進程，可能會引起計算機響應(yīng)不及時，使重要的中斷程序不能及時處理；在多處理器系統(tǒng)，通過關(guān)中斷阻止進程在臨界區(qū)執(zhí)行不被中斷沒有意義；7互斥實現(xiàn)方法-硬件方法（續(xù)2）專用機器指令：專門硬件指令，用一條指令完成檢查和改寫兩個操作TS（Test-and-Set）指令：檢查指定標(biāo)志后把該標(biāo)志置位 TS(key) while(!TS(key)); { 臨界區(qū)； if(key==1) key=0； return0; else{ key=1; return1; } }8互斥實現(xiàn)方法-硬件方法（續(xù)3）專用機器指令：專門硬件指令，用一條指令完成檢查和改寫兩個操作Swap指令：交換兩個字節(jié)的內(nèi)容Swap(a,b) x=1;{ while(x!=0) temp=a; swap(&key,&x); a=b; 臨界區(qū)； b=temp; key=0;}9互斥實現(xiàn)方法-硬件方法（續(xù)4）優(yōu)點：適用范圍廣，可用于多個并發(fā)進程及單處理器或多處理器環(huán)境；方法簡單，只需要硬件指令即可實現(xiàn)；支持多個臨界區(qū)，可為每個臨界區(qū)設(shè)置單獨標(biāo)志，在支持的臨界區(qū)的個數(shù)上沒有限制；缺點：易出現(xiàn)忙等待，在進程無法進入臨界區(qū)時會對標(biāo)志進行循環(huán)測試，耗費大量處理器資源；可能產(chǎn)生進程饑餓現(xiàn)象，某個進程釋放臨界資源后，下一個進入臨界區(qū)的進程不確定，從而可能會產(chǎn)生有的進程長期無法進入臨界區(qū)的情況；10互斥實現(xiàn)方法-軟件方法20世紀(jì)60年代開始利用軟件方法解決臨界區(qū)互斥訪問問題研究；方法主要基于內(nèi)存級別的訪問互斥，通過內(nèi)存中的標(biāo)志位實現(xiàn)并發(fā)進程對臨界資源的順序訪問；算法1：利用共享的標(biāo)志位來表示哪個并發(fā)進程可以進入臨界區(qū)：設(shè)置標(biāo)志變量，變量為0允許進程A進入，變量為1允許進程B進入； intturn=0;

進程A:

進程B: while(turn!=0); while(turn!=1); 臨界區(qū); 臨界區(qū); turn=1; turn=0;違反“空閑讓進”原則11互斥實現(xiàn)方法-軟件方法（續(xù)）算法2：利用雙標(biāo)志法判斷進程是否進入臨界區(qū)：使用數(shù)組表示進程是否希望進入臨界區(qū)，真正進入臨界區(qū)之前先查看一下對方標(biāo)志，如果對方正在進入臨界區(qū)則進行等待，還需要通過一個變量避免兩個進程都無法進入臨界區(qū) intflag[2]={0,0};

進程A:

進程B: flag[0]=1; flag[1]=1; turn=1; turn=0; while(flag[1]&&turn==1); while(flag[0]&&turn==0); 臨界區(qū); 臨界區(qū); flag[0]=0; flag[1]=0;12信號量荷蘭科學(xué)家Dijkstra在1965年提出，進程同步機制；概念上類似交通信號燈，通過信號量的狀態(tài)來決定并發(fā)進程對臨界資源的訪問順序；多進程間傳遞簡單信號，使進程在某位置阻塞，直到收到特定信號后繼續(xù)運行，達(dá)到多進程相互協(xié)作的目的；包含“檢測”和“歸還”兩個操作：檢測操作稱為P操作，查看是否可訪問臨界資源，若檢測通過，則開始訪問臨界資源，若檢測不通過，則進行等待，直到臨界資源被歸還后才能進入臨界區(qū)訪問；歸還操作稱為V操作，通知等待進程臨界資源已經(jīng)被釋放；P操作與V操作都是原子操作，每個步驟不可分割，“要么都做，要么都不做”；13信號量（續(xù)）實現(xiàn)進程互斥訪問臨界資源的模型：

進程1：

進程2： 進程3： P(mutex); P(mutex); P(mutex); 臨界區(qū); 臨界區(qū); 臨界區(qū); V(mutex); V(mutex); V(mutex);實現(xiàn)進程間同步的模型： 進程1： 進程2： 讀入數(shù)據(jù); P(mutex); V(mutex); 處理數(shù)據(jù);14整型信號量機制最簡單的一種信號量，通常是一個需要初始化值的正整型量；操作原語如下： P操作： V操作： P(x) V(x) { { while(x<=0); x=x+1; x=x-1; } }15記錄型信號量機制整型信號量在P操作不成功時需要進行循環(huán)等待，沒有放棄CPU資源，違背讓權(quán)等待原則，造成系統(tǒng)資源浪費；記錄型信號量在整型信號量基礎(chǔ)上進行改進，包含整型值外，還包含一個阻塞隊列；操作原語如下： P操作： V操作： P(x) V(x) { { x.value=x.value-1; x.value=x.value+1; if(x.value<0) if(x.value<=0) block(x.queue); wakeup(x.queue); } }16AND型信號量機制并發(fā)進程訪問多個臨界資源時，需要多次使用P、V操作，容易由于操作位置放置不當(dāng)而造成進程死鎖；

進程1： 進程2： P(x) ; P(y); P(y); P(x); 臨界區(qū); 臨界區(qū); V(y); V(x); V(x); V(y);17AND型信號量機制（續(xù)1）AND型信號量對進程所需的多個臨界資源進行批量獲取和批量釋放； SP(x1,x2,...,xn) { if(x1>=0&&x2>=0&&...xn>=0) { for(i=0;i<n;++i) xi=xi-1; } else { 在隊列中阻塞; } }18AND型信號量機制（續(xù)2） SV(x1,x2,...,xn) { for(i=0;i<n;++i) { xi=xi+1; 喚醒隊列中進程; } }19生產(chǎn)者-消費者問題最著名進程同步問題，一組生產(chǎn)者進程向一組消費者進程提供產(chǎn)品，共享一個環(huán)形緩沖池；緩沖池每個緩沖區(qū)存放一個產(chǎn)品，生產(chǎn)者進程不斷生產(chǎn)產(chǎn)品并放入緩沖池，消費者進程不斷從緩沖池取出產(chǎn)品并消費；進程滿足同步條件：任一時刻所有生產(chǎn)者存放產(chǎn)品的單元數(shù)不能超過緩沖池的總?cè)萘縉；所有消費者取出產(chǎn)品的總量不能超過所有生產(chǎn)者當(dāng)前生產(chǎn)產(chǎn)品的總量；20生產(chǎn)者-消費者問題（續(xù)1）同步關(guān)系：當(dāng)緩沖池滿時生產(chǎn)者進程需等待；當(dāng)緩沖池空時消費者進程需等待；各個進程應(yīng)互斥使用緩沖池；使用信號量解決問題。假設(shè)緩沖區(qū)編號0~（N-1），用in和out作為生產(chǎn)者和消費者進程使用的指針，指向可用的緩沖區(qū)，初值都是0。設(shè)置3個信號量：full，表示放有產(chǎn)品的緩沖區(qū)數(shù)，初值為0；empty，表示可供使用的緩沖區(qū)數(shù)，初值為N；mutex，互斥信號量，初值為1，使各進程互斥進入臨界區(qū)，保證任何時候只有一個進程使用緩沖區(qū)；21生產(chǎn)者-消費者問題（續(xù)2）算法描述：//生產(chǎn)者進程

//消費者進程while(1){while(1){P(empty);P(full);P(mutex);P(mutex);產(chǎn)品送往buffer(in);從buffer(out)取出產(chǎn)品;in=(in+1)%N;out=(out+1)%N;V(mutex);V(mutex);V(full);V(empty);}}生產(chǎn)者進程利用信號量empty保證在具有空閑的緩沖區(qū)時才將產(chǎn)品放入緩沖池，消費者進程利用信號量full保證只有在緩沖區(qū)存在產(chǎn)品時才會取出，信號量mutex保證生產(chǎn)者及消費者進程對緩沖池的互斥訪問。22讀者-寫者問題一個數(shù)據(jù)對象（如文件或記錄）可以被多個并發(fā)進程共享，有些進程只要求讀取數(shù)據(jù)對象的內(nèi)容，另一些進程則要求修改數(shù)據(jù)對象的內(nèi)容；允許多個讀進程同時訪問數(shù)據(jù)對象，但寫進程不能與其他進程同時訪問數(shù)據(jù)對象；舉例，大型數(shù)據(jù)庫系統(tǒng)；根據(jù)寫者到來后是否仍允許新讀者進入分類：讀者優(yōu)先：當(dāng)寫者提出存取共享對象的需求后，仍允許新讀者進入；寫者優(yōu)先：當(dāng)寫者提出存取共享對象的需求后，不允許新讀者進入；23讀者-寫者問題（續(xù)1）使用信號量解決問題。需要設(shè)置兩個信號量和一個共享變量：讀互斥信號量rmutex，用于使讀進程互斥訪問共享變量readcount，其初值為1；讀寫互斥信號量mutex，用于實現(xiàn)寫進程與讀進程的互斥以及寫進程與寫進程的互斥，其初值為1；讀共享變量readcount，用于記錄當(dāng)前的讀進程數(shù)目，初值為0；24讀者-寫者問題（續(xù)2）算法描述：（讀者優(yōu)先）//讀者進程

//寫者進程while(1){while(1){P(rmutex);P(mutex);readcount=readcount+1;執(zhí)行寫操作;if(readcount==1)V(mutex);P(mutex);}V(rmutex);執(zhí)行讀操作;P(rmutex);readcount=readcount-1;if(readcount==0)V(mutex);V(rmutex);使用讀取的數(shù)據(jù);}25讀者-寫者問題（續(xù)3）上述算法基礎(chǔ)上，增加3個信號量和一個共享變量解決寫者優(yōu)先的讀者-寫者問題：寫互斥信號量wmutex，用于使寫進程互斥訪問共享變量writecount，其初值為1；讀寫阻塞信號量rblock，用來在寫者到來后阻塞讀者，其初值為1；寫阻塞信號量wblock，當(dāng)有讀者被寫者阻塞時，阻塞其他新到來的讀者，其初值為1；寫共享變量writecount，用來記錄當(dāng)前寫進程的數(shù)目，初值為0；26讀者-寫者問題（續(xù)4）算法描述：（寫者優(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)V(wmutex);P(mutex);P(mutex);V(rmutex);執(zhí)行寫操作;V(rblock);V(mutex);V(wblock);P(wmutex);執(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é)家進餐問題問題描述：有5個哲學(xué)家，生活方式就是交替地進行思考和進餐，公用一張圓桌，分別坐在周圍的5張椅子上，在圓桌上有5個碗和5支筷子，平時哲學(xué)家進行思考，饑餓時便試圖取其左右最靠近他的筷子，只有在拿到兩支筷子時才能進餐，進餐完畢，放下筷子又繼續(xù)思考；3種狀態(tài)：THINKING：思考狀態(tài)，處于該狀態(tài)的哲學(xué)家正在思考；HUNGRY：饑餓狀態(tài)，處于該狀態(tài)的哲學(xué)家已經(jīng)停止思考，正在試圖取得身邊的兩根筷子；EATING：就餐狀態(tài)，處于該狀態(tài)的哲學(xué)家取得身邊的兩根筷子，正在就餐；設(shè)定哲學(xué)家編號依次為0到4，數(shù)組State表明哲學(xué)家所處狀態(tài)；定義信號量數(shù)組s，對應(yīng)每個哲學(xué)家，初值為0，在哲學(xué)家得不到筷子時阻塞。定義信號量mutex，初值為1；28哲學(xué)家進餐問題（續(xù)）算法描述：//哲學(xué)家進程i

voidphilosopher(inti)voidtest(inti){{while(1){if(state[i]==HUNGRY&&思考問題;state[LEFT(i)]!=EATING&&take_chopstick(i);state[RIGHT(i)]!=EATING)就餐;{put_chopstick(i);state[i]=EATING;}V(s[i]);}}}voidtake_chopstick(inti)voidput_chopstick(inti){{P(mutex);P(mutex);state[i]=HUNGRY;state[i]=THINKING;test(i);test(LEFT(i));V(mutex);test(RIGHT(i));P(s[i]);V(mutex);}}29打瞌睡理發(fā)師問題問題描述：理發(fā)店有一位理發(fā)師、一把理發(fā)椅和5把供等候理發(fā)的顧客坐的座椅，如果沒有顧客，理發(fā)師便在理發(fā)椅上睡覺。一個顧客到來時，必須叫醒理發(fā)師，如果理發(fā)師正在理發(fā)而且有空椅子可坐，就坐下來等待，否則就離開；設(shè)置變量waiting表示等待理發(fā)的顧客的數(shù)量，初值為0。定義3個信號量：customers：正待等待的顧客的數(shù)量，數(shù)值上與waiting相同，初值為0；barbers：理發(fā)師的狀態(tài)，初值為1；mutex：用于互斥訪問變量waiting，初值為1；30打瞌睡理發(fā)師問題（續(xù)）算法描述：#defineCHAIRS5voidbarber(void)voidcustomer(void){{while(1){P(mutex);P(customers);if(waiting<CHAIRS){P(mutex);waiting++;waiting--;V(customers);V(barbers);V(mutex);V(mutex);P(barbers);給顧客理發(fā);理發(fā);}}else}V(mutex);離開;}31使用信號的管程BrinchHansen和Hoare提出，高級同步機制，管程Monitor；基本思想：利用數(shù)據(jù)抽象地表示系統(tǒng)中的共享資源，而把對該數(shù)據(jù)實施的操作定義為一組過程。代表共享資源的數(shù)據(jù)，以及由對該共享資源實施操作的一組過程所組成的資源管理程序，共同構(gòu)成了一個操作系統(tǒng)的資源管理模塊-管程；Hansen定義：一個管程定義了一個數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進程在其上執(zhí)行的一組操作，這組操作能使進程同步和改變管程中的數(shù)據(jù)；四部分組成：管程名稱；局部于管程的數(shù)據(jù)的說明；對數(shù)據(jù)進行操作的一組過程；對局部于管程內(nèi)部的共享數(shù)據(jù)賦初值的語句；32使用信號的管程（續(xù)）進程要想進入管程，必須調(diào)用管程中的過程；面向?qū)ο笾袑ο蟮奶攸c；管程的過程體可以有局部數(shù)據(jù)；過程有兩種：由define定義的過程可以被其他模塊引用，而未定義的則僅在管程內(nèi)部使用；管程要引用模塊外定義的過程，則必須用use說明；編譯器采用與其他過程調(diào)用不同的方法來處理對管程的調(diào)用；典型處理方法：當(dāng)一個進程調(diào)用管程過程時，該過程的前幾條指令將檢查在管程中是否有其他活躍進程；進入管程時的互斥由編譯器負(fù)責(zé)，使用二值型信號量；條件變量和操作原語：wait，signal；生產(chǎn)者-消費者問題使用管程的一種解決方案（P96）；自動實現(xiàn)對臨界區(qū)的互斥，比信號量更容易保證程序的正確性；缺點：程序設(shè)計語言概念，編譯器必須識別管程并用某種方式實現(xiàn)互斥；33使用通知和廣播的管程Lampson和Redell開發(fā)另一種管程方案，解決singal處理問題，并支持許多有用擴展；singal原語被notify取代；notify含義：當(dāng)一個正在管程中的進程執(zhí)行notify（x）時，x條件隊列得到通知，但發(fā)信號的進程繼續(xù)執(zhí)行；通知的結(jié)果使得位于條件隊列頭的進程在將來方便時、當(dāng)處理器可用時被恢復(fù)；不能保證之前沒有其他進程進入管程，等待進程必須重新檢查條件；增加broadcast廣播原語，使所有在該條件上等待的進程都被置于就緒狀態(tài)；當(dāng)不知道有多少別的進程將被激活時或難以準(zhǔn)確斷定將激活哪個進程時，可使用廣播；使用通知和廣播的管程有助于程序結(jié)構(gòu)中采用更模塊化的方法；34死鎖的概念現(xiàn)實生活現(xiàn)象：兩人過獨木橋；進程死鎖問題描述：資源R1和R2是獨占性資源，進程A占有資源R1，進程B占有資源R2，進程A等待占有資源R2，進程等待占有資源R1；結(jié)果兩個進程都處于阻塞狀態(tài)，若不采取其他措施，這種循環(huán)等待狀況無限期持續(xù)。信號量是共享資源，如果P、V操作使用不當(dāng)，也會產(chǎn)生死鎖；系統(tǒng)中資源分配不當(dāng)也可引起死鎖；死鎖：多個進程循環(huán)等待他方占有的獨占性資源而無限期地僵持下去的局面。如果沒有外力作用，那么死鎖涉及的各個進程都將永遠(yuǎn)處于阻塞狀態(tài)；35死鎖的概念（續(xù)）同時具備如下4個必要條件時，發(fā)生死鎖：互斥條件：每個資源每次只能分配給一個進程使用，某個進程一旦獲得資源，就不準(zhǔn)其他進程使用；部分分配（占有且等待）條件：進程由于申請不到所需要的資源而等待時，仍然占據(jù)著已經(jīng)分配到的資源；不可搶占（非剝奪）條件：任一個進程不能從另一個進程那里搶占資源，即已被占有的資源，只能由占用進程自己來釋放；循環(huán)等待條件：存在一個循環(huán)的等待序列，從而形成一個進程循環(huán)等待環(huán)；資源分配圖示例（P99）；36死鎖的處理策略產(chǎn)生死鎖的因素：系統(tǒng)擁有的資源數(shù)量、資源分配策略、進程對資源的使用要求、并發(fā)進程的速率；策略：預(yù)防死鎖：通過破壞4個必要條件之一，可以使系統(tǒng)不具備產(chǎn)生死鎖的條件；避免死鎖：在為申請者分配資源前先測試系統(tǒng)狀態(tài)，若把資源分配給申請者會產(chǎn)生死鎖，拒絕分配，否則接受申請，為它分配資源；檢測死鎖并恢復(fù)：允許系統(tǒng)出現(xiàn)死鎖，在死鎖發(fā)生后，通過一定方法加以恢復(fù)，并盡可能地減少損失；忽略死鎖：任憑死鎖的出現(xiàn)；當(dāng)系統(tǒng)中出現(xiàn)死鎖時，將系統(tǒng)重新啟動；37死鎖的預(yù)防死鎖預(yù)防是排除死鎖的靜態(tài)策略，對進程申請資源的活動加以限制，從而使產(chǎn)生死鎖的4個必要條件不能同時具備，以保證死鎖不會發(fā)生；策略：破壞互斥條件：由于資源獨占特征引起；一般來說，不采用該方法；破壞部分分配（占有而且等待）條件：采用預(yù)分配策略，進程執(zhí)行前申請，靜態(tài)分配，申請資源系統(tǒng)調(diào)用先于其他系統(tǒng)調(diào)用；僅當(dāng)進程沒有占用資源時才允許它去申請資源，已經(jīng)占用再申請資源，應(yīng)先釋放所占資源；減低資源利用率，執(zhí)行前不知道所需全部資源；38死鎖的預(yù)防（續(xù)）策略：破壞不可搶占（非剝奪）條件：允許在一些情況下，搶占其他進程占有的資源；常用于資源狀態(tài)易于保留和恢復(fù)的環(huán)境，如CPU寄存器和內(nèi)存；破壞循環(huán)條件：實行資源按序（層次）分配策略，把全部資源事先分成多個層次，排上序號，然后依次序分配；先釋放大，再申請??；證明（P100）；資源利用率提高；進程使用資源次序和系統(tǒng)規(guī)定資源次序不同時，提高不明顯；系統(tǒng)中所有資源合理排序號是難事，增加系統(tǒng)開銷；39死鎖的避免動態(tài)策略，在為申請者分配資源前先測試系統(tǒng)裝他，若把資源分配給申請者會產(chǎn)生死鎖，拒絕分配，否則接受申請，為它分配資源；Dijkstra，1965年，經(jīng)典避免死鎖的算法-銀行家算法；模型基于一個小城鎮(zhèn)的銀行家，向一群客戶分別承諾了一定金額的貸款，而他知道不可能所有客戶同時都需要最大的貸款額。銀行家算法就是對每一個客戶的請求進行檢查，檢查如果滿足它是否會引起不安全狀態(tài)；如果是，則不滿足該請求；否，則滿足請求；系統(tǒng)安全，指系統(tǒng)中的所有進程能夠按照某一種次序分配資源，并且依次運行完畢，這種進程序列就是安全序列；如果存在這樣一個安全序列，則系統(tǒng)是安全的；如果系統(tǒng)不存在這個一個安全序列，則系統(tǒng)是不安全的；40死鎖的避免（續(xù)1）銀行家算法：系統(tǒng)給進程分配資源時，先檢查狀態(tài)是否安全，方法是看它是否有足夠的剩余資源滿足一個距最大需求最近的進程；如果有，那么分配資源給該進程，然后接著檢查下一個距最大需求最近的進程，如此反復(fù)下去。如果所有進程都能獲得所需資源，那么該狀態(tài)是安全的，最初的進程申請資源可以分配；數(shù)據(jù)結(jié)構(gòu)：向量Available[j]=k，表示類資源可用數(shù)量是k；矩陣Claim[i,j]=x，表示進程最大需求類資源x個；矩陣Allocation[i,j]=y，表示進程此時占有y個類資源；矩陣Need[i,j]=z，表示進程還總共需要z個類資源才能完成任務(wù)；Need[i,j]=Claim[i,j]-Allocation[i,j]；41死鎖的避免（續(xù)2）算法描述：設(shè)Request是進程P的申請向量，如果Request[j]=m，表示P這次申請m個r類資源；當(dāng)P發(fā)出申請后，系統(tǒng)按下述步驟進行檢查：if(Request<=Need)goto; elseerror("進程對資源的申請量大于它說明的最大值");if(Request<=Available)goto; elsewait();系統(tǒng)試探性地把資源分配給P（類似回溯算法），并根據(jù)分配修改下面數(shù)據(jù)結(jié)構(gòu)中的值： Available:=Available-Request; Allocation:=Allocation+Request; Need:=Need-Request;系統(tǒng)執(zhí)行安全性檢查，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)；若安全，才正式將資源分配給進程以完成此次分配；若不安全，試探性分配作廢，恢復(fù)原資源分配表，讓進程P等待；42死鎖的避免（續(xù)3）安全性檢查算法描述：設(shè)置兩個向量Free、Finish；向量Free表示系統(tǒng)可分配給進程的各類資源數(shù)組，含有元素個數(shù)等于資源數(shù)，執(zhí)行安全算法開始時，F(xiàn)ree:=Available；標(biāo)記向量Finish表示進程在此次檢查中是否被滿足，初始值表示當(dāng)前未滿足進程申請，即Finish[i]=false；當(dāng)有足夠資源分配給進程（Need<=Free）時，F(xiàn)inish[i]=true，P完成并釋放資源；從進程集合中找一個能滿足下述條件的進程P;Finish[i]==false，表示資源未分配給進程；Need<=Free，表示資源夠分配給進程；當(dāng)P獲得資源后，認(rèn)為P完成，釋放資源； Free:=Free+Allocation; Finish[i]：=true； gotostep1如此試探分配，若可以達(dá)到Finish[0,...,n]==true成立，則表示系統(tǒng)處于安全狀態(tài)；否則系統(tǒng)處于不安全狀態(tài)；4344資源進程AllocationClaimNeedAvailableR1R2R3R4R1R2R3R4R1R2R3R4R1R2R3R4P13011411111001020P2010002120112P3111042103100P4110111210020P5000021102110資源進程FreeNeedAllocationFree+AllocationFinishR1R2R3R4R1R2R3R4R1R2R3R4R1R2R3R4死鎖的檢測與恢復(fù)對資源的分配加以限制可以預(yù)防和避免死鎖的發(fā)生，但不利于各進程對系統(tǒng)資源的充分共享；死鎖檢測方法，對資源的分配不加以限制，系統(tǒng)周期性地運行一個“死鎖檢測”程序，判斷系統(tǒng)內(nèi)是否存在死鎖，若檢測到，則設(shè)法加以解除；檢測頻率取決于發(fā)生死鎖的可能性，申請資源時檢測可以使算法相對比較簡單，但頻繁的檢測消耗相當(dāng)多的系統(tǒng)資源；45死鎖的檢測與恢復(fù)（續(xù)1）檢測常見算法：使用Available向量、Allocation矩陣、Request矩陣；算法只調(diào)查尚待完成的各個進程所有可能的分配序列；初始化臨時向量Free:=Available；如果Allocation≠0(i=1,2,...,n)，則Finish[i]=false；否則Finish=true；算法描述：從進程集合中找一個能滿足下述條件的進程P；Finish[i]==false，表示資源未分配給進程；Request<=Free，表示資源夠分配給進程；當(dāng)P獲得資源后，認(rèn)為P完成，釋放資源；Free:=Free+Allocation;Finish[i]:=true;gotostep1;存在某些i，使得Finish[i]=false，則系統(tǒng)處于死鎖狀態(tài)，進程P處于死鎖之中；46死鎖的檢測與恢復(fù)（續(xù)2）按照檢測算法，序列{P1，P3，P2，P4}，對于所有i都有Finish[i]=true，因此，在T0時刻沒有死鎖；47資源進程AllocationRequestAvailableR1R2R3R1