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

第三章中斷與處理機調(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ū)動的！Interruptdriven3.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)并響應中斷的硬件機構識別中斷源，當有多個中斷源時，按緊迫程度排隊；保存現(xiàn)場；引出中斷處理程序。中斷響應和處理的過程正運行程序

①

⑥處理程序

④PSW’，PC’PC’:PSW,PC系統(tǒng)桟psw,pc……...②⑤③HALOS中斷3.1.2.1中斷源與中斷字中斷源引起中斷的事件。中斷寄存器保存與中斷事件相關信息的寄存器。中斷字中斷寄存器的內(nèi)容。例：IO中斷：設備狀態(tài)寄存器。3.1.2.2中斷類型與中斷向量強迫性中斷運行程序不期望的時鐘中斷IO中斷控制臺中斷硬件故障中斷powerfailure內(nèi)存校驗錯程序性中斷越界，越權缺頁溢出，除0非法指令自愿性中斷運行程序期望的系統(tǒng)調(diào)用訪管指令系統(tǒng)調(diào)用fd=open(fname,mode)訪管指令準備參數(shù)svcn取返回值3.1.2.2中斷類型與中斷向量中斷裝置中斷處理程序運行程序訪管指令運行程序中斷裝置中斷處理程序clockIOconsolePowerfailuremalfunction強迫中斷：自愿中斷：SVCntrapn3.1.2.2中斷類型與中斷向量中斷向量：中斷處理程序的運行環(huán)境與入口地址（PSW，PC）每類中斷事件有一個中斷向量,中斷向量的存放位置是由硬件規(guī)定的,中斷向量的內(nèi)容是OS在系統(tǒng)初始化時設置好的。中斷向量mode應為系統(tǒng)態(tài)3.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.3中斷嵌套與系統(tǒng)棧一般原則：高優(yōu)先級別中斷可以嵌入低優(yōu)先級中斷實現(xiàn)方法：中斷響應后立即屏蔽不高于當前中斷優(yōu)先級的中斷源。3.1.2.3中斷嵌套與系統(tǒng)棧中斷響應后一般需要進一步保存現(xiàn)場

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

開中斷（或開放高優(yōu)先級中斷）…...中斷處理…...關中斷（屏蔽所有中斷）恢復現(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ī)定的中斷響應次序，依據(jù):緊迫程度；處理時間。中斷屏蔽：高優(yōu)先級中斷事件處理不受低優(yōu)先級中斷打擾；程序調(diào)整中斷響應次序。3.1.3中斷處理程序強迫性中斷自愿性中斷保存現(xiàn)場信息取中斷字分析中斷原因保存現(xiàn)場信息取調(diào)用號分析何種系統(tǒng)調(diào)用

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

