中斷與處理機(jī)調(diào)度概念和系統(tǒng)

1、 中斷是與處理機(jī)管理密切相關(guān)的一個重要概念，確切地說,中斷是實(shí)現(xiàn)多道程序設(shè)計(jì)的必要條件。沒有中斷,OS就無法獲得系統(tǒng)的控制權(quán),就不能將處理機(jī)資源分派給不同的進(jìn)程。操作系統(tǒng)是中斷驅(qū)動的！中斷與處理機(jī)調(diào)度概念和系統(tǒng)3.1 中斷與中斷系統(tǒng) 3.1.1 中斷的概念 中斷: 在程序運(yùn)行過程中,出現(xiàn)了某種緊急事件,處理機(jī)必須中止當(dāng)前正在運(yùn)行的程序,轉(zhuǎn)去處理此事件,然后再恢復(fù)原來運(yùn)行的程序,這個過程稱作中斷。 中斷的實(shí)現(xiàn)需要硬件和軟件的合作,硬件部分稱作中斷裝置,軟件部分稱作中斷處理程序。中斷裝置和中斷處理程序統(tǒng)稱為中斷系統(tǒng)。中斷與處理機(jī)調(diào)度概念和系統(tǒng) 中斷裝置是用于發(fā)現(xiàn)并響應(yīng)中斷的硬件機(jī)構(gòu)。 中斷裝置發(fā)現(xiàn)

2、并響應(yīng)中斷的步驟: (1)識別中斷源。 引起中斷的事件稱為中斷源。 當(dāng)有多個中斷源同時存在時，中斷裝置可選擇優(yōu)先級最高的中斷源并響應(yīng)之。 (2)保存中斷現(xiàn)場。將運(yùn)行進(jìn)程的PSW及PC 中的內(nèi)容壓入系統(tǒng)棧(內(nèi)存中)。 (3)轉(zhuǎn)入中斷處理程序。將與中斷事件對應(yīng)的中斷向量從內(nèi)存指定單元取出送入PSW及PC中, 如此便轉(zhuǎn)入對應(yīng)的中斷處理程序。3.1.2 中斷裝置中斷與處理機(jī)調(diào)度概念和系統(tǒng)中斷的響應(yīng)過程如圖所示：中斷與處理機(jī)調(diào)度概念和系統(tǒng)正在運(yùn)行程序 1 6中斷處理程序 4PSW, PCPC:PSW, PC系統(tǒng)桟PSW, PC.253HALOS完整的中斷響應(yīng)和處理的過程中斷與處理機(jī)調(diào)度概念和系統(tǒng) 中斷源

3、與中斷字 引起中斷的事件稱為中斷源。例如，I/O完成、程序錯誤、缺頁、訪管(如終端用戶鍵入一個內(nèi)部命令)。 用于保存與中斷事件相關(guān)的信息的寄存器稱作中斷寄存器。中斷寄存器中的內(nèi)容稱作中斷字。 中斷與處理機(jī)調(diào)度概念和系統(tǒng)3.1.2.2 中斷類型與中斷向量 中斷分為兩大類: 強(qiáng)迫性中斷、自愿性中斷 1. 強(qiáng)迫性中斷 強(qiáng)迫性中斷是正在運(yùn)行程序所不期望的，運(yùn)行程序事先無法預(yù)知它們是否發(fā)生、何時發(fā)生。強(qiáng)迫性中斷大致可分為如下幾種: (1) 時鐘中斷: 如硬件實(shí)時時鐘到時等 (2) I/O中斷: 如設(shè)備出錯、傳輸結(jié)束等 (3) 控制臺中斷: 如系統(tǒng)操作員通過控制臺發(fā) 出命令等 (4) 硬件故障中斷: 如掉

4、電、內(nèi)存校驗(yàn)錯誤等 (5) 程序性中斷: 如目態(tài)程序執(zhí)行特權(quán)指令、 地址越界、缺頁故障、溢出、除零等 中斷與處理機(jī)調(diào)度概念和系統(tǒng)強(qiáng)迫性中斷與中斷裝置之間的關(guān)系如圖所示運(yùn)行程序時鐘中斷中斷裝置 中斷處理程序IO中斷控制臺中斷硬件故障中斷程序錯誤中斷中斷與處理機(jī)調(diào)度概念和系統(tǒng) 2. 自愿性中斷 自愿性中斷是正在運(yùn)行程序有意識安排的，它們通常由于正運(yùn)行程序執(zhí)行訪管指令而引起，目的是要求系統(tǒng)為其提供某種服務(wù)。自愿性中斷的發(fā)生具有必然性,而且發(fā)生位置確定。中斷裝置 中斷處理程序運(yùn)行程序訪管指令自愿性中斷與中斷裝置之間的關(guān)系如圖所示：中斷與處理機(jī)調(diào)度概念和系統(tǒng)PSW1, PC1 時鐘中斷向量PSW2, P

