操作系統(tǒng)第三章-處理機調(diào)度及死鎖課件

第三章處理機調(diào)度與死鎖.第三章處理機調(diào)度與死鎖3.1處理機調(diào)度的層次3.2調(diào)度隊列模型和調(diào)度準(zhǔn)則3.3調(diào)度算法3.4實時調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測與解除.3.1處理機調(diào)度的層次處理機調(diào)度如何分配處理機資源處理機調(diào)度的層次高級調(diào)度(HighLevelScheduling)中級調(diào)度(Intermediate-LevelScheduling)低級調(diào)度(LowLevelScheduling).3.1處理機調(diào)度的層次高級調(diào)度(HighLevelScheduling)也稱為作業(yè)調(diào)度或長程調(diào)度根據(jù)某種算法，把外存上處于后備隊列中的作業(yè)調(diào)入內(nèi)存僅用于批處理系統(tǒng)作業(yè)程序數(shù)據(jù)作業(yè)說明書（包含作業(yè)步）.3.1處理機調(diào)度的層次低級調(diào)度(LowLevelScheduling)也稱為進(jìn)程調(diào)度或短程調(diào)度用于決定就緒隊列中哪個進(jìn)程應(yīng)獲得處理機低級調(diào)度的功能保存CPU現(xiàn)場按某種算法選取進(jìn)程把CPU分派給進(jìn)程進(jìn)程調(diào)度的方式非搶占方式(nonpreemptivemode)搶占方式(preemptivemode).3.1處理機調(diào)度的層次非搶占式調(diào)度(nonpreemptivemode)進(jìn)程獲得CPU之后，可以一直運行下去，直至進(jìn)程完成或因等待某些事件而阻塞引起調(diào)度的原因進(jìn)程執(zhí)行完畢等待某些事件而阻塞通信或同步過程中執(zhí)行了某些原語適用于批處理系統(tǒng)，不適用于實時系統(tǒng).3.1處理機調(diào)度的層次搶占式調(diào)度(preemptivemode)允許調(diào)度程序根據(jù)某種原則暫停正在執(zhí)行的進(jìn)程，將CPU分配給另一個進(jìn)程原則：優(yōu)先權(quán)原則短作業(yè)優(yōu)先原則時間片原則.3.1處理機調(diào)度的層次中級調(diào)度(Intermediate-LevelScheduling)也稱為中程調(diào)度用于決定將哪些進(jìn)程調(diào)出外存或調(diào)入內(nèi)存即如何選擇掛起和激活的進(jìn)程.3.1處理機調(diào)度的層次調(diào)度的層次事件發(fā)生運行就緒時間片到調(diào)度阻塞完成終止靜止阻塞靜止就緒內(nèi)存空間掛起激活事件發(fā)生收容接納掛起激活等待事件進(jìn)程調(diào)度中級調(diào)度作業(yè)調(diào)度中級調(diào)度.3.2調(diào)度隊列模型和調(diào)度準(zhǔn)則面向用戶的調(diào)度準(zhǔn)則周轉(zhuǎn)時間短周轉(zhuǎn)時間：從作業(yè)被提交系統(tǒng)開始，到作業(yè)完成為止的這段時間用于評價批處理系統(tǒng)性能平均周轉(zhuǎn)時間平均帶權(quán)周轉(zhuǎn)時間.3.2調(diào)度隊列模型和調(diào)度準(zhǔn)則面向用戶的調(diào)度準(zhǔn)則響應(yīng)時間快響應(yīng)時間：從用戶通過鍵盤提交一個請求開始，直到系統(tǒng)首次產(chǎn)生響應(yīng)時間為止用于評價分時系統(tǒng)性能截止時間的保證截止時間：某任務(wù)必須開始執(zhí)行的最遲時間，或必須完成的最遲時間用于評價實時系統(tǒng)性能優(yōu)先權(quán)高的任務(wù)優(yōu)先處理用于評價批處理、分時、實時等系統(tǒng).3.2調(diào)度隊列模型和調(diào)度準(zhǔn)則面向系統(tǒng)的調(diào)度準(zhǔn)則系統(tǒng)吞吐量高處理機利用率好各類資源的平衡利用.3.3調(diào)度算法先來先服務(wù)調(diào)度算法(FCFS)FirstComeFirstServe作業(yè)調(diào)度從后備作業(yè)隊列中選擇最先進(jìn)入的一個或幾個作業(yè)，調(diào)入內(nèi)存，創(chuàng)建進(jìn)程，放入就緒隊列進(jìn)程調(diào)度就緒隊列中選擇一個最先進(jìn)入就緒隊列的進(jìn)程，將CPU分配于它.3.3調(diào)度算法先來先服務(wù)調(diào)度算法(FCFS)有利于長作業(yè)（進(jìn)程），不利于短作業(yè)(進(jìn)程)作業(yè)到達(dá)時間Tin服務(wù)時間Tr開始時間TS結(jié)束時間Tc周轉(zhuǎn)時間T帶權(quán)周轉(zhuǎn)時間WA01B1100C21D31000110110211011022021100100199111001.99.3.3調(diào)度算法短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法(SJF/SPF)ShortestJobFirst/ShortestProcessFirst作業(yè)調(diào)度從后備隊列中選擇一個或若干個估計運行時間最短的作業(yè)，將它們調(diào)入內(nèi)存運行進(jìn)程調(diào)度從就緒隊列中選出一估計運行時間最短的進(jìn)程，將處理機分配給它.短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法(SJF/SPF)能有效降低作業(yè)（進(jìn)程）的平均等待時間3.3調(diào)度算法調(diào)度算法進(jìn)程名ABE平均到達(dá)時間01234服務(wù)時間43524FCFS完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間SJF完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間441441762982.671210218163.114115.5631.518143.51392.2592.882.1DC.3.3調(diào)度算法短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法(SJF/SPF)對長作業(yè)（進(jìn)程）不利沒有考慮作業(yè)（進(jìn)程）的緊迫程度需要事先知道或至少需要估計每個作業(yè)（進(jìn)程）所需的處理時間.3.3調(diào)度算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法（HPF）HighestPriorityFirst按作業(yè)或進(jìn)程的優(yōu)先級順序進(jìn)行調(diào)度，優(yōu)先調(diào)度優(yōu)先級高的作業(yè)或進(jìn)程非搶占式優(yōu)先權(quán)算法用于批處理系統(tǒng)搶占式優(yōu)先權(quán)算法用于實時系統(tǒng).3.3調(diào)度算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法（HPF）如何確定進(jìn)程或作業(yè)的優(yōu)先級靜態(tài)優(yōu)先權(quán)進(jìn)程類型進(jìn)程對資源的需求用戶要求動態(tài)優(yōu)先權(quán)就緒隊列中的進(jìn)程，隨其等待時間的增長，其優(yōu)先權(quán)以速率a提高.3.3調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法（HRF）HighestResponseratioFirst響應(yīng)比優(yōu)先調(diào)度響應(yīng)比高的進(jìn)程FCFS強調(diào)等待時間，SJF強調(diào)要求服務(wù)時間，HRF是兩者的折中.3.3調(diào)度算法時間片輪轉(zhuǎn)法（RR）RoundRobin將CPU的處理時間分成固定大小的時間片用于分時系統(tǒng).時間片輪轉(zhuǎn)法（RR）3.3調(diào)度算法調(diào)度算法進(jìn)程名ABCDE平均到達(dá)時間01234服務(wù)時間43524RR(q=1)完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間12123109318163.2118417133.2511.63.29AAAABCBBCCCCDDEEEE調(diào)度序列：311271042516141891161381517就緒隊列：AAAABCBBCCCCDDEEEE.3.3調(diào)度算法時間片輪轉(zhuǎn)法（RR）時間片的確定R是系統(tǒng)對響應(yīng)時間的要求Nmax是就緒隊列中所允許的最大進(jìn)程數(shù).3.3調(diào)度算法多級反饋隊列調(diào)度算法（MFQ）MultilevelFeedbackQueue多個就緒隊列進(jìn)程時間片結(jié)束時尚未完成則到下一就緒隊列排隊就緒隊列1（8ms）就緒隊列2（16ms）就緒隊列3（32ms）就緒隊列n（FCFS）處理機┇.3.4實時調(diào)度實現(xiàn)實時調(diào)度的基本條件系統(tǒng)必須提供必要的信息就緒時間開始截止時間和完成截止時間處理時間資源要求優(yōu)先級.3.4實時調(diào)度實現(xiàn)實時調(diào)度的基本條件系統(tǒng)處理能力的要求單處理機系統(tǒng)多處理機系統(tǒng)Ci表示處理時間Pi

