操作系統(tǒng)第三章課件-002

第三章

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

處理機(jī)調(diào)度的層次處理機(jī)調(diào)度系統(tǒng)中有多道程序和多個(gè)進(jìn)程時(shí)，系統(tǒng)按某種算法，動(dòng)態(tài)地把處理機(jī)分配個(gè)某個(gè)就緒隊(duì)列中的進(jìn)程的過程調(diào)度的三個(gè)層次高級(jí)調(diào)度中級(jí)調(diào)度低級(jí)調(diào)度高級(jí)調(diào)度

又稱作業(yè)調(diào)度、長(zhǎng)程調(diào)度、接納調(diào)度作業(yè)和作業(yè)步作業(yè)job包含程序、數(shù)據(jù)和作業(yè)說明書系統(tǒng)根據(jù)作業(yè)說明書對(duì)程序的運(yùn)行進(jìn)行控制作業(yè)步j(luò)obstep：作業(yè)的加工處理步驟一個(gè)作業(yè)包含托干個(gè)作業(yè)步。如編譯、連接、運(yùn)行等作業(yè)調(diào)度作業(yè)調(diào)度的主要任務(wù)是完成作業(yè)從后備狀態(tài)到執(zhí)行狀態(tài)和從執(zhí)行狀態(tài)到完成狀態(tài)的轉(zhuǎn)變。作業(yè)調(diào)度功能記錄已進(jìn)入系統(tǒng)的各作業(yè)的情況（JCB，JobControlBlock）；按一定的調(diào)度算法，從后備作業(yè)中選擇一個(gè)或幾個(gè)作業(yè)進(jìn)入系統(tǒng)內(nèi)存；為被選中的作業(yè)創(chuàng)建進(jìn)程，并且為其申請(qǐng)系統(tǒng)資源；作業(yè)加束后作善后處理工作。作業(yè)控制快JCB

為管理和調(diào)度作業(yè)，為每個(gè)作業(yè)設(shè)置的控制塊是存放作業(yè)控制和管理信息的數(shù)據(jù)結(jié)構(gòu)高級(jí)調(diào)度特性接納作業(yè)數(shù)內(nèi)存駐留數(shù)太多，周轉(zhuǎn)時(shí)間T長(zhǎng)太少，

系統(tǒng)效率低接納策略決定接納哪些作業(yè)即采用何種調(diào)度算法FCFS、短作業(yè)優(yōu)先等低級(jí)調(diào)度又稱進(jìn)程調(diào)度，短程調(diào)度調(diào)度對(duì)象是進(jìn)程主要是由分派程序（Dispatcher）分配處理機(jī)進(jìn)程調(diào)度功能保護(hù)現(xiàn)場(chǎng)入就緒隊(duì)列算法實(shí)現(xiàn)處理機(jī)分派恢復(fù)現(xiàn)場(chǎng)進(jìn)程調(diào)度的三個(gè)基本機(jī)制排隊(duì)器負(fù)責(zé)將就緒進(jìn)程某種策略排隊(duì)分派程序按照進(jìn)程調(diào)度策略，從就緒進(jìn)程中取出進(jìn)程，進(jìn)行上下文切換，分配處理機(jī)給進(jìn)程上下文切換機(jī)制當(dāng)調(diào)度新的進(jìn)程執(zhí)行時(shí)，保存當(dāng)前執(zhí)行進(jìn)程的上下文，裝入即將運(yùn)行進(jìn)程的上下文調(diào)度分派結(jié)構(gòu)pcb1schedulersuspwakeupreceive…pcb2pcb3pcb4…dispatchercpuReady-qpcb5pcb2schedulersuspwakeupreceive…pcb5pcb3pcb4…dispatchercpuReady-qpcb1進(jìn)程調(diào)度方式非搶占方式一旦處理機(jī)分配后，直到進(jìn)程完成或自愿放棄處理機(jī) 簡(jiǎn)單，實(shí)時(shí)性差(如win31)搶占方式時(shí)間片原則優(yōu)先權(quán)原則短作業(yè)優(yōu)先原則中級(jí)調(diào)度又稱中程調(diào)度為提高系統(tǒng)吞吐量和內(nèi)存利用率引入進(jìn)程的內(nèi)/外存對(duì)換功能換出時(shí)，進(jìn)程為掛起或就緒駐外狀態(tài)由中程調(diào)度決定調(diào)度哪些就緒進(jìn)程入內(nèi)存調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的隊(duì)列模型就緒隊(duì)列CPU阻塞隊(duì)列交互用戶時(shí)間片完進(jìn)程調(diào)度進(jìn)程完成等待事件事件出現(xiàn)調(diào)度隊(duì)列模型具有高/低級(jí)模型就緒隊(duì)列CPU阻塞隊(duì)列時(shí)間片完進(jìn)程調(diào)度進(jìn)程完成等待事件1事件1出現(xiàn)后備隊(duì)列阻塞隊(duì)列等待事件2事件2出現(xiàn)作業(yè)調(diào)度具有三級(jí)調(diào)度就緒隊(duì)列CPU就緒、掛起隊(duì)列時(shí)間片完進(jìn)程調(diào)度進(jìn)程完成后備隊(duì)列阻塞、掛起隊(duì)列事件出現(xiàn)作業(yè)調(diào)度阻塞隊(duì)列等待事件掛起事件出現(xiàn)中級(jí)調(diào)度交互型作業(yè)選擇調(diào)度方式和算法的準(zhǔn)則面向用戶的準(zhǔn)則面向系統(tǒng)的準(zhǔn)則面向用戶的準(zhǔn)則

