進(jìn)程調(diào)度與死鎖

《操作系統(tǒng)原理》

第二章 進(jìn)程調(diào)度與死鎖主講教師：李閱歷2版權(quán)所有，轉(zhuǎn)載請(qǐng)注明出處2內(nèi)容提要進(jìn)程調(diào)度模型與方法死鎖內(nèi)容提要3版權(quán)所有，轉(zhuǎn)載請(qǐng)注明出處3進(jìn)程調(diào)度的基本概念CPU資源管理——多道程序設(shè)計(jì)面臨的挑戰(zhàn)批處理系統(tǒng)：如何安排內(nèi)存中多個(gè)作業(yè)的運(yùn)行順序？交互式系統(tǒng)：如何更好應(yīng)對(duì)不同的交互式請(qǐng)求？實(shí)時(shí)系統(tǒng)：如何保證實(shí)時(shí)服務(wù)的高質(zhì)量？進(jìn)程調(diào)度——有效的管理CPU資源When：何時(shí)進(jìn)行進(jìn)程調(diào)度？How：遵循何種規(guī)則完成調(diào)度？搶占、非搶占式；What：調(diào)度過程中需要完成哪些工作？進(jìn)程調(diào)度的發(fā)展方向：PC機(jī)和服務(wù)器進(jìn)程調(diào)度4進(jìn)程行為BurstsofCPUusagealternatewithperiodsofI/OwaitaCPU-boundprocessanI/Oboundprocess何時(shí)調(diào)度當(dāng)創(chuàng)建一個(gè)新進(jìn)程時(shí)；當(dāng)一個(gè)進(jìn)程退出時(shí)；當(dāng)一個(gè)進(jìn)程阻塞時(shí)；當(dāng)發(fā)生一個(gè)I/O中斷時(shí)；總之，在OS按照時(shí)鐘中斷來執(zhí)行調(diào)度程序；版權(quán)所有，轉(zhuǎn)載請(qǐng)注明出處5調(diào)度算法分類批處理非搶占交互式搶占實(shí)時(shí)可以非搶占7版權(quán)所有，轉(zhuǎn)載請(qǐng)注明出處7進(jìn)程調(diào)度的考量標(biāo)準(zhǔn)

響應(yīng)時(shí)間(responsetime)進(jìn)程自進(jìn)入就緒隊(duì)列開始至進(jìn)程占用CPU之間的時(shí)間間隔周轉(zhuǎn)時(shí)間(turnaroundtime)進(jìn)程自進(jìn)入就緒隊(duì)列開始至進(jìn)程結(jié)束之間的時(shí)間間隔

CPU吞吐量（throughout)單位時(shí)間內(nèi)運(yùn)行結(jié)束的進(jìn)程個(gè)數(shù)舉例進(jìn)程調(diào)度8SchedulingAlgorithmGoalsP78

作業(yè)周轉(zhuǎn)時(shí)間如果作業(yè)i提交給系統(tǒng)的時(shí)刻是ts，完成時(shí)刻是tf，該作業(yè)的周轉(zhuǎn)時(shí)間ti為：ti=tf-ts

實(shí)際上，它是作業(yè)在系統(tǒng)里的等待時(shí)間與運(yùn)行時(shí)間之和。平均作業(yè)周轉(zhuǎn)時(shí)間為了提高系統(tǒng)的性能，要讓若干個(gè)用戶的平均作業(yè)周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間最小。平均作業(yè)周轉(zhuǎn)時(shí)間T=(Σti)/n作業(yè)帶權(quán)周轉(zhuǎn)時(shí)間和平均

