操作系統(tǒng)課件：03第三章 中斷與處理機調(diào)度

1、第三章 中斷與處理機調(diào)度3.1 中斷與中斷系統(tǒng)3.2 處理機調(diào)度3.3 調(diào)度級別與多級調(diào)度3.4 實時調(diào)度3.5 多處理機調(diào)度3.6 系統(tǒng)舉例 操作系統(tǒng)是中斷驅(qū)動的！Interrupt driven3.1 中斷與中斷系統(tǒng)3.1.1 中斷的概念3.1.2 中斷裝置3.1.3 中斷處理程序3.1.1 中斷的概念處理機在運行過程中，出現(xiàn)了某一事件，必須中止正在運行的程序，轉(zhuǎn)去處理這個事件，然后再返回原來運行的程序，這一過程稱為中斷。中斷系統(tǒng)：中斷裝置(硬件)中斷處理程序(軟件)3.1.2 中斷裝置發(fā)現(xiàn)并響應(yīng)中斷的硬件機構(gòu)識別中斷源，當(dāng)有多個中斷源時，按緊迫程度排隊；保存現(xiàn)場；引出中斷處理程序。中斷響

2、應(yīng)和處理的過程正運行程序 處理程序 PSW，PCPC:PSW, PC系統(tǒng)桟.HALOS中斷正運行程序 處理程序 PSW，PCPC:PSW, PC系統(tǒng)桟psw, pc.HALOS中斷中斷響應(yīng)和處理的過程正運行程序 處理程序 PSW，PCPC:PSW, PC系統(tǒng)桟psw, pc.HALOS中斷中斷響應(yīng)和處理的過程正運行程序 處理程序 PSW，PCPC:PSW, PC系統(tǒng)桟psw, pc.HALOS中斷中斷響應(yīng)和處理的過程正運行程序 處理程序 PSW，PCPC:PSW, PC系統(tǒng)桟psw, pc.HALOS中斷中斷響應(yīng)和處理的過程正運行程序 處理程序 PSW，PCPC:PSW, PC系統(tǒng)桟psw,

3、pc.HALOS中斷中斷響應(yīng)和處理的過程3.1.2.1 中斷源與中斷字中斷源引起中斷的事件。中斷寄存器保存與中斷事件相關(guān)信息的寄存器。中斷字中斷寄存器的內(nèi)容。例：IO中斷：設(shè)備狀態(tài)寄存器。3.1.2.2 中斷類型與中斷向量強迫性中斷運行程序不期望的時鐘中斷IO中斷控制臺中斷硬件故障中斷power failure內(nèi)存校驗錯程序性中斷越界，越權(quán)缺頁溢出，除0非法指令自愿性中斷運行程序期望的系統(tǒng)調(diào)用訪管指令系統(tǒng)調(diào)用fd=open(fname,mode)訪管指令準備參數(shù)svc n取返回值3.1.2.2 中斷類型與中斷向量中斷裝置 中斷處 理程序運行程序訪管指令運行程序中斷裝置 中斷處 理程序clock

4、IOconsolePowerfailuremalfunction強迫中斷：自愿中斷：SVC ntrap n3.1.2.2 中斷類型與中斷向量中斷向量：中斷處理程序的運行環(huán)境與入口地址（PSW，PC）每類中斷事件有一個中斷向量,中斷向量的存放位置是由硬件規(guī)定的,中斷向量的內(nèi)容是OS在系統(tǒng)初始化時設(shè)置好的。 中斷向量mode應(yīng)為系統(tǒng)態(tài)3.1.2.2 中斷類型與中斷向量PSW1, PC1 時鐘中斷向量PSW2, PC2 I/O中斷向量PSW3, PC3 console中斷向量PSW4, PC4 硬件故障PSW5, PC5 程序錯誤 PSWn, PCn 訪管中斷向量000000080016002400

5、30 0090時鐘中斷處理程序PC1:I/O中斷處理程序PC2:訪管中斷處理程序PCn:系統(tǒng)空間3.1.2.3 中斷嵌套與系統(tǒng)棧一般原則：高優(yōu)先級別中斷可以嵌入低優(yōu)先級中斷實現(xiàn)方法：中斷響應(yīng)后立即屏蔽不高于當(dāng)前中斷優(yōu)先級的中斷源。3.1.2.3 中斷嵌套與系統(tǒng)棧中斷響應(yīng)后一般需要進一步保存現(xiàn)場 關(guān)中斷（屏蔽所有中斷） 進一步保存現(xiàn)場（通用寄存器等） 開中斷（或開放高優(yōu)先級中斷） . 中斷處理 . 關(guān)中斷（屏蔽所有中斷） 恢復(fù)現(xiàn)場 開中斷 中斷返回3.1.2.3 中斷嵌套與系統(tǒng)棧(Cont.)目態(tài)PSW1: PC1管態(tài)PSW2: PC2管態(tài)PSWn: PCn中斷嵌套:3.1.2.3 中斷嵌套與系

