操作系統(tǒng)教程—Linux實(shí)例分析孟慶昌第3章處理機(jī)調(diào)度ppt課件

1、第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 第第3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 3.1 調(diào)度級(jí)別調(diào)度級(jí)別 3.2 作業(yè)調(diào)度作業(yè)調(diào)度3.3 進(jìn)程調(diào)度進(jìn)程調(diào)度 3.4 性能評(píng)價(jià)標(biāo)準(zhǔn)性能評(píng)價(jià)標(biāo)準(zhǔn) 3.5 常用調(diào)度算法常用調(diào)度算法 3.6 Linux系統(tǒng)中的進(jìn)程調(diào)度系統(tǒng)中的進(jìn)程調(diào)度 習(xí)題習(xí)題 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 3.1 調(diào)調(diào) 度度 級(jí)級(jí) 別別 一般來說， 作業(yè)從進(jìn)入系統(tǒng)到最后完成， 可能要經(jīng)歷三級(jí)調(diào)度： 高級(jí)調(diào)度、 中級(jí)調(diào)度和低級(jí)調(diào)度。 (1) 高級(jí)調(diào)度： 又稱作業(yè)調(diào)度。 (2) 中級(jí)調(diào)度： 為了使內(nèi)存中同時(shí)存放的進(jìn)程數(shù)目不至于太多， 有時(shí)就需要把某些進(jìn)程從內(nèi)存中移到外存上， 以減少多道程序

2、的數(shù)目， 為此設(shè)立了中級(jí)調(diào)度。 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 (3) 低級(jí)調(diào)度： 又稱進(jìn)程調(diào)度。 其主要功能是根據(jù)一定的算法將CPU分派給就緒隊(duì)列中的一個(gè)進(jìn)程。 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 3.2 作作 業(yè)業(yè) 調(diào)調(diào) 度度 3.2.1 作業(yè)狀態(tài) 如前所述， 作業(yè)從提交給系統(tǒng)， 直到完成任務(wù)后退出系統(tǒng)前， 在整個(gè)活動(dòng)過程中它會(huì)處于不同的狀態(tài)。 通常， 作業(yè)狀態(tài)分為四種： 提交、 后備、 執(zhí)行和完成， 如圖3-1所示。第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 作業(yè) 1作業(yè) 2作業(yè) 3OSCPU后備作業(yè)磁 盤(輸入井)完成作業(yè)磁 盤(輸出井)打印機(jī)讀卡機(jī)內(nèi)存提交后備執(zhí)行完成圖3-1 作業(yè)

3、的基本狀態(tài)第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 （1） 提交狀態(tài)即用戶向系統(tǒng)提交一個(gè)作業(yè)時(shí)， 該作業(yè)所處的狀態(tài)。 （2） 后備狀態(tài)即用戶作業(yè)經(jīng)輸入設(shè)備如讀卡機(jī)送入輸入井磁盤中存放， 等待進(jìn)入內(nèi)存時(shí)所處的狀況。 （3） 執(zhí)行狀態(tài)即作業(yè)分配到所需的資源， 被調(diào)入內(nèi)存， 并且在處理機(jī)CPU上執(zhí)行相應(yīng)的程序時(shí)所處的狀況。 （4） 完成狀態(tài)即作業(yè)完成了計(jì)算任務(wù)， 結(jié)果由打印機(jī)輸出， 最后由系統(tǒng)回收分配給它的全部資源， 準(zhǔn)備退出系統(tǒng)時(shí)的作業(yè)狀況。第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 3.2.2 作業(yè)調(diào)度 1. 作業(yè)控制塊JCB） 在多道批處理系統(tǒng)中通常有上百個(gè)作業(yè)被收容在輸入井磁盤中。 為了管理和調(diào)度作業(yè)

