第三章處理機調(diào)度與死鎖

3.1處理機調(diào)度的層次3.2調(diào)度隊列模型和調(diào)度準則3.3調(diào)度算法3.4實時調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預防死鎖的方法3.7死鎖的檢測與解除1處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第1頁!教學目的與要求理解處理機調(diào)度的概念和調(diào)度的層次掌握各種作業(yè)、進程調(diào)度算法和實時調(diào)度算法理解死鎖的基本概念掌握死鎖的處理方法教學重點：各種作業(yè)、進程調(diào)度算法和死鎖的處理方法等。教學難點：作業(yè)、進程調(diào)度算法,死鎖2處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第2頁!3.1處理機調(diào)度的層次對資源進行有效的調(diào)度是非常必要的，我們生活中也會經(jīng)常遇到，如：調(diào)度銀行出納員服務顧客請求問題等。CPU是計算機系統(tǒng)中的一個十分重要的資源，對它進行高效的調(diào)度是操作系統(tǒng)設計的中心問題之一。

3處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第3頁!3.1處理機調(diào)度的層次3.1.1高級調(diào)度

（作業(yè)調(diào)度、長程調(diào)度、接納調(diào)度）1、作業(yè)和作業(yè)步作業(yè)：包含程序、數(shù)據(jù)和作業(yè)說明書。作業(yè)步：作業(yè)執(zhí)行過程中的每一個加工步驟作業(yè)流：作業(yè)進入系統(tǒng)，依次存于外存形成作業(yè)流2、作業(yè)控制塊（JCB）它是作業(yè)在系統(tǒng)中存在的標志，其中保存了系統(tǒng)對作業(yè)進行管理和調(diào)度所需的全部信息。內(nèi)容：作業(yè)標識，用戶名，作業(yè)類型，作業(yè)狀態(tài)，調(diào)度信息等進入系統(tǒng)－>建立JCB->插入相應后備隊列->作業(yè)調(diào)度->作業(yè)控制－>作業(yè)結束－>回收資源4處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第4頁!3.1.2低級調(diào)度（進程調(diào)度，短程調(diào)度）主要是決定就緒隊列中的哪個進程應獲得處理機，然后由分派程序（Dispatcher）分派處理機。1.低級調(diào)度的功能：保存處理機現(xiàn)場信息按某種算法選取進程把處理機分配給進程2.進程調(diào)度的三個進步機制排隊器分派器上下文切換機制：兩對切換5處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第5頁!3.進程調(diào)度方式：1)非搶占方式：

簡單、系統(tǒng)開銷小，實時性差(如win31)2)搶占方式（1）優(yōu)先權原則（2）短進程優(yōu)先原則（3）時間片原則引起進程調(diào)度的因素有哪些？進程正常終止或異常終止進程因某種原因阻塞：I/O請求；wait操作等時間片用完搶占方式下，就緒隊列中某進程的優(yōu)先權比當前執(zhí)行的進程高6處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第6頁!3.2調(diào)度的隊列模型和調(diào)度準則1.僅有進程調(diào)度的隊列模型就緒隊列CPU阻塞隊列交互用戶時間片完進程調(diào)度進程完成等待事件事件出現(xiàn)7處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第7頁!3.具有三級調(diào)度的隊列模型就緒隊列CPU就緒、掛起隊列時間片完進程調(diào)度進程完成后備隊列阻塞、掛起隊列事件出現(xiàn)作業(yè)調(diào)度阻塞隊列等待事件掛起事件出現(xiàn)中級調(diào)度交互型作業(yè)8處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第8頁!1、面向用戶的準則平均周轉(zhuǎn)時間

平均帶權

可見帶權w越小越好,Ts為實際服務時間。3.1.3選擇調(diào)度方式和算法的若干準則

9處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第9頁!2、面向系統(tǒng)的準則（1）吞吐量高（特別是批處理）：單位時間完成作業(yè)數(shù)（2）處理機利用率好：（因CPU貴，特別是大中型多用戶系統(tǒng)）（3）各類資源的平衡利用。3.1.3選擇調(diào)度方式和算法的若干準則

10處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第10頁!