6、統(tǒng)棧(Cont.)PSWn-1 PCn-1PSW2 PC2PSW1 PC1棧頂指針:系統(tǒng)棧:3.1.2.4 中斷優(yōu)先級與中斷屏蔽中斷優(yōu)先級：硬件規(guī)定的中斷響應(yīng)次序，依據(jù):緊迫程度；處理時間。中斷屏蔽：高優(yōu)先級中斷事件處理不受低優(yōu)先級中斷打擾；程序調(diào)整中斷響應(yīng)次序。強迫性中斷:自愿性中斷:關(guān)中斷進一步保存現(xiàn)場到系統(tǒng)棧取中斷字分析中斷原因關(guān)中斷進一步保存現(xiàn)場到系統(tǒng)棧取調(diào)用號分析何種系統(tǒng)調(diào)用中斷處理由系統(tǒng)棧恢復(fù)現(xiàn)場返回目態(tài)程序保存下降進程現(xiàn)場到PCB(核心棧=PCB)選擇上升進程由PCB恢復(fù)上升進程現(xiàn)場TF開放高優(yōu)先級中斷關(guān)中斷終止收回資源,撤銷PCB選擇上升進程由PCB恢復(fù)上升進程現(xiàn)場T等待保存下

7、降進程現(xiàn)場到PCB選擇上升進程由PCB恢復(fù)上升進程現(xiàn)場FT剝奪F中斷處理完TF3.1.3 中斷處理程序由系統(tǒng)?；貜?fù)現(xiàn)場返回目態(tài)程序是嵌套中斷由系統(tǒng)?；謴?fù)現(xiàn)場返回上層中斷F中斷分析關(guān)于等待何時等待？沒有嵌套，中斷與運行進程相關(guān)等待幾次？可能多次什么級別現(xiàn)場？核心級別現(xiàn)場等待時系統(tǒng)棧如何？棧底是目態(tài)現(xiàn)場，然后是嵌套函數(shù)的返回點、參數(shù)、局部變量、返回值中斷分析關(guān)于剝奪何時剝奪？沒有中斷嵌套中斷處理完什么級別現(xiàn)場？目態(tài)現(xiàn)場(核心棧內(nèi)容=PCB)運行user運行kernel等待就緒無創(chuàng)建終止考慮系統(tǒng)狀態(tài)的進程狀態(tài)轉(zhuǎn)換圖建立PCB, 分配必要資源，初始化PCB, 入就緒隊列調(diào)度選中運行user運行kern

8、el等待就緒無創(chuàng)建終止考慮系統(tǒng)狀態(tài)的進程狀態(tài)轉(zhuǎn)換圖PCB切換，恢復(fù)地址映射寄存器，通用(浮點)寄存器，SP調(diào)度選中運行user運行kernel等待就緒（置PSW）無創(chuàng)建終止考慮系統(tǒng)狀態(tài)的進程狀態(tài)轉(zhuǎn)換圖恢復(fù)PSW和PC中斷運行user運行kernel等待就緒無創(chuàng)建終止考慮系統(tǒng)狀態(tài)的進程狀態(tài)轉(zhuǎn)換圖現(xiàn)場在核心棧等待事件中斷運行user運行kernel等待就緒無創(chuàng)建終止考慮系統(tǒng)狀態(tài)的進程狀態(tài)轉(zhuǎn)換圖保存核心級現(xiàn)場到PCB等待事件中斷運行user運行kernel等待就緒事件發(fā)生無創(chuàng)建終止考慮系統(tǒng)狀態(tài)的進程狀態(tài)轉(zhuǎn)換圖I/O中斷，資源釋放并分給該進程等待事件調(diào)度選中中斷運行user運行kernel等待就緒事件

