處理機的多級調(diào)度

處理機的多級調(diào)度第一頁，共三十二頁，2022年，8月28日（一）處理機的多級調(diào)度一.處理機調(diào)度的功能確定數(shù)據(jù)結(jié)構(gòu)制定調(diào)度策略（調(diào)度原則）給出調(diào)度算法具體的實施處理機分派 不同類型的操作系統(tǒng)往往采用不同的處理機分配方法。

第二頁，共三十二頁，2022年，8月28日二.處理機調(diào)度的分層實現(xiàn)

只有內(nèi)存中的程序才能在CPU上運行。因此，處理機的調(diào)度通常分為兩層：宏觀上：作業(yè)調(diào)度對存放在輔存設(shè)備上的大量作業(yè)，以一定的策略進行挑選，分配主存等必要的資源，建立作業(yè)對應的進程，使其投入運行。微觀上：進程調(diào)度對進入注冊的所有進程，確定哪個進程在什么時候獲得處理機，使用多長時間。第三頁，共三十二頁，2022年，8月28日三.批處理系統(tǒng)中的處理機調(diào)度第四頁，共三十二頁，2022年，8月28日四.多任務(wù)操作系統(tǒng)中的處理機調(diào)度

在分時系統(tǒng)或支持多任務(wù)并發(fā)執(zhí)行個人計算機操作系統(tǒng)中，系統(tǒng)將用戶提交的任務(wù)處理為進程，一個進程又可以創(chuàng)建多個子進程，形成可以并發(fā)執(zhí)行的多進程。 進程調(diào)度的任務(wù)是：當處理機空閑時，以某種策略選擇一個就緒進程去運行，并分配處理機的時間。 另外，由于分時系統(tǒng)中的作業(yè)調(diào)度功能很弱（甚至沒有），因此有些分時系統(tǒng)會將進程在內(nèi)、外存之間進行交換。由于進程仍然存在，也與處理機的分配無關(guān)，故稱為中級調(diào)度。第五頁，共三十二頁，2022年，8月28日五.多線程操作系統(tǒng)中的處理機調(diào)度

在支持多線程運行的系統(tǒng)中，每個進程都創(chuàng)建一個線程，也可以創(chuàng)建多個線程。 系統(tǒng)為進程分配它所需要的資源，而處理機的分配的對象則為線程。 系統(tǒng)提供線程調(diào)度程序，其功能是當處理機空閑時，以某種策略選擇一個就緒線程去運行，并分配處理機時間。第六頁，共三十二頁，2022年，8月28日（二）作業(yè)調(diào)度一.作業(yè)的狀態(tài) 作業(yè)在整個活動期間一共有四種狀態(tài)：提交狀態(tài)：用戶將自己的程序和數(shù)據(jù)提交給系統(tǒng)，等待輸入。后備狀態(tài)：作業(yè)已存放在磁盤上，等待調(diào)進主存。執(zhí)行狀態(tài)：作業(yè)在主存中運行。完成狀態(tài)：作業(yè)計算完成，退出主存。第七頁，共三十二頁，2022年，8月28日

作業(yè)調(diào)度的主要任務(wù)是完成作業(yè)從后備狀態(tài)到執(zhí)行狀態(tài)和從執(zhí)行狀態(tài)到完成狀態(tài)的轉(zhuǎn)變。第八頁，共三十二頁，2022年，8月28日二.作業(yè)調(diào)度的功能確定數(shù)據(jù)結(jié)構(gòu)

建立作業(yè)控制塊（JCB，JobControlBlock），記錄已進入系統(tǒng)的各作業(yè)的情況（類型、狀態(tài)、資源請求與分配等）；確定調(diào)度策略與調(diào)度算法分配資源

為被選中的作業(yè)創(chuàng)建進程，并且為其申請系統(tǒng)資源；善后處理

