吉林大學(xué)數(shù)據(jù)結(jié)構(gòu)課件 第三章 中斷與處理機(jī)調(diào)度

第三章中斷與處理機(jī)調(diào)度3.1中斷與中斷系統(tǒng)3.2處理機(jī)調(diào)度3.3調(diào)度級別與多級調(diào)度3.4實(shí)時(shí)調(diào)度3.5多處理機(jī)調(diào)度3.6系統(tǒng)舉例操作系統(tǒng)是中斷驅(qū)動的！Interruptdriven3.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)識別中斷源，當(dāng)有多個(gè)中斷源時(shí)，按緊迫程度排隊(duì)；保存現(xiàn)場；引出中斷處理程序。中斷響應(yīng)和處理的過程正運(yùn)行程序

①

⑥處理程序

④PSW’，PC’PC’:PSW,PC系統(tǒng)桟psw,pc……...②⑤③HALOS中斷3.1.2.1中斷源與中斷字中斷源引起中斷的事件。中斷寄存器保存與中斷事件相關(guān)信息的寄存器。中斷字中斷寄存器的內(nèi)容。例：IO中斷：設(shè)備狀態(tài)寄存器。3.1.2.2中斷類型與中斷向量強(qiáng)迫性中斷運(yùn)行程序不期望的時(shí)鐘中斷IO中斷控制臺中斷硬件故障中斷powerfailure內(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ù)svcn取返回值3.1.2.2中斷類型與中斷向量中斷裝置中斷處理程序運(yùn)行程序訪管指令運(yùn)行程序中斷裝置中斷處理程序clockIOconsolePowerfailuremalfunction強(qiáng)迫中斷：自愿中斷：SVCntrapn3.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,PC2I/O中斷向量PSW3,PC3console中斷向量PSW4,PC4硬件故障PSW5,PC5程序錯(cuò)誤……PSWn,PCn訪管中斷向量00000008001600240030

…0090時(shí)鐘中斷處理程序PC1:I/O中斷處理程序PC2:訪管中斷處理程序PCn:…系統(tǒng)空間3.1.2.3中斷嵌套與系統(tǒng)棧一般原則：高優(yōu)先級別中斷可以嵌入低優(yōu)先級中斷實(shí)現(xiàn)方法：中斷響應(yīng)后立即屏蔽不高于當(dāng)前中斷優(yōu)先級的中斷源。3.1.2.3中斷嵌套與系統(tǒng)棧中斷響應(yīng)后一般需要進(jìn)一步保存現(xiàn)場

關(guān)中斷（屏蔽所有中斷）進(jìn)一步保存現(xiàn)場（通用寄存器等）

開中斷（或開放高優(yōu)先級中斷）…...中斷處理…...關(guān)中斷（屏蔽所有中斷）恢復(fù)現(xiàn)場開中斷（或開放高優(yōu)先級中斷）中斷返回3.1.2.3中斷嵌套與系統(tǒng)棧(Cont.)……目態(tài)PSW1:PC1……管態(tài)PSW2:PC2……管態(tài)PSWn:PCn…中斷嵌套:……3.1.2.3中斷嵌套與系統(tǒng)棧(Cont.)……PSWn-1PCn-1……PSW2PC2PSW1PC1棧頂指針:系統(tǒng)棧:3.1.2.4中斷優(yōu)先級與中斷屏蔽中斷優(yōu)先級：硬件規(guī)定的中斷響應(yīng)次序，依據(jù):緊迫程度；處理時(shí)間。中斷屏蔽：高優(yōu)先級中斷事件處理不受低優(yōu)先級中斷打擾；程序調(diào)整中斷響應(yīng)次序。3.1.3中斷處理程序強(qiáng)迫性中斷自愿性中斷保存現(xiàn)場信息取中斷字分析中斷原因保存現(xiàn)場信息取調(diào)用號分析何種系統(tǒng)調(diào)用