作業(yè)帶權(quán)周轉(zhuǎn)時(shí)間如果作業(yè)i的周轉(zhuǎn)時(shí)間為ti，所需運(yùn)行時(shí)間為tk，則稱wi=ti/tk為該作業(yè)的帶權(quán)周轉(zhuǎn)時(shí)間。ti是等待時(shí)間與運(yùn)行時(shí)間之和，故帶權(quán)周轉(zhuǎn)時(shí)間總大于1。平均作業(yè)帶權(quán)周轉(zhuǎn)時(shí)間W=(Σwi)/n1.先來先服務(wù)調(diào)度算法,first-comefirst-server,FCFS(非搶占）批處理系統(tǒng)中的調(diào)度

1.先來先服務(wù)調(diào)度算法先來先服務(wù)算法-特點(diǎn)按照作業(yè)進(jìn)入系統(tǒng)的先后次序來挑選作業(yè)，先進(jìn)入系統(tǒng)的作業(yè)優(yōu)先被挑選。算法容易實(shí)現(xiàn)，效率不高，只顧及作業(yè)等候時(shí)間，沒考慮作業(yè)要求服務(wù)時(shí)間的長短，不利于短作業(yè)而優(yōu)待了長作業(yè)。

短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法(ShortestJobFirst,SJF)-非搶占，是指對(duì)短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法。它們可以分別用于作業(yè)調(diào)度和進(jìn)程調(diào)度。短作業(yè)優(yōu)先(SJF)的調(diào)度算法，是從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。而短進(jìn)程優(yōu)先(SPF)調(diào)度算法，則是從就緒隊(duì)列中選出一估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機(jī)時(shí)，再重新調(diào)度。2.短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法FCFS和SJF調(diào)度算法的性能(1)該算法對(duì)長作業(yè)不利，如作業(yè)C的周轉(zhuǎn)時(shí)間由10增至16，其帶權(quán)周轉(zhuǎn)時(shí)間由2增至3.1。更嚴(yán)重的是，如果有一長作業(yè)(進(jìn)程)進(jìn)入系統(tǒng)的后備隊(duì)列(就緒隊(duì)列)，由于調(diào)度程序總是優(yōu)先調(diào)度那些(即使是后進(jìn)來的)短作業(yè)(進(jìn)程)，將導(dǎo)致長作業(yè)(進(jìn)程)長期不被調(diào)度。(2)該算法完全未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)(進(jìn)程)會(huì)被及時(shí)處理。(3)由于作業(yè)(進(jìn)程)的長短只是根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定的，而用戶又可能會(huì)有意或無意地縮短其作業(yè)的估計(jì)運(yùn)行時(shí)間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。SJ(P)F的缺點(diǎn)17版權(quán)所有，轉(zhuǎn)載請(qǐng)注明出處17進(jìn)程調(diào)度的三個(gè)層次進(jìn)程調(diào)度高級(jí)調(diào)度：也稱作業(yè)調(diào)度，決定哪些程序可以進(jìn)入系統(tǒng)中級(jí)調(diào)度：也稱內(nèi)存調(diào)度，決定內(nèi)存中程序的位置和狀態(tài)低級(jí)調(diào)度：也稱進(jìn)程調(diào)度，決定CPU資源在就緒進(jìn)程間的分配思考：內(nèi)存中可以保留的進(jìn)程個(gè)數(shù)？18版權(quán)所有，轉(zhuǎn)載請(qǐng)注明出處18交互式系統(tǒng)中的調(diào)度

1.時(shí)間片輪轉(zhuǎn)調(diào)度進(jìn)程調(diào)度RoundRobinSchedulinglistofrunnableprocesseslistofrunnableprocessesafterBusesupitsquantum19版權(quán)所有，轉(zhuǎn)載請(qǐng)注明出處191.時(shí)間片輪轉(zhuǎn)調(diào)度

