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

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

第三章 中斷與處理機(jī)調(diào)度,3.1 中斷與中斷系統(tǒng) 3.2 處理機(jī)調(diào)度 3.3 調(diào)度級(jí)別與多級(jí)調(diào)度 3.4 實(shí)時(shí)調(diào)度 3.5 多處理機(jī)調(diào)度 3.6 系統(tǒng)舉例,操作系統(tǒng)是中斷驅(qū)動(dòng)的！ Interrupt driven,3.1 中斷與中斷系統(tǒng),3.1.1 中斷的概念 3.1.2 中斷裝置 3.1.3 中斷處理程序,3.1.1 中斷的概念,處理機(jī)在運(yùn)行過(guò)程中，出現(xiàn)了某一事件，必須中止正在運(yùn)行的程序，轉(zhuǎn)去處理這個(gè)事件，然后再返回原來(lái)運(yùn)行的程序，這一過(guò)程稱為中斷。 中斷系統(tǒng)： 中斷裝置(硬件) 中斷處理程序(軟件),3.1.2 中斷裝置,發(fā)現(xiàn)并響應(yīng)中斷的硬件機(jī)構(gòu) 識(shí)別中斷源，當(dāng)有多個(gè)中斷源時(shí)，按緊迫程度排隊(duì)； 保存現(xiàn)場(chǎng)； 引出中斷處理程序。,中斷響應(yīng)和處理的過(guò)程,,,正運(yùn)行程序 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 中斷類型與中斷向量,強(qiáng)迫性中斷 運(yùn)行程序不期望的 時(shí)鐘中斷 IO中斷 控制臺(tái)中斷 硬件故障中斷 power failure 內(nèi)存校驗(yàn)錯(cuò) 程序性中斷 越界，越權(quán) 缺頁(yè) 溢出，除0 非法指令,自愿性中斷 運(yùn)行程序期望的 系統(tǒng)調(diào)用 訪管指令 系統(tǒng)調(diào)用 fd=open(fname,mode) 訪管指令 準(zhǔn)備參數(shù) svc n 取返回值,3.1.2.2 中斷類型與中斷向量,,,中斷裝置,中斷處 理程序,,運(yùn)行程序 訪管指令,運(yùn)行程序,中斷裝置,中斷處 理程序,,,,,,,clock,IO,console,Powerfailure,malfunction,強(qiáng)迫中斷：,自愿中斷：,SVC n trap n,,3.1.2.2 中斷類型與中斷向量,中斷向量：中斷處理程序的運(yùn)行環(huán)境與入口地址（PSW，PC） 每類中斷事件有一個(gè)中斷向量, 中斷向量的存放位置是由硬件規(guī)定的, 中斷向量的內(nèi)容是OS在系統(tǒng)初始化時(shí)設(shè)置好的。,中斷向量mode應(yīng)為系統(tǒng)態(tài),,3.1.2.2 中斷類型與中斷向量,PSW1, PC1 時(shí)鐘中斷向量 PSW2, PC2 I/O中斷向量 PSW3, PC3 console中斷向量 PSW4, PC4 硬件故障 PSW5, PC5 程序錯(cuò)誤 … … PSWn, PCn 訪管中斷向量,0000 0008 0016 0024 0030 … 0090,時(shí)鐘中斷 處理程序,PC1:,I/O中斷 處理程序,PC2:,訪管中斷 處理程序,PCn:,…,系統(tǒng)空間,3.1.2.3 中斷嵌套與系統(tǒng)棧,一般原則： 高優(yōu)先級(jí)別中斷可以嵌入低優(yōu)先級(jí)中斷 實(shí)現(xiàn)方法： 中斷響應(yīng)后立即屏蔽不高于當(dāng)前中斷優(yōu)先級(jí)的中斷源。,3.1.2.3 中斷嵌套與系統(tǒng)棧,,中斷響應(yīng)后一般需要進(jìn)一步保存現(xiàn)場(chǎng) 關(guān)中斷（屏蔽所有中斷） 進(jìn)一步保存現(xiàn)場(chǎng)（通用寄存器等） 開(kāi)中斷（或開(kāi)放高優(yōu)先級(jí)中斷） …. 中斷處理 …. 關(guān)中斷（屏蔽所有中斷） 恢復(fù)現(xiàn)場(chǎng) 開(kāi)中斷（或開(kāi)放高優(yōu)先級(jí)中斷） 中斷返回,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)先級(jí)與中斷屏蔽,中斷優(yōu)先級(jí)： 硬件規(guī)定的中斷響應(yīng)次序，依據(jù): 緊迫程度； 處理時(shí)間。 中斷屏蔽： 高優(yōu)先級(jí)中斷事件處理不受低優(yōu)先級(jí)中斷打擾； 程序調(diào)整中斷響應(yīng)次序。,3.1.3 中斷處理程序,強(qiáng)迫性中斷,自愿性中斷,保存現(xiàn)場(chǎng)信息 取中斷字 分析中斷原因,保存現(xiàn)場(chǎng)信息 取調(diào)用號(hào) 分析何種系統(tǒng)調(diào)用,中斷處理 （如等待轉(zhuǎn)dispatcher) 繼續(xù)處理,嵌套中斷,系統(tǒng)?；謴?fù)現(xiàn)場(chǎng) 返回上層中斷,需要切換進(jìn)程,系統(tǒng)?；謴?fù)現(xiàn)場(chǎng) 返回目態(tài)程序,轉(zhuǎn)dispatcher,,,,,,,,,T,F,F,T,3.1.3.1 IO中斷處理,正常結(jié)束 繼續(xù)傳輸； 喚醒相關(guān)進(jìn)程。 傳輸錯(cuò)誤 復(fù)執(zhí)（eg. 3次)； 報(bào)告系統(tǒng)操作員。,3.1.3.2 時(shí)鐘中斷處理,Housekeeping 進(jìn)程管理 重新計(jì)算進(jìn)程調(diào)度參數(shù)(eg. 動(dòng)態(tài)優(yōu)先數(shù)) 實(shí)現(xiàn)軟時(shí)鐘，啟動(dòng)定時(shí)程序 硬時(shí)鐘5ms發(fā)生一次中斷，軟時(shí)鐘50ms 考慮進(jìn)程切換,3.1.3.3 控制臺(tái)中斷處理,一個(gè)控制按鈕，一個(gè)中斷向量，一個(gè)中斷處理程序。,3.1.3.4 硬件故障處理,電源故障處理 掉電： 內(nèi)存，寄存器?外存 停止設(shè)備 停止處理機(jī) 恢復(fù)： 啟動(dòng)處理機(jī) 啟動(dòng)設(shè)備 外存?內(nèi)存，寄存器,Use UPS for critical applications,3.1.3.4 硬件故障處理(cont.),內(nèi)存故障處理 海明校驗(yàn)，奇偶校驗(yàn)錯(cuò)誤 劃出系統(tǒng) 報(bào)告操作員,3.1.3.5 程序性中斷的處理,只能由操作系統(tǒng)處理的中斷 影響系統(tǒng)或其它進(jìn)程 越界，非法指令，（處理：終止進(jìn)程、調(diào)試） 需要系統(tǒng)管理或協(xié)助 頁(yè)故障，缺段，（處理：動(dòng)態(tài)調(diào)入） 可以由用戶自己處理的中斷 不影響系統(tǒng)和其它進(jìn)程 除0，溢出，（處理：用戶處理，或OS處理）,應(yīng)用程序自己處理中斷,調(diào)試語(yǔ)句：on 例如：on goto LA;,除0中斷時(shí)轉(zhuǎn)LA處理,除0中斷時(shí)轉(zhuǎn)LB處理,on goto LB,除0中 斷續(xù)元,除0中 斷續(xù)元,LA:,LB:,相同中斷發(fā)生在不同位置 可采用不同處理方法,應(yīng)用程序自行處理中斷(Cont.),編譯時(shí)：生成中斷續(xù)元表：,中斷續(xù)元入口0,中斷續(xù)元入口1,……,中斷續(xù)元入口n,中斷事件0:,中斷事件1:,中斷事件n:,….,運(yùn)行時(shí)：執(zhí)行調(diào)試語(yǔ)句，填寫(xiě)中斷續(xù)元表。 中斷時(shí)：根據(jù)中斷原因查中斷續(xù)元表， 為0，用戶未規(guī)定中斷續(xù)元，由OS標(biāo)準(zhǔn)處理； 非0，用戶已規(guī)定中斷續(xù)元，由用戶處理。,,初始時(shí)均為0,步驟： （1）發(fā)生溢出中斷 （2）保存舊PSW和PC （3）取中斷向量 （4）轉(zhuǎn)到中斷處理程序 （5）訪問(wèn)中斷續(xù)元表（假定非0） （6）系統(tǒng)棧中現(xiàn)場(chǎng)轉(zhuǎn)移到用戶棧 （7）中斷續(xù)元入口送寄存器（OS中斷處理完成） （8）執(zhí)行中斷續(xù)元 （9）用戶棧PSW和PC送寄存器 （10）返回中斷斷點(diǎn),3.1.3.6 自愿性中斷的處理,訪管指令（SuperVisor Call)形式： 準(zhǔn)備參數(shù) SVC n 取返回值,系統(tǒng)調(diào)用（system call)形式： 返回值=系統(tǒng)調(diào)用名稱（實(shí)參1,…,實(shí)參n),參數(shù)和返回值和存放位置是由OS規(guī)定的。,3.1.3.6 自愿性中斷的處理,系統(tǒng)調(diào)用驅(qū)動(dòng)表：(table driven),Eg. UNIX,3.2 處理機(jī)調(diào)度,3.2.1 處理機(jī)調(diào)度算法 按什么原則分配 3.2.2 處理機(jī)調(diào)度時(shí)機(jī) 何時(shí)重新分配 3.2.3 處理機(jī)調(diào)度過(guò)程 如何完成分配,scheduling,3.2.1 處理機(jī)調(diào)度算法,考慮因素（scheduling criteria） CPU利用率 ; (max) 吞吐量 ; (max) 周轉(zhuǎn)時(shí)間 ; (min) 響應(yīng)時(shí)間 ; (min) 系統(tǒng)開(kāi)銷 ; (min),調(diào)度參數(shù),,,,,,,,周轉(zhuǎn)時(shí)間：完成時(shí)間-進(jìn)入時(shí)間,平均周轉(zhuǎn)時(shí)間：周轉(zhuǎn)時(shí)間的平均值,帶權(quán)周轉(zhuǎn)時(shí)間：周轉(zhuǎn)時(shí)間/運(yùn)行時(shí)間,平均帶權(quán)周轉(zhuǎn)時(shí)間：帶權(quán)周轉(zhuǎn)時(shí)間的平均值,CPU burst vs. I/O burst,陣發(fā)期 : CPU burst cycle: 進(jìn)程(線程)使用CPU計(jì)算； I/O burst cycle: 進(jìn)程(線程)使用設(shè)備I/O。 進(jìn)程運(yùn)行行為： CPU burst, I/O burst, CPU burst, I/O burst, …… CPU調(diào)度：考慮處于CPU burst進(jìn)程集合 CPU burst時(shí)間根據(jù)以前行為推定。,CPU burst vs. I/O burst,下一個(gè)CPU burst的長(zhǎng)度估算 令τn是估計(jì)的第n個(gè)CPU陣發(fā)期的長(zhǎng)度， tn的值是進(jìn)程最近一次CPU陣發(fā)期長(zhǎng)度，則有如下估算公式： τn+1=αtn + (1-α)τn 參數(shù)α(0≤α≤1)控制tn和τn在公式中起的作用：當(dāng)α=0時(shí)，τn+1=τn；當(dāng)α=1時(shí)，τn+1=tn。通常α取0.5。,剝奪式調(diào)度與非剝奪式調(diào)度,剝奪式(preemptive) 就緒進(jìn)程可以從運(yùn)行進(jìn)程手中搶占CPU。 進(jìn)程運(yùn)行,直到結(jié)束、等待或被搶先 非剝奪式(non-preemptive) 就緒進(jìn)程不可從運(yùn)行進(jìn)程手中搶占CPU。 進(jìn)程運(yùn)行,直到結(jié)束或等待,3.2.1.1 先到先服務(wù)算法,FCFS（First Come First Serve) 按進(jìn)程申請(qǐng)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)點(diǎn)： “公平”； 缺點(diǎn): 短作業(yè)等待時(shí)間長(zhǎng)。,3.2.1.2 短作業(yè)優(yōu)先,SJF（Shortest Job First) 按CPU burst長(zhǎng)度 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)先,特點(diǎn)： 假定所有任務(wù)同時(shí)到達(dá)，平均等待時(shí)間最短。 長(zhǎng)作業(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)點(diǎn): 同時(shí)到達(dá)任務(wù), 短者優(yōu)先 長(zhǎng)作業(yè)隨等待時(shí)間增加響應(yīng)比增加,3.2.1.4 最高優(yōu)先數(shù)算法(HPF),靜態(tài)優(yōu)先數(shù)(static) 優(yōu)先數(shù)在進(jìn)程創(chuàng)建時(shí)分配，生存期內(nèi)不變。 響應(yīng)速度慢，開(kāi)銷小。 適合批處理進(jìn)程 動(dòng)態(tài)優(yōu)先數(shù)(dynamic) 進(jìn)程創(chuàng)建時(shí)繼承優(yōu)先數(shù)，生存期內(nèi)可以修改。 響應(yīng)速度快，開(kāi)銷大。,3.2.1.4 最高優(yōu)先數(shù)算法(Cont.),非剝奪式靜態(tài)優(yōu)先數(shù) 獲得處理機(jī)的進(jìn)程運(yùn)行，直至 終止 等待 剝奪式動(dòng)(靜)態(tài)優(yōu)先數(shù) 獲得處理機(jī)的進(jìn)程運(yùn)行，直至 終止 等待 出現(xiàn)高優(yōu)先級(jí)的進(jìn)程,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動(dòng)態(tài)優(yōu)先數(shù)）。 計(jì)算公式：p_pri=min{127, USER+p_cpu/16+p_nice} 定義USER=100； p_cpu: 運(yùn)行進(jìn)程每20ms加1（優(yōu)先級(jí)降低），其它進(jìn)程每1200ms減10（優(yōu)先級(jí)提高）； p_nice: 可以通過(guò)系統(tǒng)調(diào)用nice(…)修改的量：規(guī)定用戶進(jìn)程0~20之間（低），系統(tǒng)進(jìn)程-20~+20之間（高）。 調(diào)度時(shí)取p_pri最小的。,3.2.1.5 循環(huán)輪轉(zhuǎn)算法(RR),Round Robin(RR) 基本輪轉(zhuǎn) 時(shí)間片(quantum,time slice)長(zhǎng)度固定，不變； 所有進(jìn)程等速向前推進(jìn)。 改進(jìn)輪轉(zhuǎn) 時(shí)間片長(zhǎng)度不定，可變。,適用于分時(shí)系統(tǒng),3.2.1.5 循環(huán)輪轉(zhuǎn)算法 (Cont.),時(shí)間片長(zhǎng)度： 幾十毫秒?幾百毫秒(eg. 50ms) 過(guò)長(zhǎng)：響應(yīng)速度慢； 過(guò)短：系統(tǒng)開(kāi)銷(overhead)大。 適應(yīng)系統(tǒng)： 分時(shí),,3.2.1.6 多級(jí)隊(duì)列算法(MLQ),多級(jí)隊(duì)列 多個(gè)就緒隊(duì)列，進(jìn)程所屬的隊(duì)列固定。 例如：通用系統(tǒng)中： 隊(duì)列1：實(shí)時(shí)進(jìn)程就緒隊(duì)列（HPF） 隊(duì)列2：分時(shí)進(jìn)程就緒隊(duì)列 （RR） 隊(duì)列3：批處理進(jìn)程就緒隊(duì)列 （HPF）,3.2.1.7 最短剩余時(shí)間優(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 最短剩余時(shí)間優(yōu)先(SRTN),3. 2.1.8 反饋排隊(duì)算法(FB),Feed-Back: 多個(gè)就緒隊(duì)列，進(jìn)程所屬隊(duì)列可變。,Q1（RR,HPF）,Q2（RR,HPF）,Qn（RR,HPF）,,運(yùn)行s1時(shí)間片,,運(yùn)行s2時(shí)間片,….,,創(chuàng)建喚醒,,優(yōu)先級(jí) 時(shí)間片,,,,,運(yùn)行sn時(shí)間片,,3.2.1.8 反饋排隊(duì)算法 (Cont.),調(diào)度效果： 資源利用率高 P1等待P2占有的資源R, P2釋放R, 分給P1, P1被喚醒, 進(jìn)入最高級(jí)隊(duì)列, 可盡早投入運(yùn)行, 使用資源R； 響應(yīng)速度快 交互式進(jìn)程經(jīng)常進(jìn)入等待狀態(tài)(等待用戶輸入),一旦被喚醒(輸入完成),進(jìn)入最高級(jí)隊(duì)列,可盡快被調(diào)度選中,投入運(yùn)行,反應(yīng)及時(shí)； 系統(tǒng)開(kāi)銷小 計(jì)算量大的進(jìn)程用完前面n-1級(jí)時(shí)間片,沒(méi)有處理完,落入底層隊(duì)列,調(diào)度頻率下降,但每次獲得較長(zhǎng)的時(shí)間片。,Feed Back,3.2.2 處理機(jī)調(diào)度時(shí)機(jī),運(yùn)行進(jìn)程結(jié)束； 運(yùn)行進(jìn)程等待； 處理機(jī)被剝奪。,Pi=Pj: 未發(fā)生進(jìn)程切換； PiPj: 發(fā)生了進(jìn)程切換。,3.2.2 處理機(jī)調(diào)度時(shí)機(jī)(Cont.),必然引起進(jìn)程切換的中斷 進(jìn)程自愿結(jié)束, exit() 進(jìn)程被強(qiáng)行終止； 非法指令，越界，kill 進(jìn)程等待 可能引起進(jìn)程切換的中斷 時(shí)鐘 系統(tǒng)調(diào)用,3.2.3 處理機(jī)調(diào)度過(guò)程,dispatcher 保存下降進(jìn)程的現(xiàn)場(chǎng) 寄存器(PSW,PC,SP,通用寄存器,地址寄存器)?PCB 選擇上升進(jìn)程 按處理機(jī)調(diào)度算法 恢復(fù)上升進(jìn)程的現(xiàn)場(chǎng) PCB ?寄存器 先恢復(fù)通用寄存器和地址寄存器,最后恢復(fù)PSW,PC PSW和PC必須用一條指令恢復(fù),3.3 調(diào)度級(jí)別與多級(jí)調(diào)度,3.3.1 交換與中級(jí)調(diào)度 Swapping and mid-level scheduling 3.3.2 作業(yè)與高級(jí)調(diào)度 Job and high-level scheduling,處理機(jī)調(diào)度為低級(jí)調(diào)度 CPU scheduling = low level scheduling,3.3.1 交換與中級(jí)調(diào)度,術(shù)語(yǔ) 交換(swapping) 中級(jí)調(diào)度(mid-level scheduling) 并發(fā)度(degree of multi-programming) 目標(biāo)：控制并發(fā)度 并發(fā)度過(guò)高 系統(tǒng)開(kāi)銷大 響應(yīng)速度慢 內(nèi)存等資源緊張 進(jìn)程(線程)頻繁進(jìn)入等待狀態(tài) More deadlocks,3.3.1 交換與中級(jí)調(diào)度,剝奪,就緒,等待,運(yùn)行,,,,選中,等待事件,事件發(fā)生,,就緒 掛起,等待 掛起,,無(wú),終止,,,創(chuàng)建,創(chuàng)建,,結(jié)束,,,,,換出,換出,換入,換入,事件發(fā)生,UNIX的中級(jí)調(diào)度（sched #0),移入SRUN狀態(tài)進(jìn)程 如內(nèi)存不夠， 移出SWAIT和SSTOP狀態(tài)進(jìn)程； 如還不夠，移出SSLEEP和SRUN狀態(tài)進(jìn)程； 條件： 待移入進(jìn)程在外存時(shí)間=3秒； 待移出進(jìn)程在內(nèi)存時(shí)間=2秒。,3.3.2 作業(yè)與高級(jí)調(diào)度,作業(yè)狀態(tài): 提交: 輸入機(jī)向輸入井傳送 后備: 在輸入井,尚未進(jìn)入內(nèi)存 執(zhí)行: 分解為進(jìn)程,在內(nèi)存處理 完成: 處理完畢,結(jié)果在輸出井 退出: 由輸出井向打印機(jī)傳送,3.3.2 作業(yè)與高級(jí)調(diào)度,狀態(tài)轉(zhuǎn)換: 提交?后備: 由SPOOLing輸入進(jìn)程完成 Simultaneous Peripheral Operation On-Line 后備?執(zhí)行: 由作業(yè)調(diào)度(1)(高級(jí)調(diào)度)完成 高級(jí)調(diào)度: 系統(tǒng)進(jìn)程 執(zhí)行?完成: 由作業(yè)調(diào)度(2)完成 完成?退出: 由SPOOLing輸出進(jìn)程完成,提交,后備,,執(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)度的算法 時(shí)間片輪轉(zhuǎn)算法(RR) 最短剩余時(shí)間優(yōu)先(SRTN) 反饋排隊(duì)算法(FB),3.4 實(shí)時(shí)調(diào)度(real-time scheduling),實(shí)時(shí)任務(wù)： 具有明確時(shí)間約束的計(jì)算任務(wù)。 Eg. 某時(shí)刻前必須開(kāi)始處理 某時(shí)刻前必須處理完畢 實(shí)時(shí)調(diào)度： 合理安排就緒實(shí)時(shí)任務(wù)的執(zhí)行次序，滿足每個(gè)實(shí)時(shí)任務(wù)時(shí)間約束條件的調(diào)度。,實(shí)時(shí)任務(wù)分類,硬實(shí)時(shí) vs. 軟實(shí)時(shí) 硬實(shí)時(shí)(hard real-time): 必須滿足任務(wù)截止期要求 . 軟實(shí)時(shí)(soft real-time): 期望滿足截止期要求 . 周期性 vs. 隨機(jī)性 周期性: 每隔固定時(shí)間發(fā)生一次 隨機(jī)性: 由隨機(jī)事件觸發(fā)，其發(fā)生時(shí)刻不確定,術(shù)語(yǔ)解釋,Ready time: 就緒時(shí)間 Starting deadline: 開(kāi)始截止期 Processing time: 處理時(shí)間 Completion deadline: 完成截止期 Occurring frequency: 發(fā)生頻率,周期性實(shí)時(shí)事務(wù),,周期性實(shí)時(shí)事務(wù): 令Ci為任務(wù)Pi處理時(shí)間，Ti為任務(wù)Pi的發(fā)生周期，則任務(wù)P1,…,Pm可調(diào)度的必要條件為：,,周期性實(shí)時(shí)事務(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)度的必要條件,周期性實(shí)時(shí)事務(wù),10/20 + 25/50 = 1, 可調(diào)度(不考慮開(kāi)銷),,例子,,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)先選擇截止期最早的實(shí)時(shí)任務(wù) 可搶先 可以證明：對(duì)EDF來(lái)說(shuō)，可調(diào)度充分條件是： 在不可調(diào)度的條件下，可使錯(cuò)過(guò)截止期任務(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年 面向周期性實(shí)時(shí)事務(wù)，非剝奪式 優(yōu)先調(diào)度發(fā)生周期最短（頻度最高）的實(shí)時(shí)任務(wù) 可調(diào)度條件：,,,RMS的上限值,,RMS vs. EDF RMS可調(diào)度條件強(qiáng)于EDF RMS調(diào)度較EDF實(shí)現(xiàn)簡(jiǎn)單,RMS例子：,可調(diào)度，具體調(diào)度結(jié)果：,0 20 60 160 180 220 240 300 320 360 460,3.5 多處理機(jī)調(diào)度,問(wèn)題： M processes (threads) N processors SMP：symmetric multi-processors all processors are identical (homogeneous) 目標(biāo)：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) 一個(gè)就緒隊(duì)列(多處理機(jī)訪問(wèn)互斥) 優(yōu)點(diǎn) 不需要專門的處理機(jī)從事任務(wù)分派工作 任務(wù)分配均衡 缺點(diǎn) 當(dāng)CPU較多時(shí),就緒隊(duì)列成為瓶頸 線程兩次調(diào)度可能處于不同處理機(jī) 不能保證同組線程同時(shí)調(diào)度,自調(diào)度(self scheduling),就緒隊(duì)列,,,,進(jìn)程(線程),進(jìn)程(線程),進(jìn)程(線程),CPU,CPU,CPU,,,,自調(diào)度(self scheduling),例子: Mach, 改進(jìn)的自調(diào)度 全局隊(duì)列:系統(tǒng)一個(gè) 局部隊(duì)列:每個(gè)CPU一個(gè) 調(diào)度時(shí) 首先考慮局部隊(duì)列 然后考慮全局隊(duì)列,3.5.2 組調(diào)度(gang scheduling),將一組相關(guān)(合作)的線程同時(shí)分派到多個(gè)處理機(jī)上運(yùn)行 避免合作線程之間的相互等待 降低開(kāi)銷,提高運(yùn)行效率 例子: Cm* Task force (一組相關(guān)的計(jì)算),3.6 系統(tǒng)舉例,Linux進(jìn)程調(diào)度 Windows2000/XP線程調(diào)度 UNIX進(jìn)程調(diào)度（見(jiàn)第12章）,三種特征進(jìn)程 Real-time FIFO Real-time Round Robin Timesharing Goodness-based scheduling priority 0-40, (缺省值20 ),可通過(guò)nice系統(tǒng)調(diào)用調(diào)整 ，nice(value)中value的取值范圍為(-20,20)之間 ,取priority=20-value. counter 進(jìn)程尚可運(yùn)行的剩余時(shí)間,3.6.1 Linux 進(jìn)程調(diào)度,Linux 進(jìn)程調(diào)度,counter 對(duì)于運(yùn)行進(jìn)程來(lái)說(shuō)，每個(gè)時(shí)鐘間隔(10ms，稱為一個(gè)jiffy)，將counter減1 當(dāng)所有就緒進(jìn)程的counter配額下降到0時(shí)，重新計(jì)算所有進(jìn)程(包括等待進(jìn)程)的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 進(jìn)程調(diào)度,調(diào)度發(fā)生時(shí)刻： 運(yùn)行進(jìn)程的counter減至0； 運(yùn)行進(jìn)程執(zhí)行系統(tǒng)調(diào)用exit ; 運(yùn)行進(jìn)程因等待I/O、信號(hào)燈而被封鎖 ; 原來(lái)具有高goodness的進(jìn)程被解除封鎖 . 調(diào)度效果 : 實(shí)時(shí)優(yōu)先于分時(shí) 交互和I/O進(jìn)程優(yōu)先于CPU進(jìn)程,Linux 對(duì)稱多處理,Linux2.0是支持對(duì)稱多處理硬件的第一個(gè)Linux核心 ; 進(jìn)程或線程可以同時(shí)運(yùn)行在多個(gè)處理機(jī)上 . 為保持核心非剝奪同步要求，SMP通過(guò)一個(gè)唯一的核心自旋鎖(spin-lock)來(lái)保證任何時(shí)刻最多只有一個(gè)處理機(jī)執(zhí)行核心代碼, 支持真正意義上的SMP：將一個(gè)自旋鎖分解為若干個(gè)相互獨(dú)立的自旋鎖，分別用于保護(hù)核心代碼不相交的子集 .,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)先級(jí)別,16個(gè)實(shí)時(shí)優(yōu)先級(jí)（16-31） 一些內(nèi)核線程 應(yīng)用程序提升為實(shí)時(shí)優(yōu)先級(jí)需要有權(quán)限 不是真正意義上的實(shí)時(shí)調(diào)度 15個(gè)可變線程優(yōu)先級(jí)（1-15） 基本優(yōu)先級(jí) vs. 當(dāng)前優(yōu)先級(jí) 線程基本優(yōu)先級(jí)繼承進(jìn)程基本優(yōu)先級(jí), 可上下浮動(dòng)2 如: 進(jìn)程基本優(yōu)先級(jí)4, 其線程基本優(yōu)先級(jí)2—6, 當(dāng)前優(yōu)先級(jí)在2—15范圍內(nèi)變動(dòng). 可動(dòng)態(tài)提升 運(yùn)行完一個(gè)quantum之后自動(dòng)下降, 不低于基本優(yōu)先級(jí) 1個(gè)系統(tǒng)線程優(yōu)先級(jí)（0）,優(yōu)先級(jí)提升,優(yōu)先級(jí)提升 IO操作完成 事件等待結(jié)束 前臺(tái)進(jìn)程中的線程完成一個(gè)等待操作 由于窗口活動(dòng)而喚醒GUI線程 就緒超過(guò)一定時(shí)限，未獲得處理機(jī) 優(yōu)先級(jí)提升不會(huì)超過(guò)15,搶占CPU,搶先情形 被喚醒線程優(yōu)先級(jí)高于運(yùn)行線程優(yōu)先級(jí)； 某線程的優(yōu)先級(jí)動(dòng)態(tài)變化 被搶先線程 回到相應(yīng)就緒隊(duì)列 時(shí)間配額 實(shí)時(shí)線程：重新分配完整時(shí)間配額 其它線程：保持剩余配額,時(shí)間配額(quantum),配額長(zhǎng)度：6--36 時(shí)鐘中斷（15ms發(fā)生一次）減3，2--12次時(shí)鐘中斷（30ms--180ms）配額用完 配額用完后進(jìn)入就緒隊(duì)列，優(yōu)先級(jí)下降,SMP上的線程調(diào)度,線程與CPU的親合關(guān)系 每個(gè)進(jìn)程有一個(gè)處理器親合掩碼，缺省為所有處理器的集合 線程繼承其進(jìn)程的親合掩碼 親合掩碼可以修改 SetProcessAffinityMask, SetThreadAffinityMask;,SMP上的線程調(diào)度,線程的理想處理器（Ideal processor） 首選處理器： 第二處理器：（在內(nèi)核線程控制塊中） 理想處理器確定 線程創(chuàng)建時(shí)隨機(jī)確定， 分散各個(gè)線程與處理機(jī)對(duì)應(yīng)關(guān)系。 線程可修改SetThreadIdealProcessor,就緒線程對(duì)處理器的選擇,有空閑處理器 首選處理器 第二處理器 當(dāng)前執(zhí)行處理器（正執(zhí)行調(diào)度代碼） 由高到低順序找空閑的處理器 無(wú)空閑處理器，考慮搶先 首選處理器 第二處理器 可運(yùn)行編號(hào)最大處理器 不能搶先進(jìn)入相應(yīng)的就緒隊(duì)列,處理器對(duì)就緒線程的選擇,空閑處理器調(diào)度 線程上次在此CPU上運(yùn)行（二級(jí)緩沖利用） 線程的理想處理器是該CPU 處于就緒狀態(tài)時(shí)間超過(guò)2個(gè)quantum 優(yōu)先級(jí)別大于等于24,作業(yè) #1,進(jìn)程切換時(shí)需要保存哪些現(xiàn)場(chǎng)信息？請(qǐng)盡量考慮完全。 由核心返回目態(tài)程序時(shí)，進(jìn)程的PSW和PC為何必須用一條機(jī)器指令同時(shí)恢復(fù)？ 對(duì)如下三個(gè)實(shí)時(shí)任務(wù): T1=100, C1=50; T2=200, C2=30; T3=500, C3=100. 采用EDF算法和RMS算法是否可調(diào)度?如是畫(huà)出對(duì)應(yīng)的Gantt圖,否則說(shuō)明原因。,