周轉(zhuǎn)時(shí)間短，常用于批處理系統(tǒng)作業(yè)從提交―>完成的時(shí)間.分為：駐外存等待調(diào)度時(shí)間駐內(nèi)存等待調(diào)度時(shí)間執(zhí)行時(shí)間阻塞時(shí)間平均周轉(zhuǎn)時(shí)間Tii進(jìn)程的周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間Ts系統(tǒng)的服務(wù)時(shí)間面向用戶的準(zhǔn)則響應(yīng)時(shí)間快（交互性作業(yè)）鍵盤提交請(qǐng)求到首次響應(yīng)時(shí)間輸入傳送時(shí)間處理時(shí)間響應(yīng)傳送時(shí)間截止時(shí)間的保證（實(shí)時(shí)系統(tǒng)）優(yōu)先權(quán)準(zhǔn)則即需要搶占調(diào)度面向系統(tǒng)的準(zhǔn)則吞吐量高對(duì)于批處理：?jiǎn)挝粫r(shí)間完成作業(yè)數(shù)處理機(jī)利用率好特別于大中型多用戶系統(tǒng)各類資源的平衡利用內(nèi)存、外存、I/O設(shè)備等調(diào)度算法是一個(gè)資源分配問題根據(jù)系統(tǒng)的資源分配策略所規(guī)定資源分配算法典型算法先來先服務(wù)短作業(yè)優(yōu)先高優(yōu)先權(quán)優(yōu)先調(diào)度時(shí)間片輪轉(zhuǎn)調(diào)度先來先服務(wù)FCFS簡(jiǎn)單，有利于長(zhǎng)作業(yè)即CPU繁忙性作業(yè)注意作業(yè)C的帶權(quán)周轉(zhuǎn)時(shí)間進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開始執(zhí)行時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A010111B110011011001C21101102100100D31001022021991.99短作業(yè)優(yōu)先調(diào)度算法短作業(yè)進(jìn)程優(yōu)先SJ(P)F提高了平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間，從而提高了系統(tǒng)吞吐量對(duì)長(zhǎng)作業(yè)不利，有可能得不到服務(wù)不易確定作業(yè)完成時(shí)間FCFS和SJF比較進(jìn)程名ABCDE平均到達(dá)時(shí)間01234服務(wù)時(shí)間43524FCFS完成時(shí)間47121418周轉(zhuǎn)時(shí)間461011149帶權(quán)周轉(zhuǎn)時(shí)間1225.53.52.8SJF完成時(shí)間4918613周轉(zhuǎn)時(shí)間4816398帶權(quán)周轉(zhuǎn)時(shí)間12.673.11.52.252.1高優(yōu)先權(quán)優(yōu)先調(diào)度算法優(yōu)先權(quán)調(diào)度算法類型非搶占式優(yōu)先權(quán)算法當(dāng)前運(yùn)行進(jìn)程不可被搶占當(dāng)要調(diào)度新的進(jìn)程時(shí)按優(yōu)先權(quán)調(diào)度搶占式優(yōu)先權(quán)算法，實(shí)時(shí)性更好如果出現(xiàn)優(yōu)先權(quán)更高的進(jìn)程，則中止當(dāng)前進(jìn)程，并將處理機(jī)分配給優(yōu)先權(quán)高的進(jìn)程優(yōu)先權(quán)類型靜態(tài)優(yōu)先權(quán)進(jìn)程優(yōu)先權(quán)在整個(gè)運(yùn)行期不變確定優(yōu)先權(quán)依據(jù)進(jìn)程類型、進(jìn)程對(duì)資源的需求、用戶需求。簡(jiǎn)單，但低優(yōu)先權(quán)作業(yè)可能長(zhǎng)期不被調(diào)度動(dòng)態(tài)優(yōu)先權(quán)如：優(yōu)先權(quán)隨執(zhí)行時(shí)間而下降，隨等待時(shí)間而升高可用響應(yīng)比Rp作為優(yōu)先權(quán)Rp=（等待時(shí)間＋服務(wù)時(shí)間）/服務(wù)時(shí)間即：Rp=（tw+ts）/ts優(yōu)點(diǎn)：長(zhǎng)短兼顧缺點(diǎn)：需計(jì)算Rp高響應(yīng)比優(yōu)先算法響應(yīng)比Rp=（tw+ts）/ts短作業(yè)Rp大ts（要求服務(wù)時(shí)間）相同的進(jìn)程間相當(dāng)于FCFS。長(zhǎng)作業(yè)等待一段時(shí)間仍能得到服務(wù)?；跁r(shí)間片的輪轉(zhuǎn)調(diào)度算法多運(yùn)用于分時(shí)系統(tǒng)中兩種策略時(shí)間片輪轉(zhuǎn)多級(jí)反饋隊(duì)列調(diào)度時(shí)間片輪轉(zhuǎn)

