計算機(jī)操作系統(tǒng)教程(第三版)張堯?qū)W 第8講-處理機(jī)調(diào)度

第四章處理機(jī)調(diào)度4.1分級調(diào)度4.2

作業(yè)調(diào)度4.3

進(jìn)程調(diào)度4.4

調(diào)度算法14.3進(jìn)程調(diào)度進(jìn)程調(diào)度的功能進(jìn)程調(diào)度的時機(jī)進(jìn)程調(diào)度性能評價234.3.1進(jìn)程調(diào)度的功能記錄系統(tǒng)中所有進(jìn)程的執(zhí)行情況將各進(jìn)程的執(zhí)行情況和狀態(tài)特征記錄在各進(jìn)程的PCB中進(jìn)程在活動期間狀態(tài)是變化的，例如由運(yùn)行狀態(tài)到等待，等待到就緒，就緒到運(yùn)行根據(jù)各進(jìn)程的狀態(tài)特征和資源需求，將各進(jìn)程的PCB表排成相應(yīng)的隊列選擇占有處理機(jī)的進(jìn)程在處理機(jī)空閑時，根據(jù)一定的原則選擇一個就緒狀態(tài)的進(jìn)程來運(yùn)行選擇策略多種多樣，他們決定了調(diào)度的性能44.3.1進(jìn)程調(diào)度的功能切換進(jìn)程上下文進(jìn)程上下文有正文段、數(shù)據(jù)段、硬件寄存器（指令計數(shù)器、處理機(jī)狀態(tài)字寄存器、過程調(diào)用時傳遞參數(shù)的通用寄存器等）的內(nèi)容以及有關(guān)的數(shù)據(jù)結(jié)構(gòu)（PCB表）組成。首先檢查是否可以做切換（執(zhí)行不允許中斷的原語時不可切換）然后保留被切換進(jìn)程的上下文，以便以后切換回該進(jìn)程時順利恢復(fù)執(zhí)行由調(diào)度程序選擇一個進(jìn)程，裝載該進(jìn)程的上下文。控制轉(zhuǎn)向該進(jìn)程，從剛恢復(fù)的程序計數(shù)器所指示的指令地址開始執(zhí)行54.3.2進(jìn)程調(diào)度的時機(jī)一個進(jìn)程完成其任務(wù)時。執(zhí)行中的進(jìn)程自己調(diào)用阻塞原語，進(jìn)入等待狀態(tài)。執(zhí)行了一次P操作，資源不滿足；執(zhí)行V操作激活了等待隊列的進(jìn)程。執(zhí)行的進(jìn)程提出I/O請求后被阻塞。在分時系統(tǒng)中，當(dāng)進(jìn)程完規(guī)定的時間片，時鐘中斷使該進(jìn)程讓出處理機(jī)時。執(zhí)行完系統(tǒng)調(diào)用，系統(tǒng)返回用戶態(tài)之前，由于系統(tǒng)進(jìn)程結(jié)束，需要調(diào)度新的進(jìn)程。在采用可剝奪調(diào)度方式的系統(tǒng)中，當(dāng)具有更高優(yōu)先級的進(jìn)程要求處理機(jī)時。6可剝奪方式與非剝奪方式就緒隊列中只要有優(yōu)先級更高的進(jìn)程就停止現(xiàn)運(yùn)行進(jìn)程而讓高優(yōu)先級的進(jìn)程運(yùn)行。這種方式叫做可剝奪式。即使就緒隊列存在高優(yōu)先級的進(jìn)程，仍然讓現(xiàn)進(jìn)程繼續(xù)運(yùn)行，直到該進(jìn)程時間片用完或因發(fā)生某事件而進(jìn)入等待狀態(tài)。這時才將處理機(jī)分派給優(yōu)先級更高的進(jìn)程，這種方式叫做非剝奪方式。74.3.3進(jìn)程調(diào)度性能評價進(jìn)程調(diào)度策略的好壞直接影響作業(yè)調(diào)度的性能。作業(yè)周轉(zhuǎn)時間和平均周轉(zhuǎn)時間在某種程度上反映了進(jìn)程調(diào)度的性能。定性評價可靠性簡潔性定量評價CPU利用率進(jìn)程在就緒隊列里的等待時間與執(zhí)行時間之比84.4調(diào)度算法先來先服務(wù)FCFS法——作業(yè)和進(jìn)程最短作業(yè)優(yōu)先SJF法最高響應(yīng)比優(yōu)先法優(yōu)先級法輪轉(zhuǎn)法多級反饋輪轉(zhuǎn)法94.4.1先來先服務(wù)(FCFS)法先來先服務(wù)算法是按作業(yè)來到的次序進(jìn)行調(diào)度的。這種算法優(yōu)先考慮在系統(tǒng)中等待時間最長的作業(yè)或進(jìn)程，而不管它要求運(yùn)行時間的長短。這種算法簡單，容易實(shí)現(xiàn)，但效率較低。因?yàn)樗鼪]有考慮作業(yè)的運(yùn)行特性和對資源的要求，所以影響了系統(tǒng)效率的發(fā)揮。10例子下面是4個作業(yè)在系統(tǒng)中從提交、運(yùn)行、完成的各個信息。作業(yè)提交時間運(yùn)行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間1828102128.50.51010.524390.110.510.61.61649.50.2010.610.81.36.5平均周轉(zhuǎn)時間：T=1.725平均帶權(quán)周轉(zhuǎn)時間W=6.875114.4.2最短作業(yè)優(yōu)先(SJF)法比較作業(yè)緩沖區(qū)中的作業(yè)預(yù)計的運(yùn)行時間，選擇預(yù)計時間最短的作業(yè)進(jìn)入運(yùn)行狀態(tài)。這種算法簡單，并且效率相對較高。主要問題是對長作業(yè)不利，如果系統(tǒng)不斷地接受短作業(yè)，就會使長作業(yè)長時間等待。12例子作業(yè)提交時間運(yùn)行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間1828102128.50.510.310.82.34.6390.11010.11.11149.50.2010.110.30.84平均周轉(zhuǎn)時間：T=1.55平均帶權(quán)周轉(zhuǎn)時間W=5.15134.4.3最高響應(yīng)比優(yōu)先法響應(yīng)比=(W+T)/T=1+W/TW:作業(yè)在后備狀態(tài)隊列中的等待時間