先來先服務算法實例11處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第11頁!3.3.2高優(yōu)先權優(yōu)先調(diào)度算法1.優(yōu)先權調(diào)度算法類型非搶占式優(yōu)先權算法搶占式優(yōu)先權算法，實時性更好。2.優(yōu)先權類型：1）靜態(tài)優(yōu)先權：進程優(yōu)先權在整個運行期不變。確定優(yōu)先權依據(jù)進程類型進程對資源的需求；根據(jù)用戶需求。特點：簡單，但低優(yōu)先權作業(yè)可能長期不被調(diào)度（饑餓）。（例子MITIBM7049）12處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第12頁!常見的批處理作業(yè)調(diào)度算法先來先服務算法（FCFS：FirstComeFirstServe）最短作業(yè)優(yōu)先算法（SJF：ShortestJobFirst）最短剩余時間優(yōu)先（SRTF:ShortestRemainingTimeFirst）最高響應比優(yōu)先算法（HRRF：HighestResponseRatioFirst）響應比R=響應時間/要求服務時間 =（等待時間+要求服務時間）/要求服務時間=1+（等待時間/要求服務時間）13處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第13頁!14處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第14頁!15處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第15頁!16處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第16頁!17處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第17頁!18處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第18頁!3.2.3基于時間片的輪轉(zhuǎn)調(diào)度算法（2）2.多級反饋隊列調(diào)度特點：長、短作業(yè)兼顧，有較好的響應時間短作業(yè)一次完成；中型作業(yè)周轉(zhuǎn)時間不長；大型作業(yè)不會長期不處理。19處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第19頁!進程調(diào)度算法對下表，分別采用先來先服務（FCFS）、非搶占最短進程優(yōu)先（SPF）及搶占的最短剩余時間優(yōu)先（SRT）、高響應比優(yōu)先（HRRN）、時間片輪轉(zhuǎn)（RR,時間片q=1）、多級反饋隊列（FB，第i級隊列的時間片=2i-1）調(diào)度算法進行CPU調(diào)度，求出各進程的執(zhí)行情況以及平均周轉(zhuǎn)時間和平均帶權周轉(zhuǎn)時間。進程到達時間服務時間A03B26C44D65E8220處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第20頁!

短作業(yè)/進程優(yōu)先（SJ(P)F）

降低對長進程有利的一種方法就是短進程優(yōu)先策略：表SPF的調(diào)度性能進程到達時間Tin服務時間Tr開始時間Ts結束時間Tc

=1.84031115939152011TA=3TB=7TC=11TD=14TE=3=7.608364522046ABCDE→→→→WE=1.50WA=1WB=1.17WC=2.75WD=2.80ECDAB周轉(zhuǎn)時間T=結束時間Tc-到達時間Tin=3-0=3周轉(zhuǎn)時間T帶權周轉(zhuǎn)時間W=周轉(zhuǎn)時間T/服務時間Tr=3/3=1帶權周轉(zhuǎn)時間W平均結束下一步下一步下一步下一步下一步下一步下一步21處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第21頁!

表HRRN的調(diào)度性能進程到達時間Tin服務時間Tr開始時間Ts結束時間Tc

=2.14039151339132015TA=3TB=7TC=9TD=14TE=7=8.008364522046ABCDE→→→→WE=3.50WA=1WB=1.17WC=2.25WD=2.80ECDAB周轉(zhuǎn)時間T=結束時間Tc-到達時間Tin=3-0=3周轉(zhuǎn)時間T帶權周轉(zhuǎn)時間W=周轉(zhuǎn)時間T/服務時間Tr=3/3=1帶權周轉(zhuǎn)時間W平均=[(9-4)+4]/4=2.25=[(9-6)+5]/5=1.6=[(9-8)+2]/2=1.5RCRDRERD=[(13-6)+5]/5=2.4RE=[(13-8)+2]/2=3.5結束下一步下一步下一步下一步下一步

最高響應比（HRRN）22處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第22頁!進程調(diào)度算法

最短剩余時間（SRT）

SRT是針對SPF增加了強占機制的一種調(diào)度算法，它總是選擇預期剩余時間最短的進程。只要新進程就緒，且有更短的剩余時間，調(diào)度程序就可能搶占當前正在運行的進程。SRT不象FCFS偏向長進程，也不象輪轉(zhuǎn)法（下個算法）產(chǎn)生額外的中斷，從而減少了開銷。必須記錄過去的服務時間，從而增加了開銷。從周轉(zhuǎn)時間來看，SRT比SPF有更好的性能。處理機調(diào)度

