第3章 處理機(jī)調(diào)度4.ppt

1、第3章 處理機(jī)調(diào)度,本章內(nèi)容,3.1 調(diào)度級(jí)別 3.2 作業(yè)調(diào)度 3.3 進(jìn)程調(diào)度 3.4 調(diào)度性能的評(píng)價(jià) 3.5 常用調(diào)度算法 3.6 中斷處理 3.7 Linux系統(tǒng)中的進(jìn)程調(diào)度,處理機(jī)調(diào)度,處理機(jī)調(diào)度是操作系統(tǒng)的重要功能之一，其調(diào)度策略決定了操作系統(tǒng)的類型，其算法優(yōu)劣直接影響整個(gè)系統(tǒng)的性能。調(diào)度問(wèn)題是操作系統(tǒng)設(shè)計(jì)的一個(gè)中心問(wèn)題。 調(diào)度就是選出待分配的作業(yè)或進(jìn)程。處理機(jī)調(diào)度的目的就是分配處理機(jī)。 除了挑選合適的進(jìn)程投入運(yùn)行以外，調(diào)度程序還要關(guān)注CPU的利用效率。,在不同的操作系統(tǒng)中所采用的調(diào)度方式并不完全相同。有的系統(tǒng)中采用一級(jí)調(diào)度、二級(jí)調(diào)度或三級(jí)調(diào)度，且調(diào)度的算法也可以完全不同。 三級(jí)調(diào)

2、度模型：作業(yè)從進(jìn)入系統(tǒng)到最后完成，可以經(jīng)歷三級(jí)調(diào)度：高級(jí)調(diào)度、中級(jí)調(diào)度和低級(jí)調(diào)度。,調(diào)度級(jí)別, 高級(jí)調(diào)度,高級(jí)調(diào)度：又稱作業(yè)調(diào)度。 主要功能：根據(jù)一定的算法，從輸入的一批作業(yè)中選出若干個(gè)作業(yè)，分配必要的資源，如內(nèi)存、外設(shè)等。為其建立相應(yīng)的用戶作業(yè)進(jìn)程和為其服務(wù)的系統(tǒng)進(jìn)程（如I/O進(jìn)程），最后把它們的程序和數(shù)據(jù)調(diào)入內(nèi)存，等待進(jìn)程調(diào)度程序?qū)ζ溥M(jìn)行調(diào)度，并在作業(yè)完成后作善后處理工作。, 中級(jí)調(diào)度,為了使內(nèi)存同時(shí)存放的進(jìn)程數(shù)目不至于太多，有時(shí)需將某些進(jìn)程從內(nèi)存中移到外存上，以減少多道程序的數(shù)目。引入中級(jí)調(diào)度的目的是提高內(nèi)存的利用率和系統(tǒng)吞吐量。實(shí)際上是內(nèi)存管理中的對(duì)換功能。, 低級(jí)調(diào)度,低級(jí)調(diào)度：又稱

3、進(jìn)程調(diào)度。 主要功能：根據(jù)一定的算法將CPU分配給就緒隊(duì)列中的一個(gè)進(jìn)程。 執(zhí)行進(jìn)程調(diào)度的程序稱為進(jìn)程調(diào)度程序，由它實(shí)現(xiàn)CPU在進(jìn)程間的切換。進(jìn)程調(diào)度程序運(yùn)行頻率很高，在分時(shí)系統(tǒng)中往往經(jīng)過(guò)幾十毫秒就要運(yùn)行一次。 進(jìn)程調(diào)度是操作系統(tǒng)中最基本的一種調(diào)度。在一般類型的操作系統(tǒng)中都必須有進(jìn)程調(diào)度，且調(diào)度策略的優(yōu)劣直接影響整個(gè)系統(tǒng)的性能。,本章內(nèi)容,3.1 調(diào)度級(jí)別 3.2 作業(yè)調(diào)度 3.3 進(jìn)程調(diào)度 3.4 調(diào)度性能的評(píng)價(jià) 3.5 常用調(diào)度算法 3.6 中斷處理 3.7 Linux系統(tǒng)中的進(jìn)程調(diào)度,3.2 作業(yè)調(diào)度,3.2.1 作業(yè)狀態(tài) 3.2.2 作業(yè)調(diào)度,3.2.1 作業(yè)狀態(tài)（4種）,提交狀態(tài)：用戶

4、向系統(tǒng)提交一個(gè)作業(yè)時(shí)，該作業(yè)所處的狀況。 后備狀態(tài)：用戶作業(yè)經(jīng)過(guò)輸入設(shè)備送入輸出井（磁盤(pán)）中存放，等待進(jìn)入內(nèi)存時(shí)所處的狀況。此時(shí)，該作業(yè)的數(shù)據(jù)已轉(zhuǎn)換成為機(jī)器可讀的內(nèi)部形式，并且作業(yè)請(qǐng)求資源等信息也交給了操作系統(tǒng)。,執(zhí)行狀態(tài)：作業(yè)分配到所需要的資源，被調(diào)入內(nèi)存，其進(jìn)程經(jīng)調(diào)度在處理機(jī)上執(zhí)行相應(yīng)的程序時(shí)所處的狀況。此時(shí)該作業(yè)真正處于活動(dòng)狀態(tài)。 完成狀態(tài)：作業(yè)完成了計(jì)算任務(wù)，結(jié)果由打印機(jī)輸出，最后由系統(tǒng)收回分配給它的全部資源，準(zhǔn)備退出系統(tǒng)時(shí)的作業(yè)狀況。,作業(yè)的流程,3.2.2 作業(yè)調(diào)度,作業(yè)控制塊（Job Control Block ，JCB ）：在多道批處理系統(tǒng)中通常有上百個(gè)作業(yè)被收容在輸入井（磁盤(pán)

