中斷與處理機調(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ū)動的！Interrupt driven3.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)并響應(yīng)中斷的硬件機構(gòu)識別中斷源，當有多個中斷源時，按緊迫程度排隊；保存現(xiàn)場；引出中斷處理程序。中斷響

2、應(yīng)和處理的過程正運行程序 1 6處理程序 4PSW，PCPC:PSW, PC系統(tǒng)桟psw, pc.253HALOS中斷3.1.2.1 中斷源與中斷字中斷源引起中斷的事件。中斷寄存器保存與中斷事件相關(guān)信息的寄存器。中斷字中斷寄存器的內(nèi)容。例：IO中斷：設(shè)備狀態(tài)寄存器。3.1.2.2 中斷類型與中斷向量強迫性中斷運行程序不期望的時鐘中斷IO中斷控制臺中斷硬件故障中斷power failure內(nèi)存校驗錯程序性中斷越界，越權(quán)缺頁溢出，除0非法指令自愿性中斷運行程序期望的系統(tǒng)調(diào)用訪管指令系統(tǒng)調(diào)用fd=open(fname,mode)訪管指令準備參數(shù)svc n取返回值3.1.2.2 中斷類型與中斷向量中斷

3、裝置 中斷處 理程序運行程序訪管指令運行程序中斷裝置 中斷處 理程序clockIOconsolePowerfailuremalfunction強迫中斷：自愿中斷：SVC ntrap n3.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 中斷類型與中斷向量PSW1, PC1 時鐘中斷向量PSW2, PC2 I/O中斷向量PSW3, PC3 console中斷向量PSW4, PC4 硬件故障PSW5, PC5

4、程序錯誤 PSWn, PCn 訪管中斷向量00000008001600240030 0090時鐘中斷處理程序PC1:I/O中斷處理程序PC2:訪管中斷處理程序PCn:系統(tǒng)空間3.1.2.3 中斷嵌套與系統(tǒng)棧一般原則：高優(yōu)先級別中斷可以嵌入低優(yōu)先級中斷實現(xiàn)方法：中斷響應(yīng)后立即屏蔽不高于當前中斷優(yōu)先級的中斷源。3.1.2.3 中斷嵌套與系統(tǒng)棧進入中斷后一般需要進一步保存現(xiàn)場 關(guān)中斷（屏蔽所有中斷） 進一步保存現(xiàn)場（通用寄存器等） 開中斷（或開放高優(yōu)先級中斷） . 中斷處理 . 關(guān)中斷（屏蔽所有中斷） 恢復(fù)現(xiàn)場 開中斷（或開放高優(yōu)先級中斷） 中斷返回3.1.2.3 中斷嵌套與系統(tǒng)棧(Cont.)目態(tài)

5、PSW1: PC1管態(tài)PSW2: PC2管態(tài)PSWn: PCn中斷嵌套:3.1.2.3 中斷嵌套與系統(tǒng)棧(Cont.)PSWn-1 PCn-1PSW2 PC2PSW1 PC1棧頂指針:系統(tǒng)棧:3.1.2.4 中斷優(yōu)先級與中斷屏蔽中斷優(yōu)先級：硬件規(guī)定的中斷響應(yīng)次序，依據(jù):緊迫程度；處理時間。中斷屏蔽：高優(yōu)先級中斷事件處理不受低優(yōu)先級中斷打擾；程序調(diào)整中斷響應(yīng)次序。3.1.3 中斷處理程序強迫性中斷： 自愿性中斷： 轉(zhuǎn)中斷處理程序 是否嵌套中斷由系統(tǒng)棧恢復(fù)現(xiàn)場 需要切換進程 返回上層中斷 由系統(tǒng)?；謴?fù)現(xiàn)場 轉(zhuǎn)CPU分派 返回目態(tài)程序 （dispatcher）保存現(xiàn)場信息取中斷字分析中斷原因保存現(xiàn)場