5、C2 I/O中斷向量PSW3, PC3 console中斷向量PSW4, PC4 硬件故障中斷向量PSW5, PC5 程序錯誤中斷向量 PSWn, PCn 訪管中斷向量00000008001600240032 0090時鐘中斷處理程序PC1:I/O中斷處理程序PC2:訪管中斷處理程序PCn:系統(tǒng)空間中斷向量與中斷處理程序的存儲方法如下：中斷與處理機(jī)調(diào)度概念和系統(tǒng)注意：(1) 每類中斷事件有一個中斷向量。(2) 中斷向量的存放位置是由硬件規(guī)定的。(3) 中斷向量的內(nèi)容是OS在系統(tǒng)初始化時 設(shè)置的。中斷與處理機(jī)調(diào)度概念和系統(tǒng) 3.1.2.3 中斷嵌套與系統(tǒng)棧 中斷嵌套：系統(tǒng)在處理一個中斷事件的過程

6、中又響應(yīng)了新的中斷,則稱發(fā)生了中斷嵌套。 理論上,中斷嵌套的層數(shù)沒有限制；實(shí)際上,在中斷事件的處理過程中,一般只容許更緊迫的(優(yōu)先級更高的)中斷事件打斷它,而硬件中斷優(yōu)先級的個數(shù)有限,因此，中斷嵌套的實(shí)際層數(shù)一般不會超過中斷優(yōu)先級的個數(shù)。中斷與處理機(jī)調(diào)度概念和系統(tǒng)中斷嵌套的一般情形如圖所示：目態(tài)PSW1, PC1管態(tài)PSW2, PC2管態(tài)PSWn, PCn中斷返回中斷響應(yīng)中斷與處理機(jī)調(diào)度概念和系統(tǒng)3.1.3 中斷處理程序 中斷裝置響應(yīng)中斷后,通過中斷向量轉(zhuǎn)入中斷處理程序。中斷處理程序需根據(jù)中斷碼進(jìn)一步分析中斷源,再進(jìn)行相應(yīng)的處理,最后根據(jù)情況決定是否需要切換進(jìn)程。 中斷處理的整個過程如下圖所示

7、： 中斷與處理機(jī)調(diào)度概念和系統(tǒng)強(qiáng)迫性中斷事件 自愿性中斷事件 轉(zhuǎn)中斷處理程序 是嵌套中斷？由系統(tǒng)棧恢復(fù)現(xiàn)場 需切換進(jìn)程？ 返回上層中斷 由系統(tǒng)棧恢復(fù)現(xiàn)場 轉(zhuǎn)CPU分派 返回目態(tài)程序保存現(xiàn)場信息取中斷碼分析中斷原因保存現(xiàn)場信息取訪管號分析調(diào)用功能TFFT中斷與處理機(jī)調(diào)度概念和系統(tǒng) 訪管指令通常分為如下幾類: (1)與文件有關(guān)的系統(tǒng)調(diào)用:如建立文件、撤消文件、打開文件、關(guān)閉文件、讀寫文件、文件指針定位等。 (2)與進(jìn)程有關(guān)的系統(tǒng)調(diào)用:如創(chuàng)建進(jìn)程、撤消進(jìn)程、創(chuàng)建線程、監(jiān)督進(jìn)程運(yùn)行狀況等。 (3)與通訊有關(guān)的系統(tǒng)調(diào)用:如發(fā)送消息、接收消息等。 (4)與同步有關(guān)的系統(tǒng)調(diào)用:如P操作、V操作等中斷與處理機(jī)

8、調(diào)度概念和系統(tǒng)3.2 處理機(jī)調(diào)度 處理機(jī)調(diào)度指CPU資源在可運(yùn)行實(shí)體之間的分配。不支持線程的OS將CPU分配給進(jìn)程；支持線程的OS，若線程是系統(tǒng)級的，OS將CPU分配給線程，若線程是用戶級的，OS將CPU分配給進(jìn)程。 處理機(jī)資源管理需解決三個問題: (1)按什么原則分配處理機(jī) -確定調(diào)度算法 (2)何時分配處理機(jī) -確定調(diào)度時機(jī) (3)如何分配處理機(jī) -給出調(diào)度過程中斷與處理機(jī)調(diào)度概念和系統(tǒng)3.2.1 處理機(jī)調(diào)度算法 計(jì)算機(jī)系統(tǒng)中，處于可運(yùn)行狀態(tài)進(jìn)程的個數(shù)通常比處理機(jī)的個數(shù)多, 所以當(dāng)處理機(jī)空閑時, 需從就緒進(jìn)程中選擇一個使其投入運(yùn)行。選擇哪個進(jìn)程呢? 這需要按照某種算法進(jìn)行。 從資源角度看,