5、）中，為了管理和調(diào)度作業(yè)，系統(tǒng)為每個(gè)作業(yè)設(shè)置了一個(gè)作業(yè)控制塊（JCB），它記錄該作業(yè)的有關(guān)信息。不同系統(tǒng)的JCB的組成內(nèi)容有所區(qū)別。,作業(yè)控制塊的主要內(nèi)容,JCB是作業(yè)在系統(tǒng)中存在的唯一標(biāo)志。作業(yè)進(jìn)入系統(tǒng)時(shí)由SPOOLing系統(tǒng)為每個(gè)作業(yè)建立一個(gè)JCB；當(dāng)作業(yè)退出系統(tǒng)時(shí)，則它的JCB也一起被撤消。 在磁盤(pán)輸入井中的所有后備作業(yè)按作業(yè)類型（CPU型、I/O型等）組成不同的后備作業(yè)隊(duì)列。由作業(yè)調(diào)度程序從中挑選作業(yè)，隨后放入內(nèi)存，予以運(yùn)行。 作業(yè)調(diào)度主要用于批處理系統(tǒng)。,2. 作業(yè)調(diào)度的主要任務(wù)：完成作業(yè)從后備狀態(tài)到執(zhí)行狀態(tài)和從執(zhí)行狀態(tài)到完成狀態(tài)的轉(zhuǎn)換。 作業(yè)調(diào)度的主要功能： 記錄系統(tǒng)中各個(gè)作業(yè)的情

6、況; 按照某種調(diào)度算法從后備作業(yè)隊(duì)列中挑選作業(yè); 為選中的作業(yè)分配內(nèi)存和外設(shè)等資源; 為選中的作業(yè)建立相應(yīng)的進(jìn)程; 作業(yè)結(jié)束后進(jìn)行善后處理工作。,本章內(nèi)容,3.1 調(diào)度級(jí)別 3.2 作業(yè)調(diào)度 3.3 進(jìn)程調(diào)度 3.4 調(diào)度性能的評(píng)價(jià) 3.5 常用調(diào)度算法 3.6 中斷處理 3.7 Linux系統(tǒng)中的進(jìn)程調(diào)度,3.3 進(jìn)程調(diào)度,3.3.1 進(jìn)程調(diào)度的功能和時(shí)機(jī) 3.3.2 兩級(jí)調(diào)度模型 3.3.3 三級(jí)調(diào)度模型,3.3.1 進(jìn)程調(diào)度的功能和時(shí)機(jī),進(jìn)程調(diào)度為低級(jí)調(diào)度，完成進(jìn)程狀態(tài)從就緒態(tài)到運(yùn)行態(tài)的轉(zhuǎn)化。進(jìn)程調(diào)度程序完成一臺(tái)物理CPU轉(zhuǎn)變?yōu)槎嗯_(tái)虛擬（或邏輯）CPU的工作。 進(jìn)程調(diào)度程序是操作系統(tǒng)的真

7、正核心，它直接負(fù)責(zé)CPU的分配。系統(tǒng)中所有進(jìn)程都是在CPU上運(yùn)行的，進(jìn)程調(diào)度程序就是它們的切換開(kāi)關(guān)。,1. 進(jìn)程調(diào)度的主要功能,保存現(xiàn)場(chǎng)：當(dāng)前運(yùn)行的進(jìn)程調(diào)用進(jìn)程調(diào)度程序時(shí), 即表示該進(jìn)程要求放棄CPU。這時(shí)，進(jìn)程調(diào)度程序把它的現(xiàn)場(chǎng)信息, 如程序計(jì)數(shù)器及通用寄存器的內(nèi)容等保留在該進(jìn)程PCB的現(xiàn)場(chǎng)信息區(qū)中； 挑選進(jìn)程：根據(jù)一定的調(diào)度算法, 從就緒隊(duì)列中選出一個(gè)進(jìn)程, 并將其狀態(tài)置為運(yùn)行態(tài), 準(zhǔn)備分配CPU； 恢復(fù)現(xiàn)場(chǎng)：為選中的進(jìn)程恢復(fù)現(xiàn)場(chǎng)信息, 并將CPU控制權(quán)交給該進(jìn)程, 從而接著上次間斷的地方繼續(xù)運(yùn)行。,2. 進(jìn)程調(diào)度的時(shí)機(jī),任務(wù)完成：正在運(yùn)行的進(jìn)程完成任務(wù)后, 主動(dòng)釋放對(duì)CPU的控制； 等待

8、資源：由于等待某些資源或事件, 正在運(yùn)行的進(jìn)程不得不放棄CPU; 運(yùn)行到時(shí)：在分時(shí)系統(tǒng)中, 當(dāng)前進(jìn)程使用完規(guī)定的時(shí)間片時(shí), 時(shí)鐘中斷使該進(jìn)程讓出CPU; 發(fā)現(xiàn)標(biāo)志：核心處理完中斷或陷入事件后, 發(fā)現(xiàn)系統(tǒng)中“重新調(diào)度”標(biāo)志被置上, 表明有比當(dāng)前用戶進(jìn)程更適宜運(yùn)行的進(jìn)程, 則執(zhí)行進(jìn)程調(diào)度。,二、進(jìn)程的狀態(tài)和組成,3.3.2 兩級(jí)調(diào)度模型,作業(yè)調(diào)度和進(jìn)程調(diào)度是CPU主要的兩級(jí)調(diào)度，它們的區(qū)別如下: 級(jí)別不同。作業(yè)調(diào)度是宏觀調(diào)度，為進(jìn)程活動(dòng)做準(zhǔn)備,進(jìn)程調(diào)度是微觀調(diào)度，使進(jìn)程真正活動(dòng)起來(lái)； 執(zhí)行頻率不同。作業(yè)調(diào)度次數(shù)少,進(jìn)程調(diào)度頻率高； 有的系統(tǒng)不設(shè)作業(yè)調(diào)度, 但進(jìn)程調(diào)度必不可少。,二級(jí)調(diào)度簡(jiǎn)化隊(duì)列圖,

