操作系統(tǒng)課件：Chapter-03處理機調(diào)度與死鎖

1處理機調(diào)度與死鎖第三章3.1處理機調(diào)度的基本概念3.2調(diào)度算法3.3實時調(diào)度3.4多處理系統(tǒng)中的調(diào)度（自學(xué)）3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測與解除2處理機調(diào)度的基本概念（1）就緒隊列中只要有兩個以上的進程存在就會競爭CPU的使用權(quán)。如果只有1個CPU可用，那么就必須選擇下一個要運行的進程。完成選擇工作的這一部分稱為調(diào)度程序（scheduler），該程序使用的算法稱為調(diào)度算法（schedulingalgorithm）。3處理機調(diào)度的基本概念（2）廣義上：有三種調(diào)度4處理機調(diào)度的基本概念（3）進程行為幾乎所有進程的（磁盤）I/O請求或計算都是交替突發(fā)的。進程類型包括計算密集型（CPU-bound）I/O密集型（I/O-bound）CPU的提高比磁盤更快，越來越多的進程傾向于I/O密集型5處理機調(diào)度的基本概念（4）（本圖摘自AndrewS.Tanenbaum：“ModernOperatingSystems”）CPU-boundI/O-bound6處理機調(diào)度的基本概念（5）當(dāng)一個新的進程被創(chuàng)建時，是執(zhí)行新進程還是繼續(xù)執(zhí)行父進程？當(dāng)一個進程運行完畢時；當(dāng)一個進程由于I/O、信號量或其他的某個原因被阻塞時；當(dāng)一個I/O中斷發(fā)生時，表明某個I/O操作已經(jīng)完成，而等待該I/O操作的進程轉(zhuǎn)入就緒狀態(tài)；在分時系統(tǒng)中，當(dāng)一個時鐘中斷發(fā)生時。進程何時被調(diào)度7處理機調(diào)度的基本概念（6）不可搶占調(diào)度方式：一個進程若被選中，就一直運行下去，直到它被阻塞（I/O，或正在等待其他的進程），或主動地交出CPU?？蓳屨颊{(diào)度方式：當(dāng)一個進程在運行時，調(diào)度程序可以打斷它。另外，在其他的一些情形下，如就緒隊列中有進程的優(yōu)先級高于當(dāng)前運行進程的優(yōu)先級，也可能立即進行調(diào)度。進程調(diào)度的方式8處理機調(diào)度的基本概念（7）批處理系統(tǒng)：無須及時的用戶響應(yīng)，采用不可搶占的調(diào)度方式，或時間間隔很長的可搶占調(diào)度方式，從而允許進程能長時間運行，減少進程的切換次數(shù)，提高系統(tǒng)的性能；交互式系統(tǒng)：及時的用戶響應(yīng)非常重要，必須采用可搶占的調(diào)度方式。以防單個進程占用太多CPU時間，影響到其他進程的運行。實時系統(tǒng)：對響應(yīng)時間要求苛刻，每個進程運行時間很短，可采用可搶占的調(diào)度方式。不同類型操作系統(tǒng)進程調(diào)度的方式9處理機調(diào)度的基本概念（8）搶占式調(diào)度實例某多道程序設(shè)計系統(tǒng)配有一臺處理器和兩臺外設(shè)IO1、IO2，現(xiàn)有3個優(yōu)先級由高到低的作業(yè)J1、J2和J3都已裝入了主存，它們使用資源的先后順序和占用時間分別是：J1：IO2（30ms），CPU（10ms），IO1（30ms），CPU（10ms）。J2：IO1（20ms），CPU（20ms），IO2（40ms）。J3：CPU（30ms），IO1（20ms）。處理器調(diào)度采用可強占式的優(yōu)先數(shù)算法，忽略其他輔助操作時間，回答下列問題：（1）分別計算作業(yè)J1、J2和J3從開始到完成所用的時間。（2）3個作業(yè)全部完成時CPU的利用率。（3）3個作業(yè)全部完成時外設(shè)IO1的利用率。10處理機調(diào)度的基本概念（9）搶占式調(diào)度實例2030405060708090IO2（30ms）CPU（10ms）IO1（30ms）CPU（10ms）IO1（20ms）CPU（10ms）CPU（10ms）IO2（40ms）CPU（20ms）CPU（10ms）IO1（20ms）time0J1J2J311處理機調(diào)度的基本概念（10）搶占式調(diào)度實例解答：（1）由圖可知，J1從開始到完成的時間是0～80ms，J2從開始到完成的時間是0～90ms，J3從開始到完成的時間是0～90ms。（2）3個作業(yè)全部完成總共需要90ms，CPU總共使用的時間是：

20＋10＋10＋10＋10＋10＝70（ms）所以CPU的利用率是：70/90×100%＝77.8％（3）3個作業(yè)全部完成時IO1的利用率是：（20＋30＋20）/90×100％＝70/90×100％≈77.8％12處理機調(diào)度的基本概念（11）分派程序是一個模塊，用來將CPU的控制交給由短期調(diào)度程序所選擇的進程。其功能包括切換上下文切換到用戶模式跳轉(zhuǎn)到用戶程序的合適位置以重新啟動這個程序分派延遲（dispatchlatency）－分派程序停止一個進程而啟動另一個進程執(zhí)行所要花費的時間。分派程序（Dispatcher）13處理機調(diào)度的基本概念（12）算法調(diào)度的目標(biāo)是多元的，有些是可以共存的，也有些是相互牽制的，對于一個實際的調(diào)度算法來說，有一個綜合權(quán)衡的過程。所有系統(tǒng)普遍適用的目標(biāo)：公平：大致相當(dāng)?shù)膬蓚€進程所得到的CPU時間也應(yīng)是大致相同的；對已制訂的調(diào)度策略必須能貫徹執(zhí)行；均衡：盡可能使整個系統(tǒng)的各部分都忙起來，提高系統(tǒng)資源的使用效率。調(diào)度算法的目標(biāo)14處理機調(diào)度的基本概念（13）批處理系統(tǒng)中調(diào)度算法的評價指標(biāo)：吞吐量（Throughput）：單位時間內(nèi)所完成的作業(yè)數(shù)，與作業(yè)本身特性和調(diào)度算法有關(guān)；周轉(zhuǎn)時間（Turnaroundtime）：一個批處理作業(yè)從提交到完成（得到結(jié)果）所經(jīng)歷的時間。包括：在收容隊列中等待，CPU上執(zhí)行，就緒隊列和阻塞隊列中等待，結(jié)果輸出等待；平均周轉(zhuǎn)時間：一批作業(yè)的周轉(zhuǎn)時間的平均值；平均帶權(quán)周轉(zhuǎn)時間：權(quán)值是實際執(zhí)行時間的倒數(shù);調(diào)度算法的目標(biāo)15處理機調(diào)度的基本概念（14）調(diào)度算法的目標(biāo)平均周轉(zhuǎn)時間平均帶權(quán)周轉(zhuǎn)時間16處理機調(diào)度的基本概念（15）調(diào)度算法的目標(biāo)交互式系統(tǒng)中調(diào)度算法的評價指標(biāo)：響應(yīng)時間：用戶輸入一個請求（如擊鍵）到系統(tǒng)給出首次響應(yīng)（如屏幕顯示）的時間。響應(yīng)時間越短越好，優(yōu)先考慮交互式進程；相稱性：滿足用戶對程序運行時間的期望值。17處理機調(diào)度的基本概念（16）調(diào)度算法的目標(biāo)實時系統(tǒng)中調(diào)度算法的評價指標(biāo)：實時響應(yīng)：必須嚴(yán)格地遵守時間期限；可預(yù)測性：在實時多媒體系統(tǒng)中，信號的播放必須連貫，不能時斷時續(xù)。18調(diào)度算法（1）先來先服務(wù)（FirstComeFirstServed，F(xiàn)CFS；FirstInFirstOut，F(xiàn)IFO）：按照作業(yè)到達的先后次序進行調(diào)度；不可搶占方式：當(dāng)前進程占用CPU，直到執(zhí)行完或被阻塞，才讓出CPU給另外一個進程；在進程被喚醒后（如I/O完成），并不立即恢復(fù)執(zhí)行，而是放在就緒隊列的末尾；優(yōu)點：簡單，易于理解也易于實現(xiàn)?，F(xiàn)實生活中應(yīng)用廣泛：排隊。批處理系統(tǒng)的調(diào)度算法-FCFS19問題1.平均周轉(zhuǎn)時間取決于各作業(yè)到達的順序，若

