第3章_進(jìn)程調(diào)度(免費(fèi)閱讀)課件

1、第3章 處理機(jī)調(diào)度與死鎖 調(diào)度目的：處理機(jī)調(diào)度的工作是對(duì)CPU資源進(jìn)行合理的分配使用，以提高處理機(jī)利用率，并使各用戶公平地得到處理機(jī)資源。3.1 處理機(jī)調(diào)度基本概念3.1.1 調(diào)度類型 1）低級(jí)（短期）調(diào)度：確定選擇哪個(gè)就緒的進(jìn)程占有CPU，所以也稱為處理機(jī)調(diào)度，進(jìn)程調(diào)度2）高級(jí)（長期、作業(yè)）調(diào)度：確定哪些作業(yè)從外存調(diào)入內(nèi)存作業(yè)：（用戶）利用計(jì)算機(jī)進(jìn)行一次運(yùn)行所需工作的集合（比如，編輯、編譯，運(yùn)行等）。要執(zhí)行一個(gè)程序，用戶必須先提交一個(gè)作業(yè)。通過批輸入設(shè)備（卡片、紙帶、磁帶）批處理作業(yè)。通過終端啟動(dòng)的作業(yè)交互式作業(yè)。提交作業(yè)方式 ： 注： 用戶進(jìn)程在運(yùn)行過程中，也可能會(huì)產(chǎn)生由系統(tǒng)管理的后臺(tái)作業(yè)

2、，比如打印作業(yè)。這些作業(yè)在條件滿足時(shí)，由系統(tǒng)調(diào)度執(zhí)行。3）中級(jí)（中期）調(diào)度：為提高效率，加快進(jìn)程運(yùn)行，調(diào)節(jié)系統(tǒng)的負(fù)荷，有時(shí)需要在選擇內(nèi)存中阻塞或就緒的進(jìn)程暫時(shí)放到外存（一般是硬盤），即所謂的掛起。這種內(nèi)外存的數(shù)據(jù)交換稱為對(duì)換。中級(jí)調(diào)度解決：在阻塞或就緒的進(jìn)程中選擇哪個(gè)（些）進(jìn)程掛起在條件允許下，在外存掛起的進(jìn)程集合中如何選進(jìn)程激活并調(diào)回內(nèi)存外存對(duì)換作業(yè)輸入 spooling輸入程序 spooling 作業(yè)調(diào)度就緒阻塞就緒運(yùn)行完成阻塞后備作業(yè)輸出4）三種調(diào)度之間的關(guān)系如圖低級(jí)調(diào)度中級(jí)調(diào)度3.1.2 調(diào)度隊(duì)列模型 一、僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型 特點(diǎn)：單就緒、單阻塞隊(duì)列就隊(duì)列緒CPU進(jìn)程調(diào)度進(jìn)程完

3、成時(shí)間片完阻隊(duì)列塞交互用戶等待事件事件出現(xiàn)二、具有高級(jí)和低級(jí)的調(diào)度隊(duì)列模型特點(diǎn) ：1)具有進(jìn)程調(diào)度、作業(yè)調(diào)度 2)根據(jù)阻塞原因設(shè)置了多個(gè)阻塞隊(duì)列后隊(duì)列備1阻隊(duì)列塞作業(yè)調(diào)度就隊(duì)列緒CPU進(jìn)程調(diào)度進(jìn)程完成時(shí)間片完等待事件1事件1出現(xiàn)2阻隊(duì)列塞n阻隊(duì)列塞等待事件2等待事件n事件2出現(xiàn)事件n出現(xiàn)三、同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型作業(yè)調(diào)度就隊(duì)列緒CPU進(jìn)程調(diào)度進(jìn)程完成時(shí)間片完事件出現(xiàn)阻塞列、起隊(duì)掛阻隊(duì)列塞等待事件就緒、掛起隊(duì)列事件出現(xiàn)掛起中級(jí)調(diào)度后隊(duì)列備交互型作業(yè)批量作業(yè)掛起選擇哪種模型應(yīng)根據(jù)系統(tǒng)的規(guī)模及目標(biāo)制定3.1.3 選擇調(diào)度方式和調(diào)度算法的若干標(biāo)準(zhǔn)1、調(diào)度目標(biāo)：1)公平確保每個(gè)進(jìn)程獲得合理的CP