9、發(fā)生無創(chuàng)建終止考慮系統(tǒng)狀態(tài)的進程狀態(tài)轉(zhuǎn)換圖恢復(fù)核心級別現(xiàn)場等待事件調(diào)度選中中斷運行user運行kernel等待就緒事件發(fā)生無創(chuàng)建終止考慮系統(tǒng)狀態(tài)的進程狀態(tài)轉(zhuǎn)換圖再次等待，喚醒，調(diào)度等待事件調(diào)度選中中斷運行user運行kernel等待就緒（置PSW）事件發(fā)生無創(chuàng)建終止考慮系統(tǒng)狀態(tài)的進程狀態(tài)轉(zhuǎn)換圖由系統(tǒng)?；貜?fù)現(xiàn)場中斷運行user運行kernel等待就緒無創(chuàng)建終止考慮系統(tǒng)狀態(tài)的進程狀態(tài)轉(zhuǎn)換圖現(xiàn)場壓入系統(tǒng)棧中斷運行user運行kernel等待就緒中斷無創(chuàng)建終止考慮系統(tǒng)狀態(tài)的進程狀態(tài)轉(zhuǎn)換圖嵌套中斷，現(xiàn)場壓入系統(tǒng)棧中斷運行user運行kernel等待就緒中斷嵌套返回?zé)o創(chuàng)建終止考慮系統(tǒng)狀態(tài)的進程狀態(tài)轉(zhuǎn)換圖由

10、系統(tǒng)棧彈出現(xiàn)場中斷運行user運行kernel等待就緒（置PSW）中斷嵌套返回?zé)o創(chuàng)建終止考慮系統(tǒng)狀態(tài)的進程狀態(tài)轉(zhuǎn)換圖退到第一層中斷，不剝奪處理機, 由系統(tǒng)棧彈出現(xiàn)場剝奪中斷運行user運行kernel等待就緒中斷嵌套返回?zé)o創(chuàng)建終止考慮系統(tǒng)狀態(tài)的進程狀態(tài)轉(zhuǎn)換圖退到第一層中斷，剝奪處理機, 系統(tǒng)棧(目態(tài))現(xiàn)場=PCB中斷運行user運行kernel等待就緒無創(chuàng)建終止考慮系統(tǒng)狀態(tài)的進程狀態(tài)轉(zhuǎn)換圖執(zhí)行系統(tǒng)調(diào)用exit(), 收回資源，撤銷PCB結(jié)束等待事件調(diào)度選中剝奪中斷運行user運行kernel等待就緒（置PSW）事件發(fā)生中斷嵌套返回?zé)o創(chuàng)建結(jié)束終止考慮系統(tǒng)狀態(tài)的進程狀態(tài)轉(zhuǎn)換圖建立PCB, 分配必要

11、資源，初始化PCB, 入就緒隊列3.1.3.1 IO中斷處理正常結(jié)束繼續(xù)傳輸；喚醒相關(guān)進程。傳輸錯誤復(fù)執(zhí)（eg. 3次)；報告系統(tǒng)操作員。3.1.3.2 時鐘中斷處理Housekeeping進程管理重新計算進程調(diào)度參數(shù)(eg. 動態(tài)優(yōu)先數(shù))實現(xiàn)軟時鐘，啟動定時程序硬時鐘5ms發(fā)生一次中斷，軟時鐘50ms如死鎖檢測考慮進程切換3.1.3.3 控制臺中斷處理一個控制按鈕，一個中斷向量，一個中斷處理程序。3.1.3.4 硬件故障處理電源故障處理掉電：內(nèi)存，寄存器外存停止設(shè)備停止處理機恢復(fù)：啟動處理機啟動設(shè)備外存內(nèi)存，寄存器 Use UPS for criticalapplications3.1.3.

12、4 硬件故障處理(cont.)內(nèi)存故障處理海明校驗，奇偶校驗錯誤下雨檢查劃出系統(tǒng)報告操作員3.1.3.5 程序性中斷的處理只能由操作系統(tǒng)處理的中斷影響系統(tǒng)或其它進程越界，非法指令，（處理：終止進程、調(diào)試）需要系統(tǒng)管理或協(xié)助頁故障，缺段，（處理：動態(tài)調(diào)入）可以由用戶自己處理的中斷不影響系統(tǒng)和其它進程除0，溢出，（處理：用戶處理，或OS處理）應(yīng)用程序自己處理中斷調(diào)試語句：on 例如：on goto LA;除0中斷時轉(zhuǎn)LA處理除0中斷時轉(zhuǎn)LB處理 on goto LB除0中斷續(xù)元除0中斷續(xù)元LA:LB:相同中斷發(fā)生在不同位置可采用不同處理方法應(yīng)用程序自行處理中斷(Cont.)編譯時：生成中斷續(xù)元表：