9、該算法確定了處理機(jī)的分配策略, 故稱其為處理機(jī)調(diào)度算法；從資源使用者角度看,該算法確定了進(jìn)程運(yùn)行的次序,故稱其為進(jìn)程調(diào)度算法。 中斷與處理機(jī)調(diào)度概念和系統(tǒng) 選擇處理機(jī)調(diào)度算法時，應(yīng)考慮與系統(tǒng)的設(shè)計(jì)目標(biāo)一致，同時兼顧公平性與用戶滿意程度。具體考慮如下指標(biāo)： (1) CPU利用率：使CPU盡量處于忙碌狀態(tài); max (2) 吞吐量：單位時間處理計(jì)算任務(wù)的數(shù)量; max (3) 周轉(zhuǎn)時間：從計(jì)算任務(wù)就緒到處理完畢所需 的時間；min (4) 響應(yīng)時間：從計(jì)算任務(wù)就緒到開始處理所需 的時間；min (5) 系統(tǒng)開銷：系統(tǒng)在進(jìn)行進(jìn)程調(diào)度過程中所付 出的時間、空間代價。min中斷與處理機(jī)調(diào)度概念和系統(tǒng) 進(jìn)

10、程運(yùn)行需要處理機(jī)資源，I/O操作需要設(shè)備資源，這兩類資源往往交替使的。 對處理機(jī)的一次連續(xù)使用稱為CPU陣發(fā)期。 在CPU burst cycle，進(jìn)程(線程)使用CPU計(jì)算。 對設(shè)備的一次連續(xù)使用稱為I/O陣發(fā)期。 在I/O burst cycle，進(jìn)程(線程)啟動并等待I/O完成。 進(jìn)程運(yùn)行行為： CPU陣發(fā)期I/O陣發(fā)期CPU陣發(fā)期 I/O陣發(fā)期CPU陣發(fā)期 中斷與處理機(jī)調(diào)度概念和系統(tǒng) 處于CPU陣發(fā)期的進(jìn)程所需要的處理時間稱為陣發(fā)時間(Burst Time，BT)。 不同進(jìn)程的CPU陣發(fā)時間不同；同一進(jìn)程在不同CPU陣發(fā)期的陣發(fā)時間亦不同。 中斷與處理機(jī)調(diào)度概念和系統(tǒng) 衡量就緒任務(wù)處理

11、效率的度量標(biāo)準(zhǔn)： 周轉(zhuǎn)時間(turnaround time)：由就緒開始時刻 到處理完畢時刻的時間； 平均周轉(zhuǎn)時間(average )：所有進(jìn)程的周轉(zhuǎn)時 間之和與進(jìn)程個數(shù)的比值； 等待時間：周轉(zhuǎn)時間與處理時間之差； 平均等待時間：所有進(jìn)程的等待時間之和與進(jìn) 程個數(shù)的比值。中斷與處理機(jī)調(diào)度概念和系統(tǒng)常用的處理機(jī)調(diào)度算法：1. 先到先服務(wù)算法 (First-Come, First-Served, FCFS)2.短作業(yè)優(yōu)先 (Shortest Job First，SJF)3.最高響應(yīng)比優(yōu)先 (Highest Response Ratio Next,HRN)4.優(yōu)先數(shù)法 (Highest Priori

12、ty First，HPF)5.循環(huán)輪轉(zhuǎn)法 (Round Robin，RR)6.分類排隊(duì)法 (Multi Level Queues，MLQ)7.最短剩余時間法 (Shortest Remaining Time Next, SRTN)8.反饋排隊(duì)法 (Feed Back，F(xiàn)B)中斷與處理機(jī)調(diào)度概念和系統(tǒng) 非剝奪式調(diào)度與剝奪式調(diào)度 非剝奪式(non-preemptive) 非剝奪式調(diào)度也叫非搶占式調(diào)度。 所謂非剝奪式，是指一個進(jìn)程不能從正在運(yùn)行進(jìn)程那里搶占CPU。 采用非剝奪式調(diào)度方式時，一個進(jìn)程一旦被選中運(yùn)行,將一直運(yùn)行下去,直至出現(xiàn)如下情形:(1)該進(jìn)程因某種事件而等待；(2)該進(jìn)程運(yùn)行完畢。