9、本章內(nèi)容,3.1 調(diào)度級(jí)別 3.2 作業(yè)調(diào)度 3.3 進(jìn)程調(diào)度 3.4 調(diào)度性能的評(píng)價(jià) 3.5 常用調(diào)度算法 3.6 中斷處理 3.7 Linux系統(tǒng)中的進(jìn)程調(diào)度,3.4 調(diào)度性能的評(píng)價(jià),3.4.1 調(diào)度策略的選擇 3.4.2 性能評(píng)價(jià)準(zhǔn)則,3.4.1 確定調(diào)度策略時(shí)應(yīng)考慮的主要因素,設(shè)計(jì)目標(biāo)。所用算法應(yīng)保證實(shí)現(xiàn)系統(tǒng)的設(shè)計(jì)目標(biāo)。 目標(biāo)不同， 系統(tǒng)設(shè)計(jì)要求不同。 批處理系統(tǒng): 提高資源利用率和增加系統(tǒng)的平均吞吐量； 分時(shí)系統(tǒng): 保證對(duì)用戶的均衡響應(yīng)時(shí)間; 實(shí)時(shí)系統(tǒng): 實(shí)現(xiàn)對(duì)事件的及時(shí)可靠的處理; 網(wǎng)絡(luò)系統(tǒng): 用戶和程序能方便、有效地利用網(wǎng)絡(luò)中的分布式資源。,公平性。對(duì)所有作業(yè)或進(jìn)程應(yīng)公平對(duì)待，使

10、每個(gè)進(jìn)程能公平地共享CPU。 均衡性。均衡使用資源，盡量使系統(tǒng)中各種資源同時(shí)得到利用，提高資源的利用率。 統(tǒng)籌兼顧。兼顧響應(yīng)時(shí)間和資源利用率。對(duì)分時(shí)系統(tǒng)，應(yīng)在很短的時(shí)間響應(yīng)用戶需求。 優(yōu)先級(jí)?；谙鄬?duì)優(yōu)先級(jí)，但避免無(wú)限延期。隨著等待時(shí)間的延長(zhǎng)，低優(yōu)先級(jí)進(jìn)程的優(yōu)先級(jí)應(yīng)得到提升。 開(kāi)銷。系統(tǒng)開(kāi)銷不應(yīng)太大。,3.4.2 性能評(píng)價(jià)準(zhǔn)則,CPU利用率： 實(shí)際系統(tǒng)中，CPU利用率一般從40%(輕負(fù)荷系統(tǒng))至90%(重負(fù)荷系統(tǒng))。通常在一定的I/O等待時(shí)間的百分比下，運(yùn)行程序道數(shù)越多，CPU空閑時(shí)間的百分比越低。 吞吐量：?jiǎn)挝粫r(shí)間內(nèi)CPU完成作業(yè)的數(shù)量。,3. 周轉(zhuǎn)時(shí)間,周轉(zhuǎn)時(shí)間：從作業(yè)提交到作業(yè)完成的時(shí)間

11、間隔。用于作業(yè)等待進(jìn)入內(nèi)存， 進(jìn)程在就緒隊(duì)列中等待， 進(jìn)程在CPU上執(zhí)行和完成I/O操作所花費(fèi)時(shí)間的總和。 Ti = tci tsi 其中： tsi表示作業(yè)的提交時(shí)間，亦即作業(yè)到達(dá) 系統(tǒng)的時(shí)間； tci表示作業(yè)的完成時(shí)刻。 平均周轉(zhuǎn)時(shí)間: n個(gè)作業(yè)的平均周轉(zhuǎn)時(shí)間T為:,帶權(quán)周轉(zhuǎn)時(shí)間：為周轉(zhuǎn)時(shí)間T和實(shí)際運(yùn)行時(shí)間R之比。能合理的反映長(zhǎng)短作業(yè)的差別。 W = T / R 平均帶權(quán)周轉(zhuǎn)時(shí)間：,4. 就緒等待時(shí)間：CPU的調(diào)度算法并不真正影響作業(yè)執(zhí)行或I/O操作的時(shí)間數(shù)量。各種CPU調(diào)度算法僅影響作業(yè)(進(jìn)程)在就緒隊(duì)列中所花費(fèi)的時(shí)間數(shù)量。 5. 響應(yīng)時(shí)間：從提交第一個(gè)請(qǐng)求到產(chǎn)生第一個(gè)請(qǐng)求的回應(yīng)所用的時(shí)間

