《計算機操作系統(tǒng)教程》(第3版)-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ū)動的！Interruptdriven第三章中斷與處理機調(diào)度3.1中斷與中斷系統(tǒng)操作13.1中斷與中斷系統(tǒng)3.1.1中斷的概念3.1.2中斷裝置3.1.3中斷處理程序3.1中斷與中斷系統(tǒng)3.1.1中斷的概念23.1.1中斷的概念處理機在運行過程中，出現(xiàn)了某一事件，必須中止正在運行的程序，轉(zhuǎn)去處理這個事件，然后再返回原來運行的程序，這一過程稱為中斷。中斷系統(tǒng)：中斷裝置(硬件)中斷處理程序(軟件)3.1.1中斷的概念處理機在運行過程中，出現(xiàn)了某一事件，必33.1.2中斷裝置發(fā)現(xiàn)并響應(yīng)中斷的硬件機構(gòu)識別中斷源，當(dāng)有多個中斷源時，按緊迫程度排隊；保存現(xiàn)場；引出中斷處理程序。3.1.2中斷裝置發(fā)現(xiàn)并響應(yīng)中斷的硬件機構(gòu)4中斷響應(yīng)和處理的過程正運行程序16處理程序4PSW’，PC’PC’:PSW,PC系統(tǒng)桟psw,pc……...253HALOS中斷中斷響應(yīng)和處理的過程正運行程序處理程序PSW’，PC’PC’53.1.2.1中斷源與中斷字中斷源引起中斷的事件。中斷寄存器保存與中斷事件相關(guān)信息的寄存器。中斷字中斷寄存器的內(nèi)容。例：IO中斷：設(shè)備狀態(tài)寄存器。3.1.2.1中斷源與中斷字中斷源63.1.2.2中斷類型與中斷向量強迫性中斷運行程序不期望的時鐘中斷IO中斷控制臺中斷硬件故障中斷powerfailure內(nèi)存校驗錯程序性中斷越界，越權(quán)缺頁溢出，除0非法指令自愿性中斷運行程序期望的系統(tǒng)調(diào)用訪管指令系統(tǒng)調(diào)用fd=open(fname,mode)訪管指令準備參數(shù)svcn取返回值3.1.2.2中斷類型與中斷向量強迫性中斷自愿性中斷73.1.2.2中斷類型與中斷向量中斷裝置中斷處理程序運行程序訪管指令運行程序中斷裝置中斷處理程序clockIOconsolePowerfailuremalfunction強迫中斷：自愿中斷：SVCntrapn3.1.2.2中斷類型與中斷向量中斷裝置中斷處運行程序83.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中斷類型與中斷向量中斷向量：中斷處理程序的運93.1.2.2中斷類型與中斷向量PSW1,PC1時鐘中斷向量PSW2,PC2I/O中斷向量PSW3,PC3console中斷向量PSW4,PC4硬件故障PSW5,PC5程序錯誤……PSWn,PCn訪管中斷向量00000008001600240030

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

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

開中斷（或開放高優(yōu)先級中斷）…...中斷處理…...關(guān)中斷（屏蔽所有中斷）恢復(fù)現(xiàn)場開中斷（或開放高優(yōu)先級中斷）中斷返回3.1.2.3中斷嵌套與系統(tǒng)棧中斷響應(yīng)后一般需要進一步保存123.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.)…目態(tài)PSW1133.1.2.3中斷嵌套與系統(tǒng)棧(Cont.)……PSWn-1PCn-1……PSW2PC2PSW1PC1棧頂指針:系統(tǒng)棧:3.1.2.3中斷嵌套與系統(tǒng)棧(Cont.)棧頂指針:系統(tǒng)143.1.2.4中斷優(yōu)先級與中斷屏蔽中斷優(yōu)先級：硬件規(guī)定的中斷響應(yīng)次序，依據(jù):緊迫程度；處理時間。中斷屏蔽：高優(yōu)先級中斷事件處理不受低優(yōu)先級中斷打擾；程序調(diào)整中斷響應(yīng)次序。3.1.2.4中斷優(yōu)先級與中斷屏蔽中斷優(yōu)先級：153.1.3中斷處理程序強迫性中斷自愿性中斷保存現(xiàn)場信息取中斷字分析中斷原因保存現(xiàn)場信息取調(diào)用號分析何種系統(tǒng)調(diào)用