4、， 系統(tǒng)為每個(gè)作業(yè)設(shè)置了一個(gè)作業(yè)控制塊JCB）， 它記錄該作業(yè)的有關(guān)信息。 不同系統(tǒng)的JCB的組成內(nèi)容有所區(qū)別。 JCB的主要內(nèi)容如圖3-2所示。第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 圖3-2 作業(yè)控制塊 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 2. 作業(yè)調(diào)度的功能 如上所述， 作業(yè)調(diào)度的主要任務(wù)是完成作業(yè)從后備狀態(tài)到執(zhí)行狀態(tài)和從執(zhí)行狀態(tài)到完成狀態(tài)的轉(zhuǎn)換。 具體來說， 通常作業(yè)調(diào)度程序要完成以下工作(這就是作業(yè)調(diào)度的功能)。 (1) 記錄系統(tǒng)中各個(gè)作業(yè)的情況。 (2) 按照某種調(diào)度算法從后備作業(yè)隊(duì)列中挑選作業(yè)。 (3) 為選中的作業(yè)分配內(nèi)存和外設(shè)等資源。 (4) 為選中的作業(yè)建立相應(yīng)的進(jìn)程。 第

5、第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 (5) 作業(yè)結(jié)束后進(jìn)行善后處理工作， 如輸出必要的信息， 收回該作業(yè)所占用的全部資源， 撤消與該作業(yè)相關(guān)的全部進(jìn)程和該作業(yè)的JCB。 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 3.3 進(jìn)進(jìn) 程程 調(diào)調(diào) 度度 3.3.1 進(jìn)程調(diào)度的功能和時(shí)機(jī) 進(jìn)程只有在得到CPU之后才能真正活動(dòng)起來。 一個(gè)就緒進(jìn)程怎樣獲得CPU的控制權(quán)呢? 這是由進(jìn)程調(diào)度實(shí)現(xiàn)的， 進(jìn)程調(diào)度也被稱為低級(jí)調(diào)度。 進(jìn)程調(diào)度程序也往往被稱為低級(jí)調(diào)度程序， 它完成進(jìn)程狀態(tài)從就緒態(tài)到運(yùn)行態(tài)的轉(zhuǎn)化。實(shí)際上， 進(jìn)程調(diào)度程序主要是完成一臺(tái)物理的CPU轉(zhuǎn)變成多臺(tái)虛擬或邏輯的CPU的工作。第第3 3章章 處理機(jī)調(diào)度處

6、理機(jī)調(diào)度 1. 功能 進(jìn)程調(diào)度的主要功能是： (1) 保存現(xiàn)場(chǎng)。 （2） 挑選進(jìn)程。 （3） 恢復(fù)現(xiàn)場(chǎng)。 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 2. 時(shí)機(jī) 在什么情況下執(zhí)行進(jìn)程調(diào)度呢? 一般是在以下事件發(fā)生后作進(jìn)程調(diào)度： （1） 完成任務(wù)。 （2） 等待資源。 （3） 運(yùn)行到時(shí)。 （4） 發(fā)現(xiàn)標(biāo)志。 （5） 創(chuàng)建新進(jìn)程。 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 圖3-3 進(jìn)程調(diào)度流程 進(jìn)程A進(jìn)程B進(jìn)程K進(jìn)程L就緒隊(duì)列CPU進(jìn)程調(diào)度程序第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 3.3.2 兩級(jí)調(diào)度模型 作業(yè)調(diào)度和進(jìn)程調(diào)度是CPU主要的兩級(jí)調(diào)度， 二者的關(guān)系可用圖3-4表示。第第3 3章章 處理機(jī)調(diào)度處

7、理機(jī)調(diào)度 圖3-4 兩級(jí)調(diào)度簡(jiǎn)化隊(duì)列圖 I/OI/O等待隊(duì)列就緒隊(duì)列作業(yè)調(diào)度后備作業(yè)隊(duì)列I/O完成CPU請(qǐng)求I/O進(jìn)程調(diào)度結(jié)束第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 3.3.3 三級(jí)調(diào)度模型 當(dāng)一個(gè)系統(tǒng)中三級(jí)調(diào)度同時(shí)存在時(shí)， 其相互間的關(guān)系如圖3-5所示。 簡(jiǎn)單來說， 作業(yè)調(diào)度從后備作業(yè)中選擇一批合適的作業(yè)放入內(nèi)存， 并創(chuàng)建相應(yīng)的進(jìn)程； 進(jìn)程調(diào)度從就緒隊(duì)列中選擇一個(gè)合適進(jìn)程， 令其投入運(yùn)行； 中級(jí)調(diào)度將在內(nèi)存中駐留時(shí)間較長的進(jìn)程換到磁盤上： 從就緒隊(duì)列轉(zhuǎn)到就緒/掛起隊(duì)列， 從阻塞隊(duì)列轉(zhuǎn)到阻塞/掛起隊(duì)列。 當(dāng)內(nèi)存中有足夠的可用空間時(shí)， 中級(jí)調(diào)度就從就緒/掛起隊(duì)列中選擇一些合適的進(jìn)程放入內(nèi)存， 使之