13、中斷續(xù)元入口0中斷續(xù)元入口1中斷續(xù)元入口n中斷事件0:中斷事件1:中斷事件n:.運行時：執(zhí)行調(diào)試語句，填寫中斷續(xù)元表。中斷時：根據(jù)中斷原因查中斷續(xù)元表， 為0，用戶未規(guī)定中斷續(xù)元，由OS標準處理； 非0，用戶已規(guī)定中斷續(xù)元，由用戶處理。初始時均為0圖3-9（P47）步驟：（1）發(fā)生溢出中斷（2）保存舊PSW和PC（3）取中斷向量（4）轉(zhuǎn)到中斷處理程序（5）訪問中斷續(xù)元表（假定非0）（6）系統(tǒng)棧中現(xiàn)場轉(zhuǎn)移到用戶棧（7）中斷續(xù)元入口送寄存器（OS中斷處理完成）（8）執(zhí)行中斷續(xù)元（9）用戶棧PSW和PC送寄存器（10）返回中斷斷點硬件OS中斷處理程序PSW PC系統(tǒng)棧PSW1, PC1 PC1:re

14、t運行程序中斷續(xù)元續(xù)元表用戶棧PSW, LALA:硬件OS中斷處理程序PSW PC系統(tǒng)棧PSW1, PC1 PC1:ret運行程序中斷續(xù)元續(xù)元表用戶棧PSW, LA溢出LA:硬件OS中斷處理程序PSW PC系統(tǒng)棧PSW1, PC1 PC1:ret運行程序中斷續(xù)元續(xù)元表用戶棧PSW, LA溢出PSW PCLA:硬件OS中斷處理程序系統(tǒng)棧PSW1, PC1 PC1:ret運行程序中斷續(xù)元續(xù)元表用戶棧PSW, LA溢出PSW PCLA:PSW1 PC1硬件OS中斷處理程序系統(tǒng)棧PSW1, PC1 PC1:ret運行程序中斷續(xù)元續(xù)元表用戶棧PSW, LA溢出PSW PCLA:PSW1 PC1硬件OS中

15、斷處理程序系統(tǒng)棧PSW1, PC1 PC1:ret運行程序中斷續(xù)元續(xù)元表用戶棧PSW, LA溢出PSW PCLA:PSW1 PC1硬件OS中斷處理程序系統(tǒng)棧PSW1, PC1 PC1:ret運行程序中斷續(xù)元續(xù)元表用戶棧PSW, LA溢出LA:PSW1 PC1PSW, PC硬件OS中斷處理程序系統(tǒng)棧PSW1, PC1 PC1:ret運行程序中斷續(xù)元續(xù)元表用戶棧PSW, LA溢出LA:PSW, PCPSW LA硬件OS中斷處理程序系統(tǒng)棧PSW1, PC1 PC1:ret運行程序中斷續(xù)元續(xù)元表用戶棧PSW, LA溢出LA:PSW, PCPSW LA硬件OS中斷處理程序系統(tǒng)棧PSW1, PC1 PC1

16、:ret運行程序中斷續(xù)元續(xù)元表用戶棧PSW, LA溢出LA:PSW PC硬件OS中斷處理程序PSW PC系統(tǒng)棧PSW1, PC1 PC1:ret運行程序中斷續(xù)元續(xù)元表用戶棧PSW, LA溢出LA:3.1.3.6 自愿性中斷的處理訪管指令（SuperVisor Call)形式：準備參數(shù)SVC n取返回值系統(tǒng)調(diào)用（system call)形式：返回值=系統(tǒng)調(diào)用名稱（實參1,實參n) 參數(shù)和返回值和存放位置是由OS規(guī)定的。3.1.3.6 自愿性中斷的處理系統(tǒng)調(diào)用驅(qū)動表：(table driven)服務(wù)程序入口addr0addrm-1訪管號：0.m-1Eg. UNIX3.2 處理機調(diào)度3.2.1 處理

