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

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

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

成，如圖3-1所示。第3章處理機(jī)調(diào)度圖3-1作業(yè)的基本狀態(tài)第3章處理機(jī)調(diào)度提交狀態(tài)——即用戶向系統(tǒng)提交一個(gè)作業(yè)時(shí)，該作業(yè)所處的狀態(tài)。后備狀態(tài)——即用戶作業(yè)經(jīng)輸入設(shè)備（如讀卡機(jī)）送入輸入井（磁盤）中存放，等待進(jìn)入內(nèi)存時(shí)所處的狀況。執(zhí)行狀態(tài)——即作業(yè)分配到所需的資源，被調(diào)入內(nèi)存，并且在處理機(jī)（CPU）上執(zhí)行相應(yīng)的程序時(shí)所處的狀況。完成狀態(tài)——即作業(yè)完成了計(jì)算任務(wù)，結(jié)果

由打印機(jī)輸出，最后由系統(tǒng)回收分配給它的全部資源，準(zhǔn)備退出系統(tǒng)時(shí)的作業(yè)狀況。第3章處理機(jī)調(diào)度3.2.2作業(yè)調(diào)度1.作業(yè)控制塊（JCB）在多道批處理系統(tǒng)中通常有上百個(gè)作業(yè)被收容在輸入井（磁盤）中。為了管理和調(diào)度作業(yè)，系統(tǒng)為每個(gè)作業(yè)設(shè)置了一個(gè)作業(yè)控制塊（JCB），它記錄該作業(yè)的有關(guān)信息。不同系統(tǒng)的JCB的組成內(nèi)容有所區(qū)別。JCB的主要內(nèi)容如圖3-2所示。第3章處理機(jī)調(diào)度圖3-2作業(yè)控制塊第3章處理機(jī)調(diào)度2.作業(yè)調(diào)度的功能如上所述，作業(yè)調(diào)度的主要任務(wù)是完成作業(yè)從后備狀態(tài)到執(zhí)行狀態(tài)和從執(zhí)行狀態(tài)到完成狀態(tài)的轉(zhuǎn)換。具體來(lái)說(shuō)，通常作業(yè)調(diào)度程序要完成以下工作(這就是作業(yè)調(diào)度的功能)。記錄系統(tǒng)中各個(gè)作業(yè)的情況。按照某種調(diào)度算法從后備作業(yè)隊(duì)列中挑選作業(yè)。為選中的作業(yè)分配內(nèi)存和外設(shè)等資源。為選中的作業(yè)建立相應(yīng)的進(jìn)程。第3章處理機(jī)調(diào)度(5)作業(yè)結(jié)束后進(jìn)行善后處理工作，如輸出必要的信息，收回該作業(yè)所占用的全部資源，撤消與該作業(yè)相關(guān)的全部進(jìn)程和該作業(yè)的JCB。第3章處理機(jī)調(diào)度3.3

進(jìn)程調(diào)度3.3.1進(jìn)程調(diào)度的功能和時(shí)機(jī)進(jìn)程只有在得到CPU之后才能真正活動(dòng)起來(lái)。一