12、。為剛開(kāi)始響應(yīng)的時(shí)間，而不是用于輸出響應(yīng)的時(shí)間。,本章內(nèi)容,3.1 調(diào)度級(jí)別 3.2 作業(yè)調(diào)度 3.3 進(jìn)程調(diào)度 3.4 調(diào)度性能的評(píng)價(jià) 3.5 常用調(diào)度算法 3.6 中斷處理 3.7 Linux系統(tǒng)中的進(jìn)程調(diào)度,3.5 常見(jiàn)調(diào)度算法,3.5.1 先來(lái)先服務(wù)法（FCFS） 3.5.2 時(shí)間片輪轉(zhuǎn)法（RR） 3.5.3 優(yōu)先級(jí)法 3.5.4 其它調(diào)度算法簡(jiǎn)介,3.5.1 先來(lái)先服務(wù)法（FCFS）,實(shí)現(xiàn)思想：每次調(diào)度都選擇隊(duì)頭的作業(yè)或進(jìn)程； 有利于長(zhǎng)作業(yè)（進(jìn)程），不利于短作業(yè)（進(jìn)程）； 有利于CPU繁忙型作業(yè)（需大量CPU時(shí)間進(jìn)行計(jì)算的作業(yè)），不利于I/O繁忙型作業(yè)（需頻繁請(qǐng)求I/O的作業(yè)）； 算

13、法簡(jiǎn)單，實(shí)現(xiàn)容易，但效率低。,例如：設(shè)有三個(gè)作業(yè)，編號(hào)為1，2，3。各作業(yè)分別對(duì)應(yīng)一個(gè)進(jìn)程。各作業(yè)依次到達(dá)，相差一個(gè)時(shí)間單位，3個(gè)進(jìn)程分別需要運(yùn)行24、3和3個(gè)時(shí)間單位。 圖示三個(gè)作業(yè)的執(zhí)行順序； 算出各作業(yè)的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間。,復(fù)習(xí)：,周轉(zhuǎn)時(shí)間：從作業(yè)提交到作業(yè)完成的時(shí)間間隔。 Ti = tci tsi 平均周轉(zhuǎn)時(shí)間: n個(gè)作業(yè)的平均周轉(zhuǎn)時(shí)間T為: 帶權(quán)周轉(zhuǎn)時(shí)間：為周轉(zhuǎn)時(shí)間T和運(yùn)行時(shí)間R之比。 W = T / R 平均帶權(quán)周轉(zhuǎn)時(shí)間：,圖示三個(gè)作業(yè)的執(zhí)行順序： 算出各作業(yè)的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間：,3.5.2 時(shí)間片輪轉(zhuǎn)法（RR）,主要用于分時(shí)系統(tǒng)中的進(jìn)程調(diào)度。 實(shí)現(xiàn)思想： 系統(tǒng)把所有就

14、緒進(jìn)程按先入先出的原則排成一個(gè)隊(duì)列。新來(lái)的進(jìn)程加到就緒隊(duì)列末尾。每當(dāng)執(zhí)行進(jìn)程調(diào)度時(shí)，進(jìn)程調(diào)度程序總是選出就緒隊(duì)列的隊(duì)首進(jìn)程，讓它在CPU上運(yùn)行一個(gè)時(shí)間片的時(shí)間。當(dāng)進(jìn)程用完分給它的時(shí)間片后，系統(tǒng)計(jì)時(shí)器發(fā)出時(shí)鐘中斷，調(diào)度程序便停止該進(jìn)程的運(yùn)行，并把它放入就緒隊(duì)列的末尾；然后，把CPU分給就緒隊(duì)列的隊(duì)首進(jìn)程，同樣也讓它運(yùn)行一個(gè)時(shí)間片，如此往復(fù)，如同輪流坐莊。,例如：設(shè)4個(gè)進(jìn)程A、B、C和D依次進(jìn)入就緒隊(duì)列（同時(shí)到達(dá)），四個(gè)進(jìn)程分別需要運(yùn)行12、5、3和6個(gè)時(shí)間單位。 圖示RR法時(shí)間片q=1和q=4時(shí)進(jìn)程運(yùn)行情況； 算出各進(jìn)程的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間。,時(shí)間片輪轉(zhuǎn)法(q=1),26,時(shí)間片輪轉(zhuǎn)法(q=

15、4),26,時(shí)間片輪轉(zhuǎn)法的性能,時(shí)間片的大小對(duì)輪轉(zhuǎn)法的性能影響很大。 時(shí)間片的長(zhǎng)短由下列因素決定： 系統(tǒng)響應(yīng)時(shí)間：在進(jìn)程數(shù)目一定時(shí)，時(shí)間片的長(zhǎng)短直接正比于系統(tǒng)對(duì)響應(yīng)時(shí)間的要求； 就緒隊(duì)列進(jìn)程的數(shù)目：當(dāng)系統(tǒng)要求響應(yīng)時(shí)間一定時(shí)，時(shí)間片的大小反比于就緒隊(duì)列中的進(jìn)程數(shù)； 進(jìn)程的轉(zhuǎn)換時(shí)間：若進(jìn)程的轉(zhuǎn)換時(shí)間為t，時(shí)間片為q，為保證系統(tǒng)開(kāi)銷不大于某個(gè)標(biāo)準(zhǔn)，應(yīng)使比值t/q不大于某一數(shù)值，如1/10； CPU運(yùn)行指令速度：CPU運(yùn)行速度快，時(shí)間片可短些。反之，則應(yīng)取長(zhǎng)些。,3.5.3 優(yōu)先級(jí)法,實(shí)現(xiàn)思想：從就緒隊(duì)列中選出優(yōu)先級(jí)最高的進(jìn)程，把CPU分給它使用。 兩種處理方式： 非搶占式優(yōu)先級(jí)法：當(dāng)前占用CPU的進(jìn)