核心思想：每個(gè)進(jìn)程運(yùn)行固定的時(shí)間片，然后調(diào)入下一個(gè)進(jìn)程，搶占；如何確定時(shí)間片的大??？實(shí)現(xiàn)機(jī)理：維護(hù)就緒進(jìn)程隊(duì)列，采用FIFO方式一次讀取，特殊控制：時(shí)間片內(nèi)發(fā)生阻塞或結(jié)束，則立即放棄時(shí)間片優(yōu)缺點(diǎn)分析優(yōu)點(diǎn)：絕對(duì)公平缺點(diǎn)：公平即合理嗎？時(shí)間片如何設(shè)計(jì)才能保證效率？結(jié)論：P82進(jìn)程調(diào)度20版權(quán)所有，轉(zhuǎn)載請(qǐng)注明出處202.優(yōu)先級(jí)調(diào)度

核心思想：為每個(gè)進(jìn)程賦予不同級(jí)別的優(yōu)先級(jí)，越高越優(yōu)先實(shí)現(xiàn)機(jī)理：維護(hù)一個(gè)優(yōu)先級(jí)隊(duì)列，自頂向下依次讀取特殊控制：靜態(tài)優(yōu)先級(jí)與動(dòng)態(tài)優(yōu)先級(jí)（時(shí)鐘滴答、I/O密集型進(jìn)程獲得更高的優(yōu)先級(jí)）概念優(yōu)缺點(diǎn)分析優(yōu)點(diǎn)：響應(yīng)時(shí)間快，易于調(diào)整。最通用的方法。缺點(diǎn)：死規(guī)則，如何保證周轉(zhuǎn)時(shí)間和吞吐量？饑餓現(xiàn)象進(jìn)程調(diào)度2.優(yōu)先級(jí)調(diào)度Aschedulingalgorithmwithfourpriorityclasses2優(yōu)先級(jí)調(diào)度例子UNIX：preemptive+dynamicpriority（可搶占CPU動(dòng)態(tài)優(yōu)先數(shù)）。計(jì)算公式：p_pri=min{127,USER+p_cpu/16+p_nice}定義USER=100；p_cpu:運(yùn)行進(jìn)程每20ms加1（優(yōu)先級(jí)降低），其它進(jìn)程每1200ms減10（優(yōu)先級(jí)提高）；p_nice:可以通過系統(tǒng)調(diào)用nice(…)修改的量：規(guī)定用戶進(jìn)程0~20之間（低），系統(tǒng)進(jìn)程-20~+20之間（高）。3.多級(jí)隊(duì)列為減少進(jìn)程之間的切換時(shí)間，高優(yōu)先級(jí)的分配較少的時(shí)間片，而低優(yōu)先級(jí)的分配較大的時(shí)間片；例如：XDS940系統(tǒng)上：終端、I/O、短時(shí)間片、長時(shí)間片通過降低計(jì)算密集型（后臺(tái)）進(jìn)程的優(yōu)先級(jí)，來照顧交互用戶和短作業(yè)進(jìn)程；4.最短進(jìn)程優(yōu)先最短響應(yīng)時(shí)間進(jìn)程優(yōu)先如何找到運(yùn)行最短的進(jìn)程“老化”算法：通過測(cè)量當(dāng)前值和先前的估計(jì)值進(jìn)行加權(quán)平均來得到下一個(gè)估計(jì)值的技術(shù)；25版權(quán)所有，轉(zhuǎn)載請(qǐng)注明出處255.彩票調(diào)度算法

核心思想：保證響應(yīng)速度最快、依據(jù)進(jìn)程對(duì)CPU資源的需求量調(diào)度實(shí)現(xiàn)機(jī)理：維護(hù)定量的彩票，不同進(jìn)程獲取數(shù)量不同，隨機(jī)選擇特殊控制：彩票交換：進(jìn)程間可以動(dòng)態(tài)自主調(diào)節(jié)調(diào)度順序優(yōu)缺點(diǎn)分析優(yōu)點(diǎn)：響應(yīng)速度最快、CPU利用率最高缺點(diǎn)：OS實(shí)現(xiàn)機(jī)制復(fù)雜、吞吐量和周轉(zhuǎn)時(shí)間無法保證進(jìn)程調(diào)度26版權(quán)所有，轉(zhuǎn)載請(qǐng)注明出處26