6、信息取訪管號分析調(diào)用功能TFFT3.1.3.1 IO中斷處理正常結(jié)束繼續(xù)傳輸；喚醒相關(guān)進程。傳輸錯誤復(fù)執(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)存，寄存器外存停止設(shè)備停止處理機恢復(fù)：啟動處理機啟動設(shè)備外存內(nèi)存，寄存器 Use UPS for criticalapplications3.1.3.4 硬件故

7、障處理(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處理）應(yīng)用程序自己處理中斷調(diào)試語句：on 例如：on goto LA;除0中斷時轉(zhuǎn)LA處理除0中斷時轉(zhuǎn)LB處理 on goto LB除0中斷續(xù)元除0中斷續(xù)元LA:LB:相同中斷發(fā)生在不同位置可采用不同處理方法應(yīng)用程序自行處理中斷(Cont.)編譯時：生成中斷續(xù)元表：中斷續(xù)元入

8、口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）返回中斷斷點3.1.3.6 自愿性中斷的處理訪管指令（SuperVisor Call)形式：

9、準備參數(shù)SVC n取返回值系統(tǒng)調(diào)用（system call)形式：返回值=系統(tǒng)調(diào)用名稱（實參1,實參n) 參數(shù)和返回值的存放位置是由OS規(guī)定的。3.1.3.6 自愿性中斷的處理系統(tǒng)調(diào)用驅(qū)動表：(table driven)服務(wù)程序入口addr0addrm-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)度算法考慮因素（scheduling criteria）CPU利用率 ; (max)吞吐量 ; (max)周轉(zhuǎn)時間 ; (min)響應(yīng)時

10、間 ; (min)系統(tǒng)開銷 ; (min)CPU burst vs. I/O burst 陣發(fā)期 :CPU burst cycle: 進程(線程)使用CPU計算；I/O burst cycle: 進程(線程)使用設(shè)備I/O。進程運行行為：CPU burst, I/O burst, CPU burst, I/O burst, CPU調(diào)度：考慮處于CPU burst進程集合 CPU burst時間根據(jù)以前行為推定。剝奪式調(diào)度與非剝奪式調(diào)度剝奪式(preemptive)就緒進程可以從運行進程手中搶占CPU。進程運行,直到結(jié)束、等待或被搶先非剝奪式(non-preemptive)就緒進程不可從運行進程

11、手中搶占CPU。進程運行,直到結(jié)束或等待3.2.1.1 先到先服務(wù)算法FCFS（First Come First Serve)按進程申請CPU（就緒）的次序。Gantt圖（到達次序：P1，P2，P3）processBurst timeP127P23P35P1P2P30 27 30 353.2.1.1 先到先服務(wù)算法(Cont.)平均等待時間：（0+27+30）/3 = 19（ms)Gantt圖（到達次序：P2，P3，P1）平均等待時間（0+3+8）/3 = 3.67P1P2P30 3 8 353.2.1.1 先到先服務(wù)算法(Cont.)優(yōu)點：“公平”；短作業(yè)等待時間長。3.2.1.2 短作業(yè)優(yōu)

12、先SJF（Shortest Job First)按CPU burst長度Gant chart:ProcessBurst timeP112P25P37P43P1P3P2P40 3 8 15 273.2.1.2 短作業(yè)優(yōu)先(SJF)平均等待時間：（0+3+8+15）/4 = 6.5 （ms)特點：假定所有任務(wù)同時到達，平均等待時間最短。長作業(yè)可能被餓死。進程到達時間運行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間P10121527272.25P2053881.6P307815152.14P4030331平均周轉(zhuǎn)時間= 13.25 ，平均帶權(quán)周轉(zhuǎn)時間1.753.2.1.3最短剩余時間優(yōu)先（SRTN)選擇

