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

處理機(jī)的多級調(diào)度第1頁，課件共32頁，創(chuàng)作于2023年2月（一）處理機(jī)的多級調(diào)度一.處理機(jī)調(diào)度的功能確定數(shù)據(jù)結(jié)構(gòu)制定調(diào)度策略（調(diào)度原則）給出調(diào)度算法具體的實(shí)施處理機(jī)分派 不同類型的操作系統(tǒng)往往采用不同的處理機(jī)分配方法。

第2頁，課件共32頁，創(chuàng)作于2023年2月二.處理機(jī)調(diào)度的分層實(shí)現(xiàn)

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

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

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

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

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

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

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

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

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

(1)應(yīng)與系統(tǒng)的整體設(shè)計(jì)目標(biāo)一致

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

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

(4)對一些專用資源的使用特性的考慮第11頁，課件共32頁，創(chuàng)作于2023年2月2.調(diào)度性能的衡量

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

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

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

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

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

每調(diào)度一個作業(yè)時，計(jì)算后備作業(yè)表中每個作業(yè)的響應(yīng)比，挑選響應(yīng)比高者投入運(yùn)行。第17頁，課件共32頁，創(chuàng)作于2023年2月

這種算法從理論上講是比較完備的，但作業(yè)調(diào)度程序要統(tǒng)計(jì)作業(yè)的等待時間，使用用戶的估計(jì)的運(yùn)行時間，并要作浮點(diǎn)運(yùn)算，從而浪費(fèi)大量的計(jì)算時間，這是系統(tǒng)程序所不允許的。第18頁，課件共32頁，創(chuàng)作于2023年2月4.優(yōu)先數(shù)調(diào)度算法

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

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

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

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

2.分派：

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

在按進(jìn)程優(yōu)先級調(diào)度的系統(tǒng)中，當(dāng)一進(jìn)程正在處理機(jī)上執(zhí)行時，若有某個更為“重要而緊迫”的進(jìn)程需要運(yùn)行時，系統(tǒng)如何分配處理機(jī)?；镜姆绞接卸N。

1.非剝奪方式

2.剝奪方式

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

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

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

當(dāng)進(jìn)程從等待狀態(tài)變?yōu)榫途w狀態(tài)時，則進(jìn)入高優(yōu)先就緒隊(duì)列。第25頁，課件共32頁，創(chuàng)作于2023年2月2.進(jìn)程調(diào)度算法當(dāng)CPU空閑時，若高優(yōu)先就緒隊(duì)列非空，則從高優(yōu)先就緒隊(duì)列中選擇一個進(jìn)程運(yùn)行，分配時間片為100ms。當(dāng)CPU空閑時，若高優(yōu)先就緒隊(duì)列為空，則從低優(yōu)先就緒隊(duì)列中選擇一個進(jìn)程運(yùn)行，分配時間片為500ms。

優(yōu)先調(diào)度與時間片調(diào)度相結(jié)合的調(diào)度策略3.調(diào)度效果 優(yōu)先照顧了I/O量大的進(jìn)程； 適當(dāng)照顧了計(jì)算量大的進(jìn)程。第26頁，課件共32頁，創(chuàng)作于2023年2月五.進(jìn)程調(diào)度算法1.進(jìn)程優(yōu)先數(shù)調(diào)度算法

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

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

循環(huán)輪轉(zhuǎn)調(diào)度實(shí)際上是一種先來先服務(wù)算法的調(diào)度算法，它把系統(tǒng)的響應(yīng)時間分成大小相等（或不相等）的時間單位，稱為時間片。每個進(jìn)程被調(diào)度到后，占用一個時間片，片用完后，該進(jìn)程讓出CPU，由運(yùn)行狀態(tài)轉(zhuǎn)換成就緒狀態(tài)，排在就緒隊(duì)列的隊(duì)尾。多個進(jìn)程循環(huán)輪轉(zhuǎn)。第29頁，課件共32頁，創(chuàng)作于2023年2月

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

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

2.