第三章中斷與處理機調度3.1中斷與中斷系統3.2處理機調度3.3調度級別與多級調度3.4實時調度3.5多處理機調度3.6系統舉例操作系統是中斷驅動的！Interruptdriven第三章中斷與處理機調度3.1中斷與中斷系統操作13.1中斷與中斷系統3.1.1中斷的概念3.1.2中斷裝置3.1.3中斷處理程序3.1中斷與中斷系統3.1.1中斷的概念23.1.1中斷的概念處理機在運行過程中，出現了某一事件，必須中止正在運行的程序，轉去處理這個事件，然后再返回原來運行的程序，這一過程稱為中斷。中斷系統：中斷裝置(硬件)中斷處理程序(軟件)3.1.1中斷的概念處理機在運行過程中，出現了某一事件，必33.1.2中斷裝置發現并響應中斷的硬件機構識別中斷源，當有多個中斷源時，按緊迫程度排隊；保存現場；引出中斷處理程序。3.1.2中斷裝置發現并響應中斷的硬件機構4中斷響應和處理的過程正運行程序16處理程序4PSW’，PC’PC’:PSW,PC系統桟psw,pc……...253HALOS中斷中斷響應和處理的過程正運行程序處理程序PSW’，PC’PC’53.1.2.1中斷源與中斷字中斷源引起中斷的事件。中斷寄存器保存與中斷事件相關信息的寄存器。中斷字中斷寄存器的內容。例：IO中斷：設備狀態寄存器。3.1.2.1中斷源與中斷字中斷源63.1.2.2中斷類型與中斷向量強迫性中斷運行程序不期望的時鐘中斷IO中斷控制臺中斷硬件故障中斷powerfailure內存校驗錯程序性中斷越界，越權缺頁溢出，除0非法指令自愿性中斷運行程序期望的系統調用訪管指令系統調用fd=open(fname,mode)訪管指令準備參數svcn取返回值3.1.2.2中斷類型與中斷向量強迫性中斷自愿性中斷73.1.2.2中斷類型與中斷向量中斷裝置中斷處理程序運行程序訪管指令運行程序中斷裝置中斷處理程序clockIOconsolePowerfailuremalfunction強迫中斷：自愿中斷：SVCntrapn3.1.2.2中斷類型與中斷向量中斷裝置中斷處運行程序83.1.2.2中斷類型與中斷向量中斷向量：中斷處理程序的運行環境與入口地址（PSW，PC）每類中斷事件有一個中斷向量,中斷向量的存放位置是由硬件規定的,中斷向量的內容是OS在系統初始化時設置好的。中斷向量mode應為系統態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:…系統空間3.1.2.2中斷類型與中斷向量PSW1,PC1103.1.2.3中斷嵌套與系統棧一般原則：高優先級別中斷可以嵌入低優先級中斷實現方法：中斷響應后立即屏蔽不高于當前中斷優先級的中斷源。3.1.2.3中斷嵌套與系統棧一般原則：113.1.2.3中斷嵌套與系統棧中斷響應后一般需要進一步保存現場

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

開中斷（或開放高優先級中斷）…...中斷處理…...關中斷（屏蔽所有中斷）恢復現場開中斷（或開放高優先級中斷）中斷返回3.1.2.3中斷嵌套與系統棧中斷響應后一般需要進一步保存123.1.2.3中斷嵌套與系統棧(Cont.)……目態PSW1:PC1……管態PSW2:PC2……管態PSWn:PCn…中斷嵌套:……3.1.2.3中斷嵌套與系統棧(Cont.)…目態PSW1133.1.2.3中斷嵌套與系統棧(Cont.)……PSWn-1PCn-1……PSW2PC2PSW1PC1棧頂指針:系統棧:3.1.2.3中斷嵌套與系統棧(Cont.)棧頂指針:系統143.1.2.4中斷優先級與中斷屏蔽中斷優先級：硬件規定的中斷響應次序，依據:緊迫程度；處理時間。中斷屏蔽：高優先級中斷事件處理不受低優先級中斷打擾；程序調整中斷響應次序。3.1.2.4中斷優先級與中斷屏蔽中斷優先級：153.1.3中斷處理程序強迫性中斷自愿性中斷保存現場信息取中斷字分析中斷原因保存現場信息取調用號分析何種系統調用

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

Arrivaltime

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

Arrivaltime

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