短作業(yè)位于長作業(yè)之后，將增大平均周轉(zhuǎn)時間。例如，三個作業(yè)A、B、C的運行時間為24、3、3時間242730ABC平均周轉(zhuǎn)時間＝(24+27+30)/3＝27

平均等待時間＝(0+24+27)/3＝17調(diào)度算法（2）20調(diào)度算法（3）時間3630ABC平均周轉(zhuǎn)時間＝(3+6+30)/3＝13

平均等待時間＝(0+3+6)/3＝3換成B、C、A的排隊順序21調(diào)度算法（4）問題2.無法充分利用CPU繁忙的作業(yè)與I/O繁忙的

作業(yè)之間的互補關(guān)系。如果CPU繁忙的作業(yè)獨占很

長時間的CPU，使得I/O設(shè)備空閑，也使得I/O繁忙

的作業(yè)無法運行。作業(yè)A作業(yè)BCPUI/O作業(yè)A作業(yè)B時間t0t1t2t3t422調(diào)度算法（5）FCFS-例題，求平均周轉(zhuǎn)時間作業(yè)進入時刻（H）運行時間（H）18228.50.5390.149.50.223調(diào)度算法（6）FCFS-例題，求平均周轉(zhuǎn)時間時間123481010.510.610.8進程1進程3進程2進程488.599.5平均周轉(zhuǎn)時間=(2+2+1.6+1.3)/4=1.725h24調(diào)度算法（7）短作業(yè)優(yōu)先（ShortestJobFirst，SJF），設(shè)計目標(biāo)是改進FCFS算法，減少平均周轉(zhuǎn)時間；SJF算法要求作業(yè)在開始執(zhí)行時預(yù)計執(zhí)行時間，對預(yù)計執(zhí)行時間短的作業(yè)優(yōu)先分派處理器兩種實現(xiàn)方案：不可搶占方式：當(dāng)前作業(yè)在運行時不會被打斷，只有運行完畢或阻塞時，才讓出CPU；可搶占方式：如果一個新的短作業(yè)到來，其運行時間小于當(dāng)前正在運行作業(yè)的剩余時間，則搶占CPU運行，稱為SRTF（ShortestRemainingTimeFirst）。批處理系統(tǒng)的調(diào)度算法-SJF25調(diào)度算法（8）可以證明：對于一組同時到達的作業(yè)，采用SJF