個(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章處理機(jī)調(diào)度1.功能進(jìn)程調(diào)度的主要功能是：(1)保存現(xiàn)場(chǎng)。挑選進(jìn)程?；謴?fù)現(xiàn)場(chǎng)。第3章處理機(jī)調(diào)度2.時(shí)機(jī)在什么情況下執(zhí)行進(jìn)程調(diào)度呢?一般是在以下事件發(fā)生后作進(jìn)程調(diào)度：完成任務(wù)。等待資源。運(yùn)行到時(shí)。發(fā)現(xiàn)標(biāo)志。創(chuàng)建新進(jìn)程。第3章處理機(jī)調(diào)度圖3-3進(jìn)程調(diào)度流程第3章處理機(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章處理機(jī)調(diào)度圖3-4兩級(jí)調(diào)度簡(jiǎn)化隊(duì)列圖第3章處理機(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)單來(lái)說(shuō)，作業(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í)間較長(zhǎng)的進(jìn)程換到磁盤上：從就緒隊(duì)列轉(zhuǎn)到就緒/掛起隊(duì)列，從阻塞隊(duì)列轉(zhuǎn)到阻塞/掛起隊(duì)列。當(dāng)內(nèi)存中有足夠的可用空間時(shí)，中級(jí)調(diào)度就從就緒/掛起隊(duì)列中選擇一些合適的進(jìn)程放入內(nèi)存，使之進(jìn)入就緒隊(duì)列。第3章處理機(jī)調(diào)度圖3-5三級(jí)調(diào)度簡(jiǎn)化隊(duì)列第3章處理機(jī)調(diào)度3.4

性能評(píng)價(jià)標(biāo)準(zhǔn)所用算法應(yīng)保證實(shí)現(xiàn)系統(tǒng)的設(shè)計(jì)目標(biāo)。對(duì)所有作業(yè)或進(jìn)程應(yīng)公平對(duì)待。均衡使用資源，盡量使系統(tǒng)中各種資源都同時(shí)得到利用。兼顧響應(yīng)時(shí)間和資源利用率?；谙鄬?duì)優(yōu)先級(jí)，但避免無(wú)限延期。系統(tǒng)開(kāi)銷不應(yīng)太大。第3章處理機(jī)調(diào)度3.4.2性能評(píng)價(jià)標(biāo)準(zhǔn)CPU利用率CPU的利用率可從0～100%。吞吐量吞吐量表示單位時(shí)間內(nèi)CPU完成作業(yè)（或進(jìn)程）的數(shù)量。周轉(zhuǎn)時(shí)間從一個(gè)特定作業(yè)的觀點(diǎn)出發(fā)，最重要的標(biāo)準(zhǔn)就是完成這個(gè)作業(yè)要花費(fèi)多長(zhǎng)時(shí)間。第3章處理機(jī)調(diào)度作業(yè)i的周轉(zhuǎn)時(shí)間Ti為其中，tsi表示作業(yè)i的提交時(shí)刻，tci表示作業(yè)i的完成時(shí)刻。系統(tǒng)中n個(gè)作業(yè)的平均周轉(zhuǎn)時(shí)間T為第3章處理機(jī)調(diào)度作業(yè)周轉(zhuǎn)時(shí)間沒(méi)有區(qū)分作業(yè)實(shí)際運(yùn)行時(shí)間長(zhǎng)短的特性，因?yàn)殚L(zhǎng)作業(yè)不可能具有比運(yùn)行時(shí)間還短的周轉(zhuǎn)時(shí)間。為了合理反映長(zhǎng)短作業(yè)的差別，定義了另一個(gè)衡量標(biāo)準(zhǔn)——帶權(quán)周轉(zhuǎn)時(shí)間W，即W=T/R，其中T為周轉(zhuǎn)時(shí)間，R為實(shí)際運(yùn)行時(shí)間。平均帶權(quán)周轉(zhuǎn)時(shí)間W為第3章處理機(jī)調(diào)度4.就緒等待時(shí)間CPU調(diào)度算法并不真正影響作業(yè)執(zhí)行或I／O操作的時(shí)間數(shù)量。各種CPU調(diào)度算法僅影響作業(yè)(進(jìn)程)在就緒隊(duì)列中所花費(fèi)的時(shí)間數(shù)量。第3章處理機(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í)間。第3章處理機(jī)調(diào)度3.5常用調(diào)度算法3.5.1先來(lái)先服務(wù)（FCFS）最簡(jiǎn)單的CPU調(diào)度算法就是先來(lái)先服務(wù)（FirstCome

First

Served）方法，即按作業(yè)（進(jìn)程）到來(lái)的先后次序進(jìn)行調(diào)度。這樣，在系統(tǒng)中等待時(shí)間最長(zhǎng)的作業(yè)就優(yōu)先被調(diào)度，而不管其所需運(yùn)行時(shí)間的長(zhǎng)短。FCFS的性能很差?？紤]下面三個(gè)作業(yè)（如圖3-6

所示），對(duì)每個(gè)作業(yè)，設(shè)已知其運(yùn)行時(shí)間，我們計(jì)算這三個(gè)作業(yè)的平均周轉(zhuǎn)時(shí)間。第3章處理機(jī)調(diào)度圖3-6三個(gè)作業(yè)第3章處理機(jī)調(diào)度如果作業(yè)按1，2，3的順序幾乎同時(shí)到達(dá)，那么采用FCFS方式的服務(wù)順序也是1→2→3，如圖3-7所示。圖3-7