4、U份額2)效率是百分之百地忙碌3)響應(yīng)時(shí)間使交互用戶的響應(yīng)時(shí)間盡可能短4)周轉(zhuǎn)時(shí)間使批處理用戶等待輸出的時(shí)間盡可能短5)吞吐量使每小時(shí)處理的作業(yè)數(shù)量多以上調(diào)度目標(biāo)有矛盾之處，不可能滿足所有情況，取決于系統(tǒng)設(shè)計(jì)目標(biāo)2、有關(guān)術(shù)語及衡量標(biāo)準(zhǔn)周轉(zhuǎn)時(shí)間T：批處理系統(tǒng)的一個(gè)重要指標(biāo)。指作業(yè)從提交到完成（得到結(jié)果）所經(jīng)歷的時(shí)間。 包括：1）在外存后備隊(duì)列中等待時(shí)間；2）CPU上執(zhí)行時(shí)間；3）就緒隊(duì)列和阻塞隊(duì)列中等待時(shí)間；4）結(jié)果輸出等待時(shí)間。周轉(zhuǎn)時(shí)間常用以下參數(shù)衡量 （原則上越小越好）平均周轉(zhuǎn)時(shí)間: 帶權(quán)周轉(zhuǎn)時(shí)間 ： 其中:Ti/Tsi為第i個(gè)作業(yè)的帶權(quán)周轉(zhuǎn)時(shí)間，Tsi系統(tǒng)為第i個(gè)作業(yè)提供的實(shí)際服務(wù)時(shí)間響應(yīng)

5、時(shí)間：分時(shí)系統(tǒng)的一個(gè)重要指標(biāo)。用戶輸入一個(gè)請(qǐng)求（如擊鍵）到系統(tǒng)給出首次響應(yīng)（如屏幕顯示）的時(shí)間。包括：1）從終端的鍵盤輸入的一個(gè)請(qǐng)求信息傳送到處理機(jī)的時(shí)間；2）處理機(jī)對(duì)請(qǐng)求的處理時(shí)間；3）處理結(jié)果送到終端顯示器的時(shí)間。吞吐量：批處理系統(tǒng)的一個(gè)重要指標(biāo)。單位時(shí)間內(nèi)所完成的作業(yè)數(shù)。處理機(jī)利用率：大中型主機(jī)多用戶系統(tǒng)的性能指標(biāo)，因?yàn)橄到y(tǒng)價(jià)格昂貴，所以非常重視其CPU利用率。PC一般不考慮這個(gè)指標(biāo)。各種設(shè)備的均衡利用：大中型主機(jī)多用戶系統(tǒng)性能指標(biāo)。如CPU繁忙的作業(yè)和I/O繁忙的作業(yè)搭配。對(duì)PC及實(shí)時(shí)系統(tǒng)該指標(biāo)并不重要。 3. 調(diào)度準(zhǔn)則面向用戶準(zhǔn)則周轉(zhuǎn)時(shí)間短；響應(yīng)時(shí)間快；截止時(shí)間保證；優(yōu)先權(quán)準(zhǔn)則面向系

6、統(tǒng)的準(zhǔn)則系統(tǒng)吞吐量處理機(jī)利用率各類資源的平衡利用3.2 調(diào)度算法 一、調(diào)度的時(shí)機(jī) 調(diào)度的時(shí)機(jī)是與調(diào)度方式有關(guān)，一般在以下情況下會(huì)發(fā)生進(jìn)程調(diào)度：（1）正在執(zhí)行的進(jìn)程正常結(jié)束或由于某種錯(cuò)誤而終止運(yùn)行；（2）執(zhí)行中的進(jìn)程提出I/O請(qǐng)求，在等待I/O完成前，進(jìn)程阻塞，轉(zhuǎn)進(jìn)程調(diào)度；（3）在分時(shí)系統(tǒng)中，按照時(shí)間片輪轉(zhuǎn)，分給進(jìn)程的時(shí)間片用完時(shí)； （4）按照優(yōu)先級(jí)調(diào)度，有更高優(yōu)先級(jí)進(jìn)程變?yōu)榫途w時(shí)；（5）在進(jìn)程通訊中，執(zhí)行中的進(jìn)程執(zhí)行了某種原語操作，如P操作、阻塞原語和喚醒原語時(shí)，都可能引起進(jìn)程調(diào)度。二、常用的調(diào)度方法1. 先來先服務(wù)（FCFS算法） 按照作業(yè)提交或進(jìn)程變?yōu)榫途w狀態(tài)的先后次序，分派CPU；當(dāng)前作