算法將得到一個最小的平均周轉(zhuǎn)時間。DACaa+ba+b+ca+b+c+d例如，考察4個作業(yè)A、B、C、D，其運行時間分

別為a、b、c、dBA、B、C、D的周轉(zhuǎn)時間分別為a、a+b、a+b+c和a+b+c+d，因此平均周轉(zhuǎn)時間為：(4a+3b+2c+d)/4顯然，當(dāng)abcd時，平均周轉(zhuǎn)時間最小。26調(diào)度算法（9）SJF-例題，求平均周轉(zhuǎn)時間作業(yè)進入時刻（H）運行時間（H）18228.50.5390.149.50.227調(diào)度算法（10）SJF-例題，求平均周轉(zhuǎn)時間123481010.110.310.8時間進程1進程3進程2進程488.599.5平均周轉(zhuǎn)時間=(2+1.1+0.8+2.3)/4=1.55h28調(diào)度算法（11）SJF搶占式-例題，求平均等待時間29調(diào)度算法（12）一種動態(tài)優(yōu)先權(quán)算法最高響應(yīng)比作業(yè)優(yōu)先算法是對FCFS方式和SJF方式的一種綜合平衡。響應(yīng)比R定義為系統(tǒng)對作業(yè)的響應(yīng)時間與作業(yè)要求運行時間的比值R＝響應(yīng)時間/要求運行時間＝(作業(yè)等待時間＋需運行時間)/需運行時間＝1＋已等待時間/需運行時間＝1＋W/T批處理系統(tǒng)的調(diào)度算法-HRN30調(diào)度算法（13）HRN-例題，求平均周轉(zhuǎn)時間作業(yè)進入時刻（H）運行時間（H）18228.50.5390.149.50.231調(diào)度算法（14）HRN-例題，求平均周轉(zhuǎn)時間時間進程1進程3進程2進程488.599.51810R2=1+1.5/0.5=4R3=1+1/0.1=11R4=1+0.5/0.2=3.5R3310.1R2=1+1.6/0.5=4.2R4=1+0.6/0.2=4R2210.6410.8平均周轉(zhuǎn)時間=(2+1.1+2.1+1.3)/4=1.625h32調(diào)度算法（15）分別按先來先服務(wù)（FCFS）、非搶占式及搶占的短進程優(yōu)先（SJF）調(diào)度算法、高響應(yīng)比優(yōu)先調(diào)度算法進行CPU調(diào)度，請給出各進程的完成時間、周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間、平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。進程到達時間服務(wù)時間A03B26C44D65E8233調(diào)度算法（16）在時間片輪轉(zhuǎn)算法（Round-Robin，RR）中，將所有的就緒進程按照FCFS原則，排成一個隊列每次調(diào)度時將處理器分派給隊首進程，讓其執(zhí)行一小段CPU時間（時間片timequantum）在一個時間片結(jié)束時，如果進程還沒有執(zhí)行完的話，將發(fā)生時鐘中斷，在時鐘中斷中，進程調(diào)度程序?qū)和．?dāng)前進程的執(zhí)行，并將其送到就緒隊列的末尾，然后執(zhí)行當(dāng)前的隊首進程如果一個進程在它的時間片用完之前就已結(jié)束或被阻塞，那么立即讓出CPU交互式系統(tǒng)的調(diào)度算法-RR34調(diào)度算法（17）開始時，進程B位于隊列之首，因此被調(diào)度執(zhí)行。當(dāng)它的時間片用完后，就把它送到就緒隊列的末尾。同時，進程F成為隊首進程，被調(diào)度運行。35調(diào)度算法（18）36調(diào)度算法（19）優(yōu)點：公平性：各個就緒進程平均地分配CPU的使用時間。假設(shè)有n個就緒進程，時間片大小為q，那么每個進程將得到1/n的CPU時間；活動性：每個進程最多等待(n-1)q時間就能夠再次得到CPU去運行；一般來說，平均周轉(zhuǎn)時間較SJF算法為長，但能夠得到較短的平均響應(yīng)時間；交互式系統(tǒng)的調(diào)度算法-RR特點37調(diào)度算法（20）缺點：q的大小難以確定（一般在20－50ms）。q太大：退化為FCFS算法，進程在一個時間片內(nèi)都執(zhí)行完，響應(yīng)時間長。如q=100ms；q太?。好總€進程都需要更多的時間片才能處理完，進程切換次數(shù)增加，增大系統(tǒng)開銷。如q=4ms交互式系統(tǒng)的調(diào)度算法-RR特點38調(diào)度算法（21）RR實例，時間片2039調(diào)度算法（22）（本圖摘自AndrewS.Tanenbaum：“ModernOperatingSystems”）進程間未必完全平等?？梢园堰M程按照不同的優(yōu)先級別分組，然后在不同級別之間使用優(yōu)先級算法，而在同一級別的各個進程之間使用時間片輪轉(zhuǎn)法。40調(diào)度算法（23）多級隊列算法（MultilevelQueue）引入多個就緒隊列，通過各個隊列的區(qū)別對待，達到一個綜合的調(diào)度目標(biāo)。根據(jù)進程的性質(zhì)或類型的不同，將就緒隊列再分為若干個子隊列，如系統(tǒng)進程、用戶交互進程、批處理進程等；不同的隊列可以有不同的優(yōu)先級；不同的隊列可以采用各自不同的調(diào)度算法，如前臺的交互式進程可采用RR算法，后臺的批處理進程可采用FCFS算法。多級隊列算法41調(diào)度算法（24）在各個隊列之間也必須進行調(diào)度：固定優(yōu)先級調(diào)度：按照各種類型的進程的優(yōu)先級別從高到低地進行，先運行最高優(yōu)先級的所有進程，再運行次一級所有進程，依此類推。