8、進(jìn)入就緒隊(duì)列。第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 圖3-5 三級(jí)調(diào)度簡(jiǎn)化隊(duì)列 CPU就緒隊(duì)列中級(jí)調(diào)度就緒, 掛起隊(duì)列阻塞, 掛起隊(duì)列阻塞隊(duì)列作業(yè)調(diào)度后備作業(yè)批作業(yè)交互式用戶事件發(fā)生等待事件中級(jí)調(diào)度結(jié)束到時(shí)進(jìn)程調(diào)度第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 3.4 性能評(píng)價(jià)標(biāo)準(zhǔn)性能評(píng)價(jià)標(biāo)準(zhǔn) (1) 所用算法應(yīng)保證實(shí)現(xiàn)系統(tǒng)的設(shè)計(jì)目標(biāo)。 (2) 對(duì)所有作業(yè)或進(jìn)程應(yīng)公平對(duì)待。 (3) 均衡使用資源， 盡量使系統(tǒng)中各種資源都同時(shí)得到利用。 (4) 兼顧響應(yīng)時(shí)間和資源利用率。 (5) 基于相對(duì)優(yōu)先級(jí)， 但避免無限延期。 (6) 系統(tǒng)開銷不應(yīng)太大。 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 3.4.2 性能評(píng)價(jià)標(biāo)準(zhǔn)

9、 1. CPU利用率 CPU的利用率可從0100%。 2. 吞吐量 吞吐量表示單位時(shí)間內(nèi)CPU完成作業(yè)或進(jìn)程的數(shù)量。 3. 周轉(zhuǎn)時(shí)間 從一個(gè)特定作業(yè)的觀點(diǎn)出發(fā)， 最重要的標(biāo)準(zhǔn)就是完成這個(gè)作業(yè)要花費(fèi)多長時(shí)間。 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 作業(yè)i的周轉(zhuǎn)時(shí)間Ti為 siciittT 其中， tsi表示作業(yè)i的提交時(shí)刻， tci表示作業(yè)i的完成時(shí)刻。 系統(tǒng)中n個(gè)作業(yè)的平均周轉(zhuǎn)時(shí)間T為nTTnii11第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 作業(yè)周轉(zhuǎn)時(shí)間沒有區(qū)分作業(yè)實(shí)際運(yùn)行時(shí)間長短的特性， 因?yàn)殚L作業(yè)不可能具有比運(yùn)行時(shí)間還短的周轉(zhuǎn)時(shí)間。 為了合理反映長短作業(yè)的差別， 定義了另一個(gè)衡量標(biāo)準(zhǔn)帶權(quán)周轉(zhuǎn)時(shí)