中斷處理系統(tǒng)?；謴?fù)現(xiàn)場返回上層中斷或目態(tài)程序需要切換進(jìn)程轉(zhuǎn)dispatcher保存下降進(jìn)程現(xiàn)場到PCB選擇上升進(jìn)程由PCB恢復(fù)上升進(jìn)程現(xiàn)場TF3.1.3中斷處理程序強(qiáng)迫性中斷自愿性中斷關(guān)中斷進(jìn)一步保存現(xiàn)場到系統(tǒng)棧取中斷字分析中斷原因關(guān)中斷保存現(xiàn)場到系統(tǒng)棧取調(diào)用號分析何種系統(tǒng)調(diào)用

中斷處理由系統(tǒng)?；謴?fù)現(xiàn)場返回上層中斷或目態(tài)程序需要切換進(jìn)程轉(zhuǎn)dispatcher保存下降進(jìn)程現(xiàn)場到PCB選擇上升進(jìn)程由PCB恢復(fù)上升進(jìn)程現(xiàn)場TF開放高優(yōu)先級中斷關(guān)中斷等待事件調(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)換圖3.1.3.1IO中斷處理正常結(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.動態(tài)優(yōu)先數(shù))實(shí)現(xiàn)軟時(shí)鐘，啟動定時(shí)程序硬時(shí)鐘5ms發(fā)生一次中斷，軟時(shí)鐘50ms如死鎖檢測考慮進(jìn)程切換3.1.3.3控制臺中斷處理一個(gè)控制按鈕，一個(gè)中斷向量，一個(gè)中斷處理程序。3.1.3.4硬件故障處理電源故障處理掉電：內(nèi)存，寄存器外存停止設(shè)備停止處理機(jī)恢復(fù)：啟動處理機(jī)啟動設(shè)備外存內(nèi)存，寄存器UseUPSforcriticalapplications3.1.3.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é)助頁故障，缺段，（處理：動態(tài)調(diào)入）可以由用戶自己處理的中斷不影響系統(tǒng)和其它進(jìn)程除0，溢出，（處理：用戶處理，或OS處理）應(yīng)用程序自己處理中斷調(diào)試語句：on<中斷條件><中斷續(xù)元入口>例如：on<divide_zero>gotoLA;除0中斷時(shí)轉(zhuǎn)LA處理除0中斷時(shí)轉(zhuǎn)LB處理on<divide_zero>gotoLB除0中斷續(xù)元除0中斷續(xù)元LA:LB:相同中斷發(fā)生在不同位置可采用不同處理方法應(yīng)用程序自行處理中斷(Cont.)編譯時(shí)：生成中斷續(xù)元表：中斷續(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)場轉(zhuǎn)移到用戶棧（7）中斷續(xù)元入口送寄存器（OS中斷處理完成）（8）執(zhí)行中斷續(xù)元（9）用戶棧PSW和PC送寄存器（10）返回中斷斷點(diǎn)硬件操作系統(tǒng)中斷處理程序PC1系統(tǒng)棧……PSW,PC寄存器用戶?！璓SW’,LA……LA:用戶程序…...iret中斷續(xù)元表中斷續(xù)元①溢出中斷②PSW,PCPSW1,PC1③用戶處理中斷的過程⑦⑨⑥PSW,PC⑤④⑧3.1.3.6自愿性中斷的處理訪管指令（SuperVisorCall)形式：準(zhǔn)備參數(shù)SVCn取返回值系統(tǒng)調(diào)用（systemcall)形式：返回值=系統(tǒng)調(diào)用名稱（實(shí)參1,…,實(shí)參n)參數(shù)和返回值和存放位置是由OS規(guī)定的。3.1.3.6自愿性中斷的處理系統(tǒng)調(diào)用驅(qū)動表：(tabledriven)服務(wù)程序入口addr0…………addrm-1訪管號：0……...m-1Eg.UNIX3.2處理機(jī)調(diào)度3.2.1處理機(jī)調(diào)度算法按什么原則分配3.2.2處理機(jī)調(diào)度時(shí)機(jī)何時(shí)重新分配3.2.3處理機(jī)調(diào)度過程如何完成分配scheduling3.2.1處理機(jī)調(diào)度算法考慮因素（schedulingcriteria）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í)間的平均值CPUburstvs.I/Oburst陣發(fā)期:CPUburstcycle:進(jìn)程(線程)使用CPU計(jì)算；I/Oburstcycle:進(jìn)程(線程)使用設(shè)備I/O。進(jìn)程運(yùn)行行為：CPUburst,I/Oburst,CPUburst,I/Oburst,……CPU調(diào)度：考慮處于CPUburst進(jìn)程集合CPUburst時(shí)間根據(jù)以前行為推定。CPUburstvs.I/Oburst下一個(gè)CPUburst的長度估算令τn是估計(jì)的第n個(gè)CPU陣發(fā)期的長度，tn的值是進(jìn)程最近一次CPU陣發(fā)期長度，則有如下估算公式：τn+1=αtn+(1-α)τn參數(shù)α(0≤α≤1)控制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)程可以從運(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（FirstComeFirstServe)按進(jìn)程申請CPU（就緒）的次序。Process