16、程一直運(yùn)行下去，直到完成任務(wù)或因等待某事件發(fā)生而主動(dòng)讓出CPU時(shí)，系統(tǒng)才讓另一個(gè)優(yōu)先級(jí)高的進(jìn)程占用CPU。 搶占式優(yōu)先級(jí)法： 當(dāng)前進(jìn)程在運(yùn)行過(guò)程中，一旦有另一個(gè)優(yōu)先級(jí)更高的進(jìn)程出現(xiàn)在就緒隊(duì)列中，進(jìn)程調(diào)度程序就停止當(dāng)前進(jìn)程的運(yùn)行，強(qiáng)行將CPU分給那個(gè)進(jìn)程。,進(jìn)程優(yōu)先級(jí)可由系統(tǒng)內(nèi)部定義或外部指定: 內(nèi)部?jī)?yōu)先級(jí)：利用某些可度量的量來(lái)定義一個(gè)進(jìn)程的優(yōu)先級(jí), 如，進(jìn)程類型, 進(jìn)程對(duì)資源的需求(時(shí)間限度,需要內(nèi)存大小,打開(kāi)文件的數(shù)目,I/O平均工作時(shí)間與CPU平均工作時(shí)間的比值等), 用它們來(lái)計(jì)算優(yōu)先級(jí)。 外部?jī)?yōu)先級(jí)：按操作系統(tǒng)以外的標(biāo)準(zhǔn)設(shè)置, 如，外單位人員租用計(jì)算中心大型計(jì)算機(jī)所付款的類型和總數(shù), 使

17、用計(jì)算機(jī)的部門(mén)以及其它的外部因素。,靜態(tài)優(yōu)先級(jí)和動(dòng)態(tài)優(yōu)先級(jí): 優(yōu)先數(shù)： 標(biāo)識(shí)優(yōu)先級(jí)的整數(shù)， 在Unix/Linux系統(tǒng)中，優(yōu)先數(shù)越小， 優(yōu)先級(jí)越高。 靜態(tài)優(yōu)先級(jí)：在創(chuàng)建進(jìn)程時(shí)確定，且在進(jìn)程的整個(gè)運(yùn)行期間保持不變。優(yōu)點(diǎn)是易于實(shí)現(xiàn)，系統(tǒng)開(kāi)銷小；缺點(diǎn)是會(huì)出現(xiàn)“饑餓”現(xiàn)象。 動(dòng)態(tài)優(yōu)先級(jí)：隨著進(jìn)程推進(jìn)優(yōu)先級(jí)不斷改變，如，使得系統(tǒng)中等待CPU很長(zhǎng)時(shí)間的進(jìn)程逐漸提升其優(yōu)先級(jí)，避免發(fā)生“饑餓”現(xiàn)象。,例如：假定在單CPU條件下有下列要執(zhí)行的作業(yè)： 各作業(yè)依次到達(dá)，相差一個(gè)時(shí)間單位。 用執(zhí)行時(shí)間圖描述非搶占優(yōu)先級(jí)調(diào)度算法執(zhí)行這些作業(yè)的情況； 算出各作業(yè)的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間。,用執(zhí)行時(shí)間圖描述非搶占優(yōu)先級(jí)調(diào)度

18、算法執(zhí)行這些作業(yè)的情況,算出各作業(yè)的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間,3.5.4 其它調(diào)度算法簡(jiǎn)介,短作業(yè)優(yōu)先法(SJF)：主要用于作業(yè)調(diào)度。 基本思想: 從后備作業(yè)隊(duì)列中選取運(yùn)行時(shí)間最短的作業(yè)放入內(nèi)存。采用非搶占策略，系統(tǒng)選中某個(gè)短作業(yè)后投入運(yùn)行，直到該作業(yè)完成并退出系統(tǒng)。 特點(diǎn): 能有效地降低作業(yè)的平均等待時(shí)間和提高系統(tǒng)吞吐量，但對(duì)長(zhǎng)作業(yè)很不利，且不能保證緊迫性作業(yè)會(huì)被及時(shí)處理。,最短剩余時(shí)間優(yōu)先（SRTF） 采用搶占式策略。當(dāng)新進(jìn)程加入就緒隊(duì)列時(shí)，若其需要的運(yùn)行時(shí)間比當(dāng)前運(yùn)行進(jìn)程所需的剩余時(shí)間還短，則強(qiáng)行奪取運(yùn)行進(jìn)程的CPU控制權(quán)，新進(jìn)程調(diào)度運(yùn)行。 特點(diǎn)：總能保證新的短作業(yè)一進(jìn)入系統(tǒng)就得到執(zhí)行，但

19、該算法需要增加系統(tǒng)開(kāi)銷，如保存進(jìn)程斷點(diǎn)現(xiàn)場(chǎng)，統(tǒng)計(jì)進(jìn)程剩余時(shí)間等。,多級(jí)隊(duì)列法 根據(jù)作業(yè)的某些特性，如占用內(nèi)存大小和作業(yè)類型等，永久性的將各個(gè)作業(yè)分別鏈入不同的隊(duì)列，每個(gè)隊(duì)列有自己的調(diào)度算法。 如，把前臺(tái)作業(yè)(交互型作業(yè))隊(duì)列和后臺(tái)作業(yè)各設(shè)一個(gè)隊(duì)列， 前臺(tái)作業(yè)可用輪轉(zhuǎn)法調(diào)度，后臺(tái)作業(yè)可用FCFS調(diào)度。 此外，各隊(duì)列間也要進(jìn)行調(diào)度，通常采用固定優(yōu)先級(jí)的搶占式調(diào)度。,多級(jí)反饋隊(duì)列,系統(tǒng)中設(shè)置多個(gè)就緒隊(duì)列, 每個(gè)隊(duì)列對(duì)應(yīng)一個(gè)優(yōu)先級(jí)，第一個(gè)隊(duì)列的優(yōu)先級(jí)最高，其余逐級(jí)降低； 各就緒隊(duì)列中進(jìn)程的運(yùn)行時(shí)間片不同，高優(yōu)先級(jí)隊(duì)列時(shí)間片小，低優(yōu)先級(jí)隊(duì)列時(shí)間片大； 新進(jìn)程進(jìn)入系統(tǒng)后，先放入第一隊(duì)列的末尾，各隊(duì)列按FC