問題：可能導(dǎo)致“饑餓”；時間片方法：把CPU時間按比例分配給不同的隊列，然后再由各個隊列的調(diào)度算法去調(diào)度，如80％給前臺的交互式進程隊列（RR算法），20％給后臺的批處理進程隊列FCFS）。多級隊列算法42調(diào)度算法（25）43調(diào)度算法（26）多級隊列算法把每個進程按照它的類型固定在一個隊列中，但問題是如何來確定進程的類型？而且有的進程其類型可能動態(tài)變化，怎么辦？多級反饋隊列算法(MultilevelFeedbackQueue)即根據(jù)一個進程的運行反饋信息，動態(tài)地調(diào)整它所在的隊列。多級反饋隊列算法44調(diào)度算法（27）如何實現(xiàn)多級反饋隊列算法？需要確定以下的一些參數(shù)：隊列的個數(shù)；每個隊列所用的調(diào)度算法；用來確定何時給一個進程“升級”的方法；用來確定何時給一個進程“降級”的方法；用來確定一個進程的初始隊列的方法；多級反饋隊列算法45調(diào)度算法（28）優(yōu)先級321三種優(yōu)先級別，3最高、1最低，三個就緒隊列。時間片長度分別為N、2N和4N；新進程進入內(nèi)存后，優(yōu)先級為3，加入隊列3的末尾，按FCFS算法調(diào)度；若一個時間片內(nèi)未能執(zhí)行完，則優(yōu)先級降為2，加入到隊列2的末尾，同樣按FCFS算法調(diào)度；依此類推。僅當(dāng)較高優(yōu)先級的隊列為空，才調(diào)度較低優(yōu)先級的隊列中的進程執(zhí)行。若進程執(zhí)行時有新進程進入較高優(yōu)先級的隊列，則搶先執(zhí)行新進程。46調(diào)度算法（29）按只按時間片進行搶占的多級反饋隊列以及立即搶占的多級反饋隊列（第i級隊列的時間片＝2i-1）調(diào)度算法進行CPU調(diào)度，請給出各進程的完成時間、周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間、平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。進程到達時間服務(wù)時間A03B26C44D65E8247調(diào)度算法（30）時間abcbdecdebcd進程a進程c進程b進程d進程e36452314171820多級反饋算法-例題，按時間片搶占平均周轉(zhuǎn)時間=(3+15+14+14+6)/5=10.4平均帶權(quán)周轉(zhuǎn)時間=(3/3+15/6+14/4+14/5+6/2)/5=2.5648調(diào)度算法（31）時間ab進程a進程c進程b進程d進程e36452415161820多級反饋算法-例題，立即搶占平均周轉(zhuǎn)時間=(4+16+11+14+8)/5=10.6平均帶權(quán)周轉(zhuǎn)時間=(4/3+16/6+11/4+14/5+8/2)/5=2.87acbdcebdcebd49調(diào)度算法（32）在實時系統(tǒng)中，對時間的要求是非常嚴(yán)格的。典型的例子是：一個或多個外部的物理設(shè)備定期或不定期地生成激勵信號，而計算機必須在一定的時間期限內(nèi)做出恰當(dāng)?shù)姆磻?yīng)。硬實時：有一個絕對的時間期限，計算機的反應(yīng)動作必須在此期限之前完成，如核電站的控制系統(tǒng)；軟實時：偶爾錯過一次期限雖然是令人不快的，但也是可以容忍的，如VCD的播放系統(tǒng)；實時調(diào)度算法可以是靜態(tài)的或動態(tài)的，前者在系統(tǒng)開始運行之前即已做好調(diào)度決策；而后者是在運行中做出調(diào)度決策。實時系統(tǒng)調(diào)度算法50調(diào)度算法（33）根據(jù)任務(wù)的開始截止時間確定任務(wù)優(yōu)先級，截止時間越早，優(yōu)先級越高。可用于搶占和非搶占式。實時系統(tǒng)調(diào)度算法-最早截止時間優(yōu)先算法1234開始截止時間執(zhí)行任務(wù)任務(wù)到達1342342151調(diào)度算法（34）最早截止時間優(yōu)先算法-例進程到達時間執(zhí)行時間開始截止時間A1020110B202020C402050D502090E6020700102030405060708090100110120ABCEDA搶占52調(diào)度算法（35）該算法是根據(jù)任務(wù)緊急(或松弛)的程度，來確定任務(wù)的優(yōu)先級。任務(wù)的緊急程度愈高，為該任務(wù)所賦予的優(yōu)先級就愈高，以使之優(yōu)先執(zhí)行。松弛度＝必須完成時間－本身運行時間－當(dāng)前時間實時系統(tǒng)調(diào)度算法-最低松弛度優(yōu)先算法53調(diào)度算法（36）假如在一個實時系統(tǒng)中，有兩個周期性實時任務(wù)A和B，任務(wù)A要求每20ms執(zhí)行一次，執(zhí)行時間為10ms；任務(wù)B只要求每50ms執(zhí)行一次，執(zhí)行時間為25ms。54調(diào)度算法（37）55死鎖（1）在一組進程中，每個進程都占用著若干個資源，同時又在等待得到該組進程中另一進程所占用的資源，因而造成的所有進程都無法進展下去的現(xiàn)象，這種現(xiàn)象稱為死鎖，這一組進程就稱為死鎖進程。什么是死鎖？56死鎖（2）57死鎖（3）在計算機系統(tǒng)中，有各種不同類型的資源：CPU,時鐘、I/O設(shè)備、內(nèi)存空間、數(shù)據(jù)庫中的記錄等。對于有的資源類型，可能有多個相同的實例，如三個磁帶驅(qū)動器，它們中的任何一個都能夠用來滿足進程對磁帶驅(qū)動器資源的請求。當(dāng)然，對于任何一個資源來說，在任何時刻只能被一個進程所使用。資源可以分為兩大類：可搶占的（preemptable）和不可搶占的（nonpreemptable）。資源是什么？58死鎖（4）可搶占的資源：當(dāng)一個進程正在使用這種類型的資源時，可以把它拿走而不會對該進程造成任何不良的影響。例如：內(nèi)存、CPU。不可搶占的資源：當(dāng)一個進程正在使用這種類型的資源時，如果強行把它拿走，將會導(dǎo)致該進程運行失敗。例如：光盤刻錄機。死鎖主要由不可搶占資源引起，對于可搶占資源而言，可以通過重新分配資源的方法來避免死鎖。因此，這里只考察不可搶占資源。資源是什么？59死鎖（5）（1）資源有限。當(dāng)系統(tǒng)中多個進程共享資源，如打印機、公用隊列等，其數(shù)目不足以滿足諸進程的需要，會引起進程對資源的競爭而產(chǎn)生死鎖。（2）并發(fā)進程間的推進順序不當(dāng)。進程在運行過程中，請求和釋放資源的順序不當(dāng)，也會導(dǎo)致產(chǎn)生進程死鎖。死鎖產(chǎn)生的原因60死鎖（6）占用打印機共同進展路徑1禁區(qū)危險區(qū)占用輸入機占用打印機甲進程的進展乙進程的進展XY61死鎖（7）互斥條件：在任何時刻，每一個資源最多只能被一個進程所使用；請求和保持條件：進程在占用若干個資源的同時又可以請求新的資源；不可搶占條件：進程已經(jīng)占用的資源，不會被強制性拿走，而必須由該進程主動釋放；環(huán)路等待條件：存在一條由兩個或多個進程所組成的環(huán)路鏈，其中每一個進程都在等待環(huán)路鏈中下一個進程所占用的資源。62死鎖（8）Holt（1972）提出用資源分配圖來描述死鎖發(fā)生的四個條件。在圖中，用兩種類型的結(jié)點來表示進程和資源，用有向邊來表示進程與資源之間的請求和分配關(guān)系。進程（用圓圈表示）：資源（用方框表示）：63死鎖（9）resourceRassignedtoprocessAprocessBisrequesting/waitingforresourceSprocessCandDareindeadlockoverresourcesTandU64死鎖（10）ABC死鎖的產(chǎn)生65死鎖（11）死鎖的避免(o)(p)(q)66死鎖（12）應(yīng)對死鎖的策略忽略死鎖，無為而治Windows、UNIX檢測并恢復(fù)動態(tài)避免小心的進行資源分配預(yù)防破壞死鎖的4個必要條件之一67死鎖（13）預(yù)防死鎖的方法就是破壞產(chǎn)生死鎖的4個必要條件。破壞互斥不是切實可行的。因為有些資源若是共享使用，則無法保證其正確性。又如，對臨界資源的訪問就必須互斥進行。所以預(yù)防死鎖可以從破壞其他3個條件入手。預(yù)防死鎖不能破壞互斥68死鎖（14）方法一：進程一次性申請到它所需要的所有資源后，才能開始運行，又稱預(yù)先靜態(tài)分配法方法二：進程提出申請資源前必須釋放已占有的一切資源優(yōu)點：簡單、易于實現(xiàn)且很安全。缺點：（1）資源嚴(yán)重浪費；（2）進程延遲運行。破壞“請求和保持”條件69死鎖（15）在進程主動釋放占有的資源前即予以剝奪，也能保證系統(tǒng)不出現(xiàn)死鎖。方法一：當(dāng)進程Pi申請rj類資源時，檢查rj中有無可分配的資源，有則分配給Pi；否則將Pi占有的資源全部釋放進入等待狀態(tài)。方法二：當(dāng)Pi申請rj時，檢查rj中有無可分配的資源，有則分配；否則檢查占有rj類資源的進程Pk。若Pk處于等待資源狀態(tài)，則剝奪Pk的rj分給Pi；若Pk處于不等待資源狀態(tài)，則置Pi于等待資源狀態(tài)(此時Pi原占有的資源可能被剝奪。)破壞“不可搶占”條件70死鎖（16）采用資源順序分配法，可以破壞循環(huán)等待條件。把系統(tǒng)中所有資源按類型編號，所有進程在申請資源時必須嚴(yán)格按資源編號的遞增次序進行，否則操作系統(tǒng)不予分配。這樣總有一個進程占有最高編號的資源，順利運行完成，釋放它所占有的資源，保證其它進程順利執(zhí)行。破壞“環(huán)路等待”條件71死鎖（17）在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統(tǒng)性能。在該方法中把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終處于安全狀態(tài)，便可避免發(fā)生死鎖。死鎖的避免72死鎖（18）所謂安全狀態(tài)，是指系統(tǒng)能按某種順序，如安全序列（P1,P2,…,Pn)來為每個進程分配其所需資源，直至最大需求，使每個進程都可順序完成。避免死鎖的實質(zhì)在于：如何使系統(tǒng)不進入不安全狀態(tài)安全狀態(tài)73死鎖（19）我們通過一個例子來說明安全性。假定系統(tǒng)中有三個進程P1、P2和P3，共有12臺磁帶機。進程P1總共要求10臺磁帶機，P2和P3分別要求4臺和9臺。假設(shè)在T0時刻，進程P1、P2和P3已分別獲得5臺、2臺和2臺磁帶機，尚有3臺空閑未分配，如下表所示：進程最大需求已分配可用P1P2P310495223安全狀態(tài)例子74死鎖（20）經(jīng)分析發(fā)現(xiàn)，在T0時刻系統(tǒng)處于安全狀態(tài)，存在一個安全序列｛P2,P1,P3｝。安全序列不唯一。安全狀態(tài)例子75死鎖（21）如果不按照安全序列分配資源，則系統(tǒng)可能會由安全狀態(tài)進入不安全狀態(tài)。例如，在T0時刻以后，P3又請求1臺磁帶機，若此時系統(tǒng)把剩余3臺中的1臺分配給P3，則系統(tǒng)便進入不安全狀態(tài)。安全狀態(tài)轉(zhuǎn)換到不安全狀態(tài)進程最大需求已分配可用P1P2P31049523276死鎖（22）1965年由Dijkstra提出的一種避免死鎖的調(diào)度算法，它模擬了一個銀行家在發(fā)放信用貸款時的處理方式。在小鎮(zhèn)上，有一位銀行家和一些需要貸款服務(wù)的客戶。銀行家根據(jù)每一位客戶的背景情況，為之設(shè)定了相應(yīng)的最高貸款限額?，F(xiàn)在的問題是銀行家必須設(shè)計出一種算法，以保證借貸過程的順利進行，也就是說，當(dāng)某個客戶提出了一個貸款申請時，該算法必須判斷，如果批準(zhǔn)了這個申請，是否會導(dǎo)致一種不安全的狀態(tài)，如果是的話，就拒絕該申請；如果否的話，就批準(zhǔn)該申請。銀行家算法77死鎖（23）銀行家算法四個客戶A、B、C、D，每個客戶都有一個最高貸款限額，初始時，銀行家手里只保留10K美元。70D40C50B60A已貸限額銀行家：10K安全狀態(tài)74D42C51B61A已貸限額銀行家：2K安全狀態(tài)74D42C52B61A已貸限額銀行家：1K不安全狀態(tài)78死鎖（24）S1