表示周期時間.3.4實時調(diào)度實現(xiàn)實時調(diào)度的基本條件采用搶占式調(diào)度機制具有快速切換機制.3.4實時調(diào)度實時調(diào)度算法最早截止時間優(yōu)先（EDF）EarliestDeadlineFirst最低松弛度優(yōu)先（LLF）LeastLaxityFirst.3.4實時調(diào)度最早截止時間優(yōu)先（EDF）開始截止時間越早，優(yōu)先級越高任務(wù)1任務(wù)執(zhí)行→任務(wù)到達(dá)→任務(wù)1t任務(wù)3任務(wù)4任務(wù)2任務(wù)2任務(wù)3任務(wù)4任務(wù)1任務(wù)3

任務(wù)4

任務(wù)2

開始截止時間：.3.4實時調(diào)度最低松弛度優(yōu)先（LLF）根據(jù)任務(wù)緊急(或松弛)的程度，來確定任務(wù)的優(yōu)先級松弛度=必須完成的時間點-本身所需運行時間-當(dāng)前時間.3.4實時調(diào)度最低松弛度優(yōu)先（LLF）假如一個實時系統(tǒng)中有兩個周期性實時任務(wù)，A和B，任務(wù)A要求每20ms執(zhí)行一次，執(zhí)行時間為10ms；任務(wù)B只要求每50ms執(zhí)行一次，執(zhí)行時間25ms。0102030405060708090100t●●A1A2A3A4A5B1B2.3.4實時調(diào)度最低松弛度優(yōu)先（LLF）A1(10)B1(20)0102030405060708090100tA2(10)A3(10)A4(10)B1(5)B2(15)B2(10)●●0102030405060708090100t●●A1A2A3A4A5B1B2.死鎖(Deadlock)指多個進(jìn)程因競爭共享資源而造成的一種僵局，若無外力作用，這些進(jìn)程都將永遠(yuǎn)不能再向前推進(jìn)wait(mutexN);wait(mutexM);M=10;N=M;print(N);signal(mutexM);signal(mutexN);ProcessAwait(mutexM);wait(mutexN);N=0;M=0;print(N);signal(mutexM);signal(mutexN);ProcessB3.5產(chǎn)生死鎖的原因和必要條件.3.5產(chǎn)生死鎖的原因和必要條件死鎖產(chǎn)生的原因競爭非剝奪性資源.wait(mutexN);wait(mutexM);M=10;N=M;print(N);signal(mutexM);signal(mutexN);ProcessAwait(mutexM);wait(mutexN);N=0;M=0;print(N);signal(mutexM);signal(mutexN);ProcessB3.5產(chǎn)生死鎖的原因和必要條件死鎖產(chǎn)生的原因進(jìn)程推進(jìn)順序不當(dāng).3.5產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的必要條件互斥條件請求和保持條件不剝奪條件環(huán)路等待條件.3.5產(chǎn)生死鎖的原因和必要條件處理死鎖的基本方法預(yù)防死鎖施加限制條件破壞四個必要條件中的一個或幾個避免死鎖根據(jù)資源的使用情況提前做出預(yù)測，避免死鎖發(fā)生檢測死鎖解除死鎖.3.6預(yù)防死鎖的方法摒棄“請求和保持”條件在進(jìn)程運行之前，為其分配所需的全部資源缺點：資源浪費嚴(yán)重進(jìn)程等待時間長互斥條件請求和保持條件不剝奪條件環(huán)路等待條件四個必要條件互斥條件請求和保持條件不剝奪條件環(huán)路等待條件四個必要條件互斥條件請求和保持條件不剝奪條件環(huán)路等待條件四個必要條件.3.6預(yù)防死鎖的方法摒棄“不剝奪”條件當(dāng)進(jìn)程提出新的資源請求而得不到滿足時，必須釋放它所占用的資源某些資源（如打印機）不適用互斥條件請求和保持條件不剝奪條件環(huán)路等待條件四個必要條件.3.6預(yù)防死鎖的方法摒棄“環(huán)路等待”條件把系統(tǒng)中所有資源編號，進(jìn)程在申請資源時必須按資源編號的遞增次序進(jìn)行例如：資源編號－1，2，3，…，10P1：申請1申請3申請9…P2：申請1申請2申請5P3……P10互斥條件請求和保持條件不剝奪條件環(huán)路等待條件四個必要條件申請9.3.6避免死鎖——銀行家算法思想系統(tǒng)運行過程中，允許進(jìn)程動態(tài)地申請資源但系統(tǒng)在進(jìn)行資源分配之前，應(yīng)先計算此次資源分配的安全性（是否會產(chǎn)生死鎖）若此次分配是安全的（不會產(chǎn)生死鎖），則將資源分配給進(jìn)程；否則，令進(jìn)程等待.3.6避免死鎖——銀行家算法安全狀態(tài)如果系統(tǒng)能按某種順序（如P4，P1，…,Pn）為每個進(jìn)程分配其所需的資源，直至每個進(jìn)程都能順利地完成，稱系統(tǒng)處于安全狀態(tài)。否則處于不安全狀態(tài)安全序列能安全分配的順序稱為安全序列安全狀態(tài)一定沒有死鎖發(fā)生.3.6避免死鎖——銀行家算法安全狀態(tài)舉例有三個進(jìn)程p1,p2,p3，有12臺磁帶機。需求及已分配如下：經(jīng)分析，此刻系統(tǒng)是安全的。因為存在一個安全序列p2、p1、p3進(jìn)程最大需求已分配可用P1P2P310495232510①②③3.3.6避免死鎖——銀行家算法不安全狀態(tài)舉例P3要求1臺磁帶機經(jīng)分析，此刻系統(tǒng)是不安全的。因為不存在安全序列進(jìn)程最大需求已分配可用P1P2P31049523232.3.6避免死鎖——銀行家算法銀行家算法中的數(shù)據(jù)結(jié)構(gòu)可利用資源向量Available含有m個元素的數(shù)組每個元素代表一類當(dāng)前系統(tǒng)可利用資源的數(shù)目如：Available=（5，2，3）R1R2R3523.3.6避免死鎖——銀行家算法銀行家算法中的數(shù)據(jù)結(jié)構(gòu)最大需求矩陣Maxn*m矩陣表示n個進(jìn)程的每一個對m類資源的最大需求R1R2R3P1562P2331P3425P4332.3.6避免死鎖——銀行家算法銀行家算法中的數(shù)據(jù)結(jié)構(gòu)已分配矩陣Allocationn*m矩陣表示每個進(jìn)程已分配的資源數(shù)R1R2R3P1212P2121P3222P4132.3.6避免死鎖——銀行家算法銀行家算法中的數(shù)據(jù)結(jié)構(gòu)需求矩陣Needn*m矩陣表示每個進(jìn)程還需要各類資源數(shù)Need=Max-AllocationR1R2R3P1352P2211P3223P4232.3.6避免死鎖——銀行家算法銀行家算法進(jìn)程pi提出資源申請Request=(a,b,c)if(Request<=Need[i]){if(Request<=Available){Available=Available–Request;Allocation[i]=Allocation[i]+Request[i];Need[i]=Need[i]–Request;if(SafetyTest)

進(jìn)行分配；else

恢復(fù)試分配前狀態(tài)；}else出錯：無足夠資源分配}else出錯：申請的資源大于需求值試分配.3.6避免死鎖——銀行家算法安全性算法中的數(shù)據(jù)結(jié)構(gòu)工作向量Work表示系統(tǒng)可用的各類資源數(shù)目初始時Work=Available布爾向量Finish記錄系統(tǒng)是否有足夠資源分配給各進(jìn)程也可以記錄某進(jìn)程是否已進(jìn)入安全序列.3.6避免死鎖——銀行家算法安全性算法(SafetyTest)Work=Available;所有Finish[i]=false;while(還有未放入安全序列的進(jìn)程){if(找到滿足Finish[i]==false&&Need[i]≤Work的進(jìn)程i){

Work=Work+Allocation[i];Finish[i]=true;}if(遍歷一遍，找不到滿足條件的進(jìn)程)break;}if(所有Finish[i]==true)

返回“安全”；else

返回“不安全”；.3.6避免死鎖——銀行家算法銀行家算法舉例設(shè)系統(tǒng)有五個進(jìn)程和三類資源，每類資源分別有10、5、7。在T0時刻資源分配情況如圖：

資源情況進(jìn)程MaxABCAllocationABCNeedABCAvailableABCP0753010P1322200P2902302P3222211P4433002011122743600431332532000743000745000①⑤④②③.3.6避免死鎖——銀行家算法銀行家算法舉例設(shè)系統(tǒng)有五個進(jìn)程和三類資源，每類資源分別有10、5、7。在T0時刻資源分配情況如圖：

資源情況進(jìn)程MaxABCAllocationABCNeedABCAvailableABCP0753010P1322200P2902302P3222211P4433002T0時刻可以找到一個安全序列{p1,p3,p4,p0,p2},系統(tǒng)是安全的011122743600431332①⑤④②③.3.6避免死鎖——銀行家算法銀行家算法舉例P1發(fā)出請求Request(1,0,2)Request<=Need[i]&&Request<=Available

資源情況進(jìn)程MaxABCAllocationABCNeedABCAvail