處理機(jī)的調(diào)度和死鎖

處理機(jī)的調(diào)度和死鎖第1頁，課件共55頁，創(chuàng)作于2023年2月3.1處理機(jī)調(diào)度的基本概念3.1高、中、低三級調(diào)度1、高級調(diào)度（作業(yè)調(diào)度、長程調(diào)度、接納調(diào)度）將外存作業(yè)調(diào)入內(nèi)存，創(chuàng)建PCB等，插入就緒隊列。一般用于批處理系統(tǒng)，分/實時系統(tǒng)一般直接入內(nèi)存，無此環(huán)節(jié)。調(diào)度特性1.接納作業(yè)數(shù)（內(nèi)存駐留數(shù)）太多―――> 周轉(zhuǎn)時間T長太少―――> 系統(tǒng)效率低2.接納策略：即采用何種調(diào)度算法：FCFS、短作業(yè)優(yōu)先等第2頁，課件共55頁，創(chuàng)作于2023年2月處理機(jī)調(diào)度的基本概念（2）2、低級調(diào)度（進(jìn)程調(diào)度，短程調(diào)度）主要是由分派程序（Dispatcher）分派處理機(jī)。1.非搶占方式： 簡單，實時性差(如win31)2.搶占方式（1）時間片原則（2）優(yōu)先權(quán)原則（3）短作業(yè)優(yōu)先原則。3、中級調(diào)度（中程）為提高系統(tǒng)吞吐量和內(nèi)存利用率而引入的一內(nèi)------外存對換功能（換出時，進(jìn)程為掛起或就緒駐外狀態(tài)）

運(yùn)行頻率：低>中>高。第3頁，課件共55頁，創(chuàng)作于2023年2月問？三種調(diào)度被引發(fā)的事件？事件的表現(xiàn)方式？第4頁，課件共55頁，創(chuàng)作于2023年2月3.1.2調(diào)度的隊列模型一、僅有進(jìn)程調(diào)度的隊列模型就緒隊列CPU阻塞隊列交互用戶時間片完進(jìn)程調(diào)度進(jìn)程完成等待事件事件出現(xiàn)第5頁，課件共55頁，創(chuàng)作于2023年2月3.1.2調(diào)度的隊列模型二、具有高/低級模型就緒隊列CPU阻塞隊列時間片完進(jìn)程調(diào)度進(jìn)程完成等待事件1事件1出現(xiàn)后備隊列阻塞隊列等待事件2事件2出現(xiàn)作業(yè)調(diào)度第6頁，課件共55頁，創(chuàng)作于2023年2月三、具有三級調(diào)度就緒隊列CPU就緒、掛起隊列時間片完進(jìn)程調(diào)度進(jìn)程完成后備隊列阻塞、掛起隊列事件出現(xiàn)作業(yè)調(diào)度阻塞隊列等待事件掛起事件出現(xiàn)中級調(diào)度交互型作業(yè)第7頁，課件共55頁，創(chuàng)作于2023年2月3.1.3選擇調(diào)度方式和算法的若干準(zhǔn)則一、面向用戶的準(zhǔn)則1．周轉(zhuǎn)時間短（常用于批處理系統(tǒng)）概念：作業(yè)從提交――>完成的時間.分為：（1）駐外等待調(diào)度時間（2）駐內(nèi)等待調(diào)度時間（3）執(zhí)行時間（4）阻塞時間第8頁，課件共55頁，創(chuàng)作于2023年2月一、面向用戶的準(zhǔn)則平均周轉(zhuǎn)時間

平均帶權(quán)