7、業(yè)或進(jìn)程占用CPU，直到執(zhí)行完或阻塞，才主動(dòng)地出讓CPU。特點(diǎn)：非常簡單，易于實(shí)現(xiàn)；但對(duì)短作業(yè)而言，帶權(quán)周轉(zhuǎn)時(shí)間可能太大。按FCFS原則的進(jìn)程調(diào)度進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A03B26C44D65E823913182037912121.001.172.252.406.000391318特點(diǎn)：比FCFS改善了平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間，縮短作業(yè)的等待時(shí)間，提高了系統(tǒng)的吞吐量；對(duì)長作業(yè)非常不利，可能長時(shí)間得不到執(zhí)行；難以準(zhǔn)確估計(jì)作業(yè)（進(jìn)程）的執(zhí)行時(shí)間，從而影響調(diào)度性能2.短作業(yè)（進(jìn)程）優(yōu)先 對(duì)執(zhí)行時(shí)間短的作業(yè)（進(jìn)程）優(yōu)先分派處理機(jī)。什么是短作業(yè)？以前沒有執(zhí)行過！

8、按什么標(biāo)準(zhǔn)：時(shí)間？程序長度？while(1);特點(diǎn)：比FCFS改善了平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間，縮短作業(yè)的等待時(shí)間，提高了系統(tǒng)的吞吐量；對(duì)長作業(yè)非常不利，可能長時(shí)間得不到執(zhí)行；難以準(zhǔn)確估計(jì)作業(yè)（進(jìn)程）的執(zhí)行時(shí)間，從而影響調(diào)度性能2.短作業(yè)（進(jìn)程）優(yōu)先 對(duì)執(zhí)行時(shí)間短的作業(yè)（進(jìn)程）優(yōu)先分派處理機(jī)。什么是短作業(yè)？ 由用戶自己利用作業(yè)控制語言說明程序預(yù)計(jì)執(zhí)行時(shí)間。按非搶占式SJF原則的進(jìn)程調(diào)度進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A03B26C44D65E82031115939152011361114316/311/414/53/2按搶占式SJF原則的進(jìn)程調(diào)度進(jìn)程名到達(dá)時(shí)間服務(wù)

9、時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A03B26C44D65E823. 時(shí)間片輪轉(zhuǎn) 主要用于低級(jí)調(diào)度，是一種最古老、最簡單、最公平且使用最廣泛的方法。 將系統(tǒng)中所有的就緒進(jìn)程按照FCFS原則，排成一個(gè)隊(duì)列。每次調(diào)度時(shí)將CPU分派給隊(duì)首進(jìn)程，讓其執(zhí)行一個(gè)時(shí)間片。在一個(gè)時(shí)間片結(jié)束時(shí)，發(fā)生時(shí)鐘中斷。調(diào)度程序據(jù)此暫停當(dāng)前進(jìn)程的執(zhí)行，將其送到就緒隊(duì)列的末尾。（進(jìn)程可以由于阻塞或已運(yùn)行結(jié)束，在未用完一個(gè)時(shí)間片時(shí)，主動(dòng)放棄CPU）。 主要問題：如何確定時(shí)間片的長短cpu效率=時(shí)間片長度/(時(shí)間片長度+調(diào)度切換時(shí)間) 對(duì)一個(gè)系統(tǒng)，調(diào)度切換時(shí)間可近似看成定數(shù)。我們可以調(diào)整時(shí)間片長度改變cpu效率。短：比如調(diào)

10、度時(shí)間需50ms,時(shí)間片50ms。效率=50%。 用戶的一次請(qǐng)求需要多個(gè)時(shí)間片才能處理完，切換次數(shù)增加。長：時(shí)間片到500ms，效率=99%。 若有10個(gè)進(jìn)程，這十個(gè)用戶若幾乎同時(shí)按下鍵盤，從第1個(gè)響應(yīng)到他再次輪到運(yùn)行要等 9*0.5=4.5秒遠(yuǎn)遠(yuǎn)超出能容忍的時(shí)間。 等待時(shí)間一般不要超出1秒，因此應(yīng)該有： (時(shí)間片長度+調(diào)度切換時(shí)間)*進(jìn)程數(shù)=1000ms所以：時(shí)間片長度=1000/進(jìn)程數(shù)-調(diào)度切換時(shí)間 1000/進(jìn)程數(shù) 對(duì)一個(gè)分時(shí)系統(tǒng)，聯(lián)機(jī)的用戶數(shù)是變化的。隨進(jìn)程數(shù)變化調(diào)整時(shí)間片長度是合理的。但由于進(jìn)程數(shù)的變化幾乎是連續(xù)不斷的，所以沒有必要隨著實(shí)時(shí)的變化，這樣系統(tǒng)開銷也大。折衷的辦法是：進(jìn)程