收回作業(yè)占用的全部資源，撤銷作業(yè)控制塊以及與該作業(yè)有關(guān)的全部進程。第九頁，共三十二頁，2022年，8月28日三.作業(yè)控制塊（JCB，JobControlBlock）每個作業(yè)進入系統(tǒng)時由系統(tǒng)為其建立一個作業(yè)控制塊JCB（JobControlBlock)，它是存放作業(yè)控制和管理信息的數(shù)據(jù)結(jié)構(gòu)，是作業(yè)存在的標志，主要信息見右圖。第十頁，共三十二頁，2022年，8月28日四.作業(yè)調(diào)度算法性能的衡量

作業(yè)調(diào)度算法規(guī)定了從后備作業(yè)中選擇作業(yè)進入系統(tǒng)內(nèi)存的原則。

1.確定調(diào)度算法時應考慮的因素

(1)應與系統(tǒng)的整體設(shè)計目標一致

(2)考慮系統(tǒng)中各種資源的負載均勻

(3)保證作業(yè)的執(zhí)行

(4)對一些專用資源的使用特性的考慮第十一頁，共三十二頁，2022年，8月28日2.調(diào)度性能的衡量

通常采用平均周轉(zhuǎn)時間和帶權(quán)平均周轉(zhuǎn)時間來衡量作業(yè)調(diào)度算法性能的好壞。

(1)周轉(zhuǎn)時間： 一個作業(yè)提交給計算機系統(tǒng)到該作業(yè)的結(jié)果返回給用戶所需要的時間。定義：ti=tci-tsi ti：作業(yè)周轉(zhuǎn)時間

tci：作業(yè)完成時間

tsi:作業(yè)提交時間意義：說明作業(yè)i在系統(tǒng)中停留的時間長短平均周轉(zhuǎn)時間：第十二頁，共三十二頁，2022年，8月28日(2)帶權(quán)周轉(zhuǎn)時間定義：一個作業(yè)的周轉(zhuǎn)時間與其運行時間的比值意義：說明作業(yè)i在系統(tǒng)中的相對等待時間。(3)平均帶權(quán)周轉(zhuǎn)時間精確度：高于周轉(zhuǎn)時間和平均周轉(zhuǎn)時間另外，還可以用CPU的利用率和吞吐量來衡量。第十三頁，共三十二頁，2022年，8月28日五.作業(yè)調(diào)度算法1.先來先服務(wù)調(diào)度算法(FCFS)策略： 按照作業(yè)來到的先后次序進行調(diào)度特點： 每次選擇的作業(yè)是等待時間最久的，而不管作業(yè)運行時間的長短。這種調(diào)度算法突出的優(yōu)點是實現(xiàn)簡單，但效率較低，在一些實際的系統(tǒng)和一般應用程序中采用這種算法的較多。第十四頁，共三十二頁，2022年，8月28日2.短作業(yè)優(yōu)先調(diào)度算法策略： 考慮作業(yè)的運行時間，每次總是選擇一個請求運行時間最小的作業(yè)調(diào)入內(nèi)存（系統(tǒng)）。特點： 易實現(xiàn)，系統(tǒng)吞吐量高。只考慮短作業(yè)，而沒有考慮長作業(yè)的利益。相對先來先服務(wù)調(diào)度算法實現(xiàn)要困難些，如果作業(yè)的到來順序及運行時間不合適，會出現(xiàn)餓死現(xiàn)象。第十五頁，共三十二頁，2022年，8月28日討論在兩種調(diào)度算法下的周轉(zhuǎn)時間與帶權(quán)周轉(zhuǎn)時間第十六頁，共三十二頁，2022年，8月28日3.響應比高者優(yōu)先調(diào)度算法

響應比高者優(yōu)先調(diào)度算法是介于這兩種算法之間的一種拆衷的算法。 響應比＝響應時間/執(zhí)行時間 ＝1＋等待時間/執(zhí)行時間

每調(diào)度一個作業(yè)時，計算后備作業(yè)表中每個作業(yè)的響應比，挑選響應比高者投入運行。第十七頁，共三十二頁，2022年，8月28日