23處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第23頁!不同調(diào)度算法的性能對比分析:進程到達時間Tin服務時間Tr從平均周轉(zhuǎn)時間及其平均帶權周轉(zhuǎn)時間來看，SRT好于前面的任何一個算法。A03B26C44D65E82FCFS8.602.56SPF7.601.84HRRN8.002.14SRT7.201.5924處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第24頁!調(diào)度算法（對同樣進程情況下，5個算法比較）FCFSABCDESPFABCDEHRRNABCDESRT

ABCDERRAq=1

BCDE

05101520各種調(diào)度算法的比較25處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第25頁!HRRFRR(q=1)FB(q=2i-1)（不立即搶占）FB(q=2i-1)（立即搶占）26處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第26頁!算法比較項FCFSRRSJFSRTHRPMFQ調(diào)度方式非搶占式搶占式(按時間片)非搶占式搶占式(進程到達)非搶占式搶占式(按時間片)吞吐量不突出時間片太小,可能變低高高高不突出響應時間可能很高，對于短進程提供良好的響應時間對短作業(yè)/進程提供良好響應時間提供良好的響應時間提供良好的響應時間不突出開銷最小低可能高可能高可能高可能高對進程的作用不利于短作業(yè)/進程和I/O忙型公平對待不利于長作業(yè)/進程不利于長進程良好的均衡（進程）可能偏向I/O繁忙的作業(yè)/進程饑餓問題無無可能可能無可能各種常用調(diào)度算法的比較表不適合作業(yè)調(diào)度27處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第27頁!解：（1）作業(yè)A、B、C、D進入內(nèi)存時刻分別為：10:00、10:20、11:10、10:50。它們的結束時刻為：11:10、10:50、12:00、12:20。（2）作業(yè)A、B、C、D的周轉(zhuǎn)時間分別為70，30，90，90分鐘，平均周轉(zhuǎn)時間為70分鐘。ABCD28處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第28頁!3.4.1實現(xiàn)實時調(diào)度的基本條件3.采用搶占調(diào)度方式剝奪方式：一般都采用此方式非剝奪方式（實現(xiàn)簡單）：一般應使實時任務較小，以及時放棄CPU。4.具有快速切換機制具有快速響應外部中斷能力?？焖偃蝿辗峙?.3實時調(diào)度29處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第29頁!進程1進程2進程n實時進程調(diào)度時間實時進程請求調(diào)度調(diào)度實時進程運行a非搶占式輪轉(zhuǎn)調(diào)度當前進程實時進程實時進程請求調(diào)度當前進程運行完成b非搶占式優(yōu)先權調(diào)度調(diào)度時間30處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第30頁!3.4.3常用的幾種實時調(diào)度算法1.最早截止時間優(yōu)先EDF（earliestdeadlinefirst)算法根據(jù)任務的截止時間來確定任務的優(yōu)先級截止時間越早，優(yōu)先級越高可以是搶占式或非搶占式31處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第31頁!圖3－10最早截止時間優(yōu)先算法用于搶占調(diào)度方式之例32處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第32頁!假如一個實時系統(tǒng)中有兩個周期性實時任務，A和B，任務A要求每20ms執(zhí)行一次，執(zhí)行時間為10ms；任務B只要求每50ms執(zhí)行一次，執(zhí)行時間25ms。對于A，合適截止時間依次為20、40、60、80、100…;對于B，合適截止時間依次為50、100、150…;圖3-11給出了A和B截止的時間點。

圖3-11A和B任務每次必須完成的時間020406080100120140160180200AAAAAAAAAAtBBBB

最低松弛度優(yōu)先（LLF）

33處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第33頁!34處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第34頁!3.5產(chǎn)生死鎖的原因和必要條件3.5.1產(chǎn)生死鎖的原因。1、競爭資源引起死鎖。1）可剝奪（CPU、內(nèi)存）和非剝奪性（打印機，磁帶機）資源2）競爭非剝奪性資源——可造成死鎖p1p2R1R2圖3-13I/O設備共享時的死鎖情況35處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第35頁!2、進程推進順序不當引起死鎖。213DP2Req(R2)P2Req(R1)P1Req(R1)P1Req(R2)P2Rel(R2)P2Rel(R1)P1Rel(R1)P1Rel(R2)4圖3-15進程推進順序?qū)λ梨i的影響36處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第36頁!3.5.3處理死鎖的基本方法