11、數(shù)在一個(gè)區(qū)間范圍內(nèi)用一個(gè)時(shí)間片，在另一個(gè)區(qū)間范圍內(nèi)，用另一個(gè)時(shí)間片。系統(tǒng)可以每間隔一段時(shí)間，檢測(cè)當(dāng)前進(jìn)程數(shù)，確定有無必要調(diào)整時(shí)間片長度。按時(shí)間片輪轉(zhuǎn)的進(jìn)程調(diào)度（時(shí)間片長為1）進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A03B26C44D65E824、優(yōu)先權(quán)調(diào)度 前者簡單，在實(shí)時(shí)性要求不高或時(shí)間片不很長時(shí)可考慮；后者適合于實(shí)時(shí)要求高的場(chǎng)合，但時(shí)刻要監(jiān)視有否更高優(yōu)先權(quán)的進(jìn)程產(chǎn)生。1）優(yōu)先權(quán)調(diào)度分為： 非搶占式：除系統(tǒng)一旦把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)城后，該進(jìn)程便一直執(zhí)行下去，直至完成；或者因發(fā)生某件事件使該進(jìn)程放棄處理機(jī)時(shí)，系統(tǒng)方可再將處理機(jī)重新分配給另一個(gè)優(yōu)先權(quán)最高的進(jìn)

12、程。 搶占方式：系統(tǒng)同樣是吧處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程，使之執(zhí)行。但在其執(zhí)行期間，只要有另外一個(gè)優(yōu)先權(quán)更高的進(jìn)程，進(jìn)程調(diào)度程序就立即停止當(dāng)前進(jìn)程的執(zhí)行，重新將處理機(jī)分配給新到的最高優(yōu)先權(quán)進(jìn)程。搶占方式在實(shí)際的操作系統(tǒng)設(shè)計(jì)中也會(huì)有細(xì)分：內(nèi)核部分可搶占：用戶態(tài)時(shí)可以隨時(shí)被搶占CPU，但當(dāng)進(jìn)程在核心態(tài)時(shí)則大部分時(shí)間都不可以搶用CPU，而只在某些時(shí)刻（稱為可搶占點(diǎn)，Preemption Point），可以搶用CPU。例： UNIX SVR 4。 內(nèi)核完全不可搶占：用戶態(tài)時(shí)可以隨時(shí)被搶占CPU，但當(dāng)進(jìn)程在核心態(tài)時(shí)，則完全不可以被搶用CPU。例：UNIX（SVR 3和4.3BSD UNIX及其以前的版本

13、）、WINDOWS NT。這些OS通常在系統(tǒng)調(diào)用或中斷處理時(shí)屏蔽大部分中斷，系統(tǒng)調(diào)用返回或中斷返回時(shí)再開放大部分中斷。 完全可搶占或內(nèi)核完全可搶占：無論處于用戶態(tài)還是核心態(tài)，都可以隨時(shí)被搶占CPU 。例：SUN公司的Solaris 、Windows 2000 / XP。實(shí)際上，Solaris和Windows 2000 / XP并不是100%完全可搶占，只是將內(nèi)核中不可搶占的代碼段盡量減少而已。任何OS都不可能是100%的完全可搶占的。2）優(yōu)先權(quán)的類型靜態(tài)優(yōu)先級(jí) 創(chuàng)建進(jìn)程時(shí)就確定，直到進(jìn)程終止前都不改變。通常是一個(gè)整數(shù)。 進(jìn)程類型（系統(tǒng)進(jìn)程優(yōu)先級(jí)較高） 依據(jù) 對(duì)資源的需求（對(duì)CPU和內(nèi)存需求較少

14、的進(jìn)程，優(yōu) 先級(jí)較高） 用戶要求（緊迫程度和付費(fèi)多少）動(dòng)態(tài)優(yōu)先級(jí) 創(chuàng)建進(jìn)程時(shí)賦予的優(yōu)先級(jí)，在進(jìn)程運(yùn)行過程中可以自動(dòng)改變，以便獲得更好的調(diào)度性能（UNIX中采用）。動(dòng)態(tài)優(yōu)先級(jí)的改變?cè)瓌t： A） 在就緒隊(duì)列中，等待時(shí)間延長則優(yōu)先級(jí)提高，從而使優(yōu)先級(jí)較低的進(jìn)程在等待足夠的時(shí)間后，其優(yōu)先級(jí)得到提高； B） 進(jìn)程每執(zhí)行一個(gè)時(shí)間片，就降低其優(yōu)先級(jí)，從而一個(gè)進(jìn)程持續(xù)執(zhí)行時(shí)，其優(yōu)先級(jí)降低到出讓CPU。5、高響應(yīng)比優(yōu)先調(diào)度響應(yīng)比：R = (等待時(shí)間 + 要求執(zhí)行時(shí)間) / 要求執(zhí)行時(shí)間是FCFS（先來先服務(wù)）和SJF的折衷：作業(yè)等待時(shí)間相同，服務(wù)時(shí)間越短，優(yōu)先權(quán)越高-SJF；要求服務(wù)時(shí)間相同，等待時(shí)間越長，優(yōu)先