這種算法從理論上講是比較完備的，但作業(yè)調(diào)度程序要統(tǒng)計作業(yè)的等待時間，使用用戶的估計的運行時間，并要作浮點運算，從而浪費大量的計算時間，這是系統(tǒng)程序所不允許的。第十八頁，共三十二頁，2022年，8月28日4.優(yōu)先數(shù)調(diào)度算法

優(yōu)先數(shù)調(diào)度算法終合考慮各方面的因素（作業(yè)等待時間、運行時間、緩急程度，系統(tǒng)資源使用等），給每個作業(yè)設(shè)置一個優(yōu)先數(shù)，調(diào)度程序總是選擇一個優(yōu)先數(shù)最大（或者最?。┑淖鳂I(yè)調(diào)入（系統(tǒng)）內(nèi)存。這種算法實現(xiàn)的困難在于如何終合考慮，這些因素之間的關(guān)系怎樣處理。第十九頁，共三十二頁，2022年，8月28日5.均衡調(diào)度算法

均衡調(diào)度算法是一種更為理想化的調(diào)度算法，實現(xiàn)更困難，并且存在算法本身的開銷有時會遠遠大于先來先服務(wù)和小作業(yè)優(yōu)先調(diào)度算法的不足，這也是后兩種算法被眾多系統(tǒng)采用的最根本的原因。第二十頁，共三十二頁，2022年，8月28日(三)進程調(diào)度一.調(diào)度/分派結(jié)構(gòu)

處理機分配由調(diào)度和分派兩個功能組成。

1.調(diào)度： 組織和維護就緒進程隊列。包括確定調(diào)度算法、按調(diào)度算法組織和維護就緒進程隊列。（按調(diào)度原則選擇進程）

2.分派：

當處理機空閑時，從就緒隊列隊首中移一個PCB，并將該進程投入運行。（賦予使用處理機的權(quán)限）第二十一頁，共三十二頁，2022年，8月28日二.進程調(diào)度的功能1.記錄和保持系統(tǒng)中所有進程的有關(guān)情況和狀態(tài)特征2.決定分配（處理機）策略 調(diào)度策略的不同，組織就緒進程隊列的方式也不同。先來先服務(wù)調(diào)度：就緒進程按等待時間大小的順序排隊優(yōu)先數(shù)調(diào)度：就緒進程按優(yōu)先數(shù)的先后次序排隊3.實施處理機的分配和回收總而言之，進程調(diào)度包括：調(diào)度算法的選擇（調(diào)度算法）調(diào)度時機的選擇（調(diào)度時機）實施進程調(diào)度（調(diào)度程序）第二十二頁，共三十二頁，2022年，8月28日三.進程調(diào)度方式什么是調(diào)度方式

在按進程優(yōu)先級調(diào)度的系統(tǒng)中，當一進程正在處理機上執(zhí)行時，若有某個更為“重要而緊迫”的進程需要運行時，系統(tǒng)如何分配處理機。基本的方式有二種。

1.非剝奪方式

2.剝奪方式

在實現(xiàn)中還可采用選擇可搶占策略。第二十三頁，共三十二頁，2022年，8月28日四.調(diào)度用的進程狀態(tài)變遷圖右圖中新創(chuàng)建的進程進入低優(yōu)就緒狀態(tài)，一個運行進程因時間片到（實際上是計算量大的進程）而轉(zhuǎn)換成低優(yōu)就緒；進程因等待I/O完成而轉(zhuǎn)換高優(yōu)就緒.通過進程調(diào)度變遷圖，可反映系統(tǒng)的進程調(diào)度的各種特征。第二十四頁，共三十二頁，2022年，8月28日1.隊列結(jié)構(gòu)I/O等待對列——

一個進程如果請求I/O，則進入I/O等待隊列；低優(yōu)先就緒隊列——

一個進程如果在運行中超過了分配給它的時間片，就進入低優(yōu)先就緒高優(yōu)先就緒隊列——

當進程從等待狀態(tài)變?yōu)榫途w狀態(tài)時，則進入高優(yōu)先就緒隊列。第二十五頁，共三十二頁，2022年，8月28日2.進程調(diào)度算法當CPU空閑時，若高優(yōu)先就緒隊列非空，則從高優(yōu)先就緒隊列中選擇一個進程運行，分配時間片為100ms。當CPU空閑時，若高優(yōu)先就緒隊列為空，則從低優(yōu)先就緒隊列中選擇一個進程運行，分配時間片為500ms。

