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

2、應(yīng)和處理的過程正運(yùn)行程序 處理程序 PSW，PCPC:PSW, PC系統(tǒng)桟.HALOS中斷正運(yùn)行程序 處理程序 PSW，PCPC:PSW, PC系統(tǒng)桟psw, pc.HALOS中斷中斷響應(yīng)和處理的過程正運(yùn)行程序 處理程序 PSW，PCPC:PSW, PC系統(tǒng)桟psw, pc.HALOS中斷中斷響應(yīng)和處理的過程正運(yùn)行程序 處理程序 PSW，PCPC:PSW, PC系統(tǒng)桟psw, pc.HALOS中斷中斷響應(yīng)和處理的過程正運(yùn)行程序 處理程序 PSW，PCPC:PSW, PC系統(tǒng)桟psw, pc.HALOS中斷中斷響應(yīng)和處理的過程正運(yùn)行程序 處理程序 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 中斷類型與中斷向量強(qiáng)迫性中斷運(yùn)行程序不期望的時(shí)鐘中斷IO中斷控制臺(tái)中斷硬件故障中斷power failure內(nèi)存校驗(yàn)錯(cuò)程序性中斷越界，越權(quán)缺頁溢出，除0非法指令自愿性中斷運(yùn)行程序期望的系統(tǒng)調(diào)用訪管指令系統(tǒng)調(diào)用fd=open(fname,mode)訪管指令準(zhǔn)備參數(shù)svc n取返回值3.1.2.2 中斷類型與中斷向量中斷裝置 中斷處 理程序運(yùn)行程序訪管指令運(yùn)行程序中斷裝置 中斷處 理程序clock

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

5、30 0090時(shí)鐘中斷處理程序PC1:I/O中斷處理程序PC2:訪管中斷處理程序PCn:系統(tǒng)空間3.1.2.3 中斷嵌套與系統(tǒng)棧一般原則：高優(yōu)先級(jí)別中斷可以嵌入低優(yōu)先級(jí)中斷實(shí)現(xiàn)方法：中斷響應(yīng)后立即屏蔽不高于當(dāng)前中斷優(yōu)先級(jí)的中斷源。3.1.2.3 中斷嵌套與系統(tǒng)棧中斷響應(yīng)后一般需要進(jìn)一步保存現(xiàn)場(chǎng) 關(guān)中斷（屏蔽所有中斷） 進(jìn)一步保存現(xiàn)場(chǎng)（通用寄存器等） 開中斷（或開放高優(yōu)先級(jí)中斷） . 中斷處理 . 關(guān)中斷（屏蔽所有中斷） 恢復(fù)現(xiàn)場(chǎng) 開中斷 中斷返回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)先級(jí)與中斷屏蔽中斷優(yōu)先級(jí)：硬件規(guī)定的中斷響應(yīng)次序，依據(jù):緊迫程度；處理時(shí)間。中斷屏蔽：高優(yōu)先級(jí)中斷事件處理不受低優(yōu)先級(jí)中斷打擾；程序調(diào)整中斷響應(yīng)次序。強(qiáng)迫性中斷:自愿性中斷:關(guān)中斷進(jìn)一步保存現(xiàn)場(chǎng)到系統(tǒng)棧取中斷字分析中斷原因關(guān)中斷進(jìn)一步保存現(xiàn)場(chǎng)到系統(tǒng)棧取調(diào)用號(hào)分析何種系統(tǒng)調(diào)用中斷處理由系統(tǒng)?；謴?fù)現(xiàn)場(chǎng)返回目態(tài)程序保存下降進(jìn)程現(xiàn)場(chǎng)到PCB(核心棧=PCB)選擇上升進(jìn)程由PCB恢復(fù)上升進(jìn)程現(xiàn)場(chǎng)TF開放高優(yōu)先級(jí)中斷關(guān)中斷終止收回資源,撤銷PCB選擇上升進(jìn)程由PCB恢復(fù)上升進(jìn)程現(xiàn)場(chǎng)T等待保存下

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

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

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

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

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

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

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

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

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

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

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

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

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

20、253035336.6平均周轉(zhuǎn)時(shí)間 =(27+29+33)/3=29.67 平均帶權(quán)周轉(zhuǎn)時(shí)間 =(1+9.67+6.6)/3=5.76 0 27 30 35P1P2P33.2.1.1 先到先服務(wù)算法(Cont.)優(yōu)點(diǎn)：“公平”；缺點(diǎn):短作業(yè)等待時(shí)間長(zhǎng)。3.2.1.2 短作業(yè)優(yōu)先SJF（Shortest Job First)按CPU burst長(zhǎng)度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進(jìn)程到達(dá)