15、權(quán)越高-FCFS；長作業(yè)隨著等待時(shí)間的增加，優(yōu)先權(quán)增加。 6、多級(jí)隊(duì)列調(diào)度 使用多個(gè)就緒隊(duì)列，各隊(duì)列的區(qū)別對(duì)待，達(dá)到綜合的調(diào)度目標(biāo)。 方法： 根據(jù)作業(yè)或進(jìn)程的性質(zhì)或類型的不同，將就緒隊(duì)列再分為若干個(gè)子隊(duì)列（如前、后臺(tái)進(jìn)程，系統(tǒng)、用戶進(jìn)程等）。 每個(gè)作業(yè)歸入一個(gè)隊(duì)列。不同隊(duì)列可有不同的優(yōu)先級(jí)、時(shí)間片長度、調(diào)度策略等；在運(yùn)行過程中還可改變進(jìn)程所在隊(duì)列。 7、多級(jí)反饋隊(duì)列調(diào)度 時(shí)間片輪轉(zhuǎn)和優(yōu)先級(jí)的綜合及發(fā)展。就緒隊(duì)列1S1至CPU就緒隊(duì)列2S2至CPU就緒隊(duì)列3S3至CPU就緒隊(duì)列nSn至CPU時(shí)間片：s1s2sn 多個(gè)就緒隊(duì)列，賦予不同的優(yōu)先級(jí)。隊(duì)列1的優(yōu)先級(jí)最高。每個(gè)隊(duì)列執(zhí)行時(shí)間片的長度也不同，

16、規(guī)定優(yōu)先級(jí)越低則時(shí)間片越長。 新進(jìn)程進(jìn)入內(nèi)存后，先投入隊(duì)列1的末尾，按FCFS算法調(diào)度；若一個(gè)時(shí)間片未完，投入到隊(duì)列2的末尾，同樣按FCFS算法調(diào)度；如此下去，降低到最后的隊(duì)列。 僅當(dāng)較高優(yōu)先級(jí)的隊(duì)列為空，才調(diào)度較低優(yōu)先級(jí)的隊(duì)列中的進(jìn)程執(zhí)行。如果進(jìn)程執(zhí)行時(shí)有新進(jìn)程進(jìn)入較高優(yōu)先級(jí)的隊(duì)列，則搶先執(zhí)行新進(jìn)程，并把被搶先的進(jìn)程投入原隊(duì)列的末尾。8、公平分享調(diào)度策略 1986年Bach提出：按進(jìn)程組（用戶）分配CPU。以前的做法，按進(jìn)程分配CPU： A用戶：1個(gè)進(jìn)程 B用戶：6個(gè)進(jìn)程 C用戶：3個(gè)進(jìn)程 ，10%的CPU分額 ，60%的CPU分額 ，30%的CPU分額現(xiàn)在 ：每個(gè)用戶都按1/3的比例分配C

17、PU A用戶的每個(gè)進(jìn)程，1/3的CPU分額 B用戶的每個(gè)進(jìn)程，1/18的CPU分額 C用戶的每個(gè)進(jìn)程，1/9的CPU分額 定義：假如在一個(gè)進(jìn)程集合中的每個(gè)進(jìn)程都在等待只能由該集合中的其它一個(gè)進(jìn)程才能引發(fā)的事件，這種狀態(tài)被看成死鎖。3.5 死鎖的原因和必要條件1、產(chǎn)生死鎖的原因 A）競爭不可剝奪資源 典型的打印機(jī)，磁帶機(jī)等。3.5.1 死鎖產(chǎn)生的原因p2rel(r1)p2rel(r2)p2req(r2)p2req(r1) p1req(r1) p1req(r2) p1rel (r1) p1rel (r2)死鎖區(qū)p1p2tt當(dāng)進(jìn)程推進(jìn)到死鎖區(qū)，進(jìn)程必死可通過增加資源來解決死鎖，比如有兩個(gè)r1和兩個(gè)r

18、2資源就不會(huì)發(fā)生死鎖,但現(xiàn)實(shí)中是不可取的。資源不夠一定死鎖嗎？ p1req(r1) p1req(r2) p1rel (r1) p1rel (r2)p1p2p2rel(r1)p2rel(r2)p2req(r2)p2req(r1)進(jìn)程沒有推進(jìn)到死鎖區(qū)，不會(huì)發(fā)生死鎖tt 定義：假如在一個(gè)進(jìn)程集合中的每個(gè)進(jìn)程都在等待只能由該集合中的其它一個(gè)進(jìn)程才能引發(fā)的事件，這種狀態(tài)被看成死鎖。產(chǎn)生死鎖的原因： A）競爭不可剝奪資源 典型的打印機(jī)，磁帶機(jī)等。B)進(jìn)程推進(jìn)順序不當(dāng)3.5.2 產(chǎn)生死鎖的必要條件 Coffman等人在1971年總結(jié)了4個(gè)死鎖的必要條件只有4個(gè)條件都滿足時(shí)，才會(huì)出現(xiàn)死鎖。(1)互斥：一個(gè)資源