實(shí)時(shí)調(diào)度針對(duì)于專用領(lǐng)域和專用應(yīng)用目的必須具備前提條件才能進(jìn)行實(shí)時(shí)調(diào)度特點(diǎn)：系統(tǒng)規(guī)模小、中斷時(shí)間短、進(jìn)程切換快、OS管理深度高如：多媒體OS中；實(shí)時(shí)系統(tǒng)包括監(jiān)控系統(tǒng)、自動(dòng)駕駛系統(tǒng)、安全控制系統(tǒng)等，這些系統(tǒng)中，遲到的響應(yīng)即使正確，也和沒有響應(yīng)一樣糟糕。進(jìn)程調(diào)度周期性和非周期性事件實(shí)時(shí)系統(tǒng)響應(yīng)的事件可劃分為周期性事件和非周期性事件。例如，m個(gè)周期性事件，事件i的周期為Pi，每個(gè)事件需要Ci秒的CPU時(shí)間來處理，則只有滿足以下條件：

C1/P1+C2/P2+…+Cm/Pm≤1

時(shí)，才可能處理所有的負(fù)載。滿足該條件的實(shí)時(shí)系統(tǒng)稱作任務(wù)可調(diào)度的（schedulable）。軟實(shí)時(shí)系統(tǒng)一個(gè)軟實(shí)時(shí)系統(tǒng)處理三個(gè)事件流，其周期分別為100ms，200ms和500ms，如果事件處理時(shí)間分別為50ms，30ms和100ms，則這個(gè)系統(tǒng)是可調(diào)度的，因?yàn)?.5+0.15+0.2≤1如果加入周期為1秒的第4個(gè)事件，則只要其處理時(shí)間不超過150ms，該系統(tǒng)仍將時(shí)可調(diào)度的。（忽略進(jìn)程的切換時(shí)間）29版權(quán)所有，轉(zhuǎn)載請(qǐng)注明出處29反思：如何實(shí)現(xiàn)進(jìn)程調(diào)度？

調(diào)度機(jī)制,schedulingmechanism不同調(diào)度算法適用于不同環(huán)境和不同目的調(diào)度算法一旦固定，則其最優(yōu)、最壞情況均無法避免如能根據(jù)具體情況動(dòng)態(tài)調(diào)整，則效果更佳調(diào)度策略,schedulingpolicy為用戶提供改變調(diào)整調(diào)度機(jī)制的渠道實(shí)現(xiàn)方法——提供系統(tǒng)調(diào)用，能夠改變調(diào)度機(jī)制結(jié)論,softwareengineer盡量使調(diào)度策略（由用戶進(jìn)程決定）和調(diào)度機(jī)制（由OS或內(nèi)核決定）分離；進(jìn)程調(diào)度30版權(quán)所有，轉(zhuǎn)載請(qǐng)注明出處30小結(jié)（2）