中斷處理由系統(tǒng)棧恢復現(xiàn)場返回上層中斷或目態(tài)程序需要切換進程轉(zhuǎn)dispatcher保存下降進程現(xiàn)場到PCB選擇上升進程由PCB恢復上升進程現(xiàn)場TF開放高優(yōu)先級中斷關中斷等待事件調(diào)度選中剝奪中斷運行user運行kernel等待就緒返回（置PSW）事件發(fā)生中斷嵌套返回無創(chuàng)建結束終止考慮系統(tǒng)狀態(tài)的進程狀態(tài)轉(zhuǎn)換圖3.1.3.1IO中斷處理正常結束繼續(xù)傳輸；喚醒相關進程。傳輸錯誤復執(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)存，寄存器外存停止設備停止處理機恢復：啟動處理機啟動設備外存內(nèi)存，寄存器UseUPSforcriticalapplications3.1.3.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處理）應用程序自己處理中斷調(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ā)生在不同位置可采用不同處理方法應用程序自行處理中斷(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圖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）返回中斷斷點硬件操作系統(tǒng)中斷處理程序PC1系統(tǒng)?！璓SW,PC寄存器用戶棧…………PSW’,LA……LA:用戶程序…...iret中斷續(xù)元表中斷續(xù)元①溢出中斷②PSW,PCPSW1,PC1③用戶處理中斷的過程⑦⑨⑥PSW,PC⑤④⑧3.1.3.6自愿性中斷的處理訪管指令（SuperVisorCall)形式：準備參數(shù)SVCn取返回值系統(tǒng)調(diào)用（systemcall)形式：返回值=系統(tǒng)調(diào)用名稱（實參1,…,實參n)參數(shù)和返回值和存放位置是由OS規(guī)定的。3.1.3.6自愿性中斷的處理系統(tǒng)調(diào)用驅(qū)動表：(tabledriven)服務程序入口addr0…………addrm-1訪管號：0……...m-1Eg.UNIX3.2處理機調(diào)度3.2.1處理機調(diào)度算法按什么原則分配3.2.2處理機調(diào)度時機何時重新分配3.2.3處理機調(diào)度過程如何完成分配scheduling3.2.1處理機調(diào)度算法考慮因素（schedulingcriteria）CPU利用率;(max)吞吐量;(max)周轉(zhuǎn)時間;(min)響應時間;(min)系統(tǒng)開銷;(min)調(diào)度參數(shù)周轉(zhuǎn)時間：完成時間-進入時間平均周轉(zhuǎn)時間：周轉(zhuǎn)時間的平均值帶權周轉(zhuǎn)時間：周轉(zhuǎn)時間/運行時間平均帶權周轉(zhuǎn)時間：帶權周轉(zhuǎn)時間的平均值CPUburstvs.I/Oburst陣發(fā)期:CPUburstcycle:進程(線程)使用CPU計算；I/Oburstcycle:進程(線程)使用設備I/O。進程運行行為：CPUburst,I/Oburst,CPUburst,I/Oburst,……CPU調(diào)度：考慮處于CPUburst進程集合CPUburst時間根據(jù)以前行為推定。CPUburstvs.I/Oburst下一個CPUburst的長度估算令τn是估計的第n個CPU陣發(fā)期的長度，tn的值是進程最近一次CPU陣發(fā)期長度，則有如下估算公式：τn+1=αtn+(1-α)τn參數(shù)α(0≤α≤1)控制tn和τn在公式中起的作用：當α=0時，τn+1=τn；當α=1時，τn+1=tn。通常α取0.5。剝奪式調(diào)度與非剝奪式調(diào)度剝奪式(preemptive)就緒進程可以從運行進程手中搶占CPU。進程運行,直到結束、等待或被搶先非剝奪式(non-preemptive)就緒進程不可從運行進程手中搶占CPU。進程運行,直到結束或等待3.2.1.1先到先服務算法FCFS（FirstComeFirstServe)按進程申請CPU（就緒）的次序。Process

Arrivaltime

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

Arrivaltime

BursttimeP1012P205P307P403GanttChart0381527P1P2P3P43.2.1.2短作業(yè)優(yōu)先0381527P1P2P3P4進程到達時間運行時間開始時間完成時間周轉(zhuǎn)時間帶權周轉(zhuǎn)時間P10121527272.25P2053881.6P307815152.14P4030331平均周轉(zhuǎn)時間=(27+8+15+3)/4=13.25

平均帶權周轉(zhuǎn)時間=(2.25+1.6+2.14+1)/4=1.753.2.1.2短作業(yè)優(yōu)先特點：假定所有任務同時到達，平均等待時間最短。長作業(yè)可能被餓死。3.2.1.3最短剩余時間優(yōu)先算法(SRTN)

ShortestRemainingTimeNext可剝奪SJFProcess

Arrivaltime

BursttimeP1012P219P336P453Gantt圖P1P2P3P4P3P2P1013581219303.2.1.3最短剩余時間優(yōu)先算法(Cont.)進程到達時間運行時間開始時間完成時間周轉(zhuǎn)時間帶權周轉(zhuǎn)時間P1012030302.5P219119182P33631291.5P4535831平均周轉(zhuǎn)時間=(30+18+9+3)/4=15平均帶權周轉(zhuǎn)時間=(2.5+2+1.5+1)/4=1.75