FCFS方式第3章處理機(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章處理機(jī)調(diào)度圖3-8另一種作業(yè)運(yùn)行順序第3章處理機(jī)調(diào)度3.5.2短作業(yè)優(yōu)先（SJF）CPU調(diào)度的另一種方式是短作業(yè)優(yōu)先（Shortest

Job

First)算法。所謂作業(yè)的長(zhǎng)短是指作業(yè)要求運(yùn)行時(shí)間的多少。當(dāng)CPU可供使用時(shí)，SJF算法就把CPU分給最短的作業(yè)。例如，考慮如圖3-9所示的一組作業(yè)（它們同時(shí)提交到系統(tǒng)）。第3章處理機(jī)調(diào)度圖3-9同時(shí)到達(dá)的一組作業(yè)第3章處理機(jī)調(diào)度利用短作業(yè)優(yōu)先法調(diào)度，作業(yè)執(zhí)行的順序如圖3-10所示。其平均周轉(zhuǎn)時(shí)間是13。圖3-10

SJF調(diào)度法第3章處理機(jī)調(diào)度對(duì)于一組給定的作業(yè)來(lái)說(shuō)，短作業(yè)優(yōu)先法給出最小的平均等待時(shí)間。可以證明，在這方面它是最佳的。證明的辦法是，把一個(gè)短作業(yè)移到長(zhǎng)作業(yè)之前所減少

的短作業(yè)的等待時(shí)間大于增加的長(zhǎng)作業(yè)等待時(shí)間。相

應(yīng)地，平均等待時(shí)間也減少了，如圖3-11所示。第3章處理機(jī)調(diào)度圖3-11

SJF有最小平均等待時(shí)間第3章處理機(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í)間越長(zhǎng)，其優(yōu)先級(jí)越低。第3章處理機(jī)調(diào)度3.5.4搶占式和非搶占式算法SJF既可以為搶占式，又可以為非搶占式。當(dāng)一