進(jìn)程調(diào)度的基本概念調(diào)度原則各種評(píng)價(jià)指標(biāo)的計(jì)算方法經(jīng)典的進(jìn)程調(diào)度機(jī)制不同調(diào)度算法的應(yīng)用環(huán)境、針對(duì)目標(biāo)各不相同從簡單到復(fù)雜，體現(xiàn)了OS歷史發(fā)展潮流調(diào)度策略的思考OS設(shè)計(jì)的關(guān)鍵——調(diào)度策略調(diào)度策略的實(shí)現(xiàn)方法——對(duì)調(diào)度機(jī)制的管理進(jìn)程調(diào)度31內(nèi)容提要進(jìn)程死鎖資源軌跡圖銀行家算法內(nèi)容提要32進(jìn)程死鎖原理死鎖舉例進(jìn)程A：獲得CD-ROM使用權(quán)，申請(qǐng)打印機(jī)進(jìn)程B：獲得打印機(jī)使用權(quán)，申請(qǐng)CD-ROM死鎖：此時(shí)進(jìn)程A、B均被阻塞，無法運(yùn)行進(jìn)程死鎖進(jìn)程A進(jìn)程B打印機(jī)CD-ROM33如何理解死鎖概念基礎(chǔ)資源、可剝奪資源與不可剝奪資源（打印機(jī)、磁盤）可剝奪資源會(huì)造成死鎖嗎？（舉例）對(duì)比理解死鎖與互斥有哪些異同？-使用信號(hào)量避免死鎖，P93,無死鎖和有死鎖的編碼；操作系統(tǒng)為什么要解決死鎖問題？在所有的操作系統(tǒng)中都會(huì)發(fā)生死鎖問題嗎？進(jìn)程死鎖34死鎖的定義進(jìn)程死鎖若一個(gè)進(jìn)程集合中的每一個(gè)進(jìn)程都在等待只能由本集合中其他進(jìn)程引發(fā)的事件。則這種情況為死鎖。假設(shè)每個(gè)進(jìn)程只有一個(gè)線程，并且被阻塞的進(jìn)程不能被中斷所喚醒，即自動(dòng)釋放自己所占用的資源；35死鎖發(fā)生的條件進(jìn)程死鎖Coffman1971互斥條件：每一個(gè)資源或者空閑，或者被分配給一個(gè)進(jìn)程保持和等待條件：已占有某些資源的進(jìn)程需申請(qǐng)新的資源后方可繼續(xù)運(yùn)行非剝奪條件：被進(jìn)程占用的資源不可剝奪，只能被進(jìn)程本身顯式釋放循環(huán)等待條件：系統(tǒng)必然存在一條由兩個(gè)或兩個(gè)以上進(jìn)程組成的循環(huán)鏈，該循環(huán)鏈中每個(gè)進(jìn)程都在等待臨近的進(jìn)程釋放資源-P93；36死鎖的形式化描述基于有向圖描述死鎖條件–死鎖建模Holt，1972進(jìn)程死鎖資源分配圖HowdeadlockoccursABC死鎖的產(chǎn)生1Howdeadlockcanbeavoided(o)(p)(q)死鎖的產(chǎn)生239死鎖處理策略不理會(huì)死鎖原因：為什么耗費(fèi)大量的時(shí)間在小概率事件上呢？死鎖檢測(cè)與恢復(fù)目標(biāo)：檢測(cè)死鎖發(fā)生，通過撤銷進(jìn)程恢復(fù)系統(tǒng)運(yùn)行死鎖預(yù)防目標(biāo)：對(duì)進(jìn)程加以適當(dāng)限制以防止死鎖情況發(fā)生,仔細(xì)控制對(duì)資源的分配；死鎖避免目標(biāo)：不對(duì)進(jìn)程加以限制，由操作系統(tǒng)完成死鎖預(yù)防，進(jìn)程死鎖40鴕鳥算法OstrichAlgorithm核心思想：忽略死鎖問題原因：死鎖問題的發(fā)生是小概率事件OS中的每一種表都代表了一種有限的資源，都可能發(fā)生死鎖舉例：對(duì)系統(tǒng)運(yùn)行的最大程序數(shù)目的限制（PCB的表項(xiàng)）；UNIXandWindowstakesthisapproachItisatradeoffbetweenconveniencecorrectness進(jìn)程死鎖41死鎖檢測(cè)與恢復(fù)核心思想：將系統(tǒng)從死鎖中解脫方法動(dòng)機(jī)：與其耗費(fèi)大量時(shí)間來避免死鎖的發(fā)生，不如采取有效的手段解決死鎖死鎖檢測(cè)的解決方法每個(gè)類型的資源只有一個(gè)每個(gè)類型的資源有多個(gè)何時(shí)檢測(cè)？每當(dāng)有資源申請(qǐng)時(shí)就去檢測(cè)；每隔K分鐘，檢測(cè)CPU的使用率，如果降低到一定的閥值以下，就進(jìn)行死鎖檢測(cè)；進(jìn)程死鎖42死鎖檢測(cè)算法簡介每個(gè)類型的資源只有一個(gè)，基于圖和集合的算法檢測(cè)是否有閉環(huán)建立資源分配圖結(jié)構(gòu)，記錄了所有的進(jìn)程、資源和有向邊從任一結(jié)點(diǎn)開始進(jìn)行深度優(yōu)先遍歷，如找到閉環(huán)則結(jié)束如某條遍歷路徑已經(jīng)到達(dá)終點(diǎn)，則回退至上一結(jié)點(diǎn)，繼續(xù)重復(fù)此過程–P97進(jìn)程死鎖DetectionwithOneResourceofEachType(1)NotetheresourceownershipandrequestsAcyclecanbefoundwithinthegraph,denotingdeadlock44死鎖檢測(cè)算法簡介每個(gè)類型的資源有多個(gè)，基于矩陣和向量比較方法檢測(cè)是否存在死鎖建立現(xiàn)有資源標(biāo)量、可用資源標(biāo)量、當(dāng)前分配矩陣、請(qǐng)求矩陣等數(shù)據(jù)結(jié)構(gòu)對(duì)當(dāng)前分配矩陣，尋找可滿足資源需求的進(jìn)程，對(duì)其標(biāo)記，并釋放其所占用的資源；如果有進(jìn)程沒有被標(biāo)記，說明該進(jìn)程是死鎖進(jìn)程進(jìn)程死鎖DetectionwithOneResourceofEachType(2)Datastructuresneededbydeadlockdetectionalgorithm，注意C矩陣、R矩陣和E、A向量之間的關(guān)系，公式，P98DetectionwithOneResourceofEachType(3)Anexampleforthedeadlockdetectionalgorithm47死鎖檢測(cè)與恢復(fù)死鎖恢復(fù)的解決方法-重新分配資源進(jìn)行資源搶占：將某個(gè)進(jìn)程的資源強(qiáng)制性分配給其他進(jìn)程，取決于資源是否可以強(qiáng)行剝奪！利用回退恢復(fù)：設(shè)定檢查點(diǎn)，發(fā)現(xiàn)存在死鎖情況后則回退殺死進(jìn)程恢復(fù)：直接殺掉占用資源的進(jìn)程，使得其他進(jìn)程得以運(yùn)行；最關(guān)鍵的問題是選擇殺死哪一個(gè)進(jìn)程，以及如何處理進(jìn)程的原工作所帶來的后果；進(jìn)程死鎖48死鎖預(yù)防核心思想：對(duì)進(jìn)程加以限制防止死鎖發(fā)生設(shè)計(jì)思路：針對(duì)四個(gè)死鎖條件，逐一避免具體解決方法——但都有些不實(shí)用互斥條件：使用Spooling技術(shù)來管理設(shè)備，保持和等待條件：資源可用性決定資源分配，在開始就請(qǐng)求分配所有資源；不可剝奪條件：由系統(tǒng)直接剝奪此類資源循環(huán)鏈條件：資源編號(hào)，按預(yù)定規(guī)則申請(qǐng)，P104；進(jìn)程死鎖DeadlockPrevention