21、時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間P10121527272.25P2053881.6P307815152.14P4030331平均周轉(zhuǎn)時(shí)間 =(27+8+15+3)/4=13.25 平均帶權(quán)周轉(zhuǎn)時(shí)間 =(2.25+1.6+2.14+1)/4=1.753.2.1.2 短作業(yè)優(yōu)先特點(diǎn)：假定所有任務(wù)同時(shí)到達(dá)，平均等待時(shí)間最短。長(zhǎng)作業(yè)可能被餓死。3.2.1.3 最短剩余時(shí)間優(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 最短剩余時(shí)間優(yōu)先算法(Cont.)進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間P1012030302.5P219119182P33631291.5P4535831平均周轉(zhuǎn)時(shí)間=(30+18+9+3)/4=15平均帶權(quán)周轉(zhuǎn)時(shí)間=(2.5+2+1.5+1)/4=1.75 平均等待時(shí)間(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)點(diǎn):同時(shí)到達(dá)任務(wù), 短者優(yōu)先長(zhǎng)作業(yè)隨等待時(shí)間增加響應(yīng)比增加3.2.1.5 最高優(yōu)先數(shù)算法(HPF)靜態(tài)優(yōu)先數(shù)(static)優(yōu)先數(shù)在進(jìn)程創(chuàng)建時(shí)分配，生存期內(nèi)不變。響應(yīng)速度慢，開銷小。適合批處理進(jìn)程動(dòng)態(tài)優(yōu)先數(shù)(dynamic)進(jìn)程創(chuàng)建時(shí)繼承優(yōu)先數(shù)，生存期內(nèi)可以修改。響應(yīng)速度快，開銷大。適用于實(shí)時(shí)系統(tǒng)3.2.1.5 最高優(yōu)先數(shù)算法(Cont.)非剝奪式優(yōu)先數(shù)獲得處理機(jī)的進(jìn)程運(yùn)行，直至終止等待剝奪式優(yōu)先數(shù)獲得處理機(jī)的進(jìn)程運(yùn)行，直至終止等待出現(xiàn)高優(yōu)先級(jí)的進(jìn)程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.)進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間優(yōu)先級(jí)開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間P10801725253.13P2251317153P347341391.29P40320331P55275721平均周轉(zhuǎn)時(shí)間 =(25+15+9+3+2)/5=38.8 平均帶權(quán)周轉(zhuǎn)時(shí)間 =(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動(dòng)態(tài)優(yōu)先數(shù)）。計(jì)算公式：p_pri=min127, USER+p_cpu/16+p_nice定義USER=100；p_cpu: 運(yùn)行進(jìn)程每20ms加1（優(yōu)先級(jí)降低），其它進(jìn)程每1200ms減10（優(yōu)先級(jí)提高）；p_nice: 可以通過系統(tǒng)調(diào)用nice()修改的量：規(guī)定用戶進(jìn)程020之間（低），系統(tǒng)進(jìn)程-20+20之間（高）。調(diào)度時(shí)取p_pri最小的。3.2.1.6 循環(huán)輪轉(zhuǎn)算法(RR)Round Robin(RR)基本輪轉(zhuǎn)時(shí)間

26、片(quantum,time slice)長(zhǎng)度固定，不變；所有進(jìn)程等速向前推進(jìn)。改進(jìn)輪轉(zhuǎn)時(shí)間片長(zhǎng)度不定，可變。適用于分時(shí)系統(tǒng)3.2.1.6 循環(huán)輪轉(zhuǎn)算法 (Cont.)時(shí)間片長(zhǎng)度： 幾十毫秒幾百毫秒(eg. 50ms)過長(zhǎng)：響應(yīng)速度慢；過短：系統(tǒng)開銷(overhead)大。適應(yīng)系統(tǒng)：分時(shí)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.)進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間P1017030301.76P2010425252.5P303811113.67平均周轉(zhuǎn)時(shí)間 (30+25+11)/3=22 平均帶權(quán)周轉(zhuǎn)時(shí)間(1.76+2.5+3.67)/3=2.64平均等待時(shí)間(13+15+8)/ 3 12(ms)P1P2P3P1P2P1P2P1P10 4 8 11 15 19 23 25 29 303.2.1.7 多級(jí)隊(duì)列算法(MLQ)多級(jí)隊(duì)列多個(gè)就緒隊(duì)列，進(jìn)程所屬的隊(duì)列固定。例如：通用系統(tǒng)中： 隊(duì)列1：實(shí)時(shí)進(jìn)程就緒隊(duì)列（HPF） 隊(duì)列2：分時(shí)進(jìn)程就緒隊(duì)列 （RR）

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

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

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

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

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

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

34、序(2)有終止的作業(yè)控制進(jìn)程等 待F作業(yè)調(diào)度(1)因內(nèi)存有n道作業(yè)而等待撤銷該作業(yè)控制進(jìn)程，做善后處理取一終止的作業(yè)控制進(jìn)程對(duì)應(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)度的算法時(shí)間片輪轉(zhuǎn)算法(RR)最短剩余時(shí)間優(yōu)先(SRTN)反饋排隊(duì)算法(FB)3.4 實(shí)時(shí)調(diào)度(real-time scheduling)實(shí)時(shí)任務(wù)：具有明確時(shí)間約束的計(jì)算任務(wù)。Eg.某時(shí)刻前必須開始處理某時(shí)刻前必須處理

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

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