13、優(yōu)點(diǎn)：系統(tǒng)開銷較小。 缺點(diǎn)：不能保證當(dāng)前正在運(yùn)行的進(jìn)程永遠(yuǎn)是 系統(tǒng)內(nèi)當(dāng)前可運(yùn)行進(jìn)程中優(yōu)先級最高 的進(jìn)程。中斷與處理機(jī)調(diào)度概念和系統(tǒng)剝奪式(preemptive) 剝奪式調(diào)度也叫搶占式調(diào)度。 所謂剝奪式，是指一個進(jìn)程可以從正在運(yùn)行進(jìn)程那里搶占CPU。 采用剝奪式調(diào)度方式時，發(fā)生如下情形可能導(dǎo)致進(jìn)程切換: (1)運(yùn)行進(jìn)程因某種事件而等待; (2)進(jìn)程運(yùn)行完畢; (3)出現(xiàn)了新的、優(yōu)先級高于正在運(yùn)行進(jìn)程的就緒進(jìn)程。 優(yōu)點(diǎn)：能保證正在運(yùn)行的進(jìn)程永遠(yuǎn)是系統(tǒng)內(nèi)當(dāng)前可運(yùn)行進(jìn)程中優(yōu)先級最高的進(jìn)程。 缺點(diǎn)：CPU在進(jìn)程間頻繁切換,系統(tǒng)開銷較大。中斷與處理機(jī)調(diào)度概念和系統(tǒng)3.2.1.1 先到先服務(wù)算法(FCFS)

14、 FCFS算法的基本思想： 按照進(jìn)程申請CPU的次序(即進(jìn)程進(jìn)入就緒狀態(tài)的次序)進(jìn)行調(diào)度。 例如，ProcessBurst timeP127P23P35若進(jìn)程到達(dá)次序?yàn)镻1, P2, P3，則Gantt圖如下：P1P2P30 27 30 35中斷與處理機(jī)調(diào)度概念和系統(tǒng)3.2.1.2 短平均等待時間=(0+27+30)/3=19 (ms)若進(jìn)程到達(dá)次序?yàn)镻2, P3, P1，則Gantt圖如下：P1P2P30 3 8 35平均等待時間 = (0+3+8) / 3 = 3.67 (ms)FCFS算法的優(yōu)點(diǎn)：具有公平性，不會出現(xiàn)餓死 情況。FCFS算法的缺點(diǎn)：短進(jìn)程(線程)等待時間長， 從而導(dǎo)致平均

15、等待時間較長。中斷與處理機(jī)調(diào)度概念和系統(tǒng)3.2.1.2 短作業(yè)優(yōu)先算法(SJF)ProcessBurst timeP112P25P37P43SJF算法的基本思想： 按CPU陣發(fā)時間由小到大的次序調(diào)度。例如，中斷與處理機(jī)調(diào)度概念和系統(tǒng)平均等待時間為: (0+3+8+15)/4=6.5(ms)SJF算法的優(yōu)點(diǎn)：所有任務(wù)同時到達(dá)時，其平均周 轉(zhuǎn)(等待)時間最短，從而最大限度地降低了 平均等待時間。SJF算法的缺點(diǎn)：具有不公平性。一個較長的就緒 任務(wù)可能由于短任務(wù)的不停到達(dá)而長期得不 到運(yùn)行機(jī)會，甚至被餓死。 Gant chart:P1P3P2P40 3 8 15 27中斷與處理機(jī)調(diào)度概念和系統(tǒng)最高響

16、應(yīng)比算法是FCFS算法和SJF算法的折中。HRN算法基本思想： 按響應(yīng)比由大到小的次序調(diào)度。響應(yīng)比計(jì)算公式如下： 3.2.1.3 最高響應(yīng)比優(yōu)先算法(HRN) 其中，RR表示響應(yīng)比，BT為CPU陣發(fā)時間，WT為等待時間。顯然，對于同時到達(dá)的任務(wù)，處理時間短的將被優(yōu)先調(diào)度，處理時間較長的作業(yè)將隨其等待時間的增加而動態(tài)提升其響應(yīng)比，因而不會出現(xiàn)餓死現(xiàn)象。中斷與處理機(jī)調(diào)度概念和系統(tǒng)3.2.1.4 最高優(yōu)先數(shù)算法(HPF) 優(yōu)先數(shù)法的基本思想：每個進(jìn)程的PCB中有一個用數(shù)字表示的優(yōu)先數(shù)。當(dāng)需要進(jìn)行處理機(jī)分配時,系統(tǒng)在可運(yùn)行進(jìn)程中選擇優(yōu)先數(shù)最高者使其投入運(yùn)行。 中斷與處理機(jī)調(diào)度概念和系統(tǒng)優(yōu)先數(shù)算法尚有兩