可見帶權(quán)w越小越好,Ts為實際服務(wù)時間。3.1.3選擇調(diào)度方式和算法的若干準(zhǔn)則第9頁，課件共55頁，創(chuàng)作于2023年2月一、面向用戶的準(zhǔn)則2．響應(yīng)時間快：（對交互性作業(yè)）概念：鍵盤提交請求到首次響應(yīng)時間（1）輸入傳送時間（2）處理時間（3）響應(yīng)傳送時間3．截止時間的保證（特別于實時系統(tǒng)）4．優(yōu)先權(quán)準(zhǔn)則：（即需要搶占調(diào)度）3.1.3選擇調(diào)度方式和算法的若干準(zhǔn)則第10頁，課件共55頁，創(chuàng)作于2023年2月二、面向系統(tǒng)的準(zhǔn)則1．吞吐量高（特別于批處理）：單位時間完成作業(yè)數(shù)2．處理機(jī)利用率好：（因CPU貴，特別于大中型多用戶系統(tǒng)）3．各類資源的平衡利用。（？折算標(biāo)準(zhǔn)）3.1.3選擇調(diào)度方式和算法的若干準(zhǔn)則第11頁，課件共55頁，創(chuàng)作于2023年2月3.2調(diào)度算法——是一個資源分配問題3.2.1先來先服務(wù)和短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法1.FCFS特點(diǎn)：簡單，有利于長作業(yè)即CPU繁忙性作業(yè)2.短作業(yè)進(jìn)程優(yōu)先調(diào)度算法：SJ(P)F提高了平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間（從而提高了系統(tǒng)吞吐量）特點(diǎn)：對長作業(yè)不利，有可能得不到服務(wù)（饑餓）估計時間不易確定第12頁，課件共55頁，創(chuàng)作于2023年2月