13、剩余執(zhí)行時間最短的進程或線程執(zhí)行.是剝奪式調(diào)度算法實現(xiàn): 1.CPU空閑時選擇剩余時間最短的進程或線程 2. 當一個新進程或線程到達時，比較新進程所需時間與當前運行進程的估計剩余時間，如果新進程所需運行時間短則切換運行進程進程到達時間運行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間P10121030302.5P219119182P33631291.5P4535831平均周轉(zhuǎn)時間= 15ms ，平均帶權(quán)周轉(zhuǎn)時間1.75ms3.2.1.4最高響應(yīng)比優(yōu)先(HRN)Highest Response Ratio NextRR=(BT+WT)/BT=1+WT/BT其中:BT=burst timeWT=wait

14、 time優(yōu)點:同時到達任務(wù), 短者優(yōu)先長作業(yè)隨等待時間增加響應(yīng)比增加3.2.1.5 最高優(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.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.)例子UNIX：preemptive+dynamic priority（可搶占

15、CPU動態(tài)優(yōu)先數(shù)）。計算公式：p_pri=min127, 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ī)定用戶進程020之間（低），系統(tǒng)進程-20+20之間（高）。3.2.1.6 循環(huán)輪轉(zhuǎn)算法(RR)Round Robin(RR)基本輪轉(zhuǎn)時間片(quantum,time slice)長度固定，不變；所有進程等速向前推進。改進輪轉(zhuǎn)時間片長度不定，可變。適用于分時系統(tǒng)3.2.1.6 循環(huán)輪轉(zhuǎn)算法(RR)例:有如下進程集合，假定進程按

16、下標次序進入就緒隊列，但彼此相差時間很短，可以近似認為“同時”到達，采用基本輪轉(zhuǎn)法，假定時間片長度為2ms。進程到達時間運行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間P1012026262.17P204212123P307422223.14P403615155平均周轉(zhuǎn)時間= 18.75ms ，平均帶權(quán)周轉(zhuǎn)時間3.33ms3.2.1.6 循環(huán)輪轉(zhuǎn)算法 (Cont.)時間片長度： 幾十毫秒幾百毫秒(eg. 50ms)過長：響應(yīng)速度慢；過短：系統(tǒng)開銷(overhead)大。適應(yīng)系統(tǒng)：分時3.2.1.7 分類排隊算法(MLQ)多級隊列多個就緒隊列，進程所屬的隊列固定。例如：通用系統(tǒng)中： 隊列1：實時進程

17、就緒隊列（HPF） 隊列2：分時進程就緒隊列 （RR） 隊列3：批處理進程就緒隊列 （HPF）3. 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 反饋排隊算法 (Cont.)調(diào)度效果： 資源利用率高P1等待P2占有的資源R, P2釋放R, 分給P1, P1被喚醒, 進入最高級隊列, 可盡早投入運行, 使用資源R； 響應(yīng)速度快交互式進程經(jīng)常進入等待狀態(tài)(等待用戶輸入),一旦被喚醒(輸入完成),進入最高級隊列,可盡快被調(diào)

18、度選中,投入運行,反應(yīng)及時； 系統(tǒng)開銷小計算量大的進程用完前面n-1級時間片,沒有處理完,落入底層隊列,調(diào)度頻率下降,但每次獲得較長的時間片。Feed Back3.2.2 處理機調(diào)度時機中斷處理完畢，沒有嵌套中斷，即將返回目態(tài)。目態(tài)（Pi運行）目態(tài)（Pj運行）管態(tài)管態(tài).中斷中斷中斷返回返回返回Pi=Pj: 未發(fā)生進程切換；PiPj: 發(fā)生了進程切換。3.2.2 處理機調(diào)度時機(Cont.)必然引起進程切換的中斷進程自愿結(jié)束, exit()進程被強行終止；非法指令，越界，kill進程等待可能引起進程切換的中斷時鐘系統(tǒng)調(diào)用3.2.3 處理機調(diào)度過程保存下降進程的現(xiàn)場系統(tǒng)棧PCB選擇上升進程按處理機