中斷處理（如等待轉(zhuǎn)dispatcher)繼續(xù)處理嵌套中斷系統(tǒng)?；謴?fù)現(xiàn)場返回上層中斷需要切換進程系統(tǒng)?；謴?fù)現(xiàn)場返回目態(tài)程序轉(zhuǎn)dispatcherTFFT3.1.3中斷處理程序強迫性中斷自愿性中斷保存現(xiàn)場信息保存163.1.3.1IO中斷處理正常結(jié)束繼續(xù)傳輸；喚醒相關(guān)進程。傳輸錯誤復(fù)執(zhí)（eg.3次)；報告系統(tǒng)操作員。3.1.3.1IO中斷處理正常結(jié)束173.1.3.2時鐘中斷處理Housekeeping進程管理重新計算進程調(diào)度參數(shù)(eg.動態(tài)優(yōu)先數(shù))實現(xiàn)軟時鐘，啟動定時程序硬時鐘5ms發(fā)生一次中斷，軟時鐘50ms考慮進程切換3.1.3.2時鐘中斷處理Housekeeping183.1.3.3控制臺中斷處理一個控制按鈕，一個中斷向量，一個中斷處理程序。3.1.3.3控制臺中斷處理一個控制按鈕，一個中斷向量，一193.1.3.4硬件故障處理電源故障處理掉電：內(nèi)存，寄存器外存停止設(shè)備停止處理機恢復(fù)：啟動處理機啟動設(shè)備外存內(nèi)存，寄存器UseUPSforcriticalapplications3.1.3.4硬件故障處理電源故障處理UseUPS203.1.3.4硬件故障處理(cont.)內(nèi)存故障處理海明校驗，奇偶校驗錯誤下雨檢查劃出系統(tǒng)報告操作員3.1.3.4硬件故障處理(cont.)內(nèi)存故障處理213.1.3.5程序性中斷的處理只能由操作系統(tǒng)處理的中斷影響系統(tǒng)或其它進程越界，非法指令，（處理：終止進程、調(diào)試）需要系統(tǒng)管理或協(xié)助頁故障，缺段，（處理：動態(tài)調(diào)入）可以由用戶自己處理的中斷不影響系統(tǒng)和其它進程除0，溢出，（處理：用戶處理，或OS處理）3.1.3.5程序性中斷的處理只能由操作系統(tǒng)處理的中斷22應(yīng)用程序自己處理中斷調(diào)試語句：on<中斷條件><中斷續(xù)元入口>例如：on<divide_zero>gotoLA;除0中斷時轉(zhuǎn)LA處理除0中斷時轉(zhuǎn)LB處理on<divide_zero>gotoLB除0中斷續(xù)元除0中斷續(xù)元LA:LB:相同中斷發(fā)生在不同位置可采用不同處理方法應(yīng)用程序自己處理中斷調(diào)試語句：on<中斷條件><中斷續(xù)元23應(yīng)用程序自行處理中斷(Cont.)編譯時：生成中斷續(xù)元表：中斷續(xù)元入口0中斷續(xù)元入口1……中斷續(xù)元入口n中斷事件0:中斷事件1:中斷事件n:…...運行時：執(zhí)行調(diào)試語句，填寫中斷續(xù)元表。中斷時：根據(jù)中斷原因查中斷續(xù)元表，為0，用戶未規(guī)定中斷續(xù)元，由OS標準處理；非0，用戶已規(guī)定中斷續(xù)元，由用戶處理。初始時均為0應(yīng)用程序自行處理中斷(Cont.)編譯時：生成中斷續(xù)元表：中24圖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）返回中斷斷點圖3-9（P47）步驟：253.1.3.6自愿性中斷的處理訪管指令（SuperVisorCall)形式：準備參數(shù)SVCn取返回值系統(tǒng)調(diào)用（systemcall)形式：返回值=系統(tǒng)調(diào)用名稱（實參1,…,實參n)參數(shù)和返回值和存放位置是由OS規(guī)定的。3.1.3.6自愿性中斷的處理訪管指令（SuperViso263.1.3.6自愿性中斷的處理系統(tǒng)調(diào)用驅(qū)動表：(tabledriven)服務(wù)程序入口addr0…………addrm-1訪管號：0……...m-1Eg.UNIX3.1.3.6自愿性中斷的處理系統(tǒng)調(diào)用驅(qū)動表：(table273.2處理機調(diào)度3.2.1處理機調(diào)度算法按什么原則分配3.2.2處理機調(diào)度時機何時重新分配3.2.3處理機調(diào)度過程如何完成分配scheduling3.2處理機調(diào)度3.2.1處理機調(diào)度算法scheduli283.2.1處理機調(diào)度算法考慮因素（schedulingcriteria）CPU利用率;(max)吞吐量;(max)周轉(zhuǎn)時間;(min)響應(yīng)時間;(min)系統(tǒng)開銷;(min)3.2.1處理機調(diào)度算法考慮因素（schedulingc29調(diào)度參數(shù)周轉(zhuǎn)時間：完成時間-進入時間平均周轉(zhuǎn)時間：周轉(zhuǎn)時間的平均值帶權(quán)周轉(zhuǎn)時間：周轉(zhuǎn)時間/運行時間平均帶權(quán)周轉(zhuǎn)時間：帶權(quán)周轉(zhuǎn)時間的平均值調(diào)度參數(shù)周轉(zhuǎn)時間：完成時間-進入時間平均周轉(zhuǎn)時間：周轉(zhuǎn)時間的30CPUburstvs.I/Oburst陣發(fā)期:CPUburstcycle:進程(線程)使用CPU計算；I/Oburstcycle:進程(線程)使用設(shè)備I/O。進程運行行為：CPUburst,I/Oburst,CPUburst,I/Oburst,……CPU調(diào)度：考慮處于CPUburst進程集合CPUburst時間根據(jù)以前行為推定。CPUburstvs.I/Oburst陣發(fā)期:31CPUburstvs.I/Oburst下一個CPUburst的長度估算令τn是估計的第n個CPU陣發(fā)期的長度，tn的值是進程最近一次CPU陣發(fā)期長度，則有如下估算公式：τn+1=αtn+(1-α)τn參數(shù)α(0≤α≤1)控制tn和τn在公式中起的作用：當(dāng)α=0時，τn+1=τn；當(dāng)α=1時，τn+1=tn。通常α取。CPUburstvs.I/Oburst下一個CPU32剝奪式調(diào)度與非剝奪式調(diào)度剝奪式(preemptive)就緒進程可以從運行進程手中搶占CPU。進程運行,直到結(jié)束、等待或被搶先非剝奪式(non-preemptive)就緒進程不可從運行進程手中搶占CPU。進程運行,直到結(jié)束或等待剝奪式調(diào)度與非剝奪式調(diào)度剝奪式(preemptive)333.2.1.1先到先服務(wù)算法FCFS（FirstComeFirstServe)按進程申請CPU（就緒）的次序。Process