1．預防死鎖：破壞4個條件之一：有效，使資源利用率低。2．避免死鎖：防止進入不安全態(tài)。3．檢測死鎖：檢測到死鎖再清除。4．解除死鎖：與“檢測”配套。37處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第37頁!3.6死鎖預防和避免

3.6.1死鎖預防

4、摒棄“環(huán)路等待”條件有序資源分配法：為資源編號，申請時需按編號進行。缺點：（1）新增資源不便，（原序號已排定）（2）資源與進程使用順序不同造成浪費（3）用戶不自由38處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第38頁!39處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第39頁!3.6.2系統(tǒng)的安全狀態(tài)（3）3安全—不安全的轉(zhuǎn)換

上例中，若P3再申請一臺，則不安全進程最大需求已分配可用P11052P242P39340處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第40頁!2．銀行家算法

reqi<=needierrorreqi<=availblockavail=avail-reqialloci=alloci+reqineedi=needi-reqi系統(tǒng)安全？YNYNYN正式將資源分配給進程Pi撤銷本次分配讓進程Pi等待41處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第41頁!4實例圖3-16T0時刻的資源分配表42處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第42頁!4實例圖3-18P1申請資源時的安全性檢查43處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第43頁!3.7死鎖的檢測和解除

3.7.1檢測1.資源分配圖p1p2r1r2圖3-20每類資源有多個時的情況44處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第44頁!Work:=availableL:={Li|alloci=0∩reqi=0}/*孤立進程點*/ForallLiLdoBegin Forallreqi<=workdo Begin Work:=work+alloci L=Li∪L End EndDeadlock:=~(L={p1…pn})3.檢測死鎖的算法：45處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第45頁!3.7.2死鎖的解除（2）

為把系統(tǒng)從死鎖狀態(tài)中解脫出來，所花費的代價可表示為：R(S)min=min{Cui}+min{Cuj}+min{Cuk}+…圖3-22付出代價最小的死鎖解除方法46處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第46頁!解判斷是否發(fā)生死鎖，可用以下經(jīng)驗公式：公式表明，若要系統(tǒng)不發(fā)生死鎖，則進程的最大需求量W不得超過x；若超過則可能導致死鎖。利用資源分配圖舉一個死鎖例子便可。47處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第47頁!例一臺計算機有10臺磁帶機被n個進程競爭，每個進程最多需要3臺磁帶機，那么n最多為_____時，系統(tǒng)沒有死鎖的危險？解：n最大為4。假設有m個資源，每個進程最多可申請k個資源，則系統(tǒng)要想避免死鎖的發(fā)生，允許的最多進程數(shù)n為1+（m-k）/（k-1）。當后面一項是小數(shù)時，總是取小整數(shù)。48處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第48頁!3、作業(yè)調(diào)度將外存作業(yè)調(diào)入內(nèi)存，創(chuàng)建PCB等，插入就緒隊列。一般用于批處理系統(tǒng)，分/實時系統(tǒng)一般直接入內(nèi)存，無此環(huán)節(jié)。調(diào)度特性接納作業(yè)數(shù)（內(nèi)存駐留數(shù)，多道程序度）太多―――> 周轉(zhuǎn)時間T長太少―――> 系統(tǒng)效率低接納策略：即采用何種調(diào)度算法：FCFS、短作業(yè)優(yōu)先等49處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第49頁!CPUSwitchFromProcesstoProcess50處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第50頁!為提高系統(tǒng)吞吐量和內(nèi)存利用率而引入的一內(nèi)--外存對換功能（換出時，進程為掛起或就緒駐外存狀態(tài)）三級調(diào)度的運行頻率低>中>高。3.1.3中級調(diào)度（中程）51處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第51頁!3.2.1調(diào)度的隊列模型2.具有高、低級調(diào)度的隊列模型就緒隊列CPU阻塞隊列時間片完進程調(diào)度進程完成等待事件1事件1出現(xiàn)后備隊列阻塞隊列等待事件2事件2出現(xiàn)作業(yè)調(diào)度52處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第52頁!