Arrivaltime

BursttimeP1027P213P325CPU調(diào)度狀況可用Gantt圖表示．0273035P1P2P33.2.1.1先到先服務(wù)算法(Cont.)進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間P1027027271P2132730299.67P3253035336.6平均周轉(zhuǎn)時(shí)間=(27+29+33)/3=29.67平均帶權(quán)周轉(zhuǎn)時(shí)間=(1+9.67+6.6)/3=5.760273035P1P2P33.2.1.1先到先服務(wù)算法(Cont.)優(yōu)點(diǎn)：“公平”；缺點(diǎn):短作業(yè)等待時(shí)間長。3.2.1.2短作業(yè)優(yōu)先SJF（ShortestJobFirst)按CPUburst長度Process

Arrivaltime

BursttimeP1012P205P307P403GanttChart0381527P1P2P3P43.2.1.2短作業(yè)優(yōu)先0381527P1P2P3P4進(jìn)程到達(dá)時(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í)間最短。長作業(yè)可能被餓死。3.2.1.3最短剩余時(shí)間優(yōu)先算法(SRTN)

ShortestRemainingTimeNext可剝奪SJFProcess

Arrivaltime

BursttimeP1012P219P336P453Gantt圖P1P2P3P4P3P2P1013581219303.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)P1P2P3P4P3P2P1013581219303.2.1.4最高響應(yīng)比優(yōu)先(HRN)HighestResponseRatioNextRR=(BT+WT)/BT=1+WT/BT其中:BT=bursttimeWT=waittime優(yōu)點(diǎn):同時(shí)到達(dá)任務(wù),短者優(yōu)先長作業(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)程動態(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.)非剝奪式靜態(tài)優(yōu)先數(shù)獲得處理機(jī)的進(jìn)程運(yùn)行，直至終止等待剝奪式動(靜)態(tài)優(yōu)先數(shù)獲得處理機(jī)的進(jìn)程運(yùn)行，直至終止等待出現(xiàn)高優(yōu)先級的進(jìn)程3.2.1.5最高優(yōu)先數(shù)算法(Cont.)可搶占CPUProcess

Arrivaltime

Priority

BursttimeP1008P2215P3437P4023P5572GanttChart

0

3

4

5

7