平均帶權周轉時間=(2.25+1.6+2.14+1)/4=1.753.2.1.2短作業優先038383.2.1.2短作業優先特點：假定所有任務同時到達，平均等待時間最短。長作業可能被餓死。3.2.1.2短作業優先特點：39最高響應比優先(HRN)HighestResponseRatioNextRR=(BT+WT)/BT=1+WT/BT其中:BT=bursttimeWT=waittime優點:同時到達任務,短者優先長作業隨等待時間增加響應比增加最高響應比優先(HRN)HighestResponseR403.2.1.4最高優先數算法(HPF)靜態優先數(static)優先數在進程創建時分配，生存期內不變。響應速度慢，開銷小。適合批處理進程動態優先數(dynamic)進程創建時繼承優先數，生存期內可以修改。響應速度快，開銷大。適用于實時系統3.2.1.4最高優先數算法(HPF)靜態優先數(stat413.2.1.4最高優先數算法(Cont.)非剝奪式靜態優先數獲得處理機的進程運行，直至終止等待剝奪式動(靜)態優先數獲得處理機的進程運行，直至終止等待出現高優先級的進程3.2.1.4最高優先數算法(Cont.)非剝奪式靜態優先423.2.1.4最高優先數算法(Cont.)可搶占CPUProcess

Arrivaltime

Priority

BursttimeP1008P2215P3437P4023P5572GanttChart

0

3

4

5

7

131725P1P4P2P2P3P3P53.2.1.4最高優先數算法(Cont.)可搶占CPU0433.2.1.4最高優先數算法(Cont.)進程到達時間運行時間優先級開始時間完成時間周轉時間帶權周轉時間P10801725253.13P2251317153P347341391.29P40320331P55275721平均周轉時間=(25+15+9+3+2)/5=38.8

平均帶權周轉時間=(3.13+3+1.29+1+1)/5=1.88

0

3

4

5

7

131725P1P4P2P2P3P3P53.2.1.4最高優先數算法(Cont.)進程到達時間運行443.2.1.4最高優先數算法(Cont.)例子UNIX：preemptive+dynamicpriority（可搶占CPU動態優先數）。計算公式：p_pri=min{127,USER+p_cpu/16+p_nice}定義USER=100；p_cpu:運行進程每20ms加1（優先級降低），其它進程每1200ms減10（優先級提高）；p_nice:可以通過系統調用nice(…)修改的量：規定用戶進程0~20之間（低），系統進程-20~+20之間（高）。調度時取p_pri最小的。3.2.1.4最高優先數算法(Cont.)例子UNIX：p453.2.1.5循環輪轉算法(RR)RoundRobin(RR)基本輪轉時間片(quantum,timeslice)長度固定，不變；所有進程等速向前推進。改進輪轉時間片長度不定，可變。適用于分時系統3.2.1.5循環輪轉算法(RR)RoundRobin(463.2.1.5循環輪轉算法(Cont.)時間片長度：幾十毫秒幾百毫秒(eg.50ms)過長：響應速度慢；過短：系統開銷(overhead)大。適應系統：分時3.2.1.5循環輪轉算法(Cont.)時間片長度：473.2.1.6多級隊列算法(MLQ)多級隊列多個就緒隊列，進程所屬的隊列固定。例如：通用系統中：隊列1：實時進程就緒隊列（HPF）隊列2：分時進程就緒隊列（RR）隊列3：批處理進程就緒隊列（HPF）3.2.1.6多級隊列算法(MLQ)多級隊列483.2.1.7最短剩余時間優先(SRTN)ShortestRemainingTimeNext可剝奪SJFProcess

Arrivaltime

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

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

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

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

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

運行進程的counter減至0；

運行進程執行系統調用exit;運行進程因等待I/O、信號燈而被封鎖;原來具有高goodness的進程被解除封鎖.調度效果:實時優先于分時

交互和I/O進程優先于CPU進程

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

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

開中斷（或開放高優先級中斷）…...中斷處理…...關中斷（屏蔽所有中斷）恢復現場開中斷（或開放高優先級中斷）中斷返回3.1.2.3中斷嵌套與系統棧中斷響應后一般需要進一步保存1063.1.2.3中斷嵌套與系統棧(Cont.)……目態PSW1:PC1……管態PSW2:PC2……管態PSWn:PCn…中斷嵌套:……3.1.2.3中斷嵌套與系統棧(Cont.)…目態PSW11073.1.2.3中斷嵌套與系統棧(Cont.)……PSWn-1PCn-1……PSW2PC2PSW1PC1棧頂指針:系統棧:3.1.2.3中斷嵌套與系統棧(Cont.)棧頂指針:系統1083.1.2.4中斷優先級與中斷屏蔽中斷優先級：硬件規定的中斷響應次序，依據:緊迫程度；處理時間。中斷屏蔽：高優先級中斷事件處理不受低優先級中斷打擾；程序調整中斷響應次序。3.1.2.4中斷優先級與中斷屏蔽中斷優先級：1093.1.3中斷處理程序強迫性中斷自愿性中斷保存現場信息取中斷字分析中斷原因保存現場信息取調用號分析何種系統調用

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

Arrivaltime

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

Arrivaltime

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

平均帶權周轉時間=(2.25+1.6+2.14+1)/4=1.753.2.1.2短作業優先0381323.2.1.2短作業優先特點：假定所有任務同時到達，平均等待時間最短。長作業可能被餓死。3.2.1.2短作業優先特點：133最高響應比優先(HRN)HighestResponseRatioNextRR=(BT+WT)/BT=1+WT/BT其中:BT=bursttimeWT=waittime優點:同時到達任務,短者優先長作業隨等待時間增加響應比增加最高響應比優先(HRN)HighestResponseR1343.2.1.4最高優先數算法(HPF)靜態優先數(static)優先數在進程創建時分配，生存期內不變。響應速度慢，開銷小。適合批處理進程動態優先數(dynamic)進程創建時繼承優先數，生存期內可以修改。響應速度快，開銷大。適用于實時系統3.2.1.4最高優先數算法(HPF)靜態優先數(stat1353.2.1.4最高優先數算法(Cont.)非剝奪式靜態優先數獲得處理機的進程運行，直至終止等待剝奪式動(靜)態優先數獲得處理機的進程運行，直至終止等待出現高優先級的進程3.2.1.4最高優先數算法(Cont.)非剝奪式靜態優先1363.2.1.4最高優先數算法(Cont.)可搶占CPUProcess

Arrivaltime

Priority

BursttimeP1008P2215P3437P4023P5572GanttChart

0

3

4

5

7

131725P1P4P2P2P3P3P53.2.1.4最高優先數算法(Cont.)可搶占CPU01373.2.1.4最高優先數算法(Cont.)進程到達時間運行時間優先級開始時間完成時間周轉時間帶權周轉時間P10801725253.13P2251317153P347341391.29P40320331P55275721平均周轉時間=(25+15+9+3+2)/5=38.8

平均帶權周轉時間=(3.13+3+1.29+1+1)/5=1.88

0

3

4

5

7

131725P1P4P2P2P3P3P53.2.1.4最高優先數算法(Cont.)進程到達時間運行1383.2.1.4最高優先數算法(Cont.)例子UNIX：preemptive+dynamicpriority（可搶占CPU動態優先數）。計算公式：p_pri=min{127,USER+p_cpu/16+p_nice}定義USER=100；p_cpu:運行進程每20ms加1（優先級降低），其它進程每1200ms減10（優先級提高）；p_nice:可以通過系統調用nice(…)修改的量：規定用戶進程0~20之間（低），系統進程-20~+20之間（高）。調度時取p_pri最小的。3.2.1.4最高優先數算法(Cont.)例子UNIX：p1393.2.1.5循環輪轉算法(RR)RoundRobin(RR)基本輪轉時間片(quantum,timeslice)長度固定，不變；所有進程等速向前推進。改進輪轉時間片長度不定，可變。適用于分時系統3.2.1.5循環輪轉算法(RR)RoundRobin(1403.2.1.5循環輪轉算法(Cont.)時間片長度：幾十毫秒幾百毫秒(eg.50ms)過長：響應速度慢；過短：系統開銷(overhead)大。適應系統：分時3.2.1.5循環輪轉算法(Cont.)時間片長度：1413.2.1.6多級隊列算法(MLQ)多級隊列多個就緒隊列，進程所屬的隊列固定。例如：通用系統中：隊列1：實時進程就緒隊列（HPF）隊列2：分時進程就緒隊列（RR）隊列3：批處理進程就緒隊列（HPF）3.2.1.6多級隊列算法(MLQ)多級隊列1423.2.1.7最短剩余時間優先(SRTN)ShortestRemainingTimeNext可剝奪SJFProcess

Arrivaltime

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

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