19、要么分配給一個(gè)進(jìn)程，要么空閑； (2)請(qǐng)求和保持：進(jìn)程可請(qǐng)求其余資源，但不主動(dòng)釋放已 經(jīng)占用的資源（部分分配）(3)不剝奪：進(jìn)程已經(jīng)占用的資源，不會(huì)被強(qiáng)制剝奪(4)環(huán)路等待：系統(tǒng)一定有兩個(gè)或兩個(gè)以上的進(jìn)程組成的一條環(huán)路，該環(huán)路中的每個(gè)進(jìn)程都在等待相鄰進(jìn)程正占用的資源。3.5.3 死鎖的解決方法一、鴕鳥策略（置之不理） 解決死鎖的最簡單方法就是鴕鳥算法。即像鴕鳥一樣，當(dāng)遇到危險(xiǎn)時(shí)，將頭埋進(jìn)沙子里，假裝毫無問題。 當(dāng)死鎖在計(jì)算機(jī)中很少出現(xiàn)時(shí)，比如說每五年或更長時(shí)間才出現(xiàn)一次時(shí)，人們就不必花費(fèi)更多的精力去解決它，而是采用類似鴕鳥一樣的辦法忽略它。 以UNIX系統(tǒng)為例，它潛在地存在死鎖，但它并不花功夫

20、去檢測(cè)和解除死鎖，而是忽略不去理它。 如果死鎖不花什么代價(jià)就能解決，那么什么問題也沒有。但實(shí)際是代價(jià)很大，常會(huì)給進(jìn)程帶來很多不便的限制。所以，需要在方便性和正確性之間進(jìn)行折衷，要充分考慮哪一個(gè)更重要，對(duì)象是誰，一般很難發(fā)現(xiàn)一般性的解決辦法。二、預(yù)防死鎖 預(yù)防死鎖是一種簡單直觀的方法，通過預(yù)先設(shè)置某些限制條件，去破壞產(chǎn)生死鎖的四個(gè)必要條件之一或幾個(gè)條件，來預(yù)防死鎖的發(fā)生。由于施加的條件過于嚴(yán)格，會(huì)導(dǎo)致系統(tǒng)資源利用率和系統(tǒng)吞吐量降低。三、避免死鎖 避免死鎖指的是在資源動(dòng)態(tài)分配過程中，采用某種方法去防止系統(tǒng)進(jìn)入不安全的狀態(tài)，從而避免發(fā)生死鎖。需要事先加以較弱的限制條件。目的地危險(xiǎn)要想過去，必須保證在

21、通過的整個(gè)過程中肯定不會(huì)發(fā)生危險(xiǎn)！保守主義者！目的地危險(xiǎn)要想過去，那么小心一點(diǎn)，時(shí)刻探測(cè)下一步是不是會(huì)遇到危險(xiǎn)！積極者！目的地只要想過去，就過去，不管有沒有危險(xiǎn)，碰到危險(xiǎn)就完蛋！蠻干者！過？徹底完蛋！過！四、檢測(cè)死鎖 檢測(cè)死鎖的功能是利用系統(tǒng)所設(shè)置的檢測(cè)機(jī)制，及時(shí)的檢測(cè)出死鎖的發(fā)生，并精確地確定與死鎖有關(guān)的進(jìn)程和資源。五、解除死鎖 解除死鎖：當(dāng)檢測(cè)到系統(tǒng)已經(jīng)發(fā)生了死鎖時(shí)，必須將進(jìn)城從死鎖狀態(tài)中解脫出來。通常會(huì)犧牲部分系統(tǒng)利用率，甚至?xí)奚糠诌M(jìn)程。3.6 死鎖的預(yù)防 預(yù)防：是采用某種策略，限制并發(fā)進(jìn)程對(duì)資源的請(qǐng)求，使系統(tǒng)在任何時(shí)刻都不滿足死鎖的必要條件。 1）預(yù)先靜態(tài)分配： 預(yù)先分配所需全部所