個(gè)作業(yè)正在執(zhí)行時(shí)，一個(gè)新作業(yè)到來(lái)，并進(jìn)入就緒隊(duì)列，而新作業(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章處理機(jī)調(diào)度圖3-12

4個(gè)作業(yè)示例第3章處理機(jī)調(diào)度如果這些作業(yè)按上面所示的時(shí)間進(jìn)入就緒隊(duì)列并需要指定的運(yùn)行時(shí)間，那么下面的示意圖（如圖3-13所示）就說(shuō)明了最短剩余時(shí)間優(yōu)先法調(diào)度的結(jié)果。第3章處理機(jī)調(diào)度圖3-13

SRTF法調(diào)度示例第3章處理機(jī)調(diào)度表3-1

SRTF調(diào)度算法的性能第3章處理機(jī)調(diào)度3.5.5輪轉(zhuǎn)法（RR）輪轉(zhuǎn)法（RR，Round

Robin）主要是為分時(shí)系統(tǒng)設(shè)計(jì)的。一個(gè)極為重要的參數(shù)就是時(shí)間片，它是一個(gè)小的時(shí)間單位，不能取得過(guò)大或者過(guò)小，通常為10～

100

ms數(shù)量級(jí)。就緒隊(duì)列可看成是一個(gè)環(huán)形隊(duì)列，

CPU調(diào)度程序輪流地把CPU分給就緒隊(duì)列中的每個(gè)進(jìn)程，時(shí)間長(zhǎng)度都是一個(gè)時(shí)間片。第3章處理機(jī)調(diào)度圖3-14

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

RR調(diào)度算法的性能第3章處理機(jī)調(diào)度時(shí)間片的長(zhǎng)短通常由以下幾個(gè)因素確定：系統(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章處理機(jī)調(diào)度3.5.6多級(jí)隊(duì)列法（MQ）另一類調(diào)度算法是把多個(gè)進(jìn)程分成不同級(jí)別的組。例如，通常的劃分方式是分為前臺(tái)進(jìn)程（交互）和后臺(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章處理機(jī)調(diào)度圖3-15多級(jí)隊(duì)列調(diào)度第3章處理機(jī)調(diào)度下面是多級(jí)隊(duì)列調(diào)度法的一個(gè)例子，有如下5個(gè)隊(duì)列：系統(tǒng)進(jìn)程；交互進(jìn)程；交互編輯進(jìn)程；批處理進(jìn)程；學(xué)生批處理進(jìn)程。第3章處理機(jī)調(diào)度3.5.7多級(jí)反饋隊(duì)列法（MFQ）通常在多級(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ū)分開(kāi)來(lái)。第3章處理機(jī)調(diào)度圖3-16多級(jí)反饋隊(duì)列第3章處理機(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、MQ等算法。例如，在一個(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章處理機(jī)調(diào)度圖3-17作業(yè)序列示例第3章處理機(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-18所示。第3章處理機(jī)調(diào)度圖3-18

4個(gè)作業(yè)的活動(dòng)過(guò)程第3章處理機(jī)調(diào)度表3-3

4個(gè)作業(yè)活動(dòng)的有關(guān)數(shù)據(jù)第3章處理機(jī)調(diào)度3.6

Linux系統(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章處理機(jī)調(diào)度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ì)算出來(lái)。實(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章處理機(jī)調(diào)度2.調(diào)度策略Linux系統(tǒng)針對(duì)不同類別的進(jìn)程提供了三種不同的調(diào)度策略，即SCHED_FIFO、SCHED_RR以及

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

shell基本工作原理Linux系統(tǒng)提供給用戶的最重要的系統(tǒng)程序是shell命令語(yǔ)言解釋程序。它不屬于內(nèi)核部分，而是在核心之外以用戶態(tài)方式運(yùn)行。其基本功能是解釋并執(zhí)行用戶鍵入的各種命令，實(shí)現(xiàn)用戶與Linux核心的接口。系統(tǒng)初啟后，核心為每個(gè)終端用戶建立一個(gè)進(jìn)程去執(zhí)行shell解釋程序。它的執(zhí)行過(guò)程基本上按照如下步驟：第3章處理機(jī)調(diào)度讀取用戶由鍵盤輸入的命令行。分析命令，以命令名作為文件名，并將其他參數(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)命令，則不等待)。（5）如果命令末尾有&號(hào)（后臺(tái)命令符號(hào)），則終端進(jìn)程不用執(zhí)行系統(tǒng)調(diào)用wait4()，而是立即發(fā)提示符，讓用戶輸入下一個(gè)命令，轉(zhuǎn)步驟（1）。shell基本執(zhí)行過(guò)程以及父子進(jìn)程之間的關(guān)系如圖3-19所示。第3章處理機(jī)調(diào)度圖3-19

shell命令執(zhí)行過(guò)程第3章處理機(jī)調(diào)度3.6.3系統(tǒng)初啟硬件檢測(cè)當(dāng)PC啟動(dòng)時(shí)，首先CPU進(jìn)入實(shí)模式，開(kāi)始執(zhí)行ROM-BIOS起始位置的代碼。加載引導(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章處理機(jī)調(diào)度引導(dǎo)扇區(qū)中的程序及其輔助程序（不包括LILO）采用匯編語(yǔ)言編寫，共有三個(gè)：bootsect.S，這是Linux引導(dǎo)扇區(qū)的源代碼，匯編后不能超過(guò)512字節(jié)。setup.S，這是輔助程序的一部分。video.S，這是另一部分輔助程序，用于引導(dǎo)過(guò)程中的屏幕顯示。第3章處理機(jī)調(diào)度3.系統(tǒng)初始化輔助程序setup為內(nèi)核映像的執(zhí)行作好了準(zhǔn)備（包括解壓縮）以后，就跳轉(zhuǎn)到0x100000開(kāi)始執(zhí)行內(nèi)核本身，下面就是內(nèi)核的初始化過(guò)程。初始化過(guò)程可以分為三個(gè)階段。第一階段主要是CPU本身的初始化，例如頁(yè)

式映射的建立；第二階段主要是系統(tǒng)中一些基礎(chǔ)設(shè)施的初始化，例如內(nèi)存管理和進(jìn)程管理的建立和初始化；最后是對(duì)上層部分初始化，如根設(shè)備的安裝和外部設(shè)備的初始化等。第3章處理機(jī)調(diào)度在初始化的第一階段，首先設(shè)置內(nèi)核頁(yè)表，并啟動(dòng)頁(yè)面映射機(jī)制。在第二階段調(diào)用函數(shù)start_kernel()，繼續(xù)進(jìn)行內(nèi)核的初始化，甚至可以說(shuō)這才真正開(kāi)始內(nèi)核初始化，這是在較高層次上的初始化。第3章處理機(jī)調(diào)度在第三階段，內(nèi)核線程init首先鎖定內(nèi)核，