17、機調(diào)度算法按什么原則分配3.2.2 處理機調(diào)度時機何時重新分配3.2.3 處理機調(diào)度過程如何完成分配scheduling3.2.1 處理機調(diào)度算法考慮因素（scheduling criteria）CPU利用率 ; (max)吞吐量 ; (max)周轉(zhuǎn)時間 ; (min)響應(yīng)時間 ; (min)系統(tǒng)開銷 ; (min)調(diào)度參數(shù)周轉(zhuǎn)時間：完成時間-進入時間平均周轉(zhuǎn)時間：周轉(zhuǎn)時間的平均值帶權(quán)周轉(zhuǎn)時間：周轉(zhuǎn)時間/運行時間平均帶權(quán)周轉(zhuǎn)時間：帶權(quán)周轉(zhuǎn)時間的平均值CPU burst vs. I/O burst 陣發(fā)期 :CPU burst cycle: 進程(線程)使用CPU計算；I/O burst cyc

18、le: 進程(線程)使用設(shè)備I/O。進程運行行為：CPU burst, I/O burst, CPU burst, I/O burst, CPU調(diào)度：考慮處于CPU burst進程集合 CPU burst時間根據(jù)以前行為推定。CPU burst vs. I/O burst下一個CPU burst的長度估算令n是估計的第n個CPU陣發(fā)期的長度， tn的值是進程最近一次CPU陣發(fā)期長度，則有如下估算公式：n+1=tn + (1-)n參數(shù)(01)控制tn和n在公式中起的作用：當(dāng)=0時，n+1=n；當(dāng)=1時，n+1=tn。通常取0.5。剝奪式調(diào)度與非剝奪式調(diào)度剝奪式(preemptive)就緒進程可以

19、從運行進程手中搶占CPU。進程運行,直到結(jié)束、等待或被搶先非剝奪式(non-preemptive)就緒進程不可從運行進程手中搶占CPU。進程運行,直到結(jié)束或等待3.2.1.1 先到先服務(wù)算法FCFS（First Come First Serve)按進程申請CPU（就緒）的次序。Process Arrival time Burst timeP1 0 27P2 1 3P3 2 5CPU調(diào)度狀況可用Gantt 圖表示0 27 30 35P1P2P33.2.1.1 先到先服務(wù)算法(Cont.)進程到達時間運行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間P1027027271P2132730299.67P3

20、253035336.6平均周轉(zhuǎn)時間 =(27+29+33)/3=29.67 平均帶權(quán)周轉(zhuǎn)時間 =(1+9.67+6.6)/3=5.76 0 27 30 35P1P2P33.2.1.1 先到先服務(wù)算法(Cont.)優(yōu)點：“公平”；缺點:短作業(yè)等待時間長。3.2.1.2 短作業(yè)優(yōu)先SJF（Shortest Job First)按CPU burst長度Process Arrival time Burst time P1 0 12 P2 0 5 P3 0 7 P4 0 3Gantt Chart0 3 8 15 27P1P2P3P43.2.1.2 短作業(yè)優(yōu)先0 3 8 15 27P1P2P3P4進程到達

21、時間運行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間P10121527272.25P2053881.6P307815152.14P4030331平均周轉(zhuǎn)時間 =(27+8+15+3)/4=13.25 平均帶權(quán)周轉(zhuǎn)時間 =(2.25+1.6+2.14+1)/4=1.753.2.1.2 短作業(yè)優(yōu)先特點：假定所有任務(wù)同時到達，平均等待時間最短。長作業(yè)可能被餓死。3.2.1.3 最短剩余時間優(yōu)先算法(SRTN) Shortest Remaining Time Next 可剝奪SJFProcess Arrival time Burst time P1 0 12 P2 1 9 P3 3 6 P4 5 3Gan

22、tt圖P1P2P3P4P3P2P10 1 3 5 8 12 19 303.2.1.3 最短剩余時間優(yōu)先算法(Cont.)進程到達時間運行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間P1012030302.5P219119182P33631291.5P4535831平均周轉(zhuǎn)時間=(30+18+9+3)/4=15平均帶權(quán)周轉(zhuǎn)時間=(2.5+2+1.5+1)/4=1.75 平均等待時間(18+9+3+0)/ 4 7.5(ms)P1P2P3P4P3P2P10 1 3 5 8 12 19 303.2.1.4最高響應(yīng)比優(yōu)先(HRN)Highest Response Ratio NextRR=(BT+WT)/B