131725P1P4P2P2P3P3P53.2.1.5最高優(yōu)先數(shù)算法(Cont.)進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間優(yōu)先級開始時(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

131725P1P4P2P2P3P3P53.2.1.5最高優(yōu)先數(shù)算法(Cont.)例子UNIX：preemptive+dynamicpriority（可搶占CPU動態(tài)優(yōu)先數(shù)）。計(jì)算公式：p_pri=min{127,USER+p_cpu/16+p_nice}定義USER=100；p_cpu:運(yùn)行進(jìn)程每20ms加1（優(yōu)先級降低），其它進(jìn)程每1200ms減10（優(yōu)先級提高）；p_nice:可以通過系統(tǒng)調(diào)用nice(…)修改的量：規(guī)定用戶進(jìn)程0~20之間（低），系統(tǒng)進(jìn)程-20~+20之間（高）。調(diào)度時(shí)取p_pri最小的。3.2.1.6循環(huán)輪轉(zhuǎn)算法(RR)RoundRobin(RR)基本輪轉(zhuǎn)時(shí)間片(quantum,timeslice)長度固定，不變；所有進(jìn)程等速向前推進(jìn)。改進(jìn)輪轉(zhuǎn)時(shí)間片長度不定，可變。適用于分時(shí)系統(tǒng)3.2.1.6循環(huán)輪轉(zhuǎn)算法(Cont.)時(shí)間片長度：幾十毫秒幾百毫秒(eg.50ms)過長：響應(yīng)速度慢；過短：系統(tǒng)開銷(overhead)大。適應(yīng)系統(tǒng)：分時(shí)3.2.1.6循環(huán)輪轉(zhuǎn)算法(Cont.)

RR可搶占CPU調(diào)度：timeslice=4msProcess

Arriveraltime

BursttimeP1017P2010P303GanttChartP1P2P3P1P2P1P2P1P1048111519232529303.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)P1P2P3P1P2P1P2P1P1048111519232529303.2.1.7多級隊(duì)列算法(MLQ)多級隊(duì)列多個(gè)就緒隊(duì)列，進(jìn)程所屬的隊(duì)列固定。例如：通用系統(tǒng)中：隊(duì)列1：實(shí)時(shí)進(jìn)程就緒隊(duì)列（HPF）隊(duì)列2：分時(shí)進(jìn)程就緒隊(duì)列（RR）隊(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)先級時(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)入最高級隊(duì)列,可盡早投入運(yùn)行,使用資源R；響應(yīng)速度快交互式進(jìn)程經(jīng)常進(jìn)入等待狀態(tài)(等待用戶輸入),一旦被喚醒(輸入完成),進(jìn)入最高級隊(duì)列,可盡快被調(diào)度選中,投入運(yùn)行,反應(yīng)及時(shí)；系統(tǒng)開銷小計(jì)算量大的進(jìn)程用完前面n-1級時(shí)間片,沒有處理完,落入底層隊(duì)列,調(diào)度頻率下降,但每次獲得較長的時(shí)間片。FeedBack3.2.2處理機(jī)調(diào)度時(shí)機(jī)運(yùn)行進(jìn)程結(jié)束；運(yùn)行進(jìn)程等待；處理機(jī)被剝奪。3.2.2處理機(jī)調(diào)度時(shí)機(jī)(Cont.)必然引起進(jìn)程切換的中斷進(jìn)程自愿結(jié)束,exit()進(jìn)程被強(qiáng)行終止；非法指令，越界，kill進(jìn)程等待可能引起進(jìn)程切換的中斷時(shí)鐘設(shè)備I/O中斷系統(tǒng)調(diào)用3.2.3處理機(jī)調(diào)度過程dispatcher保存下降進(jìn)程的現(xiàn)場寄存器(PSW,PC,SP,通用寄存器,地址寄存器)PCB選擇上升進(jìn)程按處理機(jī)調(diào)度算法恢復(fù)上升進(jìn)程的現(xiàn)場PCB寄存器先恢復(fù)通用寄存器和地址寄存器,最后恢復(fù)PSW,PCPSW和PC必須用一條指令恢復(fù)3.3調(diào)度級別與多級調(diào)度3.3.1交換與中級調(diào)度Swappingandmid-levelscheduling3.3.2作業(yè)與高級調(diào)度Jobandhigh-levelscheduling處理機(jī)調(diào)度為低級調(diào)度CPUscheduling=lowlevelscheduling3.3.1交換與中級調(diào)度術(shù)語交換(swapping)中級調(diào)度(mid-levelscheduling)并發(fā)度(degreeofmulti-programming)目標(biāo)：控制并發(fā)度并發(fā)度過高系統(tǒng)開銷大響應(yīng)速度慢內(nèi)存等資源緊張進(jìn)程(線程)頻繁進(jìn)入等待狀態(tài)Moredeadlocks3.3.1交換與中級調(diào)度剝奪就緒等待運(yùn)行選中等待事件事件發(fā)生就緒掛起等待掛起無終止創(chuàng)建創(chuàng)建結(jié)束換出換出換入換入事件發(fā)生UNIX的中級調(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è)與高級調(diào)度作業(yè)狀態(tài):提交:輸入機(jī)向輸入井傳送后備:在輸入井,尚未進(jìn)入內(nèi)存執(zhí)行:分解為進(jìn)程,在內(nèi)存處理完成:處理完畢,結(jié)果在輸出井退出:由輸出井向打印機(jī)傳送3.3.2作業(yè)與高級調(diào)度狀態(tài)轉(zhuǎn)換:提交后備:由SPOOLing輸入進(jìn)程完成SimultaneousPeripheralOperationOn-Line后備執(zhí)行:由作業(yè)調(diào)度(1)(高級調(diào)度)完成高級調(diào)度:系統(tǒng)進(jìn)程執(zhí)行完成:由作業(yè)調(diào)度(2)完成完成退出:由SPOOLing輸出進(jìn)程完成提交后備執(zhí)行完成退出SPOOLing輸入作業(yè)調(diào)度1作業(yè)調(diào)度2SPOOLing輸出3.3.2作業(yè)與高級調(diào)度(Cont.)批處理作業(yè)調(diào)度程序(1)：在后備作業(yè)集合中選擇作業(yè)，并為其建立作業(yè)控制進(jìn)程來處理該作業(yè)。作業(yè)調(diào)度程序(1)內(nèi)存已有n道作業(yè)等待T輸入井中有后備作業(yè)等待F訪問磁盤中作業(yè)控制表根據(jù)作業(yè)控制塊中控制參數(shù)按作業(yè)調(diào)度算法選擇后備作業(yè)作業(yè)狀態(tài)標(biāo)志為“執(zhí)行”為該作業(yè)建立作業(yè)控制進(jìn)程3.3.2作業(yè)與高級調(diào)度(Cont.)2.批處理作業(yè)調(diào)度程序(2)對終止的作業(yè)控制進(jìn)程進(jìn)行善后處理。作業(yè)調(diào)度程序(2)有終止的作業(yè)控制進(jìn)程等待F作業(yè)調(diào)度(1)等待完成撤銷該作業(yè)控制進(jìn)程，做善后處理取一終止的作業(yè)控制進(jìn)程對應(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-timescheduling)實(shí)時(shí)任務(wù)：具有明確時(shí)間約束的計(jì)算任務(wù)。Eg.某時(shí)刻前必須開始處理某時(shí)刻前必須處理完畢實(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í)(hardreal-time):必須滿足任務(wù)截止期要求.軟實(shí)時(shí)(softreal-time):期望滿足截止期要求.周期性vs.隨機(jī)性