20、FS方式排隊(duì)； 若某個(gè)進(jìn)程在相應(yīng)時(shí)間片內(nèi)未完成工作，則將其轉(zhuǎn)到下一級(jí)隊(duì)列的末尾； 系統(tǒng)先執(zhí)行第一隊(duì)列中的進(jìn)程, 第一隊(duì)列為空后，才運(yùn)行第二隊(duì)列，以此類推，最后一個(gè)隊(duì)列采用時(shí)間片輪轉(zhuǎn)法進(jìn)行調(diào)度。,多級(jí)反饋隊(duì)列,特點(diǎn): 算法復(fù)雜, 但性能較好, 如 Unix, Windows NT, OS/2系統(tǒng)等采用。,本章內(nèi)容,3.1 調(diào)度級(jí)別 3.2 作業(yè)調(diào)度 3.3 進(jìn)程調(diào)度 3.4 調(diào)度性能的評(píng)價(jià) 3.5 常用調(diào)度算法 3.6 中斷處理 3.7 Linux系統(tǒng)中的進(jìn)程調(diào)度,3.6 中斷處理,3.6.1 中斷概述 3.6.2 中斷處理過(guò)程 3.6.3 中斷優(yōu)先級(jí)和多重中斷 3.6.4 系統(tǒng)調(diào)用處理 3.6

21、.5 shell命令的一般執(zhí)行過(guò)程,3.6.1 中斷概述,操作系統(tǒng)實(shí)施并發(fā)的基礎(chǔ)是由硬件和軟件結(jié)合而成的中斷機(jī)制。 中斷的典型實(shí)例是I/O中斷，由系統(tǒng)調(diào)用引發(fā)的事件稱作陷入（Trap）。 中斷的概念 中斷是指CPU對(duì)系統(tǒng)發(fā)生的某個(gè)事件做出的一種反應(yīng)，它使CPU暫停正在執(zhí)行的程序，保留現(xiàn)場(chǎng)后自動(dòng)執(zhí)行相應(yīng)的處理程序，處理該事件后，如被中斷進(jìn)程的優(yōu)先級(jí)最高，則返回?cái)帱c(diǎn)繼續(xù)執(zhí)行被“打斷”的程序。,中斷示意圖,幾個(gè)概念,中斷源：引起中斷的事件或發(fā)出中斷請(qǐng)求的來(lái)源。 中斷請(qǐng)求：中斷源向CPU提出的處理請(qǐng)求。 斷點(diǎn)：發(fā)生中斷時(shí)，被打斷程序的暫停點(diǎn)。 中斷最初作為通道（或設(shè)備）與CPU之間進(jìn)行通信的工具。后來(lái)

22、發(fā)展為： 系統(tǒng)其他部件也可以造成中斷。如，程序執(zhí)行時(shí)運(yùn)算的溢出、取數(shù)時(shí)奇偶錯(cuò)、電源故障、時(shí)鐘計(jì)數(shù)等。 訪管指令（或系統(tǒng)調(diào)用）中斷。用戶程序以此得到系統(tǒng)的內(nèi)部服務(wù)。,2. 中斷的類型 按功能劃分 機(jī)器故障中斷：產(chǎn)生于硬件故障 I/O中斷：產(chǎn)生于通道和各種外部設(shè)備 外部中斷：產(chǎn)生于計(jì)算機(jī)系統(tǒng)外部裝置 程序性中斷：產(chǎn)生于指令或數(shù)據(jù)的錯(cuò)誤使用 訪管中斷：產(chǎn)生于“訪問(wèn)管理程序”的執(zhí)行,按產(chǎn)生中斷的方式劃分 強(qiáng)迫中斷：預(yù)料之外的事件發(fā)生，如機(jī)器故障、I/O中斷、外部中斷、程序性中斷。 自愿中斷：程序中有意使用的訪管指令或系統(tǒng)調(diào)用。 按中斷事件來(lái)源劃分 中斷：由CPU以外的事件引起的。如I/O中斷、時(shí)鐘中斷

23、、控制臺(tái)中斷等。 異常：來(lái)自CPU內(nèi)部的事件或程序執(zhí)行中的事件。如CPU故障、程序故障、訪管指令等。,3.中斷系統(tǒng)的作用,提高主機(jī)的利用率，使高速CPU與低速外部設(shè)備可以并行工作； 及時(shí)進(jìn)行事故處理； 實(shí)現(xiàn)分時(shí)操作； 實(shí)現(xiàn)實(shí)時(shí)操作； 方便程序調(diào)試。,3.6.2 中斷處理過(guò)程,硬件級(jí)的中斷結(jié)構(gòu)與過(guò)程,1.中斷的硬件結(jié)構(gòu),2. 中斷響應(yīng) 由硬件對(duì)中斷請(qǐng)求做出反應(yīng)的過(guò)程，稱為中斷響應(yīng)。 中斷響應(yīng)順序執(zhí)行以下動(dòng)作： 中止當(dāng)前程序的執(zhí)行； 保存原程序的斷點(diǎn)信息（主要是程序計(jì)數(shù)器PC和程序狀態(tài)寄存器PS的內(nèi)容）； 轉(zhuǎn)到相應(yīng)的處理程序。 通常CPU在執(zhí)行完一條指令后，立即檢查有無(wú)中斷請(qǐng)求。如有，而且“中斷允