10、間W， 即W=T/R， 其中T為周轉(zhuǎn)時(shí)間， R為實(shí)際運(yùn)行時(shí)間。 平均帶權(quán)周轉(zhuǎn)時(shí)間W為nRTnWWniiinii1)(1)(11第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 4. 就緒等待時(shí)間 CPU調(diào)度算法并不真正影響作業(yè)執(zhí)行或IO操作的時(shí)間數(shù)量。 各種CPU調(diào)度算法僅影響作業(yè)(進(jìn)程)在就緒隊(duì)列中所花費(fèi)的時(shí)間數(shù)量。 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 5. 響應(yīng)時(shí)間 在交互式系統(tǒng)中， 周轉(zhuǎn)時(shí)間不可能是最好的評(píng)價(jià)標(biāo)準(zhǔn)。 一個(gè)進(jìn)程往往可以很早地就產(chǎn)生某些輸出， 當(dāng)前面的結(jié)果在終端上輸出時(shí)它可以繼續(xù)計(jì)算新的結(jié)果。 于是， 有另一個(gè)評(píng)價(jià)標(biāo)準(zhǔn)， 就是從提交第一個(gè)請(qǐng)求到產(chǎn)生第一個(gè)響應(yīng)所用的時(shí)間， 這就叫做響應(yīng)時(shí)

11、間。 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 3.5 常用調(diào)度算法常用調(diào)度算法 3.5.1 先來先服務(wù)FCFS） 最簡(jiǎn)單的CPU調(diào)度算法就是先來先服務(wù)First Come First Served方法， 即按作業(yè)進(jìn)程到來的先后次序進(jìn)行調(diào)度。 這樣， 在系統(tǒng)中等待時(shí)間最長的作業(yè)就優(yōu)先被調(diào)度， 而不管其所需運(yùn)行時(shí)間的長短。 FCFS的性能很差。 考慮下面三個(gè)作業(yè)如圖3-6所示）， 對(duì)每個(gè)作業(yè)， 設(shè)已知其運(yùn)行時(shí)間， 我們計(jì)算這三個(gè)作業(yè)的平均周轉(zhuǎn)時(shí)間。 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 圖3-6 三個(gè)作業(yè) 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 如果作業(yè)按1， 2， 3的順序幾乎同時(shí)到達(dá)， 那么采用F

12、CFS方式的服務(wù)順序也是123， 如圖3-7所示。圖3-7 FCFS方式 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 作業(yè)1的周轉(zhuǎn)時(shí)間是24； 作業(yè)2的周轉(zhuǎn)時(shí)間是27； 作業(yè)3的周轉(zhuǎn)時(shí)間是30， 平均周轉(zhuǎn)時(shí)間是24+27+30）/3=27。 然而， 若作業(yè)的到達(dá)順序是2， 3， 1， 則服務(wù)順序如圖3-8所示。第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 圖3-8 另一種作業(yè)運(yùn)行順序 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 3.5.2 短作業(yè)優(yōu)先SJF） CPU調(diào)度的另一種方式是短作業(yè)優(yōu)先Shortest Job First)算法。 所謂作業(yè)的長短是指作業(yè)要求運(yùn)行時(shí)間的多少。 當(dāng)CPU可供使用時(shí)， SJF算法

13、就把CPU分給最短的作業(yè)。 例如， 考慮如圖3-9所示的一組作業(yè)它們同時(shí)提交到系統(tǒng)）。第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 圖3-9 同時(shí)到達(dá)的一組作業(yè) 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 利用短作業(yè)優(yōu)先法調(diào)度， 作業(yè)執(zhí)行的順序如圖3-10所示。其平均周轉(zhuǎn)時(shí)間是13。 圖3-10 SJF調(diào)度法 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 對(duì)于一組給定的作業(yè)來說， 短作業(yè)優(yōu)先法給出最小的平均等待時(shí)間。 可以證明， 在這方面它是最佳的。 證明的辦法是， 把一個(gè)短作業(yè)移到長作業(yè)之前所減少的短作業(yè)的等待時(shí)間大于增加的長作業(yè)等待時(shí)間。 相應(yīng)地， 平均等待時(shí)間也減少了， 如圖3-11所示。第第3 3章章 處理

14、機(jī)調(diào)度處理機(jī)調(diào)度 圖3-11 SJF有最小平均等待時(shí)間 長作業(yè)短作業(yè)長作業(yè)短作業(yè)第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 3.5.3 優(yōu)先級(jí)Priority） 短作業(yè)優(yōu)先法是一般優(yōu)先級(jí)調(diào)度算法的特例。 每個(gè)進(jìn)程有一個(gè)優(yōu)先級(jí)， CPU分給優(yōu)先級(jí)最高的進(jìn)程。 優(yōu)先級(jí)相同的進(jìn)程按FCFS調(diào)度。 短作業(yè)優(yōu)先法是簡(jiǎn)化的優(yōu)先級(jí)算法， 這里優(yōu)先級(jí)p反比于估計(jì)的下一次CPU工作時(shí)間）, p=1/。 CPU工作時(shí)間越長， 其優(yōu)先級(jí)越低。第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 3.5.4 搶占式和非搶占式算法 SJF既可以為搶占式， 又可以為非搶占式。 當(dāng)一個(gè)作業(yè)正在執(zhí)行時(shí)， 一個(gè)新作業(yè)到來， 并進(jìn)入就緒隊(duì)列， 而新作