系統(tǒng)根據(jù)按時(shí)間片輪流調(diào)度進(jìn)程時(shí)間片大小的確定太大：退化為FCFS太小：系統(tǒng)開銷過大系統(tǒng)對(duì)進(jìn)程的響應(yīng)時(shí)間T=nq；q為時(shí)間片,n為就緒隊(duì)列中進(jìn)程的數(shù)目；系統(tǒng)的處理能力應(yīng)保證一個(gè)時(shí)間片處理完常用命令多級(jí)反饋隊(duì)列調(diào)度設(shè)置多個(gè)就緒隊(duì)列，為每個(gè)隊(duì)列設(shè)定不同的優(yōu)先級(jí)第一個(gè)隊(duì)列優(yōu)先級(jí)最高，其他依次遞減優(yōu)先級(jí)越高的隊(duì)列、每個(gè)時(shí)間片越短第i+1個(gè)隊(duì)列的時(shí)間片長(zhǎng)是第i個(gè)隊(duì)列的2倍新進(jìn)程進(jìn)入內(nèi)存后，首先加入第一隊(duì)列隊(duì)尾，按FCFS等待調(diào)度第一輪結(jié)束后，若進(jìn)程未結(jié)束，則加入第二隊(duì)列，依此類推僅當(dāng)?shù)谝魂?duì)列空閑時(shí)，才會(huì)調(diào)度第二隊(duì)列進(jìn)程運(yùn)行，依此類推就緒隊(duì)列1至CPUS1就緒隊(duì)列2S2至CPU就緒隊(duì)列3S3至CPU就緒隊(duì)列nSn至CPU時(shí)間片：S1<S2<S3多級(jí)隊(duì)列反饋調(diào)度算法