T:該作業(yè)估計需要的執(zhí)行時間每調(diào)度一個作業(yè)后，就計算作業(yè)緩沖區(qū)中作業(yè)的響應(yīng)比，下一次選擇響應(yīng)比高的作業(yè)運(yùn)行。預(yù)計運(yùn)行時間短的作業(yè)，其響應(yīng)比較高，所以它的總的執(zhí)行時間較短。而長作業(yè)如果在系統(tǒng)中等待的時間較長，其響應(yīng)比隨著等待時間的增加而提高，所以它的等待時間也不會太長。這種算法既照顧了短作業(yè)、也考慮到了長作業(yè)。14例子作業(yè)提交時間運(yùn)行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間1828102128.50.510.110.62.14.2390.11010.11.11149.50.2010.6010.81.36．5平均周轉(zhuǎn)時間：T=1.625W=5.675154.4.4優(yōu)先級法系統(tǒng)或用戶按照某種原則為作業(yè)或進(jìn)程指定一個優(yōu)先級來表示所享有的優(yōu)先權(quán)。系統(tǒng)將處理機(jī)的使用權(quán)交給就緒隊列中優(yōu)先數(shù)最高的進(jìn)程。確定優(yōu)先級的方法靜態(tài)法:開始執(zhí)行之前就確定，執(zhí)行開始之后不可改變動態(tài)法：隨著執(zhí)行過程不斷變化優(yōu)先級作業(yè)靜態(tài)優(yōu)先級用戶指定，高優(yōu)先級高費(fèi)用根據(jù)作業(yè)類型指定優(yōu)先級根據(jù)作業(yè)要求資源情況指定優(yōu)先級164.4.4優(yōu)先級法進(jìn)程靜態(tài)優(yōu)先級根據(jù)進(jìn)程的類型系統(tǒng)進(jìn)程調(diào)度進(jìn)程I/O進(jìn)程中斷處理進(jìn)程存儲管理進(jìn)程I/O繁忙CPU繁忙I/O與CPU均衡將作業(yè)的靜態(tài)優(yōu)先級作為它所屬進(jìn)程的優(yōu)先級174.4.4優(yōu)先級法進(jìn)程動態(tài)優(yōu)先級根據(jù)進(jìn)程占用CPU時間的長短占用處理機(jī)時間越長，阻塞之后再次獲得調(diào)度的優(yōu)先級越低根據(jù)就緒進(jìn)程等待CPU的時間長短等待時間越長，獲得調(diào)度選中的優(yōu)先級越高動態(tài)進(jìn)程優(yōu)先級需要系統(tǒng)付出一定的開銷184.4.5輪轉(zhuǎn)法將CPU的處理時間分成固定大小的時間片如果一個進(jìn)程用完了時間片，但沒有完成任務(wù)，則釋放CPU而排到就緒隊列的末尾，等待下一次調(diào)度輪轉(zhuǎn)法只能用來調(diào)度分配可以搶占的資源作業(yè)調(diào)度包括有不可搶占硬件資源的分配，所以不使用輪轉(zhuǎn)法時間片的長度為系統(tǒng)要求的響應(yīng)時間/就緒隊列允許的最大進(jìn)程數(shù)194.4.5輪轉(zhuǎn)法就緒隊列中的進(jìn)程均勻獲得時間片。如果時間片太大，則每個進(jìn)程等待的時間就會較長，用戶會感覺到明顯的等待，如果時間片太小，則系統(tǒng)的開銷就顯得較大。所以時間片的選擇是非常重要的。一般為100或幾百毫秒。每個進(jìn)程獲得的時間片是固定的，并且只有一個就緒隊列。改進(jìn)的方向：將固定時間片為可變時間片、將一個就緒隊列該為多個就緒隊列。204.4.5輪轉(zhuǎn)法在固定時間片的方法中，如果有Q=T/Nmax關(guān)系，當(dāng)用戶允許的響應(yīng)時間為3秒，最大進(jìn)程數(shù)為30時，每個進(jìn)程占用處理機(jī)的時間時0.1秒。如果在某個時刻，系統(tǒng)中的進(jìn)程數(shù)為6個，因?yàn)槊總€進(jìn)程占用處理機(jī)的時間是固定的，所以這時響應(yīng)時間變短。但實(shí)際上，用戶已經(jīng)滿意了3秒的響應(yīng)時間，沒有必要縮短響應(yīng)時間，而使每個進(jìn)程多占用一些處理機(jī)時間對提高系統(tǒng)效率有好處。這時就可以使用可變時間片算法：每當(dāng)一輪開始時，系統(tǒng)便根據(jù)就緒隊列中的進(jìn)程數(shù)計算一次時間片，然后按新的時間片運(yùn)行，在此期間到達(dá)的進(jìn)程都不入就緒隊列，而等到這輪完成后，參加新的時間片計算。214.4.6多級反饋輪轉(zhuǎn)法輪轉(zhuǎn)法中，加入就