15、業(yè)比當(dāng)前正在執(zhí)行的作業(yè)還短， 在此情況下， 就有兩種不同的處理方式： 搶占式短作業(yè)優(yōu)先算法強(qiáng)行中止當(dāng)前正在執(zhí)行的作業(yè)， 調(diào)度新作業(yè)執(zhí)行； 而非搶占式SJF將允許當(dāng)前作業(yè)繼續(xù)運(yùn)行， 直到完成它的CPU運(yùn)行工作。 搶占式短作業(yè)優(yōu)先法也叫做最短剩余時(shí)間優(yōu)先法SRTF， Shortes Remaining Time First）。 作為例子， 考慮下面4個(gè)作業(yè)如圖3-12所示）。 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 圖3-12 4個(gè)作業(yè)示例 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 如果這些作業(yè)按上面所示的時(shí)間進(jìn)入就緒隊(duì)列并需要指定的運(yùn)行時(shí)間， 那么下面的示意圖如圖3-13所示就說明了最短剩余時(shí)間優(yōu)先法

16、調(diào)度的結(jié)果。第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 圖3-13 SRTF法調(diào)度示例 作業(yè)1作業(yè)2作業(yè)4015101726作業(yè)1作業(yè)3搶占第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 表3-1 SRTF調(diào)度算法的性能 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 3.5.5 輪轉(zhuǎn)法RR） 輪轉(zhuǎn)法RR， Round Robin主要是為分時(shí)系統(tǒng)設(shè)計(jì)的。 一個(gè)極為重要的參數(shù)就是時(shí)間片， 它是一個(gè)小的時(shí)間單位， 不能取得過大或者過小， 通常為10100 ms數(shù)量級(jí)。 就緒隊(duì)列可看成是一個(gè)環(huán)形隊(duì)列， CPU調(diào)度程序輪流地把CPU分給就緒隊(duì)列中的每個(gè)進(jìn)程， 時(shí)間長度都是一個(gè)時(shí)間片。第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 圖3-

17、14 RR法q=1和q=4時(shí)進(jìn)程運(yùn)行的情況 ABCD0ABCDq4q1進(jìn)程510201525t第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 由圖3-14可以看出， 在輪轉(zhuǎn)法中， 一次輪回時(shí)間內(nèi)分給任何進(jìn)程的CPU時(shí)間都不會(huì)大于一個(gè)時(shí)間片。 如果一個(gè)進(jìn)程在一個(gè)時(shí)間片內(nèi)沒有做完自己的事情， 那么在時(shí)間片用完時(shí)， 該進(jìn)程就被剝奪對(duì)CPU的控制權(quán)， 放回到就緒隊(duì)列的末尾。 所以， 一個(gè)需運(yùn)行較長時(shí)間的進(jìn)程要經(jīng)過多次輪轉(zhuǎn)才能完成工作。 表3-2給出各進(jìn)程的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間項(xiàng)等指標(biāo)。 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 表3-2 RR調(diào)度算法的性能 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 時(shí)間片的長短通常由

18、以下幾個(gè)因素確定： （1） 系統(tǒng)的響應(yīng)時(shí)間： 在進(jìn)程數(shù)目一定時(shí)， 時(shí)間片的長短直接正比于系統(tǒng)對(duì)響應(yīng)時(shí)間的要求； （2） 就緒隊(duì)列進(jìn)程的數(shù)目： 當(dāng)系統(tǒng)要求的響應(yīng)時(shí)間一定時(shí)， 時(shí)間片的大小反比于就緒隊(duì)列中的進(jìn)程數(shù)； （3） 進(jìn)程的轉(zhuǎn)換時(shí)間： 若進(jìn)程的轉(zhuǎn)換時(shí)間為t， 時(shí)間片為q， 為保證系統(tǒng)開銷不大于某個(gè)標(biāo)準(zhǔn)， 應(yīng)使比值t/q不大于某一數(shù)值， 如1/10； （4） CPU運(yùn)行指令速度： CPU運(yùn)行速度快， 則時(shí)間片可以短些； 反之， 則應(yīng)取得長些。第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 3.5.6 多級(jí)隊(duì)列法MQ） 另一類調(diào)度算法是把多個(gè)進(jìn)程分成不同級(jí)別的組。 例如， 通常的劃分方式是分為前臺(tái)進(jìn)程交互