22、需資源，這樣可保證不等待資源；降低了對(duì)資源的利用率（資源分配了可能不用）預(yù)先要知道所需資源；2）資源強(qiáng)制變?yōu)椤翱蓜儕Z”的 在申請(qǐng)資源得不到時(shí)，占用資源也釋放。實(shí)用中可行嗎？3）破壞“環(huán)路等待”條件 有序資源使用法：每個(gè)獨(dú)享資源都給一個(gè)唯一序號(hào)，使用只能按序號(hào)申請(qǐng)資源，三、利用銀行家算法避免死鎖1、銀行家算法思想 避免死鎖的算法是Dijkstra在1965年提出的，被稱為銀行家算法。 這個(gè)算法是用來模擬一個(gè)小城鎮(zhèn)的銀行家為一批顧客貸款的問題。 例： 有四個(gè)顧客：A，B，C，D，每個(gè)顧客提出的最大貸款數(shù)量分別為6、5、4、7。銀行家知道不是所有顧客都馬上需要其全部貸款（6+5+4+7=22）。因此

23、，他只保留10個(gè)單位數(shù)量(而不是全部22個(gè)單位)為這些顧客服務(wù)。銀行家擁有量:10當(dāng)前剩余量: 2當(dāng)B請(qǐng)求1個(gè)時(shí)，當(dāng)前剩余量:1 當(dāng)前剩余量:1 現(xiàn)在銀行家要破產(chǎn)了，剩余的資金貸給誰都不夠，因此項(xiàng)目不能完成，銀行家不能收回貸款。破產(chǎn)了錯(cuò)誤發(fā)生在最后貸款給B的1個(gè)億上當(dāng)前剩余量: 2B請(qǐng)求：不貸款C請(qǐng)求2個(gè)億：可以貸款 C完成項(xiàng)目后，還出4，這個(gè)4銀行家下次可貸給B，也可貸給D其中的3，不管如何處理，B或D都能完成歸還5或歸還7；最后貸給A所需資金5。 最終，A、B、C、D都完成了項(xiàng)目，銀行家得到了貸款利潤。 存在的安全序列是：C、B、D、A或C、D、B、A賺錢了2. 銀行家算法假定顧客分成若干

24、次借款；并在第一次借款時(shí)，能說明他的最大借款額。具體算法：顧客的借款操作依次順序進(jìn)行，直到全部操作完成；銀行家對(duì)當(dāng)前顧客的借款操作進(jìn)行判斷，以確定其安全性（能否支持顧客借款，直到全部歸還）；安全時(shí)，貸款；否則，暫不貸款。 銀行家算法可陳述如下： 當(dāng)一個(gè)進(jìn)程提出資源請(qǐng)求時(shí)，假定分配給它，并檢查系統(tǒng)因此是否仍處于安全狀態(tài)。如果安全，則滿足它的請(qǐng)求。否則，推遲它的請(qǐng)求。 為了檢查狀態(tài)是否安全，銀行家要檢查他是否還有足夠資源滿足某一個(gè)顧客。如果能滿足，這個(gè)顧客就能很快將貸款歸還。重復(fù)這一檢查過程。如果所有顧客的貸款都能滿足，系統(tǒng)的這個(gè)狀態(tài)是安全的?？蓪?shí)施實(shí)際的分配。如果不安全，則讓其阻塞等待。 上述算

25、法可簡單歸納如下：當(dāng)某進(jìn)程請(qǐng)求分配資源時(shí)，系統(tǒng)假定先分配給它，之后若能找到一個(gè)進(jìn)程完成序列，說明系統(tǒng)是安全的，可進(jìn)行實(shí)際分配；否則，讓申請(qǐng)者等待。3、算法描述： 設(shè)有n個(gè)客戶，max i:第i個(gè)客戶的資金總需求數(shù) alloc i:第i個(gè)客戶已得到的資金數(shù)，初值為0 needi:第i個(gè)客戶還需要的資金數(shù)，初值為maxi (1=i=n)av:銀行家目前可以貸出的資金,開始為總資本三者關(guān)系： maxi=alloci+needirequesti:第i個(gè)客戶當(dāng)前需要的資金數(shù)（必需有：requesti=needi)if(requesti=av & requesti=needi) av-=requesti;