某個客戶提出貸款請求；S2

假設(shè)批準(zhǔn)該請求，將得到系統(tǒng)狀態(tài)T；S3

判斷狀態(tài)T是否安全，如果安全，則批準(zhǔn)該請求，轉(zhuǎn)S1；如果不安全，則不批準(zhǔn)該請求，延期到以后處理，轉(zhuǎn)S1；銀行家算法79死鎖（25）S1

銀行家檢查一下，看他手里的資源能否滿足某個客戶的請求（剩余的最大限額）；S2如果可以，則該客戶的貸款請求已經(jīng)滿足，因此他償還了所有貸款。轉(zhuǎn)S1；S3如果到最后，所有的貸款都能償還，則狀態(tài)T就是安全的，否則就是不安全的。判斷是否安全狀態(tài)80死鎖（26）OS中的銀行家算法拓展了僅有一種資源的情況。假設(shè)有n個進程，競爭m個資源。對于資源的現(xiàn)有狀況、每個進程的資源最大需求、當(dāng)前分配狀況、當(dāng)前需求狀況等需要用向量和矩陣來描述。包括：Availablem維向量Maxn*m維矩陣Allocationn*m維矩陣Needn*m維矩陣Requestim維向量銀行家算法的數(shù)據(jù)結(jié)構(gòu)81死鎖（27）可利用資源向量Available這是一個含有m個元素的數(shù)組，其中的每一個元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動態(tài)地改變。如果Available［j］=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個。銀行家算法的數(shù)據(jù)結(jié)構(gòu)82死鎖（28）最大需求矩陣Max這是一個n×m的矩陣，它定義了系統(tǒng)中n個進程中的每一個進程對m類資源的最大需求。如果Max［i,j］=K，則表示進程i需要Rj類資源的最大數(shù)目為K。銀行家算法的數(shù)據(jù)結(jié)構(gòu)83死鎖（29）分配矩陣Allocation這也是一個n×m的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進程的資源數(shù)。如果Allocation［i,j］=K，則表示進程i當(dāng)前已分得Rj類資源的數(shù)目為K。銀行家算法的數(shù)據(jù)結(jié)構(gòu)84死鎖（30）需求矩陣Need是一個n×m的矩陣，用以表示每一個進程尚需的各類資源數(shù)。如果Need［i,j］=K，則表示進程i還需要Rj類資源K個，方能完成其任務(wù)。Need［i,j］=Max［i,j］-Allocation［i,j］銀行家算法的數(shù)據(jù)結(jié)構(gòu)85死鎖（31）銀行家算法的數(shù)據(jù)結(jié)構(gòu)86死鎖（32）銀行家算法的數(shù)據(jù)結(jié)構(gòu)進程Pi的請求向量Requesti如果Requesti［j］=K，表示進程Pi需要K個Rj類型的資源。87死鎖（33）銀行家算法描述S1：如果Requesti［j］≤Need［i,j］，便轉(zhuǎn)向S2；否則認(rèn)為出錯，因為它所需要的資源數(shù)已超過它所宣布的最大值。S2：如果Requesti［j］≤Available［j］，便轉(zhuǎn)向步驟S3；否則，表示尚無足夠資源，Pi須等待。88死鎖（34）銀行家算法描述S1：如果Requesti［j］≤Need［i,j］