平均等待時間＝(18+9+3+0)/4＝7.5(ms)P1P2P3P4P3P2P1013581219303.2.1.4最高響應比優(yōu)先(HRN)HighestResponseRatioNextRR=(BT+WT)/BT=1+WT/BT其中:BT=bursttimeWT=waittime優(yōu)點:同時到達任務,短者優(yōu)先長作業(yè)隨等待時間增加響應比增加3.2.1.5最高優(yōu)先數(shù)算法(HPF)靜態(tài)優(yōu)先數(shù)(static)優(yōu)先數(shù)在進程創(chuàng)建時分配，生存期內(nèi)不變。響應速度慢，開銷小。適合批處理進程動態(tài)優(yōu)先數(shù)(dynamic)進程創(chuàng)建時繼承優(yōu)先數(shù)，生存期內(nèi)可以修改。響應速度快，開銷大。適用于實時系統(tǒng)3.2.1.5最高優(yōu)先數(shù)算法(Cont.)非剝奪式靜態(tài)優(yōu)先數(shù)獲得處理機的進程運行，直至終止等待剝奪式動(靜)態(tài)優(yōu)先數(shù)獲得處理機的進程運行，直至終止等待出現(xiàn)高優(yōu)先級的進程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.)進程到達時間運行時間優(yōu)先級開始時間完成時間周轉(zhuǎn)時間帶權周轉(zhuǎn)時間P10801725253.13P2251317153P347341391.29P40320331P55275721平均周轉(zhuǎn)時間=(25+15+9+3+2)/5=38.8

平均帶權周轉(zhuǎn)時間=(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ù)）。計算公式：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.6循環(huán)輪轉(zhuǎn)算法(RR)RoundRobin(RR)基本輪轉(zhuǎn)時間片(quantum,timeslice)長度固定，不變；所有進程等速向前推進。改進輪轉(zhuǎn)時間片長度不定，可變。適用于分時系統(tǒng)3.2.1.6循環(huán)輪轉(zhuǎn)算法(Cont.)時間片長度：幾十毫秒幾百毫秒(eg.50ms)過長：響應速度慢；過短：系統(tǒng)開銷(overhead)大。適應系統(tǒng)：分時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.)進程到達時間運行時間開始時間完成時間周轉(zhuǎn)時間帶權周轉(zhuǎn)時間P1017030301.76P2010425252.5P303811113.67平均周轉(zhuǎn)時間＝(30+25+11)/3=22

平均帶權周轉(zhuǎn)時間＝(1.76+2.5+3.67)/3=2.64平均等待時間＝(13+15+8)/3＝12(ms)P1P2P3P1P2P1P2P1P1048111519232529303.2.1.7多級隊列算法(MLQ)多級隊列多個就緒隊列，進程所屬的隊列固定。例如：通用系統(tǒng)中：隊列1：實時進程就緒隊列（HPF）隊列2：分時進程就緒隊列（RR）隊列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；響應速度快交互式進程經(jīng)常進入等待狀態(tài)(等待用戶輸入),一旦被喚醒(輸入完成),進入最高級隊列,可盡快被調(diào)度選中,投入運行,反應及時；系統(tǒng)開銷小計算量大的進程用完前面n-1級時間片,沒有處理完,落入底層隊列,調(diào)度頻率下降,但每次獲得較長的時間片。FeedBack3.2.2處理機調(diào)度時機運行進程結束；運行進程等待；處理機被剝奪。3.2.2處理機調(diào)度時機(Cont.)必然引起進程切換的中斷進程自愿結束,exit()進程被強行終止；非法指令，越界，kill進程等待可能引起進程切換的中斷時鐘設備I/O中斷系統(tǒng)調(diào)用3.2.3處理機調(diào)度過程dispatcher保存下降進程的現(xiàn)場寄存器(PSW,PC,SP,通用寄存器,地址寄存器)PCB選擇上升進程按處理機調(diào)度算法恢復上升進程的現(xiàn)場PCB寄存器先恢復通用寄存器和地址寄存器,最后恢復PSW,PCPSW和PC必須用一條指令恢復3.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.1交換與中級調(diào)度術語交換(swapping)中級調(diào)度(mid-levelscheduling)并發(fā)度(degreeofmulti-programming)目標：控制并發(fā)度并發(fā)度過高系統(tǒng)開銷大響應速度慢內(nèi)存等資源緊張進程(線程)頻繁進入等待狀態(tài)Moredeadlocks3.3.1交換與中級調(diào)度剝奪就緒等待運行選中等待事件事件發(fā)生就緒掛起等待掛起無終止創(chuàng)建創(chuàng)建結束換出換出換入換入事件發(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):提交:輸入機向輸入井傳送后備:在輸入井,尚未進入內(nèi)存執(zhí)行:分解為進程,在內(nèi)存處理完成:處理完畢,結果在輸出井退出:由輸出井向打印機傳送3.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)度(Cont.)批處理作業(yè)調(diào)度程序(1)：在后備作業(yè)集合中選擇作業(yè)，并為其建立作業(yè)控制進程來處理該作業(yè)。作業(yè)調(diào)度程序(1)內(nèi)存已有n道作業(yè)等待T輸入井中有后備作業(yè)等待F訪問磁盤中作業(yè)控制表根據(jù)作業(yè)控制塊中控制參數(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)度程序(2)有終止的作業(yè)控制進程等待F作業(yè)調(diào)度(1)等待完成撤銷該作業(yè)控制進程，做善后處理取一終止的作業(yè)控制進程對應作業(yè)狀態(tài)改為“完成”喚醒作業(yè)調(diào)度(1)TSpooling輸出等待作業(yè)完成喚醒Spooling輸出T作業(yè)調(diào)度算法適合批作業(yè)調(diào)度的算法先到先服務算法(FCFS)優(yōu)先數(shù)調(diào)度算法(HPF)短作業(yè)優(yōu)先調(diào)度算法(SJF)最高響應比優(yōu)先調(diào)度算法(HRN)不適合批作業(yè)調(diào)度的算法時間片輪轉(zhuǎn)算法(RR)最短剩余時間優(yōu)先(SRTN)反饋排隊算法(FB)3.4實時調(diào)度(real-timescheduling)實時任務：具有明確時間約束的計算任務。Eg.某時刻前必須開始處理某時刻前必須處理完畢實時調(diào)度：合理安排就緒實時任務的執(zhí)行次序，滿足每個實時任務時間約束條件的調(diào)度。實時任務分類硬實時vs.軟實時

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

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