3.2.2選擇調(diào)度方式和調(diào)度算法的若干準則1、面向用戶的準則（1）周轉(zhuǎn)時間短（常用于批處理系統(tǒng)）概念：作業(yè)從提交――>完成的時間.分為：駐外存等待調(diào)度時間駐內(nèi)存等待調(diào)度時間執(zhí)行時間阻塞時間53處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第53頁!1、面向用戶的準則（2）響應時間快：（對交互性作業(yè)）概念：鍵盤提交請求到首次響應時間輸入傳送時間處理時間響應傳送時間（3）截止時間的保證（特別是實時系統(tǒng)）（4）優(yōu)先權準則：（即需要搶占調(diào)度）3.1.3選擇調(diào)度方式和算法的若干準則

54處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第54頁!3.3調(diào)度算法——是一個資源分配問題

3.3.1先來先服務和短作業(yè)（進程）優(yōu)先調(diào)度算法1.先來先服務調(diào)度算法（FCFS）特點：簡單，有利于長作業(yè)（進程）即CPU繁忙性作業(yè),不利于短作業(yè)（進程）2.短作業(yè)（進程）優(yōu)先調(diào)度算法：SJ(P)F提高了平均周轉(zhuǎn)時間和平均帶權周轉(zhuǎn)時間（從而提高了系統(tǒng)吞吐量）特點：對長作業(yè)不利，有可能得不到服務估計時間不易確定55處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第55頁!圖3-4FCFS和SJ(P)F比較56處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第56頁!3.3.2高優(yōu)先權優(yōu)先調(diào)度算法(2)

2）動態(tài)優(yōu)先權：如：優(yōu)先權隨執(zhí)行時間而下降，隨等待時間而升高。優(yōu)點：長短兼顧缺點：需經(jīng)常計算各進程優(yōu)先級3.高響應比優(yōu)先調(diào)度算法：響應比Rp=（Tw+Ts）/Ts特點：（1）短作業(yè)RP大。（2）Ts（要求服務時間）相同的進程間相當于FCFS。（3）長作業(yè)等待一段時間仍能得到服務。57處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第57頁!基于優(yōu)先數(shù)調(diào)度算法（HPF：HighestPriorityFirst）（a）由用戶規(guī)定優(yōu)先數(shù)（外部優(yōu)先數(shù)）用戶提交作業(yè)時，根據(jù)急迫程度規(guī)定適當?shù)膬?yōu)先數(shù)，作業(yè)調(diào)度程序根據(jù)JCB優(yōu)先數(shù)決定進入內(nèi)存的次序。（b）由系統(tǒng)計算優(yōu)先數(shù)（內(nèi)部優(yōu)先數(shù)）例：可按如下公式計算作業(yè)的優(yōu)先數(shù)：優(yōu)先數(shù)=用戶規(guī)定優(yōu)先數(shù)–作業(yè)處理時間+作業(yè)等待時間–輸出量58處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第58頁!59處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第59頁!60處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第60頁!61處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第61頁!62處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第62頁!3.2.3基于時間片的輪轉(zhuǎn)調(diào)度算法1.時間片輪轉(zhuǎn)時間片大小的確定太大：退化為FCFS；太?。合到y(tǒng)開銷過大系統(tǒng)對響應時間的要求；T=nq就緒隊列中進程的數(shù)目；系統(tǒng)的處理能力：（應保證一個時間片處理完常用命令）63處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第63頁!就緒隊列1至CPUS1就緒隊列2S2至CPU就緒隊列3S3至CPU就緒隊列nSn至CPU時間片：S1<S2<S3圖3－5多級隊列反饋調(diào)度算法64處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第64頁!

FCFS的調(diào)度性能進程到達時間Tin服務時間Tr開始時間Ts結束時間Tc周轉(zhuǎn)時間T帶權周轉(zhuǎn)時間WA0303TA=3WA=1B2639TB=7WB=1.17C44913TC=9WC=2.25D651318TD=12WD=2.40.E821820TE=12WE=6平均=8.60=2.56同樣，看到進程E的不利情況。

先來先服務（FCFS）

65處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第65頁!

SJF對短作業(yè)有利，明顯的作業(yè)E提前接受了服務，并且整體性能也得到了提高；SJF的問題：