，便轉(zhuǎn)向S2；否則認(rèn)為出錯，因為它所需要的資源數(shù)已超過它所宣布的最大值。S2：如果Requesti［j］

≤Available［j］

，便轉(zhuǎn)向步驟S3；否則，表示尚無足夠資源，Pi須等待。89死鎖（35）銀行家算法描述S3:系統(tǒng)試探著把資源分配給進程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：Available［j］

:=Available［j］

-Requesti［j］

;Allocation［i，j］

:=Allocation［i，j］+Requesti

［j］;Need［i，j］:=Need［i，j］-Requesti

［j］;90死鎖（36）銀行家算法描述S4:系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進程Pi

等待。91死鎖（37）安全性算法描述S1：設(shè)置兩個向量：①工作向量Work:它表示系統(tǒng)可提供給進程繼續(xù)運行所需的各類資源數(shù)目，它含有m個元素，在執(zhí)行安全算法開始時，Work∶=Available;②Finish:它表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成。開始時先做Finish［i］:=false;當(dāng)有足夠資源分配給進程時，再令Finish［i］:=true。92死鎖（38）安全性算法描述S2：從進程集合中找到一個能滿足下述條件的進程：①Finish［i］=false;②Need［i,j］≤Work［j］；若找到，執(zhí)行步驟S3，否則，執(zhí)行步驟S4。S3：當(dāng)進程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：Work［j］:=Work［i］+Allocation［i,j］;Finish［i］:=true;gotostep2;93死鎖（39）安全性算法描述S4：如果所有進程的Finish［i］=true都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。94死鎖（40）安全性算法實例MAXALLONEEDAVAIWORKFINISHP0753010743332P1322200122P2902302600P3222211011P4433002431T0時刻安全嗎？