Arrivaltime

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

Arrivaltime

BursttimeP1012P205P307P403GanttChart0381527P1P2P3P43.2.1.2短作業(yè)優(yōu)先SJF（ShortestJob373.2.1.2短作業(yè)優(yōu)先0381527P1P2P3P4進程到達時間運行時間開始時間完成時間周轉(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)先038383.2.1.2短作業(yè)優(yōu)先特點：假定所有任務(wù)同時到達，平均等待時間最短。長作業(yè)可能被餓死。3.2.1.2短作業(yè)優(yōu)先特點：39最高響應(yīng)比優(yōu)先(HRN)HighestResponseRatioNextRR=(BT+WT)/BT=1+WT/BT其中:BT=bursttimeWT=waittime優(yōu)點:同時到達任務(wù),短者優(yōu)先長作業(yè)隨等待時間增加響應(yīng)比增加最高響應(yīng)比優(yōu)先(HRN)HighestResponseR403.2.1.4最高優(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.4最高優(yōu)先數(shù)算法(HPF)靜態(tài)優(yōu)先數(shù)(stat413.2.1.4最高優(yōu)先數(shù)算法(Cont.)非剝奪式靜態(tài)優(yōu)先數(shù)獲得處理機的進程運行，直至終止等待剝奪式動(靜)態(tài)優(yōu)先數(shù)獲得處理機的進程運行，直至終止等待出現(xiàn)高優(yōu)先級的進程3.2.1.4最高優(yōu)先數(shù)算法(Cont.)非剝奪式靜態(tài)優(yōu)先423.2.1.4最高優(yōu)先數(shù)算法(Cont.)可搶占CPUProcess

Arrivaltime

Priority

BursttimeP1008P2215P3437P4023P5572GanttChart

0

3

4

5

7

131725P1P4P2P2P3P3P53.2.1.4最高優(yōu)先數(shù)算法(Cont.)可搶占CPU0433.2.1.4最高優(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

131725P1P4P2P2P3P3P53.2.1.4最高優(yōu)先數(shù)算法(Cont.)進程到達時間運行443.2.1.4最高優(yōu)先數(shù)算法(Cont.)例子UNIX：preemptive+dynamicpriority（可搶占CPU動態(tài)優(yōu)先數(shù)）。計算公式：p_pri=min{127,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ī)定用戶進程0~20之間（低），系統(tǒng)進程-20~+20之間（高）。調(diào)度時取p_pri最小的。3.2.1.4最高優(yōu)先數(shù)算法(Cont.)例子UNIX：p453.2.1.5循環(huán)輪轉(zhuǎn)算法(RR)RoundRobin(RR)基本輪轉(zhuǎn)時間片(quantum,timeslice)長度固定，不變；所有進程等速向前推進。改進輪轉(zhuǎn)時間片長度不定，可變。適用于分時系統(tǒng)3.2.1.5循環(huán)輪轉(zhuǎn)算法(RR)RoundRobin(463.2.1.5循環(huán)輪轉(zhuǎn)算法(Cont.)時間片長度：幾十毫秒幾百毫秒(eg.50ms)過長：響應(yīng)速度慢；過短：系統(tǒng)開銷(overhead)大。適應(yīng)系統(tǒng)：分時3.2.1.5循環(huán)輪轉(zhuǎn)算法(Cont.)時間片長度：473.2.1.6多級隊列算法(MLQ)多級隊列多個就緒隊列，進程所屬的隊列固定。例如：通用系統(tǒng)中：隊列1：實時進程就緒隊列（HPF）隊列2：分時進程就緒隊列（RR）隊列3：批處理進程就緒隊列（HPF）3.2.1.6多級隊列算法(MLQ)多級隊列483.2.1.7最短剩余時間優(yōu)先(SRTN)ShortestRemainingTimeNext可剝奪SJFProcess

Arrivaltime

BursttimeP1012P215P337P453Gantt圖01691627P1P2P3P1P43.2.1.7最短剩余時間優(yōu)先(SRTN)Shortest493.2.1.7最短剩余時間優(yōu)先(SRTN)進程到達時間運行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間P1012027272.25P2151651P337916131.86P4536941.33平均周轉(zhuǎn)時=(27+5+13+4)/4=12.25平均帶權(quán)周轉(zhuǎn)時間=(2.25+1+1.86+1.33)=1.61

01691627P1P2P3P1P43.2.1.7最短剩余時間優(yōu)先(SRTN)進程到達時間運行503.2.1.8反饋排隊算法(FB)Feed-Back:多個就緒隊列，進程所屬隊列可變。Q1（RR,HPF）Q2（RR,HPF）Qn（RR,HPF）運行s1時間片運行s2時間片….創(chuàng)建喚醒優(yōu)先級時間片運行sn時間片3.2.1.8反饋排隊算法(FB)Feed-Back:Q513.2.1.8反饋排隊算法(Cont.)調(diào)度效果：資源利用率高P1等待P2占有的資源R,P2釋放R,分給P1,P1被喚醒,進入最高級隊列,可盡早投入運行,使用資源R；響應(yīng)速度快交互式進程經(jīng)常進入等待狀態(tài)(等待用戶輸入),一旦被喚醒(輸入完成),進入最高級隊列,可盡快被調(diào)度選中,投入運行,反應(yīng)及時；系統(tǒng)開銷小計算量大的進程用完前面n-1級時間片,沒有處理完,落入底層隊列,調(diào)度頻率下降,但每次獲得較長的時間片。FeedBack3.2.1.8反饋排隊算法(Cont.)調(diào)度效果：Fee523.2.2處理機調(diào)度時機運行進程結(jié)束；運行進程等待；處理機被剝奪。目態(tài)（Pi運行）目態(tài)（Pj運行）管態(tài)管態(tài)…...中斷中斷中斷返回返回返回Pi=Pj:未發(fā)生進程切換；Pi<>Pj:發(fā)生了進程切換。3.2.2處理機調(diào)度時機運行進程結(jié)束；目態(tài)（Pi運行）管態(tài)533.2.2處理機調(diào)度時機(Cont.)必然引起進程切換的中斷進程自愿結(jié)束,exit()進程被強行終止；非法指令，越界，kill進程等待可能引起進程切換的中斷時鐘系統(tǒng)調(diào)用3.2.2處理機調(diào)度時機(Cont.)必然引起進程切換的中543.2.3處理機調(diào)度過程dispatcher保存下降進程的現(xiàn)場寄存器(PSW,PC,SP,通用寄存器,地址寄存器)PCB選擇上升進程按處理機調(diào)度算法恢復(fù)上升進程的現(xiàn)場PCB寄存器先恢復(fù)通用寄存器和地址寄存器,最后恢復(fù)PSW,PCPSW和PC必須用一條指令恢復(fù)3.2.3處理機調(diào)度過程dispatcher553.3調(diào)度級別與多級調(diào)度3.3.1交換與中級調(diào)度Swappingandmid-levelscheduling3.3.2作業(yè)與高級調(diào)度Jobandhigh-levelscheduling處理機調(diào)度為低級調(diào)度CPUscheduling=lowlevelscheduling3.3調(diào)度級別與多級調(diào)度3.3.1交換與中級調(diào)度處理機調(diào)563.3.1交換與中級調(diào)度術(shù)語交換(swapping)中級調(diào)度(mid-levelscheduling)并發(fā)度(degreeofmulti-programming)目標：控制并發(fā)度并發(fā)度過高系統(tǒng)開銷大響應(yīng)速度慢內(nèi)存等資源緊張進程(線程)頻繁進入等待狀態(tài)Moredeadlocks3.3.1交換與中級調(diào)度術(shù)語573.3.1交換與中級調(diào)度剝奪就緒等待運行選中等待事件事件發(fā)生就緒掛起等待掛起無終止創(chuàng)建創(chuàng)建結(jié)束換出換出換入換入事件發(fā)生3.3.1交換與中級調(diào)度剝奪就緒等待運行58UNIX的中級調(diào)度（sched#0)移入SRUN狀態(tài)進程如內(nèi)存不夠，移出SWAIT和SSTOP狀態(tài)進程；如還不夠，移出SSLEEP和SRUN狀態(tài)進程；條件：待移入進程在外存時間>=3秒；待移出進程在內(nèi)存時間>=2秒。UNIX的中級調(diào)度（sched#0)移入SRUN狀態(tài)進程593.3.2作業(yè)與高級調(diào)度作業(yè)狀態(tài):提交:輸入機向輸入井傳送后備:在輸入井,尚未進入內(nèi)存執(zhí)行:分解為進程,在內(nèi)存處理完成:處理完畢,結(jié)果在輸出井退出:由輸出井向打印機傳送3.3.2作業(yè)與高級調(diào)度作業(yè)狀態(tài):603.3.2作業(yè)與高級調(diào)度狀態(tài)轉(zhuǎn)換:提交后備:由SPOOLing輸入進程完成SimultaneousPeripheralOperationOn-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輸出3.3.2作業(yè)與高級調(diào)度狀態(tài)轉(zhuǎn)換:提交后備執(zhí)行完成退出SP61作業(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)作業(yè)調(diào)度算法適合批作業(yè)調(diào)度的算法623.4實時調(diào)度(real-timescheduling)實時任務(wù)：具有明確時間約束的計算任務(wù)。Eg.某時刻前必須開始處理某時刻前必須處理完畢實時調(diào)度：合理安排就緒實時任務(wù)的執(zhí)行次序，滿足每個實時任務(wù)時間約束條件的調(diào)度。3.4實時調(diào)度(real-timescheduling)63實時任務(wù)分類硬實時vs.軟實時

硬實時(hardreal-time):必須滿足任務(wù)截止期要求.軟實時(softreal-time):期望滿足截止期要求.周期性vs.隨機性

周期性:每隔固定時間發(fā)生一次隨機性:由隨機事件觸發(fā)，其發(fā)生時刻不確定實時任務(wù)分類硬實時vs.軟實時64術(shù)語解釋Readytime:就緒時間Startingdeadline:開始截止期Processingtime:處理時間Completiondeadline:完成截止期Occurringfrequency:發(fā)生頻率術(shù)語解釋Readytime:就緒時間65周期性實時事務(wù)周期性實時事務(wù):令Ci為任務(wù)Pi處理時間，Ti為任務(wù)Pi的發(fā)生周期，則任務(wù)P1,…,Pm可調(diào)度的必要條件為：

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

counter=(counter/2)+prioritygoodnessif(Real-time)goodness=1000+priorityif(Timesharing&&counter=0)goodness=0if(Timesharing&&counter>0)goodness=counter+priorityLinux進程調(diào)度counter82Linux進程調(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進程調(diào)度調(diào)度發(fā)生時刻：83Linux對稱多處理是支持對稱多處理硬件的第一個Linux核心;進程或線程可以同時運行在多個處理機上.為保持核心非剝奪同步要求，SMP通過一個唯一的核心自旋鎖(spin-lock)來保證任何時刻最多只有一個處理機執(zhí)行核心代碼,支持真正意義上的SMP：將一個自旋鎖分解為若干個相互獨立的自旋鎖，分別用于保護核心代碼不相交的子集.Linux對稱多處理是支持對稱多處理硬件的第一個Linux843.6.2Windows2000/XP線程調(diào)度MainFeatures：Threadlevelscheduling;Realtime+foreground+background;realtime:nodeadlinescheduling;foreground:GUIwindowbackground:non-interactivePreemptive+dynamicpriority+RR+Feedback;SymmetricMulti-Processor(SMP)support;3.6.2Windows2000/XP線程調(diào)度Main85優(yōu)先級別16個實時優(yōu)先級（16-31）一些內(nèi)核線程應(yīng)用程序提升為實時優(yōu)先級需要有權(quán)限不是真正意義上的實時調(diào)度15個可變線程優(yōu)先級（1-15）基本優(yōu)先級vs.當(dāng)前優(yōu)先級線程基本優(yōu)先級繼承進程基本優(yōu)先級,可上下浮動2如:進程基本優(yōu)先級4,其線程基本優(yōu)先級2—6,當(dāng)前優(yōu)先級在2—15范圍內(nèi)變動.可動態(tài)提升運行完一個quantum之后自動下降,不低于基本優(yōu)先級1個系統(tǒng)線程優(yōu)先級（0）優(yōu)先級別16個實時優(yōu)先級（16-31）86優(yōu)先級提升優(yōu)先級提升IO操作完成事件等待結(jié)束前臺進程中的線程完成一個等待操作由于窗口活動而喚醒GUI線程就緒超過一定時限，未獲得處理機優(yōu)先級提升不會超過15優(yōu)先級提升優(yōu)先級提升87搶占CPU搶先情形被喚醒線程優(yōu)先級高于運行線程優(yōu)先級；某線程的優(yōu)先級動態(tài)變化被搶先線程回到相應(yīng)就緒隊列時間配額實時線程：重新分配完整時間配額其它線程：保持剩余配額搶占CPU搶先情形88時間配額(quantum)配額長度：6--36時鐘中斷（15ms發(fā)生一次）減3，2--12次時鐘中斷（30ms--180ms）配額用完配額用完后進入就緒隊列，優(yōu)先級下降時間配額(quantum)配額長度：6--3689SMP上的線程調(diào)度線程與CPU的親合關(guān)系每個進程有一個處理器親合掩碼，缺省為所有處理器的集合線程繼承其進程的親合掩碼親合掩碼可以修改SetProcessAffinityMask,SetThreadAffinityMask;SMP上的線程調(diào)度線程與CPU的親合關(guān)系90SMP上的線程調(diào)度線程的理想處理器（Idealprocessor）首選處理器：第二處理器：（在內(nèi)核線程控制塊中）理想處理器確定線程創(chuàng)建時隨機確定，分散各個線程與處理機對應(yīng)關(guān)系。線程可修改SetThreadIdealProcessorSMP上的線程調(diào)度線程的理想處理器（Idealproces91就緒線程對處理器的選擇有空閑處理器首選處理器第二處理器當(dāng)前執(zhí)行處理器（正執(zhí)行調(diào)度代碼）由高到低順序找空閑的處理器無空閑處理器，考慮搶先首選處理器第二處理器可運行編號最大處理器不能搶先進入相應(yīng)的就緒隊列就緒線程對處理器的選擇有空閑處理器92處理器對就緒線程的選擇空閑處理器調(diào)度線程上次在此CPU上運行（二級緩沖利用）線程的理想處理器是該CPU處于就緒狀態(tài)時間超過2個quantum優(yōu)先級別大于等于24處理器對就緒線程的選擇空閑處理器調(diào)度93作業(yè)#1進程切換時需要保存哪些現(xiàn)場信息？請盡量考慮完全。由核心返回目態(tài)程序時，進程的PSW和PC為何必須用一條機器指令同時恢復(fù)？對如下三個實時任務(wù):T1=100,C1=50;T2=200,C2=30;T3=500,C3=100.采用EDF算法和RMS算法是否可調(diào)度?如是畫出對應(yīng)的Gantt圖,否則說明原因。作業(yè)#1進程切換時需要保存哪些現(xiàn)場信息？請盡量考慮完全。94第三章中斷與處理機調(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ū)動的！Interruptdriven第三章中斷與處理機調(diào)度3.1中斷與中斷系統(tǒng)操作953.1中斷與中斷系統(tǒng)3.1.1中斷的概念3.1.2中斷裝置3.1.3中斷處理程序3.1中斷與中斷系統(tǒng)3.1.1中斷的概念963.1.1中斷的概念處理機在運行過程中，出現(xiàn)了某一事件，必須中止正在運行的程序，轉(zhuǎn)去處理這個事件，然后再返回原來運行的程序，這一過程稱為中斷。中斷系統(tǒng)：中斷裝置(硬件)中斷處理程序(軟件)3.1.1中斷的概念處理機在運行過程中，出現(xiàn)了某一事件，必973.1.2中斷裝置發(fā)現(xiàn)并響應(yīng)中斷的硬件機構(gòu)識別中斷源，當(dāng)有多個中斷源時，按緊迫程度排隊；保存現(xiàn)場；引出中斷處理程序。3.1.2中斷裝置發(fā)現(xiàn)并響應(yīng)中斷的硬件機構(gòu)98中斷響應(yīng)和處理的過程正運行程序16處理程序4PSW’，PC’PC’:PSW,PC系統(tǒng)桟psw,pc……...253HALOS中斷中斷響應(yīng)和處理的過程正運行程序處理程序PSW’，PC’PC’993.1.2.1中斷源與中斷字中斷源引起中斷的事件。中斷寄存器保存與中斷事件相關(guān)信息的寄存器。中斷字中斷寄存器的內(nèi)容。例：IO中斷：設(shè)備狀態(tài)寄存器。3.1.2.1中斷源與中斷字中斷源1003.1.2.2中斷類型與中斷向量強迫性中斷運行程序不期望的時鐘中斷IO中斷控制臺中斷硬件故障中斷powerfailure內(nèi)存校驗錯程序性中斷越界，越權(quán)缺頁溢出，除0非法指令自愿性中斷運行程序期望的系統(tǒng)調(diào)用訪管指令系統(tǒng)調(diào)用fd=open(fname,mode)訪管指令準備參數(shù)svcn取返回值3.1.2.2中斷類型與中斷向量強迫性中斷自愿性中斷1013.1.2.2中斷類型與中斷向量中斷裝置中斷處理程序運行程序訪管指令運行程序中斷裝置中斷處理程序clockIOconsolePowerfailuremalfunction強迫中斷：自愿中斷：SVCntrapn3.1.2.2中斷類型與中斷向量中斷裝置中斷處運行程序1023.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中斷類型與中斷向量中斷向量：中斷處理程序的運1033.1.2.2中斷類型與中斷向量PSW1,PC1時鐘中斷向量PSW2,PC2I/O中斷向量PSW3,PC3console中斷向量PSW4,PC4硬件故障PSW5,PC5程序錯誤……PSWn,PCn訪管中斷向量00000008001600240030

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

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

開中斷（或開放高優(yōu)先級中斷）…...中斷處理…...關(guān)中斷（屏蔽所有中斷）恢復(fù)現(xiàn)場開中斷（或開放高優(yōu)先級中斷）中斷返回3.1.2.3中斷嵌套與系統(tǒng)棧中斷響應(yīng)后一般需要進一步保存1063.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.)…目態(tài)PSW11073.1.2.3中斷嵌套與系統(tǒng)棧(Cont.)……PSWn-1PCn-1……PSW2PC2PSW1PC1棧頂指針:系統(tǒng)棧:3.1.2.3中斷嵌套與系統(tǒng)棧(Cont.)棧頂指針:系統(tǒng)1083.1.2.4中斷優(yōu)先級與中斷屏蔽中斷優(yōu)先級：硬件規(guī)定的中斷響應(yīng)次序，依據(jù):緊迫程度；處理時間。中斷屏蔽：高優(yōu)先級中斷事件處理不受低優(yōu)先級中斷打擾；程序調(diào)整中斷響應(yīng)次序。3.1.2.4中斷優(yōu)先級與中斷屏蔽中斷優(yōu)先級：1093.1.3中斷處理程序強迫性中斷自愿性中斷保存現(xiàn)場信息取中斷字分析中斷原因保存現(xiàn)場信息取調(diào)用號分析何種系統(tǒng)調(diào)用

中斷處理（如等待轉(zhuǎn)dispatcher)繼續(xù)處理嵌套中斷系統(tǒng)棧恢復(fù)現(xiàn)場返回上層中斷需要切換進程系統(tǒng)?；謴?fù)現(xiàn)場返回目態(tài)程序轉(zhuǎn)dispatcherTFFT3.1.3中斷處理程序強迫性中斷自愿性中斷保存現(xiàn)場信息保存1103.1.3.1IO中斷處理正常結(jié)束繼續(xù)傳輸；喚醒相關(guān)進程。傳輸錯誤復(fù)執(zhí)（eg.3次)；報告系統(tǒng)操作員。3.1.3.1IO中斷處理正常結(jié)束1113.1.3.2時鐘中斷處理Housekeeping進程管理重新計算進程調(diào)度參數(shù)(eg.動態(tài)優(yōu)先數(shù))實現(xiàn)軟時鐘，啟動定時程序硬時鐘5ms發(fā)生一次中斷，軟時鐘50ms考慮進程切換3.1.3.2時鐘中斷處理Housekeeping1123.1.3.3控制臺中斷處理一個控制按鈕，一個中斷向量，一個中斷處理程序。3.1.3.3控制臺中斷處理一個控制按鈕，一個中斷向量，一1133.1.3.4硬件故障處理電源故障處理掉電：內(nèi)存，寄存器外存停止設(shè)備停止處理機恢復(fù)：啟動處理機啟動設(shè)備外存內(nèi)存，寄存器UseUPSforcriticalapplications3.1.3.4硬件故障處理電源故障處理UseUPS1143.1.3.4硬件故障處理(cont.)內(nèi)存故障處理海明校驗，奇偶校驗錯誤下雨檢查劃出系統(tǒng)報告操作員3.1.3.4硬件故障處理(cont.)內(nèi)存故障處理1153.1.3.5程序性中斷的處理只能由操作系統(tǒng)處理的中斷影響系統(tǒng)或其它進程越界，非法指令，（處理：終止進程、調(diào)試）需要系統(tǒng)管理或協(xié)助頁故障，缺段，（處理：動態(tài)調(diào)入）可以由用戶自己處理的中斷不影響系統(tǒng)和其它進程除0，溢出，（處理：用戶處理，或OS處理）3.1.3.5程序性中斷的處理只能由操作系統(tǒng)處理的中斷116應(yīng)用程序自己處理中斷調(diào)試語句：on<中斷條件><中斷續(xù)元入口>例如：on<divide_zero>gotoLA;除0中斷時轉(zhuǎn)LA處理除0中斷時轉(zhuǎn)LB處理on<divide_zero>gotoLB除0中斷續(xù)元除0中斷續(xù)元LA:LB:相同中斷發(fā)生在不同位置可采用不同處理方法應(yīng)用程序自己處理中斷調(diào)試語句：on<中斷條件><中斷續(xù)元117應(yīng)用程序自行處理中斷(Cont.)編譯時：生成中斷續(xù)元表：中斷續(xù)元入口0中斷續(xù)元入口1……中斷續(xù)元入口n中斷事件0:中斷事件1:中斷事件n:…...運行時：執(zhí)行調(diào)試語句，填寫中斷續(xù)元表。中斷時：根據(jù)中斷原因查中斷續(xù)元表，為0，用戶未規(guī)定中斷續(xù)元，由OS標準處理；非0，用戶已規(guī)定中斷續(xù)元，由用戶處理。初始時均為0應(yīng)用程序自行處理中斷(Cont.)編譯時：生成中斷續(xù)元表：中118圖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）返回中斷斷點圖3-9（P47）步驟：1193.1.3.6自愿性中斷的處理訪管指令（SuperVisorCall)形式：準備參數(shù)SVCn取返回值系統(tǒng)調(diào)用（systemcall)形式：返回值=系統(tǒng)調(diào)用名稱（實參1,…,實參n)參數(shù)和返回值和存放位置是由OS規(guī)定的。3.1.3.6自愿性中斷的處理訪管指令（SuperViso1203.1.3.6自愿性中斷的處理系統(tǒng)調(diào)用驅(qū)動表：(tabledriven)服務(wù)程序入口addr0…………addrm-1訪管號：0……...m-1Eg.UNIX3.1.3.6自愿性中斷的處理系統(tǒng)調(diào)用驅(qū)動表：(table1213.2處理機調(diào)度3.2.1處理機調(diào)度算法按什么原則分配3.2.2處理機調(diào)度時機何時重新分配3.2.3處理機調(diào)度過程如何完成分配scheduling3.2處理機調(diào)度3.2.1處理機調(diào)度算法scheduli1223.2.1處理機調(diào)度算法考慮因素（schedulingcriteria）CPU利用率;(max)吞吐量;(max)周轉(zhuǎn)時間;(min)響應(yīng)時間;(min)系統(tǒng)開銷;(min)3.2.1處理機調(diào)度算法考慮因素（schedulingc123調(diào)度參數(shù)周轉(zhuǎn)時間：完成時間-進入時間平均周轉(zhuǎn)時間：周轉(zhuǎn)時間的平均值帶權(quán)周轉(zhuǎn)時間：周轉(zhuǎn)時間/運行時間平均帶權(quán)周轉(zhuǎn)時間：帶權(quán)周轉(zhuǎn)時間的平均值調(diào)度參數(shù)周轉(zhuǎn)時間：完成時間-進入時間平均周轉(zhuǎn)時間：周轉(zhuǎn)時間的124CPUburstvs.I/Oburst陣發(fā)期:CPUburstcycle:進程(線程)使用CPU計算；I/Oburstcycle:進程(線程)使用設(shè)備I/O。進程運行行為：CPUburst,I/Oburst,CPUburst,I/Oburst,……CPU調(diào)度：考慮處于CPUburst進程集合CPUburst時間根據(jù)以前行為推定。CPUburstvs.I/Oburst陣發(fā)期:125CPUburstvs.I/Oburst下一個CPUburst的長度估算令τn是估計的第n個CPU陣發(fā)期的長度，tn的值是進程最近一次CPU陣發(fā)期長度，則有如下估算公式：τn+1=αtn+(1-α)τn參數(shù)α(0≤α≤1)控制tn和τn在公式中起的作用：當(dāng)α=0時，τn+1=τn；當(dāng)α=1時，τn+1=tn。通常α取。CPUburstvs.I/Oburst下一個CPU126剝奪式調(diào)度與非剝奪式調(diào)度剝奪式(preemptive)就緒進程可以從運行進程手中搶占CPU。進程運行,直到結(jié)束、等待或被搶先非剝奪式(non-preemptive)就緒進程不可從運行進程手中搶占CPU。進程運行,直到結(jié)束或等待剝奪式調(diào)度與非剝奪式調(diào)度剝奪式(preemptive)1273.2.1.1先到先服務(wù)算法FCFS（FirstComeFirstServe)按進程申請CPU（就緒）的次序。Process