SJF需要事先知道或至少需要估計每個作業(yè)所需的處理機時間。只要不斷的有短作業(yè)進入系統(tǒng)，就有可能使長作業(yè)長期得不到運行而“餓死”。SJF偏向短作業(yè)，不利于分時系統(tǒng)（由于不可搶占性）。

短作業(yè)/進程優(yōu)先（SJF）

66處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第66頁!不同調(diào)度算法對的性能分析:進程到達時間Tin服務時間Tr從平均周轉(zhuǎn)時間及其平均帶權周轉(zhuǎn)時間來看，HRRN剛好介于FCFS與SPF之間，即好于FCFS，次于SPF。A03B26C44D65E82FCFS8.602.56SPF7.601.84HRRN8.002.1467處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第67頁!

表SRT的調(diào)度性能進程到達時間Tin服務時間Tr開始時間Ts結束時間Tc

=1.5903415831582010TA=3TB=13TC=4TD=14TE=2=7.208364522046ABCBE→→→→WE=1.00WA=1WB=2.17WC=1.00WD=2.80ECDAB周轉(zhuǎn)時間T=結束時間Tc-到達時間Tin=3-0=3周轉(zhuǎn)時間T帶權周轉(zhuǎn)時間W=周轉(zhuǎn)時間T/服務時間Tr=3/3=1帶權周轉(zhuǎn)時間W平均01234567891011121314151617181920D→B剩余時間=6-1=5；C剩余時間=4-0=4；0500結束下一步下一步下一步下一步下一步下一步

最短剩余時間（SRT）

68處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第68頁!

表RR的調(diào)度性能進程到達時間Tin服務時間Tr開始時間Ts結束時間Tc

周轉(zhuǎn)時間T帶權周轉(zhuǎn)時間W=2.71025710418172015TA=4TB=16TC=13TD=14TE=7=10.808364522046WE=3.50WA=1.33WB=2.67WC=3.25WD=2.80ECDAB平均

輪轉(zhuǎn)（RR——RoundRobin）

69處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第69頁!FCFSSPF(非搶占)SRT(搶占)70處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第70頁!進程ABCDE平均FCFS完成時間周轉(zhuǎn)時間帶權周轉(zhuǎn)時間331.0971.171392.2518122.420126.08.62.56SPF（非搶占）完成時間周轉(zhuǎn)時間帶權周轉(zhuǎn)時間331.0971.1715112.7520142.81131.57.61.84SPF（搶占）完成時間周轉(zhuǎn)時間帶權周轉(zhuǎn)時間331.015132.16841.020142.81021.07.21.59HRRN完成時間周轉(zhuǎn)時間帶權周轉(zhuǎn)時間331.0971.171392.2520142.81573.582.14RR（q=1）完成時間周轉(zhuǎn)時間帶權周轉(zhuǎn)時間441.3318162.6717133.2520142.81573.510.82.71FB(q=2i-1)（不立即搶占）完成時間周轉(zhuǎn)時間帶權周轉(zhuǎn)時間33117152.518143.520142.81463.010.42.56FB(q=2i-1)（立即搶占）完成時間周轉(zhuǎn)時間帶權周轉(zhuǎn)時間341.3317162.6718112.7520142.81484.010.62.7171處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第71頁!作業(yè)調(diào)度與進程調(diào)度有一個具有兩道作業(yè)的批處理系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)優(yōu)先的調(diào)度算法，進程調(diào)度采用以優(yōu)先數(shù)為基礎的搶占式調(diào)度算法。如下表所示(作業(yè)的優(yōu)先數(shù)即為進程的優(yōu)先數(shù)，優(yōu)先數(shù)越小越好)。（1）列出所有作業(yè)進入內(nèi)存時刻及結束時刻？（2）計算平均周轉(zhuǎn)時間？作業(yè)名到達時間估計運行時間優(yōu)先數(shù)A10:00405B10:20303C10:30504D10:5020672處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第72頁!3.4.1實現(xiàn)實時調(diào)度的基本條件1．提供必要的調(diào)度信息（1）就緒時間；（2）開始/完成截止時間；（3）處理時間；（4）資源要求；（5）優(yōu)先級；2．系統(tǒng)處理能力強3.4實時調(diào)度Ci為處理時間，Pi為周期時間（基于周期性實時任務）73處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第73頁!3.4.2實時調(diào)度算法的分類1.非搶占式調(diào)度算法時間片輪轉(zhuǎn) 秒級非搶占優(yōu)先權 秒-毫秒級2.搶占式調(diào)度算法時鐘中斷搶占優(yōu)先權 毫秒級基于搶占點搶占立即搶占immediatepreemption毫秒-微秒級只要不在臨界區(qū)即搶占（中斷引發(fā)）74處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第74頁!c基于時鐘中斷搶占的優(yōu)先權調(diào)度當前進程實時進程實時進程請求調(diào)度實時進程搶占當前進程，并立即執(zhí)行d立即搶占的優(yōu)先權調(diào)度當前進程實時進程實時進程請求調(diào)度時鐘中斷到來時調(diào)度時間調(diào)度時間75處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第75頁!最早截止時間優(yōu)先算法既可以用于搶占式也可用于非搶占式方式中。圖3-9給出了該算法用于非搶占式調(diào)度方式示例。在該例子中具有四個非周期任務，它們先后到達。任務1任務執(zhí)行→任務到達→任務1t圖3-9EDF算法用于非搶占式點的調(diào)度方式任務3任務4任務2任務2任務3任務4開始截止時間：任務1的任務3的任務4的任務2的結束下一步下一步