17、個問題需要解決: 如何確定進(jìn)程的優(yōu)先數(shù) 何時進(jìn)行處理機(jī)調(diào)度1. 確定進(jìn)程優(yōu)先數(shù)的方法有兩種： (1) 靜態(tài)優(yōu)先數(shù)(static priority) 每個進(jìn)程在創(chuàng)建時被賦予一個優(yōu)先數(shù), 該 優(yōu)先數(shù)在進(jìn)程的整個生存期內(nèi)固定不變。 優(yōu)點(diǎn)：比較簡單, 開銷較?。?缺點(diǎn)：公平性差, 可能造成低優(yōu)先數(shù)進(jìn)程的 長期等待。 靜態(tài)優(yōu)先數(shù)法適合于批處理進(jìn)程。中斷與處理機(jī)調(diào)度概念和系統(tǒng) (2) 動態(tài)優(yōu)先數(shù)(dynamic priority) 每個進(jìn)程在創(chuàng)建時被賦予一個優(yōu)先數(shù),該優(yōu)先數(shù)在進(jìn)程的生存期內(nèi)可以動態(tài)變化。 比如，當(dāng)進(jìn)程獲得某種資源時，其優(yōu)先級應(yīng)增高。又如,當(dāng)進(jìn)程處于就緒狀態(tài)時,其優(yōu)先級應(yīng)隨著等待時間的增長而

18、提高等。因此，動態(tài)優(yōu)先數(shù)算法適用于實(shí)時系統(tǒng)。 優(yōu)點(diǎn)：資源利用率高,公平性好; 缺點(diǎn)：開銷較大,實(shí)現(xiàn)較為復(fù)雜。中斷與處理機(jī)調(diào)度概念和系統(tǒng)2.處理機(jī)的調(diào)度時刻有兩種: 非剝奪式、剝奪式 非剝奪式靜態(tài)優(yōu)先數(shù)： 獲得CPU的進(jìn)程一直運(yùn)行，直至 終止、等待剝奪式動(靜)態(tài)優(yōu)先數(shù) 獲得CPU的進(jìn)程運(yùn)行，直至 終止、等待、出現(xiàn)高優(yōu)先級的進(jìn)程中斷與處理機(jī)調(diào)度概念和系統(tǒng)3.2.1.5 循環(huán)輪轉(zhuǎn)算法(RR) 循環(huán)輪轉(zhuǎn)算法的基本思想：系統(tǒng)為每個進(jìn)程規(guī)定一個時間片(time slice),所有進(jìn)程按其時間片的長短輪流地運(yùn)行。 采用循環(huán)輪轉(zhuǎn)算法時，所有就緒進(jìn)程排成一個隊(duì)列，當(dāng)處理機(jī)空閑時便選擇隊(duì)列頭部的進(jìn)程使其投入運(yùn)行

19、,同時分給它一個時間片,當(dāng)此時間片用完時,如果此進(jìn)程既未結(jié)束，其CPU陣發(fā)也未因某種原因而等待,則剝奪此進(jìn)程所占有的處理機(jī),將其排在就緒隊(duì)列的尾部,并選擇就緒隊(duì)列中隊(duì)頭的進(jìn)程運(yùn)行。 中斷與處理機(jī)調(diào)度概念和系統(tǒng)循環(huán)輪轉(zhuǎn)法在實(shí)現(xiàn)時分為基本輪轉(zhuǎn)和改進(jìn)輪轉(zhuǎn)。 1.基本輪轉(zhuǎn) 基本輪轉(zhuǎn)法分給所有進(jìn)程的時間片的長度是相同的,而且是不變的。 采用基本輪轉(zhuǎn)法的系統(tǒng),若不考慮I/O等待,所有進(jìn)程以基本均等的速度向前推進(jìn)。 2.改進(jìn)輪轉(zhuǎn) 改進(jìn)輪轉(zhuǎn)法分給不同進(jìn)程的時間片的長度是不同的,而且(或者)是可變的。 采用改進(jìn)輪轉(zhuǎn)法的系統(tǒng), 可根據(jù)不同進(jìn)程的不同特性為其動態(tài)地分配不同長度的時間片, 以達(dá)到更靈活的調(diào)度效果。 中