24、許”觸發(fā)器為1，則立即做出響應(yīng)。,3. 中斷處理 中斷響應(yīng)后，就由軟件（中斷處理程序）進(jìn)行相應(yīng)處理。 中斷處理過(guò)程分為4個(gè)階段： （1）保存被中斷程序的現(xiàn)場(chǎng)； （2）分析中斷原因； （3）轉(zhuǎn)入相應(yīng)處理程序進(jìn)程處理 （4）恢復(fù)被中斷程序現(xiàn)場(chǎng)（即中斷返回）,中斷處理的一般過(guò)程,3.6.3 中斷優(yōu)先級(jí)和多重中斷,中斷優(yōu)先級(jí) 當(dāng)系統(tǒng)中同時(shí)發(fā)生多個(gè)中斷時(shí)，硬/軟件按優(yōu)先次序處理中斷。采用中斷屏蔽可以改變中斷處理順序。 與某種中斷相關(guān)的優(yōu)先權(quán)稱為它的中斷優(yōu)先級(jí)。優(yōu)先級(jí)高的中斷優(yōu)先響應(yīng)，通過(guò)線路排隊(duì)辦法實(shí)現(xiàn)。 另外，級(jí)別高的中斷一般有打破級(jí)別低的中斷處理程序的權(quán)利。,2. 中斷屏蔽 中斷屏蔽：在提出中斷請(qǐng)求

25、后，CPU不予響應(yīng)的狀態(tài)。 中斷禁止：在可引起中斷的事件發(fā)生時(shí)系統(tǒng)不接收該中斷信號(hào)，因而就不可能提出中斷請(qǐng)求而導(dǎo)致中斷。即不讓某些事件產(chǎn)生中斷。 兩者的區(qū)別： 中斷屏蔽表明硬件接受了中斷請(qǐng)求，但暫時(shí)不能響應(yīng)，要等待中斷開(kāi)放即可得到響應(yīng)； 中斷禁止是硬件根本不允許提出中斷請(qǐng)求。,中斷屏蔽的作用： 延遲或禁止對(duì)某些中斷的響應(yīng)； 協(xié)調(diào)中斷響應(yīng)與中斷處理的關(guān)系 ； 防止同類中斷的相互干擾 。 中斷屏蔽的方式： 屏蔽方式隨機(jī)器而異，可以用于整級(jí)屏蔽，也可用于單個(gè)屏蔽。,3. 多重中斷 處理多個(gè)中斷的方法有順序處理方式和嵌套處理方式。 順序處理方式 當(dāng)一個(gè)中斷正被處理期間，屏蔽其他的中斷；在該中斷處理完后

26、，開(kāi)放中斷，由處理器查看有無(wú)尚未處理的中斷。如果有，則依次處理。 缺點(diǎn)：沒(méi)有考慮中斷的相對(duì)優(yōu)先級(jí)或時(shí)間的緊迫程度 。,嵌套處理方式 這種方式對(duì)每類中斷賦予不同的優(yōu)先級(jí)，允許高優(yōu)先級(jí)中斷打斷低優(yōu)先級(jí)中斷的處理程序 。 缺點(diǎn)：給程序設(shè)計(jì)帶來(lái)困難。,3.6.4 系統(tǒng)調(diào)用處理,1陷入事件的處理方式 在UNIX/Linux系統(tǒng)中，對(duì)異常的處理稱作陷入。 引起陷入的事件可以分為兩組：一組是自愿進(jìn)入陷入，稱作自陷，如使用系統(tǒng)調(diào)用、斷點(diǎn)跟蹤；另一組是由于程序運(yùn)行過(guò)程中出現(xiàn)軟、硬件故障或錯(cuò)誤，如轉(zhuǎn)換無(wú)效、訪問(wèn)違章、非法指令等，也稱作捕俘。 陷入處理的基本過(guò)程與中斷處理基本相同。,陷入處理子程序的處理方式： 請(qǐng)求

27、系統(tǒng)管理人員干預(yù)：核心態(tài)下的陷入 ； 按用戶規(guī)定方式進(jìn)行處理 ：用戶態(tài)下的陷入； 用戶棧自動(dòng)擴(kuò)充：用戶棧滿自動(dòng)擴(kuò)充； 系統(tǒng)調(diào)用處理。,2. 系統(tǒng)調(diào)用的處理方式 UNIX/Linux系統(tǒng)中，系統(tǒng)調(diào)用以C語(yǔ)言函數(shù)形式出現(xiàn)在程序中。 系統(tǒng)調(diào)用可以做到把進(jìn)程的運(yùn)行模式從用戶態(tài)變?yōu)楹诵膽B(tài)，即從用戶空間轉(zhuǎn)入系統(tǒng)空間，而一般的函數(shù)調(diào)用序列無(wú)法做到。 系統(tǒng)調(diào)用是CPU主動(dòng)、同步地進(jìn)入系統(tǒng)空間的手段。因?yàn)橄到y(tǒng)調(diào)用是由用戶預(yù)先安排在程序的確切位置上的。,trap指令的一般格式是： trap xx 參數(shù)1 參數(shù)2 其中，xx表示系統(tǒng)調(diào)用號(hào)。 當(dāng)CPU執(zhí)行到trap指令時(shí)，CPU的狀態(tài)就從用戶態(tài)變?yōu)楹诵膽B(tài)。 陷入總控

