計算機操作系統教程(第三版)張堯學 第8講-處理機調度

第四章處理機調度4.1分級調度4.2

作業調度4.3

進程調度4.4

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

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