20、斷與處理機(jī)調(diào)度概念和系統(tǒng) 采用循環(huán)輪轉(zhuǎn)法進(jìn)行調(diào)度時,時間片的長度需認(rèn)真加以考慮。如果時間片過長,則會影響系統(tǒng)的響應(yīng)速度;如果過短,則會頻繁地發(fā)生進(jìn)程切換,增加系統(tǒng)的開銷。通常,時間片的長度為幾十毫秒至幾百毫秒。 循環(huán)輪轉(zhuǎn)法特別適用于分時系統(tǒng)，具有公平性且響應(yīng)及時等特點(diǎn)。中斷與處理機(jī)調(diào)度概念和系統(tǒng)3.2.1.6 分類排隊(duì)算法(MLQ) 分類排隊(duì)法又稱多級隊(duì)列法，它以多個就緒進(jìn)程隊(duì)列為特征。 多個就緒隊(duì)列將系統(tǒng)中所有可運(yùn)行進(jìn)程按某種原則加以分類,以實(shí)現(xiàn)某種調(diào)度目標(biāo)。 例如,在通用操作系統(tǒng)中,可將所有就緒進(jìn)程排成如下三個隊(duì)列: Q1: 實(shí)時就緒進(jìn)程隊(duì)列 Q2: 分時就緒進(jìn)程隊(duì)列 Q3: 批處理就緒進(jìn)

21、程隊(duì)列 當(dāng)處理機(jī)空閑時,首先選擇Q1中的進(jìn)程,若Q1為空，則選擇Q2中的進(jìn)程；若Q1,Q2均為空,則選擇Q3中的進(jìn)程。每個隊(duì)列內(nèi)部又可分別采用不同的調(diào)度算法。中斷與處理機(jī)調(diào)度概念和系統(tǒng)3.2.1.7 最短剩余時間算法(SRTN) SRTN算法為剝奪式調(diào)度算法。當(dāng)CPU空閑時，選擇剩余時間最短的進(jìn)程或線程。當(dāng)一個新進(jìn)程或線程到達(dá)時，比較新進(jìn)程與當(dāng)前運(yùn)行進(jìn)程的估計(jì)剩余時間，如果新進(jìn)程的剩余運(yùn)行時間短則切換運(yùn)行進(jìn)程。 SRTN算法實(shí)質(zhì)上是可剝奪的短作業(yè)優(yōu)先調(diào) 度算法。中斷與處理機(jī)調(diào)度概念和系統(tǒng)3. 2.1.8 反饋排隊(duì)算法(FB) 分類排隊(duì)法中,盡管系統(tǒng)中有多個進(jìn)程就緒隊(duì)列,但一個進(jìn)程僅屬于一個就緒

22、隊(duì)列,即進(jìn)程不能在不同的就緒隊(duì)列之間移動。 反饋排隊(duì)法也以多個進(jìn)程就緒隊(duì)列為特征,每個隊(duì)列中通常采用時間片輪轉(zhuǎn)調(diào)度算法,與分類排隊(duì)法不同的是進(jìn)程可以在不同的就緒隊(duì)列之間移動。 中斷與處理機(jī)調(diào)度概念和系統(tǒng)Q1（RR，HPF）Q2（RR，HPF）Qn（RR，HPF）運(yùn)行s1時間片運(yùn)行s2時間片.創(chuàng)建喚醒優(yōu)先級 時間片運(yùn)行sn時間片中斷與處理機(jī)調(diào)度概念和系統(tǒng) 反饋排隊(duì)法的基本思想： 多個就緒隊(duì)列的優(yōu)先級依次遞減,而其時間片的長度則依次遞增。當(dāng)一進(jìn)程被創(chuàng)建或所等待的事件發(fā)生時,進(jìn)入第一級就緒隊(duì)列。當(dāng)某隊(duì)列的一個進(jìn)程獲得CPU并使用完該隊(duì)列所對應(yīng)的時間片后,如果它尚未結(jié)束,則進(jìn)入下一級就緒隊(duì)列。 當(dāng)最后

23、一級隊(duì)列的一個進(jìn)程獲得CPU并使用完該隊(duì)列所對應(yīng)的時間片后,如果它尚未結(jié)束,則進(jìn)入同一級就緒隊(duì)列。當(dāng)處理機(jī)空閑時,先選擇第一級就緒隊(duì)列的進(jìn)程,當(dāng)該級隊(duì)列為空時,選擇第二級就緒隊(duì)列的進(jìn)程,如此類推。 中斷與處理機(jī)調(diào)度概念和系統(tǒng) 反饋排隊(duì)法的特點(diǎn): (1)短進(jìn)程優(yōu)先處理。因?yàn)檫\(yùn)行時間短的進(jìn)程經(jīng)過前面幾個隊(duì)列之后便已經(jīng)執(zhí)行完,而這些隊(duì)列中的進(jìn)程被優(yōu)先調(diào)度。 (2)設(shè)備資源利用率高。因?yàn)榕c設(shè)備打交道的進(jìn)程可能會由于下面的原因而進(jìn)入等待狀態(tài):(a)所申請的資源被占用;(b)啟動了I/O傳輸。當(dāng)進(jìn)程得到所等待的資源或I/O傳輸完成時,它將進(jìn)入第一級就緒隊(duì)列,盡快獲得CPU并使用資源。 (3)系統(tǒng)開銷較小。