AttackingtheMutualExclusionConditionSomedevices(suchasprinter)canbespooledonlytheprinterdaemonusesprinterresourcethusdeadlockforprintereliminatedNotalldevicescanbespooledPrinciple:avoidassigningresourcewhennotabsolutelynecessaryasfewprocessesaspossibleactuallyclaimtheresourceAttackingtheHoldandWaitConditionRequireprocessestorequestresourcesbeforestartingaprocessneverhastowaitforwhatitneedsProblemsmaynotknowrequiredresourcesatstartofrunalsotiesupresourcesotherprocessescouldbeusingVariation:processmustgiveupallresourcesthenrequestallimmediatelyneededAttackingtheNoPreemptionConditionThisisnotaviableoptionConsideraprocessgiventheprinterhalfwaythroughitsjobnowforciblytakeawayprinter!!??

Normallyorderedresources，Aresourcegraph；b圖只有在A申請(qǐng)j和B同時(shí)申請(qǐng)i時(shí)才死鎖；可以規(guī)定各個(gè)進(jìn)程，都必須按升序來申請(qǐng)各個(gè)所需資源，或者僅要求進(jìn)程只能申請(qǐng)比當(dāng)前所占有的資源號(hào)高的資源，從而避免死鎖，p104；(a)(b)AttackingtheCycleWaitingConditionSummaryofapproaches