26、 alloci+=requesti; needi-=requesti; if(check() )資金分配處理；else 拒絕分配，恢復(fù)av,needi,alloci的值;check:安全性檢查:work=av;finishi=False; i=1,2,nwhile(1) flag=1; for(k=1;k=n;k+) if(finishk=False & needk avi i=1,2,.m代表第i個(gè)銀行家當(dāng)前能提供的資金原來的一維數(shù)組擴(kuò)充為二維(n*m)，如：alloci(i=1,2,.n) :代表第i個(gè)客戶已得到的資金- alloci,j (i=1,2, n；j=1,2,.m): 代表第i

27、個(gè)客戶在第j個(gè)銀行家處已得到的資金 其它類推。 5、存在的問題：要求事先說明最大資源要求，在現(xiàn)實(shí)中很困難系統(tǒng)中有5個(gè)進(jìn)程（p0,P1,P2,P3,P4）和三類資源(A,B,C)，各種資源的數(shù)量分別為10，5，7，在T0時(shí)刻資源分配的情況如下表。Max(最多)A B CALLOC(已分配)A B CNEED(還需)A B CAVA(剩余)A B Cp07 5 30 1 0 7 4 33 3 2P13 2 2P2P3p42 0 01 2 29 0 23 0 26 0 00 1 12 1 12 2 24 3 30 0 24 3 1T0時(shí)刻是否安全？找到一個(gè)能夠把所有進(jìn)程執(zhí)行完成的序列即可說明其安全性

28、。Max(最多)A B CALLOC(已分配)A B CNEED(還需)A B CAVA(剩余)A B Cp07 5 30 1 0 7 4 33 3 2P13 2 2P2P3p42 0 01 2 29 0 23 0 26 0 00 1 12 1 12 2 24 3 30 0 24 3 1現(xiàn)在P1進(jìn)程發(fā)出請(qǐng)求Request（1，0，2）Max(最多)A B CALLOC(已分配)A B CNEED(還需)A B CAVA(剩余)A B Cp07 5 30 1 0 7 4 33 3 2P13 2 2P2P3p42 0 01 2 29 0 23 0 26 0 00 1 12 1 12 2 24 3

29、30 0 24 3 12 3 03 0 20 2 0如果P1請(qǐng)求得到滿足，那么系統(tǒng)的安全性怎么樣？再次發(fā)生進(jìn)程請(qǐng)求資源：P4進(jìn)程發(fā)出請(qǐng)求Request（3，3，0）Max(最多)A B CALLOC(已分配)A B CNEED(還需)A B CAVA(剩余)A B Cp07 5 30 1 0 7 4 3P13 2 2P2P3p49 0 23 0 26 0 00 1 12 1 12 2 24 3 30 0 24 3 12 3 03 0 20 2 0（3，3，0）大于(2 ,3, 0)所以P4必須等待再次發(fā)生進(jìn)程請(qǐng)求資源：P0進(jìn)程發(fā)出請(qǐng)求Request（0，2，0）Max(最多)A B CALLO

30、C(已分配)A B CNEED(還需)A B CAVA(剩余)A B Cp07 5 30 1 0 7 4 3P13 2 2P2P3p49 0 23 0 26 0 00 1 12 1 12 2 24 3 30 0 24 3 12 3 03 0 20 2 00 3 07 2 32 1 0剩余的資源(2,1,0)不能使得任何一個(gè)進(jìn)程得到全部滿足，導(dǎo)致找不到任何安全序列，所以此次分配是不安全的！4.8 死鎖的檢測(cè)和解除一、死鎖的檢測(cè) 1、死鎖模型 Holt1972年指出，用有向圖可以建立死鎖四個(gè)必要條件模型。圖中用圓形結(jié)點(diǎn)表示進(jìn)程，方形結(jié)點(diǎn)代表資源。從資源結(jié)點(diǎn)到進(jìn)程結(jié)點(diǎn)的弧表示該資源已分配給該進(jìn)程，從

31、進(jìn)程到資源結(jié)點(diǎn)的弧表示進(jìn)程請(qǐng)求資源。p1p2刪除出度為0的進(jìn)程結(jié)點(diǎn)的所有?。òǔ龆扰c入度）。 （含義是：該結(jié)點(diǎn)對(duì)應(yīng)進(jìn)程不處于阻塞態(tài)），該點(diǎn)變?yōu)楣铝Ⅻc(diǎn)。重復(fù)上述過程，若最后所有進(jìn)程結(jié)點(diǎn)是孤立點(diǎn)，則稱該資源圖是完全可簡化的，否則是不可完全簡化的。不可完全簡化的資源分配圖存在死鎖，其中的有邊進(jìn)程為死鎖進(jìn)程。2、資源分配圖的化簡（類似于數(shù)據(jù)結(jié)構(gòu)的拓?fù)渑判颍?、死鎖定理 狀態(tài)S為死鎖狀態(tài)的充分條件是：當(dāng)且僅當(dāng)S狀態(tài)的資源分配圖是不可完全簡化的。本質(zhì)是數(shù)據(jù)結(jié)構(gòu)的拓?fù)渑判?、死鎖檢測(cè) 1）數(shù)據(jù)結(jié)構(gòu)：類似于銀行家算法中所使用的 （A）av 代表所有不同類資源的當(dāng)前可用資源數(shù)（一維數(shù)組） （B）alloci i = 1,2,. (n為進(jìn)程數(shù)）， alloci 代表第i個(gè)進(jìn)程的目前已得到的不同種類資源的資源