95死鎖（41）MAXALLONEEDAVAIWORKFINISHP0753010743332P1322200122P2902302600P3222211011P4433002431532TRUE743TRUE745TRUE755TRUE1057TRUE1.T0時刻的安全序列：P1-P3-P4-P0-P296死鎖（42）2.P1發(fā)出請求向量Request1（1，0，2）MAXALLONEEDAVAIWORKFINISHP0753010743P1322P2902302600P3222211011P443300243133223012202020030297死鎖（43）MAXALLONEEDAVAIWORKFINISHP0753010743230P1322302020P2902302600P3222211011P4433002431532TRUE743TRUE745TRUE755TRUE1057TRUE有安全序列P1-P3-P4-P0-P2，可以實際進行分配98死鎖（44）3.P4請求資源：P4發(fā)出請求向量Request4（3，3，0），系統(tǒng)按銀行家算法進行檢查：（1）Request4(3，3，0)<=Need4(4，3，1)（2）Request4(3，3，0)不小于或等于Available(2，3，0),讓P4等待。99死鎖（45）4.P0請求資源：P0發(fā)出請求向量Request0（0，2，0），系統(tǒng)按銀行家算法進行檢查：（1）Request0（0，2，0）<=Need0(7,4,3)（2）Request0（0，2，0）<=Available(2,3,0)（3）系統(tǒng)先假定可為P0分配資源，并修改有關(guān)數(shù)據(jù)。100死鎖（46）MAXALLONEEDAVAIWORKFINISHP0753030723210P1322302020P2902302600P322221