19、和后臺(tái)進(jìn)程批處理）。 這兩類進(jìn)程的響應(yīng)時(shí)間要求是完全不同的， 所以有不同的調(diào)度算法。 多級(jí)隊(duì)列MQ， Multilevel Queue調(diào)度算法把就緒隊(duì)列劃分成幾個(gè)單獨(dú)的隊(duì)列如圖3-15所示）。 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 圖3-15 多級(jí)隊(duì)列調(diào)度 系統(tǒng)進(jìn)程交互進(jìn)程學(xué)生批處理進(jìn)程批處理進(jìn)程交互編輯進(jìn)程最高優(yōu)先級(jí)最低優(yōu)先級(jí)第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 下面是多級(jí)隊(duì)列調(diào)度法的一個(gè)例子， 有如下5個(gè)隊(duì)列：（1） 系統(tǒng)進(jìn)程；（2） 交互進(jìn)程；（3） 交互編輯進(jìn)程；（4） 批處理進(jìn)程；（5） 學(xué)生批處理進(jìn)程。第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 3.5.7 多級(jí)反饋隊(duì)列法MFQ） 通常在

20、多級(jí)隊(duì)列法中， 進(jìn)程是永久性地放到一個(gè)隊(duì)列中的， 它們不能從一個(gè)隊(duì)列移到另一個(gè)隊(duì)列。 而多級(jí)反饋隊(duì)列法MFQ， Multilevel Feedback Queue允許進(jìn)程在各隊(duì)列間移動(dòng)， 其基本思想是把具有不同CPU工作時(shí)間這一特性的進(jìn)程區(qū)分開來。 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 圖3-16 多級(jí)反饋隊(duì)列 時(shí)間片8時(shí)間片16FCFS第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 3.5.8 多級(jí)調(diào)度綜合示例 在一個(gè)系統(tǒng)中會(huì)采用多級(jí)調(diào)度， 如作業(yè)調(diào)度和進(jìn)程調(diào)度， 并且各采用不同的調(diào)度算法， 如作業(yè)調(diào)度可采用FCFS、 SJF、 SRTF等算法， 而進(jìn)程調(diào)度可采用最高優(yōu)先權(quán)優(yōu)先法HPF）、 RR、 M

21、Q等算法。例如， 在一個(gè)有兩道作業(yè)的批處理系統(tǒng)中， 作業(yè)調(diào)度采用短作業(yè)優(yōu)先的調(diào)度算法， 進(jìn)程調(diào)度采用搶占式優(yōu)先級(jí)調(diào)度算法。 設(shè)有以下作業(yè)序列如圖3-17所示）。 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 圖3-17 作業(yè)序列示例 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 其中， 給出的作業(yè)優(yōu)先數(shù)即為相應(yīng)進(jìn)程的優(yōu)先數(shù)。 其數(shù)值越小， 優(yōu)先級(jí)越高。 在這種情況下， 每個(gè)作業(yè)從到達(dá)系統(tǒng)到完成要經(jīng)歷兩級(jí)調(diào)度： 首先由作業(yè)調(diào)度程序根據(jù)其采用的算法和內(nèi)存的實(shí)際情況， 挑選作業(yè)送入內(nèi)存， 并建立相應(yīng)進(jìn)程； 然后由進(jìn)程調(diào)度程序依據(jù)自己的調(diào)度算法從就緒隊(duì)列中選出合適進(jìn)程， 令其投入運(yùn)行。 這4個(gè)作業(yè)進(jìn)程的活動(dòng)情況如圖3