23、T=1+WT/BT其中:BT=burst timeWT=wait time優(yōu)點:同時到達任務(wù), 短者優(yōu)先長作業(yè)隨等待時間增加響應(yīng)比增加3.2.1.5 最高優(yōu)先數(shù)算法(HPF)靜態(tài)優(yōu)先數(shù)(static)優(yōu)先數(shù)在進程創(chuàng)建時分配，生存期內(nèi)不變。響應(yīng)速度慢，開銷小。適合批處理進程動態(tài)優(yōu)先數(shù)(dynamic)進程創(chuàng)建時繼承優(yōu)先數(shù)，生存期內(nèi)可以修改。響應(yīng)速度快，開銷大。適用于實時系統(tǒng)3.2.1.5 最高優(yōu)先數(shù)算法(Cont.)非剝奪式優(yōu)先數(shù)獲得處理機的進程運行，直至終止等待剝奪式優(yōu)先數(shù)獲得處理機的進程運行，直至終止等待出現(xiàn)高優(yōu)先級的進程3.2.1.5 最高優(yōu)先數(shù)算法(Cont.)可搶占CPUProcess

24、 Arrival time Priority Burst timeP1 0 0 8P2 2 1 5P3 4 3 7P4 0 2 3P5 5 7 2Gantt Chart0 3 4 5 7 13 17 25P1P4P2P2P3P3P53.2.1.5 最高優(yōu)先數(shù)算法(Cont.)進程到達時間運行時間優(yōu)先級開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間P10801725253.13P2251317153P347341391.29P40320331P55275721平均周轉(zhuǎn)時間 =(25+15+9+3+2)/5=38.8 平均帶權(quán)周轉(zhuǎn)時間 =(3.13+3+1.29+1+1)/5=1.88 0 3 4 5 7

25、13 17 25P1P4P2P2P3P3P53.2.1.5 最高優(yōu)先數(shù)算法(Cont.)例子UNIX：preemptive+dynamic priority（可搶占CPU動態(tài)優(yōu)先數(shù)）。計算公式：p_pri=min127, USER+p_cpu/16+p_nice定義USER=100；p_cpu: 運行進程每20ms加1（優(yōu)先級降低），其它進程每1200ms減10（優(yōu)先級提高）；p_nice: 可以通過系統(tǒng)調(diào)用nice()修改的量：規(guī)定用戶進程020之間（低），系統(tǒng)進程-20+20之間（高）。調(diào)度時取p_pri最小的。3.2.1.6 循環(huán)輪轉(zhuǎn)算法(RR)Round Robin(RR)基本輪轉(zhuǎn)時間

26、片(quantum,time slice)長度固定，不變；所有進程等速向前推進。改進輪轉(zhuǎn)時間片長度不定，可變。適用于分時系統(tǒng)3.2.1.6 循環(huán)輪轉(zhuǎn)算法 (Cont.)時間片長度： 幾十毫秒幾百毫秒(eg. 50ms)過長：響應(yīng)速度慢；過短：系統(tǒng)開銷(overhead)大。適應(yīng)系統(tǒng)：分時3.2.1.6 循環(huán)輪轉(zhuǎn)算法 (Cont.) RR可搶占CPU調(diào)度：time slice=4msProcess Arriveral time Burst timeP1 0 17P2 0 10 P3 0 3 Gantt ChartP1P2P3P1P2P1P2P1P10 4 8 11 15 19 23 25 29

27、303.2.1.6 循環(huán)輪轉(zhuǎn)算法 (Cont.)進程到達時間運行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間P1017030301.76P2010425252.5P303811113.67平均周轉(zhuǎn)時間 (30+25+11)/3=22 平均帶權(quán)周轉(zhuǎn)時間(1.76+2.5+3.67)/3=2.64平均等待時間(13+15+8)/ 3 12(ms)P1P2P3P1P2P1P2P1P10 4 8 11 15 19 23 25 29 303.2.1.7 多級隊列算法(MLQ)多級隊列多個就緒隊列，進程所屬的隊列固定。例如：通用系統(tǒng)中： 隊列1：實時進程就緒隊列（HPF） 隊列2：分時進程就緒隊列 （RR）