周期性實時事務例：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)度的必要條件周期性實時事務進程就緒時間處理時間完成截止期發(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)先選擇截止期最早的實時任務可搶先可以證明：對EDF來說，可調(diào)度充分條件是：在不可調(diào)度的條件下，可使錯過截止期任務最小化例子:EarliestDeadlineFirst0102030405060708090100TimeA2A2dlA3A3dlA4A4dlB1A1A1dlB1dlB2B2dlA5A5dlA1B1A2B1A3B2A5B2A4A1A2B1A3A4A5B23.4.2速率單調(diào)調(diào)度RMS（RateMonotonicScheduling）提出于1973年面向周期性實時事務，非剝奪式優(yōu)先調(diào)度發(fā)生周期最短（頻度最高）的實時任務可調(diào)度條件：RMS的上限值n123456┇1.00.8280.7790.7560.7430.734┇ln20.693RMSvs.EDFRMS可調(diào)度條件強于EDFRMS調(diào)度較EDF實現(xiàn)簡單RMS例子：進程ＴiCiA10020B15040C350100可調(diào)度，具體調(diào)度結果：A1B1C1A2B2A3A4B3C2020601601802202403003203604603.5多處理機調(diào)度問題：Mprocesses(threads)NprocessorsSMP：symmetricmulti-processorsallprocessorsareidentical(homogeneous)目標：load-sharingseparatereadyqueueforeachprocessor,notreallybalanced;commonreadyqueueQforallprocessorseachprocessoraccessesQonitsown,master/slaveassignment.3.5.1自調(diào)度(selfscheduling)均衡調(diào)度(balancedscheduling)一個就緒隊列(多處理機訪問互斥)優(yōu)點不需要專門的處理機從事任務分派工作任務分配均衡缺點當CPU較多時,就緒隊列成為瓶頸線程兩次調(diào)度可能處于不同處理機不能保證同組線程同時調(diào)度自調(diào)度(selfscheduling)就緒隊列進程(線程)進程(線程)進程(線程)CPUCPUCPU自調(diào)度(selfscheduling)例子:Mach,改進的自調(diào)度全局隊列:系統(tǒng)一個局部隊列:每個CPU一個調(diào)度時首先考慮局部隊列然后考慮全局隊列3.5.2組調(diào)度(gangscheduling)將一組相關(合作)的線程同時分派到多個處理機上運行避免合作線程之間的相互等待降低開銷,提高運行效率例子:Cm*Taskforce(一組相關的計算)3.6系統(tǒng)舉例Linux進程調(diào)度Windows2000/XP線程調(diào)度UNIX進程調(diào)度（見第12章）三種特征進程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)度Linux進程調(diào)度counter對于運行進程來說，每個時鐘間隔(10ms，稱為一個jiffy)，將counter減1當所有就緒進程的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)度調(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是支持