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

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

任務4

任務2

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

進行分配；else

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

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

返回“安全”；else

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

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

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

資源情況進程MaxABCAllocationABCNeedABCAvailableABCP0753010P1322P2902302P3222211P4433002743600122011332431230020可以找到一個安全序列{p1,p3,p4,p0,p2},系統(tǒng)是安全的302200.3.6避免死鎖——銀行家算法銀行家算法舉例資3.6避免死鎖——銀行家算法銀行家算法舉例P0發(fā)出請求Request(0,2,0)Request<=Need[i]&&Request<=Available

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

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

任務4

任務2

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

進行分配；else

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

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