28、程序：處理所有的陷入事件的總服務(wù)程序，屬于內(nèi)核。,執(zhí)行過(guò)程,首先，陷入總控程序?qū)⒂嘘P(guān)參數(shù)壓入系統(tǒng)棧中，以備返回用戶空間、恢復(fù)現(xiàn)場(chǎng)時(shí)使用。 然后，調(diào)用陷入處理程序trap。trap程序根據(jù)陷入事件的不同類型做不同的處理。對(duì)于非法指令、跟蹤陷入、指令故障、算術(shù)陷入、訪問(wèn)違章、轉(zhuǎn)換無(wú)效等事件，轉(zhuǎn)入信號(hào)機(jī)構(gòu)進(jìn)行處理（見(jiàn)下一節(jié)）；對(duì)于系統(tǒng)調(diào)用事件，調(diào)用system_call（系統(tǒng)調(diào)用處理函數(shù)）進(jìn)行處理。 系統(tǒng)調(diào)用處理函數(shù)根據(jù)trap指令后面的系統(tǒng)調(diào)用號(hào)去查系統(tǒng)調(diào)用入口表，然后轉(zhuǎn)入各個(gè)具體的系統(tǒng)調(diào)用處理程序。,3. 系統(tǒng)調(diào)用實(shí)現(xiàn)過(guò)程示例,問(wèn)題描述： 設(shè)用戶進(jìn)程A在運(yùn)行中要向已打開(kāi)的文件（用fd表示）寫(xiě)一批

29、數(shù)據(jù)，為此在用戶C源程序中可用如下系統(tǒng)調(diào)用語(yǔ)句： rw=write (fd,buf,count)； 編譯后形成的匯編指令形式如下： trap 4 參數(shù)1 參數(shù)2 參數(shù)3 k1： 其中，參數(shù)1，2，3分別對(duì)應(yīng)該文件的文件描述字fd，用戶信息所在內(nèi)存始址buf，傳送字節(jié)數(shù)count。,系統(tǒng)調(diào)用執(zhí)行過(guò)程,3.6.5 shell命令的一般執(zhí)行過(guò)程,Linux系統(tǒng)提供給用戶的最重要的系統(tǒng)程序是shell命令語(yǔ)言解釋程序。它不屬于內(nèi)核部分，而是在核心之外以用戶態(tài)方式運(yùn)行。 shell基本功能：解釋并執(zhí)行用戶輸入的各種命令，實(shí)現(xiàn)用戶與Linux核心的接口。系統(tǒng)初啟后，核心為每個(gè)終端用戶建立一個(gè)進(jìn)程去執(zhí)行sh

30、ell解釋程序。,shell命令執(zhí)行過(guò)程：,讀取用戶由鍵盤(pán)輸入的命令行 ； 分析命令，以命令名作為文件名，其他參數(shù)改造為系統(tǒng)調(diào)用execve( )內(nèi)部處理所要求的形式； 終端進(jìn)程調(diào)用fork( )建立一個(gè)子進(jìn)程 ； 終端進(jìn)程本身用系統(tǒng)調(diào)用wait4( )來(lái)等待子進(jìn)程完成（如果是后臺(tái)命令，則不等待）。當(dāng)子進(jìn)程運(yùn)行時(shí)調(diào)用execve( )，子進(jìn)程根據(jù)文件名（即命令名）到目錄中查找有關(guān)文件（這是命令解釋程序構(gòu)成的文件），調(diào)入內(nèi)存，執(zhí)行這個(gè)程序（即執(zhí)行這條命令）；, 如果命令末尾有&號(hào)（后臺(tái)命令符號(hào)），則終端進(jìn)程不用執(zhí)行系統(tǒng)調(diào)用wait4( )，而是立即發(fā)提示符，讓用戶輸入下一個(gè)命令，轉(zhuǎn)步驟（1）。

31、如果命令末尾沒(méi)有&號(hào)，則終端進(jìn)程要一直等待，當(dāng)子進(jìn)程（即運(yùn)行命令的進(jìn)程）完成工作后要終止，向父進(jìn)程（終端進(jìn)程）報(bào)告，此時(shí)終端進(jìn)程醒來(lái)，在做必要的判別等工作后，終端進(jìn)程發(fā)提示符，讓用戶輸入新的命令，重復(fù)上述處理過(guò)程。,shell命令基本執(zhí)行過(guò)程,本章內(nèi)容,3.1 調(diào)度級(jí)別 3.2 作業(yè)調(diào)度 3.3 進(jìn)程調(diào)度 3.4 調(diào)度性能的評(píng)價(jià) 3.5 常用調(diào)度算法 3.6 中斷處理 3.7 Linux系統(tǒng)中的進(jìn)程調(diào)度,3.7 Linux系統(tǒng)中的進(jìn)程調(diào)度,3.7.1 Linux進(jìn)程調(diào)度 3.7.2 Linux常用調(diào)度命令,3.7.1 Linux進(jìn)程調(diào)度,1調(diào)度方式 Linux系統(tǒng)的調(diào)度方式基本上采用“搶占式優(yōu)先級(jí)”方式； Linux系統(tǒng)中的調(diào)度基本上繼承了UNIX系統(tǒng)的以優(yōu)先級(jí)為基礎(chǔ)的調(diào)度。即核心為系統(tǒng)中每個(gè)進(jìn)程計(jì)算出一個(gè)優(yōu)先級(jí)，該優(yōu)先級(jí)反映了一個(gè)進(jìn)程獲得CPU使用權(quán)的資格，即高優(yōu)先級(jí)的進(jìn)程優(yōu)先得到運(yùn)行。,2調(diào)度策略 Linux系統(tǒng)針對(duì)不同類別的進(jìn)程