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

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

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

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

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

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

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

作業(yè)帶權(quán)周轉(zhuǎn)時間如果作業(yè)i的周轉(zhuǎn)時間為ti，所需運(yùn)行時間為tk，則稱wi=ti/tk為該作業(yè)的帶權(quán)周轉(zhuǎn)時間。ti是等待時間與運(yùn)行時間之和，故帶權(quán)周轉(zhuǎn)時間總大于1。平均作業(yè)帶權(quán)周轉(zhuǎn)時間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)先被挑選。算法容易實現(xiàn)，效率不高，只顧及作業(yè)等候時間，沒考慮作業(yè)要求服務(wù)時間的長短，不利于短作業(yè)而優(yōu)待了長作業(yè)。

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

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

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

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

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

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

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

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

調(diào)度機(jī)制,schedulingmechanism不同調(diào)度算法適用于不同環(huán)境和不同目的調(diào)度算法一旦固定，則其最優(yōu)、最壞情況均無法避免如能根據(jù)具體情況動態(tài)調(diào)整，則效果更佳調(diào)度策略,schedulingpolicy為用戶提供改變調(diào)整調(diào)度機(jī)制的渠道實現(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)載請注明出處30小結(jié)（2）

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

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

Normallyorderedresources，Aresourcegraph；b圖只有在A申請j和B同時申請i時才死鎖；可以規(guī)定各個進(jìn)程，都必須按升序來申請各個所需資源，或者僅要求進(jìn)程只能申請比當(dāng)前所占有的資源號高的資源，從而避免死鎖，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死鎖避免核心思想：不對進(jìn)程進(jìn)行限制，預(yù)防死鎖設(shè)計思路：操作系統(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)具體實現(xiàn)方法資源軌跡圖：針對兩個進(jìn)程的死鎖避免銀行家算法：單種資源和多種資源的算法進(jìn)程死鎖58使用資源軌跡圖方法避免死鎖針對兩個進(jìn)程、兩種資源的死鎖避免方法條件：兩個進(jìn)程A和B，兩種資源“打印機(jī)”和“繪圖儀”根據(jù)指令運(yùn)行過程來判斷是否發(fā)生死鎖進(jìn)程A：P點(diǎn)啟動，I1~I3使用打印機(jī)，I2~I4使用繪圖儀；進(jìn)程B：Q點(diǎn)啟動，I5~I7使用繪圖儀，I6~I8使用打印機(jī)；進(jìn)程死鎖59使用資源軌跡圖方法避免死鎖進(jìn)程死鎖A、B不能同時進(jìn)入不安全區(qū)域，如在t點(diǎn)OS只能掛起B(yǎng)，執(zhí)行A到I4，P10060單種資源銀行家算法核心思想記錄每個進(jìn)程的已有資源（已貸金額）和所需最大資源數(shù)（貸款額度）對每一個資源請求（再次申請貸款金額）進(jìn)行檢查，判斷是否會造成不安全（信用危機(jī)）如果不安全則不分配，從而避免死鎖（破產(chǎn)）方法分析對任何資源