28、隊列3：批處理進程就緒隊列 （HPF）3. 2.1.8 反饋排隊算法(FB)Feed-Back:多個就緒隊列，進程所屬隊列可變。運行s1時間片運行s2時間片.創(chuàng)建喚醒優(yōu)先級 時間片運行sn時間片Q1 ( RR, HPF1 ) Q2 ( RR, HPF2 ) Qn ( RR, HPFn ) 3.2.1.8 反饋排隊算法 (Cont.)調(diào)度效果： 資源利用率高P1等待P2占有的資源R, P2釋放R, 分給P1, P1被喚醒, 進入最高級隊列, 可盡早投入運行, 使用資源R； 響應(yīng)速度快交互式進程經(jīng)常進入等待狀態(tài)(等待用戶輸入),一旦被喚醒(輸入完成),進入最高級隊列,可盡快被調(diào)度選中,投入運行,反

29、應(yīng)及時； 系統(tǒng)開銷小計算量大的進程用完前面n-1級時間片,沒有處理完,落入底層隊列,調(diào)度頻率下降,但每次獲得較長的時間片。Feed Back3.2.2 處理機調(diào)度時機運行進程結(jié)束；運行進程等待；核心級現(xiàn)場=PCB處理機被剝奪。(中斷處理完，沒有嵌套)用戶級現(xiàn)場=PCB中斷與處理機切換的關(guān)系中斷是處理機切換的必要條件，但不是充分條件必然引起進程切換的中斷進程自愿結(jié)束, exit()進程被強行終止；非法指令，越界，kill可能引起進程切換的中斷時鐘系統(tǒng)調(diào)用3.2.3 處理機調(diào)度過程dispatcher保存下降進程的現(xiàn)場寄存器(PSW,PC,SP,通用(浮點)寄存器,地址寄存器)PCB核心級別現(xiàn)場是

30、統(tǒng)一的；用戶級別現(xiàn)場部分在系統(tǒng)棧，部分在寄存器選擇上升進程按處理機調(diào)度算法恢復(fù)上升進程的現(xiàn)場PCB 寄存器先恢復(fù)地址寄存器、用寄存器、浮點寄存器、sp,最后恢復(fù)PSW,PCPSW和PC必須用一條指令恢復(fù)3.3 調(diào)度級別與多級調(diào)度3.3.1 交換與中級調(diào)度Swapping and mid-level scheduling3.3.2 作業(yè)與高級調(diào)度Job and high-level scheduling處理機調(diào)度為低級調(diào)度CPU scheduling = low level scheduling3.3.1 交換與中級調(diào)度術(shù)語交換(swapping)中級調(diào)度(mid-level schedulin

31、g)并發(fā)度(degree of multi-programming)目標：控制并發(fā)度并發(fā)度過高系統(tǒng)開銷大響應(yīng)速度慢內(nèi)存等資源緊張進程(線程)頻繁進入等待狀態(tài)More deadlocks3.3.1 交換與中級調(diào)度剝奪就緒等待運行 選中等待事件事件發(fā)生就緒掛起等待掛起無終止創(chuàng)建創(chuàng)建結(jié)束換出換出換入換入事件發(fā)生UNIX的中級調(diào)度（sched #0)移入SRUN狀態(tài)進程如內(nèi)存不夠，移出SWAIT和SSTOP狀態(tài)進程；如還不夠，移出SSLEEP和SRUN狀態(tài)進程；條件：待移入進程在外存時間=3秒；待移出進程在內(nèi)存時間=2秒。3.3.2 作業(yè)與高級調(diào)度作業(yè)狀態(tài):提交: 輸入機向輸入井傳送后備: 在輸入井,

32、尚未進入內(nèi)存執(zhí)行: 分解為進程,在內(nèi)存處理完成: 處理完畢,結(jié)果在輸出井退出: 由輸出井向打印機傳送3.3.2 作業(yè)與高級調(diào)度狀態(tài)轉(zhuǎn)換:提交后備: 由SPOOLing輸入進程完成Simultaneous Peripheral Operation On-Line后備執(zhí)行: 由作業(yè)調(diào)度(1)(高級調(diào)度)完成高級調(diào)度: 系統(tǒng)進程執(zhí)行完成: 由作業(yè)調(diào)度(2)完成完成退出: 由SPOOLing輸出進程完成提交后備執(zhí)行完成退出SPOOLing輸入作業(yè)調(diào)度1作業(yè)調(diào)度2SPOOLing輸出作業(yè)控制塊與作業(yè)表JCB（Job Control Block）：作業(yè)存在的數(shù)據(jù)結(jié)構(gòu)，其中保存系統(tǒng)對作業(yè)進行管理的全部信息作