多級(jí)隊(duì)列反饋調(diào)度算法特點(diǎn)長(zhǎng)、短作業(yè)兼顧，有較好的響應(yīng)時(shí)間短作業(yè)一次完成；中型作業(yè)周轉(zhuǎn)時(shí)間不長(zhǎng)；大型作業(yè)不會(huì)長(zhǎng)期不處理實(shí)時(shí)調(diào)度實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件提供必要的調(diào)度信息就緒時(shí)間、開始/完成截止時(shí)間、處理時(shí)間、資源要求、優(yōu)先級(jí)；系統(tǒng)處理能力強(qiáng)滿足限制條件m:周期性實(shí)時(shí)任務(wù)Ci:處理時(shí)間Pi:周期時(shí)間N:處理器數(shù)目實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件采用搶占調(diào)度方式剝奪方式非剝奪方式實(shí)現(xiàn)簡(jiǎn)單一般實(shí)時(shí)任務(wù)較小，以及時(shí)放棄CPU具有快速切換機(jī)制具有快速響應(yīng)外部中斷能力。快速任務(wù)分派實(shí)時(shí)調(diào)度算法的分類非搶占式調(diào)度算法時(shí)間片輪轉(zhuǎn) 秒級(jí)非搶占優(yōu)先權(quán)（協(xié)同） 秒~毫秒級(jí)搶占式調(diào)度算法時(shí)鐘中斷搶占優(yōu)先權(quán) 毫秒級(jí)基于搶占點(diǎn)搶占立即搶占