24、因?yàn)檫\(yùn)行時間長的進(jìn)程最后進(jìn)入低優(yōu)先級的隊(duì)列,這些隊(duì)列的時間片較長,因而進(jìn)程的調(diào)度頻率較低。中斷與處理機(jī)調(diào)度概念和系統(tǒng) 說明： 在反饋排隊(duì)法中,如果高優(yōu)先級隊(duì)列一直不為空,則低優(yōu)先級隊(duì)列中的進(jìn)程可能長時間得不到運(yùn)行的機(jī)會,如此便可能會發(fā)生“餓死”現(xiàn)象。 為解決這一問題,常根據(jù)某種原則允許將低優(yōu)先級隊(duì)列中的進(jìn)程移到高優(yōu)先級隊(duì)列中去。中斷與處理機(jī)調(diào)度概念和系統(tǒng)3.2.2 處理機(jī)調(diào)度時機(jī) 為方便敘述,引入一個進(jìn)程切換的概念。 如果在時刻T1進(jìn)程P1在運(yùn)行,在時刻T2進(jìn)程P2在運(yùn)行,且P1P2,則稱在時刻T1和時刻T2之間發(fā)生了進(jìn)程切換,并稱P1為下降進(jìn)程,稱P2為上升進(jìn)程。 處理機(jī)調(diào)度程序是操作系統(tǒng)低

25、層中的一個模塊,在系統(tǒng)運(yùn)行過程中,除非顯式調(diào)用該模塊,否則系統(tǒng)不會發(fā)生進(jìn)程切換。 中斷與處理機(jī)調(diào)度概念和系統(tǒng) 何時可能調(diào)用到處理機(jī)調(diào)度程序呢? 前提是必須進(jìn)入操作系統(tǒng),即處于系統(tǒng)態(tài),因?yàn)樘幱谟脩魬B(tài)運(yùn)行的用戶程序不可能直接調(diào)用操作系統(tǒng)中的任何模塊。 中斷是系統(tǒng)由用戶態(tài)轉(zhuǎn)換為系統(tǒng)態(tài)的必要條件。據(jù)此,假如在時刻T1與時刻T2之間發(fā)生了進(jìn)程切換,則在時刻T1與時刻T2之間一定發(fā)生過中斷。中斷是進(jìn)程切換的前提,也可以說，操作系統(tǒng)是中斷驅(qū)動的。中斷與處理機(jī)調(diào)度概念和系統(tǒng) 中斷可以嵌套,且嵌套層數(shù)原則上沒有限制。若發(fā)生中斷嵌套,系統(tǒng)將一直處于管態(tài)。中斷返回逐層進(jìn)行,僅當(dāng)返回到最外層時,才退回到目態(tài)。如圖所示

26、目態(tài)（Pi運(yùn)行）目態(tài)（Pj運(yùn)行）管態(tài)管態(tài).中斷中斷中斷返回返回返回Pi=Pj 未發(fā)生進(jìn)程切換；PiPj 發(fā)生了進(jìn)程切換。中斷與處理機(jī)調(diào)度概念和系統(tǒng) 中斷是否一定會導(dǎo)致進(jìn)程切換呢? 回答是否定的,就是說，中斷不是進(jìn)程切換的充分條件。例如，一個進(jìn)程執(zhí)行一個系統(tǒng)調(diào)用命令將一個消息發(fā)給另一個進(jìn)程。該命令的執(zhí)行將通過中斷進(jìn)入操作系統(tǒng),操作系統(tǒng)處理完消息的發(fā)送工作后可能返回原調(diào)用進(jìn)程,也可能選擇一個新的進(jìn)程。在上圖中,如果PiPj, 則中斷未導(dǎo)致進(jìn)程切換；如PiPj,則中斷導(dǎo)致了進(jìn)程切換。中斷與處理機(jī)調(diào)度概念和系統(tǒng) 何種情況下中斷可能導(dǎo)致進(jìn)程切換，何種情況下中斷不會導(dǎo)致進(jìn)程切換呢? 該問題與系統(tǒng)選擇的進(jìn)程