22、-18所示。第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 圖3-18 4個(gè)作業(yè)的活動(dòng)過程 作業(yè)DCBA8:00 8:208:308:509:1010:0010:20時(shí)間搶占進(jìn)入內(nèi)存第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 表3-3 4個(gè)作業(yè)活動(dòng)的有關(guān)數(shù)據(jù) 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 3.6 Linux系統(tǒng)中的進(jìn)程調(diào)度系統(tǒng)中的進(jìn)程調(diào)度 3.6.1 進(jìn)程調(diào)度 1. 調(diào)度方式 Linux內(nèi)核的調(diào)度方式基本上采用“搶占式優(yōu)先級(jí)方式， 即當(dāng)進(jìn)程在用戶模式下運(yùn)行時(shí)， 不管是否自愿， 在一定條件下如時(shí)間片用完或等待I/O）， 核心就可以暫時(shí)剝奪其運(yùn)行而調(diào)度其他進(jìn)程進(jìn)入運(yùn)行。 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)

23、度 Linux系統(tǒng)中進(jìn)程分為實(shí)時(shí)進(jìn)程和非實(shí)時(shí)進(jìn)程， 它們的優(yōu)先級(jí)由不同方式確定： 實(shí)時(shí)進(jìn)程的優(yōu)先級(jí)采用靜態(tài)優(yōu)先級(jí)， 即由用戶預(yù)先指定， 以后不會(huì)改變； 非實(shí)時(shí)進(jìn)程的優(yōu)先級(jí)采用動(dòng)態(tài)優(yōu)先級(jí)， 它由調(diào)度程序計(jì)算出來。 實(shí)時(shí)進(jìn)程的靜態(tài)優(yōu)先級(jí)通常比非實(shí)時(shí)進(jìn)程的動(dòng)態(tài)優(yōu)先級(jí)要高。 Linux系統(tǒng)中的調(diào)度策略基本上繼承了UNIX的以優(yōu)先級(jí)為基礎(chǔ)的調(diào)度。 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 2. 調(diào)度策略 Linux系統(tǒng)針對(duì)不同類別的進(jìn)程提供了三種不同的調(diào)度策略， 即SCHED_FIFO、 SCHED_RR以及SCHED_OTHER。 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 3. 調(diào)度時(shí)機(jī) 核心進(jìn)行進(jìn)程調(diào)度的時(shí)

24、機(jī)有以下5種情況： (1) 當(dāng)前進(jìn)程調(diào)用nanosleep()或者pause()， 使自己進(jìn)入睡眠狀態(tài)， 主動(dòng)讓出一段時(shí)間CPU的使用權(quán)。 (2) 進(jìn)程終止， 永久地放棄對(duì)CPU的使用。 (3) 在時(shí)鐘中斷處理程序執(zhí)行過程中， 發(fā)現(xiàn)當(dāng)前進(jìn)程連續(xù)運(yùn)行的時(shí)間過長。第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 (4) 當(dāng)喚醒一個(gè)睡眠進(jìn)程時(shí)， 發(fā)現(xiàn)被喚醒的進(jìn)程比當(dāng)前進(jìn)程更有資格運(yùn)行。 (5) 一個(gè)進(jìn)程通過執(zhí)行系統(tǒng)調(diào)用來改變調(diào)度策略或者降低自身的優(yōu)先權(quán)(如nice命令)， 從而引起立即調(diào)度。 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 4. 調(diào)度算法 進(jìn)程調(diào)度的算法應(yīng)該比較簡(jiǎn)單， 以便減少頻繁調(diào)度時(shí)的系統(tǒng)開銷。 Li

25、nux執(zhí)行進(jìn)程調(diào)度時(shí)， 首先查找所有在就緒隊(duì)列中的進(jìn)程， 從中選出優(yōu)先級(jí)最高且在內(nèi)存的一個(gè)進(jìn)程。 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 3.6.2 shell基本工作原理 Linux系統(tǒng)提供給用戶的最重要的系統(tǒng)程序是shell命令語言解釋程序。 它不屬于內(nèi)核部分， 而是在核心之外以用戶態(tài)方式運(yùn)行。 其基本功能是解釋并執(zhí)行用戶鍵入的各種命令， 實(shí)現(xiàn)用戶與Linux核心的接口。 系統(tǒng)初啟后， 核心為每個(gè)終端用戶建立一個(gè)進(jìn)程去執(zhí)行shell解釋程序。 它的執(zhí)行過程基本上按照如下步驟： 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 (1) 讀取用戶由鍵盤輸入的命令行。 (2) 分析命令， 以命令名作為文件名，