優(yōu)先調(diào)度與時間片調(diào)度相結(jié)合的調(diào)度策略3.調(diào)度效果 優(yōu)先照顧了I/O量大的進程； 適當照顧了計算量大的進程。第二十六頁，共三十二頁，2022年，8月28日五.進程調(diào)度算法1.進程優(yōu)先數(shù)調(diào)度算法

是目前操作系統(tǒng)廣泛采用的一種進程調(diào)度算法，這種算法按照某種原則由系統(tǒng)（或用戶、或系統(tǒng)與用戶結(jié)合）賦予每個進程一個優(yōu)先數(shù)，在處理機空閑時，進程調(diào)度程序就從就緒進程中選擇一個優(yōu)先數(shù)最大（或者最?。┑倪M程占用CPU（該進程就從就緒狀態(tài)轉(zhuǎn)換成運行狀態(tài)）。 采用這種調(diào)度算法的關(guān)鍵是如何確定進程的優(yōu)先數(shù)、一個進程的優(yōu)先數(shù)確定之后是固定的，還是隨著該進程運行的情況的變化而變化。第二十七頁，共三十二頁，2022年，8月28日靜態(tài)：進程的優(yōu)先數(shù)在進程創(chuàng)建時確定后就不再變化確定進程優(yōu)先數(shù)：系統(tǒng)確定：（運行時間、使用資源，進程的類型）用戶確定：（緊迫程度，計費與進程優(yōu)先數(shù)有關(guān)） 系統(tǒng)與用戶結(jié)合（用戶可以為本用戶的進程設(shè)置優(yōu)先數(shù)，但不是作調(diào)度用，系統(tǒng)還要根據(jù)系統(tǒng)情況把用戶設(shè)置的進程優(yōu)先數(shù)作為確定進程優(yōu)先數(shù)的一個參數(shù)）動態(tài)：

系統(tǒng)在運行的過程中，根據(jù)系統(tǒng)的設(shè)計目標，不斷地調(diào)整進程的優(yōu)先數(shù)，這種方法的優(yōu)點是能比較客觀地反映進程的實際情況和保證達到系統(tǒng)設(shè)計目標。第二十八頁，共三十二頁，2022年，8月28日2.循環(huán)輪轉(zhuǎn)調(diào)度算法

循環(huán)輪轉(zhuǎn)調(diào)度實際上是一種先來先服務(wù)算法的調(diào)度算法，它把系統(tǒng)的響應時間分成大小相等（或不相等）的時間單位，稱為時間片。每個進程被調(diào)度到后，占用一個時間片，片用完后，該進程讓出CPU，由運行狀態(tài)轉(zhuǎn)換成就緒狀態(tài)，排在就緒隊列的隊尾。多個進程循環(huán)輪轉(zhuǎn)。第二十九頁，共三十二頁，2022年，8月28日

簡單循環(huán)輪轉(zhuǎn)調(diào)度實現(xiàn)簡單、系統(tǒng)開銷小。不靈活，當系統(tǒng)中進程較多時，系統(tǒng)開銷變大?？勺儠r間片輪轉(zhuǎn)調(diào)度時間片的大小可變，系統(tǒng)可根據(jù)系統(tǒng)中當前的進程數(shù)來確定時間片的大小。例：Q=T/NT：系統(tǒng)響應時間，一般為1秒，具體大小由系統(tǒng)設(shè)計時根據(jù)系統(tǒng)設(shè)計目標確定。N：系統(tǒng)中進程的個數(shù)，也由系統(tǒng)設(shè)計時確定，或者通過系統(tǒng)配置文件，由系統(tǒng)管理員確定。第三十頁，共三十二頁，2022年，8月28日第六章小結(jié)一.處理機的二級調(diào)度二.作業(yè)調(diào)度

1.作業(yè)的狀態(tài)

2.