例進(jìn)程名到達(dá)時間服務(wù)時間開始執(zhí)行時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間A010111B110011011001C21101102100100D31001022021991.99第13頁，課件共55頁，創(chuàng)作于2023年2月圖3.4FCFS和SJF比較進(jìn)程名ABCDE平均到達(dá)時間01234服務(wù)時間43524FCFS完成時間47121418周轉(zhuǎn)時間461011149帶權(quán)周轉(zhuǎn)時間1225.53.52.8SJF完成時間4918613周轉(zhuǎn)時間4816398帶權(quán)周轉(zhuǎn)時間12.673.11.52.252.1第14頁，課件共55頁，創(chuàng)作于2023年2月3.2.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法1.優(yōu)先權(quán)調(diào)度算法類型非搶占式優(yōu)先權(quán)算法搶占式優(yōu)先權(quán)算法，實時性更好。2.優(yōu)先權(quán)類型：1．靜態(tài)優(yōu)先權(quán)：進(jìn)程優(yōu)先權(quán)在整個運(yùn)行期不變。確定優(yōu)先權(quán)依據(jù)（1）進(jìn)程類型（2）進(jìn)程對資源的需求；（3）根據(jù)用戶需求。特點(diǎn)：簡單，但低優(yōu)先權(quán)作業(yè)可能長期不被調(diào)度。第15頁，課件共55頁，創(chuàng)作于2023年2月3.2.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法(2)2．動態(tài)優(yōu)先權(quán)：如：優(yōu)先權(quán)隨執(zhí)行時間而下降，隨等待時間而升高。響應(yīng)比Rp=（等待時間＋服務(wù)時間）/服務(wù)時間作為優(yōu)先權(quán)優(yōu)點(diǎn)：長短兼顧缺點(diǎn)：需計算Rp3.高響應(yīng)比優(yōu)先算法：特點(diǎn)：響應(yīng)比Rp=（tw+ts）/ts（1）短作業(yè)RP大。（2）ts（要求服務(wù)時間）相同的進(jìn)程間相當(dāng)于FCFS。（3）長作業(yè)等待一段時間仍能得到服務(wù)。第16頁，課件共55頁，創(chuàng)作于2023年2月3.2.3基于時間片的輪轉(zhuǎn)調(diào)度算法1.時間片輪轉(zhuǎn)時間片大小的確定太大：退化為FCFS；太?。合到y(tǒng)開銷過大系統(tǒng)對響應(yīng)時間的要求；T=nq就緒隊列中進(jìn)程的數(shù)目；系統(tǒng)的處理能力：（應(yīng)保證一個時間片處理完常用命令）第17頁，課件共55頁，創(chuàng)作于2023年2月3.2.3基于時間片的輪轉(zhuǎn)調(diào)度算法2.多級反饋隊列調(diào)度特點(diǎn)：長、短作業(yè)兼顧，有較好的響應(yīng)時間（1）短作業(yè)一次完成；（2）中型作業(yè)周轉(zhuǎn)時間不長；（3）大型作業(yè)不會長期不處理。第18頁，課件共55頁，創(chuàng)作于2023年2月就緒隊列1至CPUS1就緒隊列2S2至CPU就緒隊列3S3至CPU就緒隊列nSn至CPU時間片：S1<S2<S3圖3－5多級隊列反饋調(diào)度算法第19頁，課件共55頁，創(chuàng)作于2023年2月3.3.1實現(xiàn)實時調(diào)度的基本條件1．提供必要的調(diào)度信息（1）就緒時間；（2）開始/完成截止時間；（3）處理時間；（4）資源要求；（5）優(yōu)先級；2．系統(tǒng)處理能力強(qiáng)3.3實時調(diào)度Ci為處理時間，Pi為周期時間（基于周期性實時任務(wù)）第20頁，課件共55頁，創(chuàng)作于2023年2月3.3.1實現(xiàn)實時調(diào)度的基本條件3.采用搶占調(diào)度方式剝奪方式：一般都采用此非剝奪方式（實現(xiàn)簡單）：一般應(yīng)使實時任務(wù)較小，以及時放棄CPU。4.具有快速切換機(jī)制具有快速響應(yīng)外部中斷能力?？焖偃蝿?wù)分派3.3實時調(diào)度第21頁，課件共55頁，創(chuàng)作于2023年2月3.3.2實時調(diào)度算法的分類1非搶占式調(diào)度算法時間片輪轉(zhuǎn) 秒級非搶占優(yōu)先權(quán)（協(xié)同） 秒~毫秒級2搶占式調(diào)度算法時鐘中斷搶占優(yōu)先權(quán) 毫秒級基于搶占點(diǎn)搶占立即搶占immediatepreemption毫秒~微秒級只要不在臨界區(qū)即搶占（中斷引發(fā)）第22頁，課件共55頁，創(chuàng)作于2023年2月進(jìn)程1進(jìn)程2進(jìn)程n實時進(jìn)程調(diào)度時間實時進(jìn)程要求調(diào)度調(diào)度實時進(jìn)程運(yùn)行a非搶占輪轉(zhuǎn)調(diào)度當(dāng)前進(jìn)程實時進(jìn)程實時進(jìn)程要求調(diào)度當(dāng)前進(jìn)程運(yùn)行完成b非搶占優(yōu)先權(quán)調(diào)度調(diào)度時間第23頁，課件共55頁，創(chuàng)作于2023年2月c基于時鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度當(dāng)前進(jìn)程實時進(jìn)程實時進(jìn)程要求調(diào)度搶占時刻（其它中斷）b立即搶占優(yōu)先權(quán)調(diào)度當(dāng)前進(jìn)程實時進(jìn)程實時進(jìn)程要求調(diào)度時鐘中斷到達(dá)時調(diào)度時間調(diào)度時間第24頁，課件共55頁，創(chuàng)作于2023年2月3.3.3常用的幾種實時調(diào)度算法1.最早截止時間優(yōu)先EDF（earliestdeadlinefirst)算法根據(jù)任務(wù)的截止時間來確定任務(wù)的優(yōu)先級截止時間越早，優(yōu)先級越高可以是搶占式或非搶占式第25頁，課件共55頁，創(chuàng)作于2023年2月最早截止時間優(yōu)先EDF例134213421234t開始截止時間任務(wù)到達(dá)任務(wù)執(zhí)行圖3－7EDF算法用于非搶占調(diào)度方式第26頁，課件共55頁，創(chuàng)作于2023年2月2.最低松弛度優(yōu)先LLF算法松弛度：若A進(jìn)程需在200ms時完成，其本身運(yùn)行需要100ms，當(dāng)前時刻是10ms，則A的松弛度為：200－100－10＝90主要用于可搶占的調(diào)度方式中例：A1A2A3A4A5A6A7A8B1B2B3020406080100120140160t圖3－8A/B任務(wù)每次必須完成的時間第27頁，課件共55頁，創(chuàng)作于2023年2月最低松弛度優(yōu)先LLF算法(2)A1(10)A2(10)A3(10)A4(10)t01020304050607080t1=0B1(20)B1(5)B2(15)B2(10)t1t2t3t4t5t6t7t8第28頁，課件共55頁，創(chuàng)作于2023年2月3.4多處理機(jī)系統(tǒng)中的調(diào)度1.緊密耦合MPS和松弛耦合MPS緊密耦合共享RAM和I/O高速總線和交叉開關(guān)連接松弛耦合獨(dú)立RAM和I/O通道和通信線路連接2.對稱多處理器系統(tǒng)和非對稱多處理器系統(tǒng)處理器是否結(jié)構(gòu)相同第29頁，課件共55頁，創(chuàng)作于2023年2月3.4.2進(jìn)程分配方式1.SMP中進(jìn)程分配方式靜態(tài)分配動態(tài)分配可防止系統(tǒng)中多個處理器忙閑不均2.非SMP中進(jìn)程分配方式進(jìn)程調(diào)度在主處理器上執(zhí)行有潛在的不可靠性第30頁，課件共55頁，創(chuàng)作于2023年2月3.4.3進(jìn)程（線程）調(diào)度方式