26、 并將其他參數(shù)改造為系統(tǒng)調(diào)用execve()內(nèi)部處理所要求的形式。 (3) 終端進(jìn)程調(diào)用fork()建立一個(gè)子進(jìn)程。 (4) 終端進(jìn)程本身用系統(tǒng)調(diào)用wait4()來等待子進(jìn)程完成(如果是后臺(tái)命令， 則不等待)。 （5） 如果命令末尾有&號(hào)后臺(tái)命令符號(hào)）， 則終端進(jìn)程不用執(zhí)行系統(tǒng)調(diào)用wait4()， 而是立即發(fā)提示符， 讓用戶輸入下一個(gè)命令， 轉(zhuǎn)步驟1）。 shell基本執(zhí)行過程以及父子進(jìn)程之間的關(guān)系如圖3-19所示。第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 圖3-19 shell命令執(zhí)行過程 讀入命令行分離命令名，按execve的要求放置參數(shù)idfrok( )創(chuàng)建子進(jìn)程id0？0父進(jìn)程有“

27、&”？無wait4()等待子進(jìn)程終止發(fā)提示符$終端進(jìn)程有0調(diào)度到子進(jìn)程execve()更換進(jìn)程映像子進(jìn)程運(yùn)行相應(yīng)的可執(zhí)行文件，完成命令的功能exit( )終止子進(jìn)程，釋放所用資源，喚醒父進(jìn)程子進(jìn)程中止向父進(jìn)程報(bào)告子進(jìn)程第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 3.6.3 系統(tǒng)初啟 1. 硬件檢測(cè) 當(dāng)PC啟動(dòng)時(shí)， 首先CPU進(jìn)入實(shí)模式， 開始執(zhí)行ROM-BIOS起始位置的代碼。 2. 加載引導(dǎo)程序 整個(gè)硬盤的第一個(gè)扇區(qū)是引導(dǎo)扇區(qū)， 加電后從這個(gè)扇區(qū)“引導(dǎo)”， 所以它稱為“主引導(dǎo)記錄塊MBR。 MBR中會(huì)有磁盤分區(qū)的數(shù)據(jù)和一段簡(jiǎn)短的程序， 共512字節(jié)。 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度

28、引導(dǎo)扇區(qū)中的程序及其輔助程序不包括LILO采用匯編語言編寫， 共有三個(gè)： （1） bootsect.S， 這是Linux引導(dǎo)扇區(qū)的源代碼， 匯編后不能超過512字節(jié)。 （2） setup.S， 這是輔助程序的一部分。 （3） video.S， 這是另一部分輔助程序， 用于引導(dǎo)過程中的屏幕顯示。第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 3. 系統(tǒng)初始化 輔助程序setup為內(nèi)核映像的執(zhí)行作好了準(zhǔn)備包括解壓縮以后， 就跳轉(zhuǎn)到0 x100000開始執(zhí)行內(nèi)核本身， 下面就是內(nèi)核的初始化過程。 初始化過程可以分為三個(gè)階段。 第一階段主要是CPU本身的初始化， 例如頁式映射的建立； 第二階段主要是系統(tǒng)中一些基礎(chǔ)設(shè)施的初始化， 例如內(nèi)存管理和進(jìn)程管理的建立和初始化； 最后是對(duì)上層部分初始化， 如根設(shè)備的安裝和外部設(shè)備的初始化等。 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 在初始化的第一階段， 首先設(shè)置內(nèi)核頁表， 并啟動(dòng)頁面映射機(jī)制。 在第二階段調(diào)用函數(shù)start_kernel()， 繼續(xù)進(jìn)行內(nèi)核的初始化， 甚至可以說這才真正開始內(nèi)核初始化， 這是在較高層次上的初始化。 第第3 3章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 在第三階段， 內(nèi)核線程init首先鎖定內(nèi)核， 然后