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

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

表示周期時(shí)間.3.4實(shí)時(shí)調(diào)度實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件采用搶占式調(diào)度機(jī)制具有快速切換機(jī)制.3.4實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度算法最早截止時(shí)間優(yōu)先（EDF）EarliestDeadlineFirst最低松弛度優(yōu)先（LLF）LeastLaxityFirst.3.4實(shí)時(shí)調(diào)度最早截止時(shí)間優(yōu)先（EDF）開始截止時(shí)間越早，優(yōu)先級(jí)越高任務(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

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

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

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

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