1.自調(diào)度各個處理機(jī)自行在就緒隊列中取任務(wù)。特點(diǎn)；簡單，分布式調(diào)度，調(diào)度算法可采用前述方法，多個CPU利用率都不錯（不會閑）但：瓶頸問題，（單隊列）低效性；（需拷貝現(xiàn)場）線程切換頻繁（當(dāng)線程合作時,各線程并行的條件不容易滿足）第31頁，課件共55頁，創(chuàng)作于2023年2月2.成組調(diào)度優(yōu)點(diǎn)：（1）對相互合作的進(jìn)（線）程組調(diào)度，可以減小切換，減小系統(tǒng)開銷。（2）每次分配一組CPU，減少了調(diào)度頻率。分配時間（1）面向程序（2）面向線程：使處理機(jī)利用率更高。第32頁，課件共55頁，創(chuàng)作于2023年2月2.成組調(diào)度應(yīng)用程序A應(yīng)用程序BCpu1線程1線程1Cpu2線程2空閑Cpu3線程3空閑Cpu4線程4空閑時間1/21/2浪費(fèi)37.5%應(yīng)用程序A應(yīng)用程序BCpu1線程1線程1Cpu2線程2空閑Cpu3線程3空閑Cpu4線程4空閑時間4/51/5浪費(fèi)15%第33頁，課件共55頁，創(chuàng)作于2023年2月3.專用處理機(jī)分配