27、調(diào)度策略等因素有關(guān)。一般地,若中斷處理完后，原進(jìn)程不再具備繼續(xù)運(yùn)行的條件,則一定會發(fā)生進(jìn)程切換;反之,若中斷處理完后，原進(jìn)程仍具備繼續(xù)運(yùn)行的條件,則可能發(fā)生進(jìn)程切換,也可能不發(fā)生進(jìn)程切換,這與處理機(jī)調(diào)度策略有關(guān)。 例如,一個進(jìn)程欲讀取文件內(nèi)容,通過讀文件系統(tǒng)調(diào)用進(jìn)入管態(tài),OS做完必要的準(zhǔn)備后啟動設(shè)備進(jìn)行I/O傳輸。因原進(jìn)程需等待I/O傳輸完成,此時CPU可轉(zhuǎn)去運(yùn)行其它進(jìn)程,發(fā)生了進(jìn)程切換。 中斷與處理機(jī)調(diào)度概念和系統(tǒng) 再如，在采用時間片輪轉(zhuǎn)處理機(jī)調(diào)度算法的系統(tǒng)中,一個進(jìn)程在運(yùn)行過程中發(fā)生了時鐘中斷進(jìn)入管態(tài),OS完成與時間有關(guān)的維護(hù)工作后,若原進(jìn)程的時間片已用完,則發(fā)生進(jìn)程切換,否則不發(fā)生進(jìn)程切

28、換。 一定能引起進(jìn)程切換的中斷原因有： 進(jìn)程運(yùn)行終止、進(jìn)程等待資源、進(jìn)程等待I/O傳輸完成等 可能引起進(jìn)程切換的中斷原因有： 時鐘中斷、設(shè)備I/O中斷信號、系統(tǒng)調(diào)用等中斷與處理機(jī)調(diào)度概念和系統(tǒng)3.2.3 處理機(jī)調(diào)度過程處理機(jī)調(diào)度需經(jīng)歷如下三個主要步驟: 1.保存下降進(jìn)程現(xiàn)場 中斷響應(yīng)時,中斷裝置將被中斷進(jìn)程的中斷向量壓入系統(tǒng)棧。中斷響應(yīng)后,中斷處理程序?qū)⒈恢袛噙M(jìn)程的其它斷點(diǎn)信息,如寄存器內(nèi)容等壓入系統(tǒng)棧。中斷處理后,若需進(jìn)程切換,則將系統(tǒng)棧中的現(xiàn)場信息彈出,送入下降進(jìn)程的PCB。 (系統(tǒng)棧PCB) 兩種特殊情形：(1)系統(tǒng)初啟時無下降進(jìn)程，這步不執(zhí)行；(2)下降進(jìn)程為終止進(jìn)程時，只需將系統(tǒng)棧中

29、的現(xiàn)場信息彈出，不需保存。 中斷與處理機(jī)調(diào)度概念和系統(tǒng) 2.選擇將要運(yùn)行的進(jìn)程 按處理機(jī)調(diào)度算法在就緒隊(duì)列中選擇一個進(jìn)程,將其投入運(yùn)行。 為防止就緒隊(duì)列為空，系統(tǒng)通常安排一個特殊進(jìn)程,該進(jìn)程永遠(yuǎn)也進(jìn)行不完,且其調(diào)度級別最低(閑逛進(jìn)程)。當(dāng)系統(tǒng)中無其它進(jìn)程可運(yùn)行時,就運(yùn)行該閑逛進(jìn)程。閑逛進(jìn)程很容易構(gòu)造,如一個死循環(huán)程序、一個計(jì)算值的程序等對應(yīng)的進(jìn)程都可作為閑逛進(jìn)程。中斷與處理機(jī)調(diào)度概念和系統(tǒng) 3.恢復(fù)上升進(jìn)程現(xiàn)場 由于進(jìn)程下降時已將其現(xiàn)場信息保存在對應(yīng)的PCB中,故進(jìn)程上升時由其PCB中的信息恢復(fù)現(xiàn)場(PCB寄存器)。 恢復(fù)進(jìn)程現(xiàn)場的步驟: 先恢復(fù)通用寄存器等內(nèi)容,再恢復(fù)中斷向量,而且中斷向量中的PSW與PC的內(nèi)容必須由一條指令同時恢復(fù).(為什么?) 因?yàn)橹挥杏靡粭l指令同時恢復(fù)PSW和PC的內(nèi)容，才能保證系統(tǒng)由管態(tài)轉(zhuǎn)到目態(tài)時,能正確轉(zhuǎn)到上升進(jìn)程的斷點(diǎn)處繼續(xù)執(zhí)行?；蛘?因?yàn)槿粲脙蓷l或多條指令恢復(fù)PSW和PC的內(nèi)容，無法保證系統(tǒng)在由管態(tài)轉(zhuǎn)到目態(tài)時，能正確轉(zhuǎn)到上升進(jìn)程的斷點(diǎn)處繼續(xù)執(zhí)行。 中斷與處理機(jī)調(diào)度概念和系統(tǒng)3.