最早截止時間優(yōu)先（EDF）

76處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第76頁!2.最低松弛度優(yōu)先LLF算法松弛度：根據(jù)任務緊急（或松弛）的程度，來確定任務的優(yōu)先級。任務的緊急程度越高，該任務的優(yōu)先級就越高，使之優(yōu)先執(zhí)行。若A進程需在200ms時完成，其本身運行需要100ms，當前時刻是10ms，則A的松弛度為：200－100－10＝90主要用于可搶占的調(diào)度方式中在實現(xiàn)該算法時，要求系統(tǒng)中有一個按松弛度排序的實時任務就緒隊列，松弛度最低的（數(shù)值小的）任務排在隊列的前面。77處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第77頁!松弛度=必須完成的時間點-本身所需運行時間-當前時間:A1(10)B1(20)0102030405060708090100t1t2

t3

t4

t5t6

t7

t8

t圖3.12利用LLF算法對兩個周期性實時任務進行調(diào)度A2(10)A3(10)A4(10)B1(5)B2(15)B2(10)初始：t=0時刻，計算A，B松弛度：A1=20–10–0=10B1=50–25–0=25t=10時刻，計算A，B松弛度：A2=40–10–10=20B1=50–25–10=15t=30時刻，計算A，B松弛度：A2=40–10–30=0B1=50–5–30=15t=40時刻，計算A，B松弛度：A3=60–10–40=10B1=50–5–40=5t=45時刻，計算A，B松弛度：A3=60–10–45=5B2=100–25–45=30t=55時刻，計算A，B松弛度：A4=80–10–55=35B2=100–25–55=20t=70時刻，計算A，B松弛度：A4=80–10–70=0B2=100–10–70=20t=80時刻，計算A，B松弛度：A5=100–10–80=10B2=100–10–80=10結束●●下一步下一步下一步下一步下一步下一步下一步下一步

最低松弛度優(yōu)先（LLF）

78處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第78頁!79處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第79頁!3.5產(chǎn)生死鎖的原因和必要條件3）競爭臨時性資源臨時性資源是指由一個進程產(chǎn)生，被另一個進程使用一段時間后便無用的資源。P1P3S3S1P2S2圖3-14進程之間通信時的死鎖80處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第80頁!3.5.2產(chǎn)生死鎖的必要條件1．互斥條件（資源的臨界性）2．請求和保持條件3．不剝奪條件4．環(huán)路等待條件81處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第81頁!3.6死鎖預防和避免

3.6.1死鎖預防

1、互斥條件是資源固有屬性，不能避免。2、摒棄請求和保持條件全分配，全釋放（AND同步p52）優(yōu)點：簡單且安全缺點：（1）資源嚴重浪費 （2）延遲進程運行3、摒棄“不剝奪”條件 增加系統(tǒng)開銷，且進程前段工作可能失效。82處理機調(diào)度與死鎖N共93頁，您現(xiàn)在瀏覽的是第82頁!3.6.2系統(tǒng)的安全狀態(tài)在“避免死鎖”方法中的判斷條件1.安全狀態(tài)系統(tǒng)按某種順序并發(fā)進