引入：多處理機(jī)系統(tǒng)，每個處理已不再屬寶貴資源。特點(diǎn)：每個進(jìn)（線）程專用處理機(jī)，使其切換小，提高效率。主要用于大型計算，實時系統(tǒng)第34頁，課件共55頁，創(chuàng)作于2023年2月3.5產(chǎn)生死鎖的原因和必要條件3.5.1產(chǎn)生死鎖的原因。一、競爭資源引起死鎖。1．可剝奪（CPU、內(nèi)存，）和非剝奪性（打印機(jī)，磁帶機(jī)）資源2．競爭非剝奪性資源——可造成死鎖p1p2R1R2第35頁，課件共55頁，創(chuàng)作于2023年2月3.5產(chǎn)生死鎖的原因和必要條件3．競爭臨時性資源臨時性資源是指由一個進(jìn)程產(chǎn)生，被另一個進(jìn)程使用一段時間后便無用的資源。第36頁，課件共55頁，創(chuàng)作于2023年2月二、進(jìn)程推進(jìn)順序不當(dāng)引起死鎖。213DP2Req(R2)P2Req(R1)P1Req(R1)P1Req(R2)P2Rel(R2)P2Rel(R1)P1Rel(R1)P1Rel(R2)4第37頁，課件共55頁，創(chuàng)作于2023年2月3.5.2產(chǎn)生死鎖的必要條件1．互斥條件（資源的臨界性）2．請求和保持條件3．不剝奪條件4．環(huán)路等待第38頁，課件共55頁，創(chuàng)作于2023年2月3.5.3處理死鎖的基本方法1．預(yù)防；破壞4個條件之一：有效，使資源利用率低。2．避免：防止進(jìn)入不安全態(tài)。3．檢測：檢測到死鎖再清除。4．解除：與“檢”配套。第39頁，課件共55頁，創(chuàng)作于2023年2月3.6死鎖預(yù)防和避免3.6.1死鎖預(yù)防一、互斥條件是資源固有屬性，不能避免。二、摒棄請求和保持條件全分配，全釋放（AND）缺點(diǎn)：（1）延遲進(jìn)程運(yùn)行 （2）資源嚴(yán)重浪費(fèi)三、摒棄“不剝奪”條件 增加系統(tǒng)開銷，且進(jìn)程前段工作可能失效。第40頁，課件共55頁，創(chuàng)作于2023年2月3.6死鎖預(yù)防和避免3.6.1死鎖預(yù)防 四、摒棄“環(huán)路”條件有序資源分配法：為資源編號，申請時需按編號進(jìn)行。缺點(diǎn)：（1）新增資源不便，（原序號已排定）（2）用戶不自由（3）資源與進(jìn)程使用順序不同造成浪費(fèi)第41頁，課件共55頁，創(chuàng)作于2023年2月3.6.2系統(tǒng)的安全狀態(tài)在“避免死鎖”方法中的判斷條件1.安全狀態(tài)按某種順序并發(fā)進(jìn)程都能達(dá)到獲得最大資源而順序完成的序列為安全序列。能找到安全序列的狀態(tài)為安全狀態(tài)。第42頁，課件共55頁，創(chuàng)作于2023年2月3.6.2系統(tǒng)的安全狀態(tài)（2）2.安全狀態(tài)例進(jìn)程最大需求已分配可用P11053P242P392安全序列：p2p1p3第43頁，課件共55頁，創(chuàng)作于2023年2月3.6.2系統(tǒng)的安全狀態(tài)（3）3安全——不安全的轉(zhuǎn)換上例中，若P3再申請一臺，則不安全進(jìn)程最大需求已分配可用P11052P242P393第44頁，課件共55頁，創(chuàng)作于2023年2月3.6.3利用銀行家算法避免死鎖1．?dāng)?shù)據(jù)結(jié)構(gòu)available[j]=k:系統(tǒng)現(xiàn)有Rj類資源k個；max[i,j]=k:進(jìn)程i需要Rj的最大數(shù)k個；alloc[i,j]=k:進(jìn)程i已得到Rj類資源k個；need[i,j]=k: 進(jìn)程i需要Rj類資源k個有：need[i,j]=max[i,j]－alloc[i,j]requesti 進(jìn)程i請求資源數(shù)worki：進(jìn)程i執(zhí)行完后系統(tǒng)應(yīng)有資源數(shù)（也即可用數(shù)）finish[i]：布爾量，表進(jìn)程i能否順序完成。第45頁，課件共55頁，創(chuàng)作于2023年2月3.6.3利用銀行家算法避免死鎖2．銀行家算法reqi<=needierrorreqi<=availiblock第46頁，課件共55頁，創(chuàng)作于2023年2月3.6.3利用銀行家算法避免死鎖avail=avail-reqialloci=alloci+reqineedi=needi-reqifinish[i]=.F.needi<=workwork=work+allocifinish[i]=.T.第47頁，課件共55頁，創(chuàng)作于2023年2月4實例MaxABCAllocationABCNeedABCAvailableABCp0753010743332(230)p1322200(302)122(020)p2902302600p3222211011p4433002431T0時刻的資源分配表第48頁，課件共55頁，創(chuàng)作于2023年2月4實例WorkABCNeedABCAllocABCWork+allocABCFinishp1332122200532truep3532011211743truep4743431002745truep27456003021047truep010477430101057trueT0時刻的安全序列第49頁，課件共55頁，創(chuàng)作于2023年2月4實例WorkABCNeedABCAllocABCWork+allocABCFinishp1230020302532truep3532011211743truep4743431002745truep0745743010755t