毫秒~微秒級(jí)只要不在臨界區(qū)即搶占（中斷引發(fā)）進(jìn)程1進(jìn)程2進(jìn)程n實(shí)時(shí)進(jìn)程調(diào)度時(shí)間實(shí)時(shí)進(jìn)程要求調(diào)度調(diào)度實(shí)時(shí)進(jìn)程運(yùn)行a非搶占輪轉(zhuǎn)調(diào)度當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程實(shí)時(shí)進(jìn)程要求調(diào)度當(dāng)前進(jìn)程運(yùn)行完成b非搶占優(yōu)先權(quán)調(diào)度調(diào)度時(shí)間c基于時(shí)鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程實(shí)時(shí)進(jìn)程要求調(diào)度搶占時(shí)刻（其它中斷）b立即搶占優(yōu)先權(quán)調(diào)度當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程實(shí)時(shí)進(jìn)程要求調(diào)度時(shí)鐘中斷到達(dá)時(shí)調(diào)度時(shí)間調(diào)度時(shí)間常用的幾種實(shí)時(shí)調(diào)度算法最早截止時(shí)間優(yōu)先EDF（earliestdeadlinefirst)算法根據(jù)任務(wù)的截止時(shí)間來確定任務(wù)的優(yōu)先級(jí)截止時(shí)間越早，優(yōu)先級(jí)越高可以是搶占式或非搶占式最早截止時(shí)間優(yōu)先EDF例134213421234t開始截止時(shí)間任務(wù)到達(dá)任務(wù)執(zhí)行EDF算法用于非搶占調(diào)度方式最低松弛度優(yōu)先LLF算法松弛度若A進(jìn)程需在200ms時(shí)完成，其本身運(yùn)行需要100ms，當(dāng)前時(shí)刻是10ms，則A的松弛度為：200－100－10＝90主要用于可搶占的調(diào)度方式中例：A的執(zhí)行周期為20ms,執(zhí)行時(shí)間10msB的執(zhí)行周期為50ms,執(zhí)行時(shí)間25msA1A2A3A4A5A6A7A8B1B2B3020406080100120140160t圖3－11A/B任務(wù)每次必須完成的時(shí)間最低松弛度優(yōu)先LLF算法A1(10)A2(10)A3(10)A4(10)t01020304050607080t1=0B1(20)B1(5)B2(15)B2(10)t1t2t3t4t5t6t7t8進(jìn)程死鎖系統(tǒng)中的進(jìn)程無法進(jìn)一步推進(jìn)產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因競(jìng)爭(zhēng)資源引起死鎖進(jìn)程推進(jìn)順序不當(dāng)引起死鎖競(jìng)爭(zhēng)資源引起死鎖可剝奪（CPU、內(nèi)存，）和非剝奪性（打印機(jī)，磁帶機(jī)）資源競(jìng)爭(zhēng)非剝奪性資源——可造成死鎖競(jìng)爭(zhēng)臨時(shí)性資源由一個(gè)進(jìn)程產(chǎn)生，被另一個(gè)進(jìn)程使用一段時(shí)間后便無用的資源。p1p2R1R2進(jìn)程推進(jìn)順序不當(dāng)引起死鎖213DP2Req(R2)P2Req(R1)P1Req(R1)P1Req(R2)P2Rel(R2)P2Rel(R1)P1Rel(R1)P1Rel(R2)4產(chǎn)生死鎖的必要條件互斥條件（資源的臨界性）請(qǐng)求和保持條件不剝奪條件環(huán)路等待處理死鎖的基本方法預(yù)防破壞4個(gè)條件之一有效，使資源利用率低避免防止進(jìn)入不安全態(tài)。檢測(cè)檢測(cè)到死鎖再清除。解除與“檢測(cè)”配套。死鎖預(yù)防互斥條件是資源固有屬性，不能避免。摒棄請(qǐng)求和保持條件全分配，全釋放（AND）缺點(diǎn)：延遲進(jìn)程運(yùn)行、資源嚴(yán)重浪費(fèi)摒棄“不剝奪”條件增加系統(tǒng)開銷，且進(jìn)程前段工作可能失效摒棄“環(huán)路”條件有序資源分配法：為資源編號(hào)，申請(qǐng)時(shí)需按編號(hào)進(jìn)行缺點(diǎn)：原序號(hào)已排定，新增資源不便；用戶不自由；資源與進(jìn)程使用順序不同造成浪費(fèi)系統(tǒng)的安全狀態(tài)在“避免死鎖”方法中的判斷條件安全狀態(tài)按某種順序并發(fā)進(jìn)程都能達(dá)到獲得最大資源而順序完成的序列為安全序列。能找到安全序列的狀態(tài)為安全狀態(tài)。系統(tǒng)的安全狀態(tài)例進(jìn)程最大需求已分配可用P11053P242P392安全序列：p2p1p3上例中，若P3再申請(qǐng)一臺(tái)，則不安全進(jìn)程最大需求已分配可用P11052P242P393安全——不安全的轉(zhuǎn)換銀行家算法死鎖避免算法算法思想系統(tǒng)分配資源前進(jìn)行安全性檢查此次分配后，仍然可以找到一個(gè)安全的推進(jìn)序列，則可以完成分配銀行家算法（cont.）數(shù)據(jù)結(jié)構(gòu)available[j]系統(tǒng)現(xiàn)有Rj類資源max[i,j]進(jìn)程i需要Rj的最大數(shù)alloc[i,j]進(jìn)程i已分配的Rj資源數(shù)need[i,j]進(jìn)程i需要Rj類資源即：need[i,j]=max[i,j]－alloc[i,j]Requesti[] 進(jìn)程i請(qǐng)求資源數(shù)Worki[j]進(jìn)程j執(zhí)行完后系統(tǒng)可用資源數(shù)finish[i]布爾量，進(jìn)程i能順利完成為真避免死鎖-銀行家算法銀行家算法Requesti[j]<=need[i,j]errorRequesti[j]<=availiable[j]blockYNYN銀行家算法Available[j]=available-requesti[j]Allocation[i,j]=allocation[i,j]+requesti[j]Need[i,j]=need[i,j]-requesti[j]安全性檢查安全性算法(1)設(shè)置向量Work[]和Finish[] Work[j]:=available Finish[i]:=true(2)從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程Finish[i]=falseNeed[i,j]<=work[j](3)找到,進(jìn)程i可執(zhí)行完 work[j]:=work[j]+allocation[i,j] finish[i]:=true goto(2)(4)檢查所有進(jìn)程的finish[]=true?,是則系統(tǒng)處于安全狀態(tài),否則為不安全狀態(tài)實(shí)例MaxABCAllocationABCNeedABCAvailableABCp0753010743332(230)p1322200(302)122(020)p2902302600p3222211011p4433002431T0時(shí)刻的資源分配表，P1請(qǐng)求1,0,2實(shí)例WorkABCNeedABCAllocABCWork+allocABCFinishp1332122200532truep3532011211743truep4743431002745truep27456003021047truep010477430101057trueT0時(shí)刻的安全序列實(shí)例WorkABCNeedABCAllocABCWork+allocABCFinishp1230020302532truep3532011211743truep4743431002745truep0745743010755truep27556003021057true