中斷與處理器調(diào)度.ppt

《中斷與處理器調(diào)度.ppt》由會員分享，可在線閱讀，更多相關(guān)《中斷與處理器調(diào)度.ppt（94頁珍藏版）》請在裝配圖網(wǎng)上搜索。

第三章 中斷與處理機調(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 driven,3.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)場； 引出中斷處理程序。,中斷響應(yīng)和處理的過程,,,正運行程序 1 6,,,處理程序 4,,,PSW’，PC’,PC’:,PSW, PC,,系統(tǒng)桟,psw, pc,…….,,2,,5,,3,HAL,OS,,中斷,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 中斷類型與中斷向量,,,中斷裝置,中斷處 理程序,,運行程序 訪管指令,運行程序,中斷裝置,中斷處 理程序,,,,,,,clock,IO,console,Powerfailure,malfunction,強迫中斷：,自愿中斷：,SVC n trap n,,3.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 程序錯誤 … … PSWn, PCn 訪管中斷向量,0000 0008 0016 0024 0030 … 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)棧,,中斷響應(yī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),PSW1: PC1,… …,管態(tài),PSW2: PC2,… …,管態(tài),PSWn: PCn,,,,…,,,,中斷嵌套:,…,…,3.1.2.3 中斷嵌套與系統(tǒng)棧(Cont.),…… PSWn-1 PCn-1 …… PSW2 PC2 PSW1 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 中斷處理程序,強迫性中斷,自愿性中斷,保存現(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)dispatcher,,,,,,,,,T,F,F,T,3.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 critical applications,3.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處理）,應(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ù)元入口0,中斷續(xù)元入口1,……,中斷續(xù)元入口n,中斷事件0:,中斷事件1:,中斷事件n:,….,運行時：執(zhí)行調(diào)試語句，填寫中斷續(xù)元表。 中斷時：根據(jù)中斷原因查中斷續(xù)元表， 為0，用戶未規(guī)定中斷續(xù)元，由OS標準處理； 非0，用戶已規(guī)定中斷續(xù)元，由用戶處理。,,初始時均為0,步驟： （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)形式： 準備參數(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),Eg. UNIX,3.2 處理機調(diào)度,3.2.1 處理機調(diào)度算法 按什么原則分配 3.2.2 處理機調(diào)度時機 何時重新分配 3.2.3 處理機調(diào)度過程 如何完成分配,scheduling,3.2.1 處理機調(diào)度算法,考慮因素（scheduling criteria） CPU利用率 ; (max) 吞吐量 ; (max) 周轉(zhuǎn)時間 ; (min) 響應(yīng)時間 ; (min) 系統(tǒng)開銷 ; (min),調(diào)度參數(shù),,,,,,,,周轉(zhuǎn)時間：完成時間-進入時間,平均周轉(zhuǎn)時間：周轉(zhuǎn)時間的平均值,帶權(quán)周轉(zhuǎn)時間：周轉(zhuǎn)時間/運行時間,平均帶權(quán)周轉(zhuǎn)時間：帶權(quán)周轉(zhuǎn)時間的平均值,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ù)以前行為推定。,CPU burst vs. I/O burst,下一個CPU burst的長度估算 令τ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。 進程運行,直到結(jié)束、等待或被搶先 非剝奪式(non-preemptive) 就緒進程不可從運行進程手中搶占CPU。 進程運行,直到結(jié)束或等待,3.2.1.1 先到先服務(wù)算法,FCFS（First Come First Serve) 按進程申請CPU（就緒）的次序。 Process Arrival time Burst time P1 0 27 P2 1 3 P3 2 5 CPU調(diào)度狀況可用Gantt 圖表示．,3.2.1.1 先到先服務(wù)算法(Cont.),,3.2.1.1 先到先服務(wù)算法(Cont.),優(yōu)點： “公平”； 缺點: 短作業(yè)等待時間長。,3.2.1.2 短作業(yè)優(yōu)先,SJF（Shortest Job First) 按CPU burst長度 Process Arrival time Burst time P1 0 12 P2 0 5 P3 0 7 P4 0 3 Gantt Chart,,,3.2.1.2 短作業(yè)優(yōu)先,3.2.1.2 短作業(yè)優(yōu)先,特點： 假定所有任務(wù)同時到達，平均等待時間最短。 長作業(yè)可能被餓死。,3.2.1.3最高響應(yīng)比優(yōu)先(HRN),Highest Response Ratio Next RR=(BT+WT)/BT=1+WT/BT 其中: BT=burst time WT=wait time 優(yōu)點: 同時到達任務(wù), 短者優(yōu)先 長作業(yè)隨等待時間增加響應(yīng)比增加,3.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)速度快，開銷大。,3.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.),可搶占CPU Process Arrival time Priority Burst time P1 0 0 8 P2 2 1 5 P3 4 3 7 P4 0 2 3 P5 5 7 2 Gantt Chart,3.2.1.4 最高優(yōu)先數(shù)算法(Cont.),3.2.1.4 最高優(yōu)先數(shù)算法(Cont.),例子UNIX：preemptive+dynamic priority（可搶占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.5 循環(huán)輪轉(zhuǎn)算法(RR),Round Robin(RR) 基本輪轉(zhuǎn) 時間片(quantum,time slice)長度固定，不變； 所有進程等速向前推進。 改進輪轉(zhuǎn) 時間片長度不定，可變。,適用于分時系統(tǒng),3.2.1.5 循環(huán)輪轉(zhuǎn)算法 (Cont.),時間片長度： 幾十毫秒?幾百毫秒(eg. 50ms) 過長：響應(yīng)速度慢； 過短：系統(tǒng)開銷(overhead)大。 適應(yīng)系統(tǒng)： 分時,,3.2.1.6 多級隊列算法(MLQ),多級隊列 多個就緒隊列，進程所屬的隊列固定。 例如：通用系統(tǒng)中： 隊列1：實時進程就緒隊列（HPF） 隊列2：分時進程就緒隊列 （RR） 隊列3：批處理進程就緒隊列 （HPF）,3.2.1.7 最短剩余時間優(yōu)先(SRTN),Shortest Remaining Time Next 可剝奪SJF Process Arrival time Burst time P1 0 12 P2 1 5 P3 3 7 P4 5 3 Gantt圖,3.2.1.7 最短剩余時間優(yōu)先(SRTN),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)度選中,投入運行,反應(yīng)及時； 系統(tǒng)開銷小 計算量大的進程用完前面n-1級時間片,沒有處理完,落入底層隊列,調(diào)度頻率下降,但每次獲得較長的時間片。,Feed Back,3.2.2 處理機調(diào)度時機,運行進程結(jié)束； 運行進程等待； 處理機被剝奪。,Pi=Pj: 未發(fā)生進程切換； PiPj: 發(fā)生了進程切換。,3.2.2 處理機調(diào)度時機(Cont.),必然引起進程切換的中斷 進程自愿結(jié)束, exit() 進程被強行終止； 非法指令，越界，kill 進程等待 可能引起進程切換的中斷 時鐘 系統(tǒng)調(diào)用,3.2.3 處理機調(diào)度過程,dispatcher 保存下降進程的現(xiàn)場 寄存器(PSW,PC,SP,通用寄存器,地址寄存器)?PCB 選擇上升進程 按處理機調(diào)度算法 恢復(fù)上升進程的現(xiàn)場 PCB ?寄存器 先恢復(fù)通用寄存器和地址寄存器,最后恢復(fù)PSW,PC PSW和PC必須用一條指令恢復(fù),3.3 調(diào)度級別與多級調(diào)度,3.3.1 交換與中級調(diào)度 Swapping and mid-level scheduling 3.3.2 作業(yè)與高級調(diào)度 Job and high-level scheduling,處理機調(diào)度為低級調(diào)度 CPU scheduling = low level scheduling,3.3.1 交換與中級調(diào)度,術(shù)語 交換(swapping) 中級調(diào)度(mid-level scheduling) 并發(fā)度(degree of multi-programming) 目標：控制并發(fā)度 并發(fā)度過高 系統(tǒng)開銷大 響應(yīng)速度慢 內(nèi)存等資源緊張 進程(線程)頻繁進入等待狀態(tài) More deadlocks,3.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é)果在輸出井 退出: 由輸出井向打印機傳送,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)度2,SPOOLing輸出,,,,,作業(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),3.4 實時調(diào)度(real-time scheduling),實時任務(wù)： 具有明確時間約束的計算任務(wù)。 Eg. 某時刻前必須開始處理 某時刻前必須處理完畢 實時調(diào)度： 合理安排就緒實時任務(wù)的執(zhí)行次序，滿足每個實時任務(wù)時間約束條件的調(diào)度。,實時任務(wù)分類,硬實時 vs. 軟實時 硬實時(hard real-time): 必須滿足任務(wù)截止期要求 . 軟實時(soft real-time): 期望滿足截止期要求 . 周期性 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=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.851 滿足可調(diào)度的必要條件,周期性實時事務(wù),10/20 + 25/50 = 1, 可調(diào)度(不考慮開銷),,例子,,Process Arrival time Execution time completion deadline,A(1) A(2) A(3) A(4) A(5) …. B(1) B(2),0 20 40 60 80 …. 0 50,10 10 10 10 10 …… 25 25,20 40 60 80 100 …. 50 100,3.4.1 最早截止期調(diào)度,EDF（Earliest Deadline First) 優(yōu)先選擇截止期最早的實時任務(wù) 可搶先 可以證明：對EDF來說，可調(diào)度充分條件是： 在不可調(diào)度的條件下，可使錯過截止期任務(wù)最小化,例子: Earliest Deadline First,,0 10 20 30 40 50 60 70 80 90 100 Time,,A2,B1,A3,B2,A5,B2,A4,3.4.2 速率單調(diào)調(diào)度,RMS（Rate Monotonic Scheduling） 提出于1973年 面向周期性實時事務(wù)，非剝奪式 優(yōu)先調(diào)度發(fā)生周期最短（頻度最高）的實時任務(wù) 可調(diào)度條件：,,,RMS的上限值,,RMS vs. EDF RMS可調(diào)度條件強于EDF RMS調(diào)度較EDF實現(xiàn)簡單,RMS例子：,可調(diào)度，具體調(diào)度結(jié)果：,0 20 60 160 180 220 240 300 320 360 460,3.5 多處理機調(diào)度,問題： M processes (threads) N processors SMP：symmetric multi-processors all processors are identical (homogeneous) 目標：load-sharing separate ready queue for each processor, not really balanced; common ready queue Q for all processors each processor accesses Q on its own, master/slave assignment.,3.5.1 自調(diào)度(self scheduling),均衡調(diào)度(balanced scheduling) 一個就緒隊列(多處理機訪問互斥) 優(yōu)點 不需要專門的處理機從事任務(wù)分派工作 任務(wù)分配均衡 缺點 當CPU較多時,就緒隊列成為瓶頸 線程兩次調(diào)度可能處于不同處理機 不能保證同組線程同時調(diào)度,自調(diào)度(self scheduling),就緒隊列,,,,進程(線程),進程(線程),進程(線程),CPU,CPU,CPU,,,,自調(diào)度(self scheduling),例子: Mach, 改進的自調(diào)度 全局隊列:系統(tǒng)一個 局部隊列:每個CPU一個 調(diào)度時 首先考慮局部隊列 然后考慮全局隊列,3.5.2 組調(diào)度(gang scheduling),將一組相關(guān)(合作)的線程同時分派到多個處理機上運行 避免合作線程之間的相互等待 降低開銷,提高運行效率 例子: Cm* Task force (一組相關(guān)的計算),3.6 系統(tǒng)舉例,Linux進程調(diào)度 Windows2000/XP線程調(diào)度 UNIX進程調(diào)度（見第12章）,三種特征進程 Real-time FIFO Real-time Round Robin Timesharing Goodness-based scheduling priority 0-40, (缺省值20 ),可通過nice系統(tǒng)調(diào)用調(diào)整 ，nice(value)中value的取值范圍為(-20,20)之間 ,取priority=20-value. counter 進程尚可運行的剩余時間,3.6.1 Linux 進程調(diào)度,Linux 進程調(diào)度,counter 對于運行進程來說，每個時鐘間隔(10ms，稱為一個jiffy)，將counter減1 當所有就緒進程的counter配額下降到0時，重新計算所有進程(包括等待進程)的counter值 counter= (counter/2) + priority goodness if(Real-time)goodness=1000+priority if(Timesharing && counter=0)goodness=0 if(Timesharing && counter0)goodness=counter+priority,Linux 進程調(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是支持對稱多處理硬件的第一個Linux核心 ; 進程或線程可以同時運行在多個處理機上 . 為保持核心非剝奪同步要求，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 window background: non-interactive Preemptive + dynamic priority + RR + Feed back; Symmetric Multi-Processor(SMP) support;,優(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. 當前優(yōu)先級 線程基本優(yōu)先級繼承進程基本優(yōu)先級, 可上下浮動2 如: 進程基本優(yōu)先級4, 其線程基本優(yōu)先級2—6, 當前優(yōu)先級在2—15范圍內(nèi)變動. 可動態(tài)提升 運行完一個quantum之后自動下降, 不低于基本優(yōu)先級 1個系統(tǒng)線程優(yōu)先級（0）,優(yōu)先級提升,優(yōu)先級提升 IO操作完成 事件等待結(jié)束 前臺進程中的線程完成一個等待操作 由于窗口活動而喚醒GUI線程 就緒超過一定時限，未獲得處理機 優(yōu)先級提升不會超過15,搶占CPU,搶先情形 被喚醒線程優(yōu)先級高于運行線程優(yōu)先級； 某線程的優(yōu)先級動態(tài)變化 被搶先線程 回到相應(yīng)就緒隊列 時間配額 實時線程：重新分配完整時間配額 其它線程：保持剩余配額,時間配額(quantum),配額長度：6--36 時鐘中斷（15ms發(fā)生一次）減3，2--12次時鐘中斷（30ms--180ms）配額用完 配額用完后進入就緒隊列，優(yōu)先級下降,SMP上的線程調(diào)度,線程與CPU的親合關(guān)系 每個進程有一個處理器親合掩碼，缺省為所有處理器的集合 線程繼承其進程的親合掩碼 親合掩碼可以修改 SetProcessAffinityMask, SetThreadAffinityMask;,SMP上的線程調(diào)度,線程的理想處理器（Ideal processor） 首選處理器： 第二處理器：（在內(nèi)核線程控制塊中） 理想處理器確定 線程創(chuàng)建時隨機確定， 分散各個線程與處理機對應(yīng)關(guān)系。 線程可修改SetThreadIdealProcessor,就緒線程對處理器的選擇,有空閑處理器 首選處理器 第二處理器 當前執(zhí)行處理器（正執(zhí)行調(diào)度代碼） 由高到低順序找空閑的處理器 無空閑處理器，考慮搶先 首選處理器 第二處理器 可運行編號最大處理器 不能搶先進入相應(yīng)的就緒隊列,處理器對就緒線程的選擇,空閑處理器調(diào)度 線程上次在此CPU上運行（二級緩沖利用） 線程的理想處理器是該CPU 處于就緒狀態(tài)時間超過2個quantum 優(yōu)先級別大于等于24,作業(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圖,否則說明原因。,