Arrivaltime

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

Arrivaltime

BursttimeP1012P205P307P403GanttChart0381527P1P2P3P43.2.1.2短作業(yè)優(yōu)先SJF（ShortestJob1313.2.1.2短作業(yè)優(yōu)先0381527P1P2P3P4進程到達時間運行時間開始時間完成時間周轉(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)先0381323.2.1.2短作業(yè)優(yōu)先特點：假定所有任務(wù)同時到達，平均等待時間最短。長作業(yè)可能被餓死。3.2.1.2短作業(yè)優(yōu)先特點：133最高響應(yīng)比優(yōu)先(HRN)HighestResponseRatioNextRR=(BT+WT)/BT=1+WT/BT其中:BT=bursttimeWT=waittime優(yōu)點:同時到達任務(wù),短者優(yōu)先長作業(yè)隨等待時間增加響應(yīng)比增加最高響應(yīng)比優(yōu)先(HRN)HighestResponseR1343.2.1.4最高優(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.4最高優(yōu)先數(shù)算法(HPF)靜態(tài)優(yōu)先數(shù)(stat1353.2.1.4最高優(yōu)先數(shù)算法(Cont.)非剝奪式靜態(tài)優(yōu)先數(shù)獲得處理機的進程運行，直至終止等待剝奪式動(靜)態(tài)優(yōu)先數(shù)獲得處理機的進程運行，直至終止等待出現(xiàn)高優(yōu)先級的進程3.2.1.4最高優(yōu)先數(shù)算法(Cont.)非剝奪式靜態(tài)優(yōu)先1363.2.1.4最高優(yōu)先數(shù)算法(Cont.)可搶占CPUProcess

Arrivaltime

Priority

BursttimeP1008P2215P3437P4023P5572GanttChart

0

3

4

5

7

131725P1P4P2P2P3P3P53.2.1.4最高優(yōu)先數(shù)算法(Cont.)可搶占CPU01373.2.1.4最高優(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

131725P1P4P2P2P3P3P53.2.1.4最高優(yōu)先數(shù)算法(Cont.)進程到達時間運行1383.2.1.4最高優(yōu)先數(shù)算法(Cont.)例子UNIX：preemptive+dynamicpriority（可搶占CPU動態(tài)優(yōu)先數(shù)）。計算公式：p_pri=min{127,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ī)定用戶進程0~20之間（低），系統(tǒng)進程-20~+20之間（高）。調(diào)度時取p_pri最小的。3.2.1.4最高優(yōu)先數(shù)算法(Cont.)例子UNIX：p1393.2.1.5循環(huán)輪轉(zhuǎn)算法(RR)RoundRobin(RR)基本輪轉(zhuǎn)時間片(quantum,timeslice)長度固定，不變；所有進程等速向前推進。改進輪轉(zhuǎn)時間片長度不定，可變。適用于分時系統(tǒng)3.2.1.5循環(huán)輪轉(zhuǎn)算法(RR)RoundRobin(1403.2.1.5循環(huán)輪轉(zhuǎn)算法(Cont.)時間片長度：幾十毫秒幾百毫秒(eg.50ms)過長：響應(yīng)速度慢；過短：系統(tǒng)開銷(overhead)大。適應(yīng)系統(tǒng)：分時3.2.1.5循環(huán)輪轉(zhuǎn)算法(Cont.)時間片長度：1413.2.1.6多級隊列算法(MLQ)多級隊列多個就緒隊列，進程所屬的隊列固定。例如：通用系統(tǒng)中：隊列1：實時進程就緒隊列（HPF）隊列2：分時進程就緒隊列（RR）隊列3：批處理進程就緒隊列（HPF）3.2.1.6多級隊列算法(MLQ)多級隊列1423.2.1.7最短剩余時間優(yōu)先(SRTN)ShortestRemainingTimeNext可剝奪SJFProcess

Arrivaltime

BursttimeP1012P215P337P453Gantt圖01691627P1P2P3P1P43.2.1.7最短剩余時間優(yōu)先(SRTN)Shortest1433.2.1.7最短剩余時間優(yōu)先(SRTN)進程到達時間運行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間P1012027272.25P2151651P337916131.86P4536941.33平均周轉(zhuǎn)時=(27+5+13+4)/4=12.25平均帶權(quán)周轉(zhuǎn)時間=(2.25+1+1.86+1.33)=1.61

01691627P1P2P3P1P43.2.1.7最短剩余時間優(yōu)先(SRTN)進程到達時間運行1443.2.1.8反饋排隊算法(FB)Feed-Back:多個就緒隊列，進程所屬隊列可變。Q1（RR,HPF）Q2（RR,HPF）Qn（RR,HPF）運行s1時間片運行s2時間片….創(chuàng)建喚醒優(yōu)先級時間片運行sn時間片3.2.1.8反饋排隊算法(FB)Feed-Back:Q1453.2.1.8反饋排隊算法(Cont.)調(diào)度效果：資源利用率高P1等待P2占有的資源R,P2釋放R,分給P1,P1被喚醒,進入最高級隊列,可盡早投入運行,使用資源R；響應(yīng)速度快交互式進程經(jīng)常進入等待狀態(tài)(等待用戶輸入),一旦被喚醒(輸入完成),進入最高級隊列,可盡快被調(diào)度選中,投入運行,反應(yīng)及時；系統(tǒng)開銷小計算量大的進程用完前面n-1級時間片,沒有處理完,落入底層隊列,調(diào)度頻率下降,但每次獲得較長的時間片。FeedBack3.2.1.8反饋排隊算法(Cont.)調(diào)度效果：Fee1463.2.2處理機調(diào)度時機運行進程結(jié)束；運行進程等待；處理機被剝奪。目態(tài)（Pi運行）目態(tài)（Pj運行）管態(tài)管態(tài)…...中斷中斷中斷返回返回返回Pi=Pj:未發(fā)生進程切換；Pi<>Pj:發(fā)生了進程切換。3.2.2處理機調(diào)度時機運行進程結(jié)束；目態(tài)（Pi運行）管態(tài)1473.2.2處理機調(diào)度時機(Cont.)必然引起進程切換的中斷進程自愿結(jié)束,exit()進程被強行終止；非法指令，越界，kill進程等待可能引起進程切換的中斷時鐘系統(tǒng)調(diào)用3.2.2處理機調(diào)度時機(Cont.)必然引起進程切換的中1483.2.3處理機調(diào)度過程dispatcher保存下降進程的現(xiàn)場寄存器(PSW,PC,SP,通用寄存器,地址寄存器)PCB選擇上升進程按處理機調(diào)度算法恢復(fù)上升進程的現(xiàn)場PCB寄存器先恢復(fù)通用寄存器和地址寄存器,最后恢復(fù)PSW,PCPSW和PC必須用一條指令恢復(fù)3.2.3處理機調(diào)度過程dispatcher1493.3調(diào)度級別與多級調(diào)度3.3.1交換與中級調(diào)度Swappingandmid-levelscheduling3.3.2作業(yè)與高級調(diào)度Jobandhigh-levelscheduling處理機調(diào)度為低級調(diào)度CPUsch