19、調(diào)度算法恢復(fù)上升進程的現(xiàn)場PCB 寄存器先恢復(fù)通用寄存器和地址寄存器,最后恢復(fù)PSW,PCPSW和PC必須用一條指令恢復(fù)3.3 調(diào)度級別與多級調(diào)度3.3.1 交換與中級調(diào)度Swapping and mid-level scheduling3.3.2 作業(yè)與高級調(diào)度Job and high-level scheduling處理機調(diào)度為低級調(diào)度CPU scheduling = low level scheduling3.3.1 交換與中級調(diào)度術(shù)語交換(swapping)中級調(diào)度(mid-level scheduling)并發(fā)度(degree of multi-programming)目標：控制并發(fā)

20、度并發(fā)度過高系統(tǒng)開銷大響應(yīng)速度慢內(nèi)存等資源緊張進程(線程)頻繁進入等待狀態(tài)More deadlocks3.3.1 交換與中級調(diào)度剝奪就緒等待運行 選中等待事件事件發(fā)生就緒掛起等待掛起無終止創(chuàng)建創(chuàng)建結(jié)束換出換出換入換入事件發(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)存處理完成: 處理完畢,結(jié)果在輸出井退出: 由

21、輸出井向打印機傳送3.3.2 作業(yè)與高級調(diào)度狀態(tài)轉(zhuǎn)換:提交后備: 由SPOOLing輸入進程完成Simultaneous Peripheral Operation On-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.4 實時調(diào)度(real-time scheduling)實時任務(wù)：具有明確時間約束的計算任務(wù)。Eg.某時刻前必須開始處理某時刻前必須處理完畢實時調(diào)度：合理安排就緒實時任務(wù)的執(zhí)行次序，滿足每個實時任務(wù)時

22、間約束條件的調(diào)度。實時任務(wù)分類硬實時 vs. 軟實時 硬實時: 必須滿足任務(wù)截止期要求 . 軟實時: 期望滿足截止期要求 . 周期性 vs. 隨機性 周期性: 每隔固定時間發(fā)生一次 隨機性: 由隨機事件觸發(fā)，其發(fā)生時刻不確定 術(shù)語解釋Ready time: 就緒時間Starting deadline: 開始截止期Processing time: 處理時間Completion deadline: 完成截止期Occurring frequency: 發(fā)生頻率周期性實時事務(wù)周期性實時事務(wù):令Ci為任務(wù)Pi處理時間，Ti為任務(wù)Pi的發(fā)生周期，則任務(wù)P1,Pm可調(diào)度的必要條件為： 周期性實時事務(wù)例：T1

23、=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=quantum+priorityLinux 進程調(diào)度調(diào)度發(fā)生時刻： 運行進程的quantum減至0； 運行進程執(zhí)行系統(tǒng)調(diào)用exit ;運行進程因等待I/O、信號燈而被封鎖 ;原來具有高goodness的進程被解除封鎖 .調(diào)度效果 :實時優(yōu)先于分時 交互和I/O進程優(yōu)先于CPU進程 Linux 對稱多處理Linux2.0是支持對稱多處理硬件的第一個Linux核心 ; 進程或線程可以同時運行在多個處理機上 .

24、為保持核心非剝奪同步要求，SMP通過一個唯一的核心自旋鎖(spin-lock)來保證任何時刻最多只有一個處理機執(zhí)行核心代碼, 支持真正意義上的SMP：將一個自旋鎖分解為若干個相互獨立的自旋鎖，分別用于保護核心代碼不相交的子集 .3.6.2 Windows 2000/XP線程調(diào)度Main Features：Thread level scheduling;Real time + foreground + background;real time: no deadline scheduling;foreground: GUI windowbackground: non-interactivePreemptive + dynamic priority + RR + Feed back;Symmetric Multi-Processor(SMP) support;優(yōu)先級別16個實時優(yōu)先級（16-31）一些內(nèi)核線程應(yīng)用程序提升