周期性:每隔固定時(shí)間發(fā)生一次隨機(jī)性:由隨機(jī)事件觸發(fā)，其發(fā)生時(shí)刻不確定術(shù)語解釋Readytime:就緒時(shí)間Startingdeadline:開始截止期Processingtime:處理時(shí)間Completiondeadline:完成截止期Occurringperiod:發(fā)生周期Occurringfrequency:發(fā)生頻率周期性實(shí)時(shí)事務(wù)周期性實(shí)時(shí)事務(wù)可調(diào)度的必要條件:令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.85<1滿足可調(diào)度的必要條件周期性實(shí)時(shí)事務(wù)進(jìn)程就緒時(shí)間處理時(shí)間完成截止期發(fā)生周期A0102020B025505010/20+25/50=1,可調(diào)度(不考慮開銷)例子ProcessArrivaltimeExecutiontimecompletiondeadlineA(1)A(2)A(3)A(4)A(5)…...B(1)B(2)020406080…...0501010101010……252520406080100…...501003.4.1最早截止期調(diào)度EDF（EarliestDeadlineFirst)優(yōu)先選擇截止期最早的實(shí)時(shí)任務(wù)可搶先可以證明：對EDF來說，可調(diào)度充分條件是：在不可調(diào)度的條件下，可使錯(cuò)過截止期任務(wù)最小化例子:EarliestDeadlineFirst0102030405060708090100TimeA2A2dlA3A3dlA4A4dlB1A1A1dlB1dlB2B2dlA5A5dlA1B1A2B1A3B2A5B2A4A1A2B1A3A4A5B23.4.2速率單調(diào)調(diào)度RMS（RateMonotonicScheduling）提出于1973年面向周期性實(shí)時(shí)事務(wù)，非剝奪式優(yōu)先調(diào)度發(fā)生周期最短（頻度最高）的實(shí)時(shí)任務(wù)可調(diào)度條件：RMS的上限值n123456┇1.00.8280.7790.7560.7430.734┇ln20.693RMSvs.EDFRMS可調(diào)度條件強(qiáng)于EDFRMS調(diào)度較EDF實(shí)現(xiàn)簡單RMS例子：進(jìn)程ＴiCiA10020B15040C350100可調(diào)度，具體調(diào)度結(jié)果：A1B1C1A2B2A3A4B3C2020601601802202403003203604603.5多處理機(jī)調(diào)度問題：Mprocesses(threads)NprocessorsSMP：symmetricmulti-processorsallprocessorsareidentical(homogeneous)目標(biāo)：load-sharingseparatereadyqueueforeachprocessor,notreallybalanced;commonreadyqueueQforallprocessorseachprocessoraccessesQonitsown,master/slaveassignment.3.5.1自調(diào)度(selfscheduling)均衡調(diào)度(balancedscheduling)一個(gè)就緒隊(duì)列(多處理機(jī)訪問互斥)優(yōu)點(diǎn)不需要專門的處理機(jī)從事任務(wù)分派工作任務(wù)分配均衡缺點(diǎn)當(dāng)CPU較多時(shí),就緒隊(duì)列成為瓶頸線程兩次調(diào)度可能處于不同處理機(jī)不能保證同組線程同時(shí)調(diào)度自調(diào)度(selfscheduling)就緒隊(duì)列進(jìn)程(線程)進(jìn)程(線程)進(jìn)程(線程)CPUCPUCPU自調(diào)度(selfscheduling)例子:Mach,改進(jìn)的自調(diào)度全局隊(duì)列:系統(tǒng)一個(gè)局部隊(duì)列:每個(gè)CPU一個(gè)調(diào)度時(shí)首先考慮局部隊(duì)列然后考慮全局隊(duì)列3.5.2組調(diào)度(gangscheduling)將一組相關(guān)(合作)的線程同時(shí)分派到多個(gè)處理機(jī)上運(yùn)行避免合作線程之間的相互等待降低開銷,提高運(yùn)行效率例子:Cm*Taskforce(一組相關(guān)的計(jì)算)3.6系統(tǒng)舉例Linux進(jìn)程調(diào)度Windows2000/XP線程調(diào)度UNIX進(jìn)程調(diào)度（見第12章）三種特征進(jìn)程Real-timeFIFOReal-timeRoundRobinTimesharingGoodness-basedschedulingpriority0-40,(缺省值20),可通過nice系統(tǒng)調(diào)用調(diào)整，nice(value)中value的取值范圍為(-20,20)之間,取priority=20-value.counter進(jìn)程尚可運(yùn)行的剩余時(shí)間3.6.1Linux進(jìn)程調(diào)度Linux進(jìn)程調(diào)度counter對于運(yùn)行進(jìn)程來說，每個(gè)時(shí)鐘間隔(10ms，稱為一個(gè)jiffy)，將counter減1當(dāng)所有就緒進(jìn)程的counter配額下降到0時(shí)，重新計(jì)算所有進(jìn)程(包括等待進(jìn)程)的counter值

counter=(counter/2)+prioritygoodnessif(Real-time)goodness=1000+priorityif(Timesharing&&counter=0)goodness=0if(Timesharing&&counter>0)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、信號燈而被封鎖

;原來具有高goodness的進(jìn)程被解除封鎖

.調(diào)度效果

:實(shí)時(shí)優(yōu)先于分時(shí)

交互和I/O進(jìn)程優(yōu)先于CPU進(jìn)程

Linux對稱多處理Linux2.0是支持