33、業(yè)標識所屬用戶作業(yè)狀態(tài)調(diào)度參數(shù)輸入井地址輸出井地址資源需求進入時間處理時間完成時間SPOOling輸入建立，作業(yè)調(diào)度使用，SPOOling輸出撤銷。JCB1JCB2JCB3JCBk作業(yè)表3.3.2 作業(yè)與高級調(diào)度(Cont.)批處理作業(yè)調(diào)度程序(1)：在后備作業(yè)集合中選擇作業(yè)，并為其建立作業(yè)控制進程來處理該作業(yè)。作業(yè)調(diào)度程序(1)內(nèi)存已有n 道作業(yè)等 待T輸入井中有后備作業(yè)等 待F訪問磁盤中JCB表根據(jù)調(diào)度參數(shù)按作業(yè)調(diào)度算法選擇后備作業(yè)作業(yè)狀態(tài)標志為“執(zhí)行”為該作業(yè)建立作業(yè)控制進程3.3.2 作業(yè)與高級調(diào)度(Cont.)2. 批處理作業(yè)調(diào)度程序(2)對終止的作業(yè)控制進程進行善后處理。作業(yè)調(diào)度程

34、序(2)有終止的作業(yè)控制進程等 待F作業(yè)調(diào)度(1)因內(nèi)存有n道作業(yè)而等待撤銷該作業(yè)控制進程，做善后處理取一終止的作業(yè)控制進程對應(yīng)作業(yè)狀態(tài)改為“完成”喚醒作業(yè)調(diào)度(1)TSpooling輸出等待作業(yè)完成喚醒Spooling輸出T作業(yè)調(diào)度算法適合批作業(yè)調(diào)度的算法先到先服務(wù)算法(FCFS)優(yōu)先數(shù)調(diào)度算法(HPF)短作業(yè)優(yōu)先調(diào)度算法(SJF)最高響應(yīng)比優(yōu)先調(diào)度算法(HRN)不適合批作業(yè)調(diào)度的算法時間片輪轉(zhuǎn)算法(RR)最短剩余時間優(yōu)先(SRTN)反饋排隊算法(FB)3.4 實時調(diào)度(real-time scheduling)實時任務(wù)：具有明確時間約束的計算任務(wù)。Eg.某時刻前必須開始處理某時刻前必須處理

35、完畢實時調(diào)度：合理安排就緒實時任務(wù)的執(zhí)行次序，滿足每個實時任務(wù)時間約束條件的調(diào)度。實時任務(wù)分類硬實時 vs. 軟實時 硬實時(hard real-time): 必須滿足任務(wù)截止期要求 . 軟實時(soft real-time): 期望滿足截止期要求 . 周期性 vs. 隨機性 周期性: 每隔固定時間發(fā)生一次 隨機性: 由隨機事件觸發(fā)，其發(fā)生時刻不確定 術(shù)語解釋Ready time: 就緒時間Starting deadline: 開始截止期Processing time: 處理時間Completion deadline: 完成截止期Occurring frequency: 發(fā)生頻率周期性實時事務(wù)

36、周期性實時事務(wù):令Ci為任務(wù)Pi處理時間，Ti為任務(wù)Pi的發(fā)生周期，則任務(wù)P1,Pm可調(diào)度的必要條件為： 周期性實時事務(wù)例：T1=100, T2=200, T3=500 (ms)C1=50, C2=30, C3=100 (ms)C1/T1+C2/T2+C3/T3=0.5+0.15+0.2=0.850)goodness=counter+priorityLinux 進程調(diào)度調(diào)度發(fā)生時刻： 運行進程的counter減至0； 運行進程執(zhí)行系統(tǒng)調(diào)用exit ;運行進程因等待I/O、信號燈而被封鎖 ;原來具有高goodness的進程被解除封鎖 .調(diào)度效果 :實時優(yōu)先于分時 交互和I/O進程優(yōu)先于CPU進程 Linux 對稱多處理Linux2.0是支持對稱多處理硬件的第一個Linux核心 ; 進程或線程可以同時運行在多個處理機上 .為保持核心非剝奪同步要求，SMP通過一個唯一的核心自旋鎖(spin-lock)來保證任何時刻最多只有一個處理機執(zhí)行核心代碼, 支持真正意義上的SMP：將一個自旋鎖分解為若干個相互獨立的自旋鎖，分別用于保護核心代碼不相交的子集 .3.6.2 Windows 2000/XP線程調(diào)度Main Features：Thread level scheduling;Real time + foreground + background;real time: no deadlin