todeadlockpreventionOtherIssues

Two-PhaseLockingPhaseOneprocesstriestolockallrecordsitneeds,oneatatimeifneededrecordfoundlocked,startover(norealworkdoneinphaseone)Ifphaseonesucceeds,itstartssecondphase,performingupdatesreleasinglocksNotesimilaritytorequestingallresourcesatonceAlgorithmworkswhereprogrammercanarrangeprogramcanbestopped,restartedNonresourceDeadlocksPossiblefortwoprocessestodeadlockeachiswaitingfortheothertodosometaskCanhappenwithsemaphoreseachprocessrequiredtodoadown()ontwosemaphores(mutexandanother)ifdoneinwrongorder,deadlockresultsForexample,Producer-ConsumerProblemStarvationAlgorithmtoallocatearesourcemaybetogivetoshortestjobfirstForexample，SJF：WorksgreatformultipleshortjobsinasystemMaycauselongjobtobepostponedindefinitely,eventhoughnotblockedSolution:First-come,first-servepolicy57死鎖避免核心思想：不對(duì)進(jìn)程進(jìn)行限制，預(yù)防死鎖設(shè)計(jì)思路：操作系統(tǒng)分析資源分配情況防止死鎖核心思想安全狀態(tài)：存在某種資源調(diào)度順序，保證所有進(jìn)程正常運(yùn)行完成，則稱該狀態(tài)為安全狀態(tài)不安全狀態(tài)：不存在可滿足所有進(jìn)程正常運(yùn)行的資源調(diào)度順序，則稱該狀態(tài)為不安全狀態(tài)具體實(shí)現(xiàn)方法資源軌跡圖：針對(duì)兩個(gè)進(jìn)程的死鎖避免銀行家算法：單種資源和多種資源的算法進(jìn)程死鎖58使用資源軌跡圖方法避免死鎖針對(duì)兩個(gè)進(jìn)程、兩種資源的死鎖避免方法條件：兩個(gè)進(jìn)程A和B，兩種資源“打印機(jī)”和“繪圖儀”根據(jù)指令運(yùn)行過程來判斷是否發(fā)生死鎖進(jìn)程A：P點(diǎn)啟動(dòng)，I1~I3使用打印機(jī)，I2~I4使用繪圖儀；進(jìn)程B：Q點(diǎn)啟動(dòng)，I5~I7使用繪圖儀，I6~I8使用打印機(jī)；進(jìn)程死鎖59使用資源軌跡圖方法避免死鎖進(jìn)程死鎖A、B不能同時(shí)進(jìn)入不安全區(qū)域，如在t點(diǎn)OS只能掛起B(yǎng)，執(zhí)行A到I4，P10060單種資源銀行家算法核心思想記錄每個(gè)進(jìn)程的已有資源（已貸金額）和所需最大資源數(shù)（貸款額度）對(duì)每一個(gè)資源請(qǐng)求（再次申請(qǐng)貸款金額）進(jìn)行檢查，判斷是否會(huì)造成不安全（信用危機(jī)）如果不安全則不分配，從而避免死鎖（破產(chǎn)）方法分析對(duì)任何資源