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

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

響應時間(responsetime)進程自進入就緒隊列開始至進程占用CPU之間的時間間隔周轉時間(turnaroundtime)進程自進入就緒隊列開始至進程結束之間的時間間隔

CPU吞吐量（throughout)單位時間內運行結束的進程個數(shù)舉例進程調度8SchedulingAlgorithmGoalsP78

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

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

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

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

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

1.時間片輪轉調度進程調度RoundRobinSchedulinglistofrunnableprocesseslistofrunnableprocessesafterBusesupitsquantum19版權所有，轉載請注明出處191.時間片輪轉調度

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

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

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

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

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

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

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

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

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

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