操作系統(tǒng)原理 第6章 處理機(jī)調(diào)度.ppt

1、1,6.1 處理機(jī)的多級調(diào)度 6.2 作業(yè)調(diào)度 6.3 進(jìn)程調(diào)度 6.4 UNIX系統(tǒng)的進(jìn)程調(diào)度,第六章 處理機(jī)調(diào)度,2,6.1 處理機(jī)的多級調(diào)度 一. 處理機(jī)調(diào)度的功能 確定數(shù)據(jù)結(jié)構(gòu) 制訂調(diào)度策略 (調(diào)度原則) 給出調(diào)度算法 具體的實(shí)施處理機(jī)分派 不同類型的操作系統(tǒng)往往采用不同的處理機(jī)分配方法。,3,二. 批處理系統(tǒng)中的處理機(jī)調(diào)度 處理機(jī)調(diào)度分為兩級：作業(yè)調(diào)度和進(jìn)程調(diào)度。 1. 作業(yè)調(diào)度 作業(yè)調(diào)度又稱為宏觀調(diào)度。 任務(wù)對存放在輔存設(shè)備上的大量作業(yè)，以一定的策略進(jìn)行挑選，分配主存等必要的資源，建立作業(yè)對應(yīng)的進(jìn)程，使其投入運(yùn)行。 2. 進(jìn)程調(diào)度 進(jìn)程調(diào)度又稱為微觀調(diào)度 。 任務(wù)對進(jìn)入主存的所有進(jìn)

2、程，確定哪個進(jìn)程在什么時候獲得處理機(jī)，使用多長時間。,4,三. 多任務(wù)操作系統(tǒng)中的處理機(jī)調(diào)度 在分時系統(tǒng)或支持多任務(wù)并發(fā)執(zhí)行個人計算機(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ī)的時間。,5,四. 多線程操作系統(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

3、,6.2 作業(yè)調(diào)度 一. 作業(yè)的狀態(tài) 作業(yè)在整個活動期間一共有四種狀態(tài)， 提交狀態(tài)：用戶將自己的程序和數(shù)據(jù)提交給系統(tǒng)，等待輸入。 后備狀態(tài)：作業(yè)已存放在磁盤上，等待調(diào)度。 執(zhí)行狀態(tài)：作業(yè)進(jìn)入主存開始運(yùn)行，到作業(yè)計算完成為止。 完成狀態(tài)：作業(yè)計算完成開始，到善后處理完成并退出系統(tǒng)為止。,7,8,二. 作業(yè)調(diào)度的功能 1. 確定數(shù)據(jù)結(jié)構(gòu) 建立作業(yè)控制塊jcb (job control block)。 作業(yè)控制塊記錄了每個作業(yè)類型、狀態(tài)、資源請求及分配情況 。 2. 確定調(diào)度策略與調(diào)度算法 3. 分配資源 為選中的作業(yè)分配所需要的系統(tǒng)資源。 4. 善后處理 收回該作業(yè)所占用的全部資源，撤消作業(yè)控制塊

4、以及與該作業(yè)有關(guān)的全部進(jìn)程。,9,三. 作業(yè)控制塊 作業(yè)控制塊jcb存在于系統(tǒng)的整個過程中，jcb是一個作業(yè)存在的標(biāo)志。jcb的主要內(nèi)容如下： 作 業(yè) 名 資 源 要 求 資 源 使 用 情況 估計執(zhí)行時間 進(jìn)入系統(tǒng)時間 最遲完成時間 開始執(zhí)行時間 要求的主存量 已執(zhí)行時間 要求外設(shè)的類型及臺數(shù) 主存地址 要求文件量和輸出量 外設(shè)臺號 類 型 優(yōu) 先 級 控制方式 狀 態(tài) 作業(yè)類型,10,四. 作業(yè)調(diào)度算法性能的衡量 采用平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間來衡量作業(yè)調(diào)度算法性能的好壞。 1. 周轉(zhuǎn)時間 一個作業(yè)提交給計算機(jī)系統(tǒng)到該作業(yè)的結(jié)果返回給用戶所需要的時間。 (1) 定義 ti = tci

5、- tsi ti作業(yè)i的周轉(zhuǎn)時間 tsi作業(yè)i的提交時間， tci作業(yè)i的完成時間。 (2) 意義 說明作業(yè)i在系統(tǒng)中停留時間的長短。 (3)平均周轉(zhuǎn)時間 t =,11,2. 帶權(quán)周轉(zhuǎn)時間 (1) 定義 一個作業(yè)的周轉(zhuǎn)時間與其運(yùn)行時間的比值。 wi = tri為作業(yè)i的實(shí)際執(zhí)行時間 (2) 意義 說明作業(yè)i在系統(tǒng)中相對等待時間。 (3) 平均帶權(quán)周轉(zhuǎn)時間 w=,12,五. 作業(yè)調(diào)度算法 1. 先來先服務(wù)調(diào)度算法(FCFS) (1) 策略：按作業(yè)來到的先后次序進(jìn)行調(diào)度。 (2) 特點(diǎn)： 簡單，易實(shí)現(xiàn)。 (3) 討論在先來先服調(diào)度算法下的周轉(zhuǎn)時間與帶權(quán)周轉(zhuǎn)時間 作業(yè) 提交時間 執(zhí)行時間 開始時間

6、完成時間 周轉(zhuǎn)時間 帶權(quán)周轉(zhuǎn)時間 1 8.00 2.00 28.50 0.50 39.00 0.10 4 9.50 0.20,8.00 10.00 2.00 1,10.00 10.50 2.00 4,10.50 10.60 1.60 16,10.60 10.80 1.30 6.5,平均周轉(zhuǎn)時間 t = 平均帶權(quán)周轉(zhuǎn)時間 w=,1.725,6.875,13,五. 作業(yè)調(diào)度算法 2. 短作業(yè)優(yōu)先調(diào)度算法 (1) 策略：按作業(yè)請求運(yùn)行的時間長短進(jìn)行調(diào)度。 (2) 特點(diǎn)：易實(shí)現(xiàn)，系統(tǒng)吞吐量高；只照顧短作業(yè)，而沒有考慮長作業(yè)的利益易實(shí)現(xiàn)。 (3) 討論短作業(yè)優(yōu)先調(diào)度算法下的周轉(zhuǎn)時間與帶權(quán)周轉(zhuǎn)時間 作業(yè)

7、提交時間 執(zhí)行時間 開始時間 完成時間 周轉(zhuǎn)時間 帶權(quán)周轉(zhuǎn)時間 1 8.00 2.00 28.50 0.50 39.00 0.10 4 9.50 0.20,平均周轉(zhuǎn)時間 t = 平均帶權(quán)周轉(zhuǎn)時間 w=,1.55,5.15,8.00 10.00 2.00 1,10.30 10.80 2.30 4.6,10.00 10.10 1.10 11,10.10 10.30 0.80 4,14,3. 響應(yīng)比高者優(yōu)先調(diào)度算法 響應(yīng)比=響應(yīng)時間/ 執(zhí)行時間 =（等待時間+執(zhí)行時間）/ 執(zhí)行時間 =1+等待時間 /執(zhí)行時間 4. 優(yōu)先調(diào)度算法 優(yōu)先數(shù)：作業(yè)緩急程度、作業(yè)大小、等待時間長短、外設(shè)使用情況等,15,6

8、.3 進(jìn)程調(diào)度 一. 調(diào)度/分派結(jié)構(gòu) 1. 調(diào)度 在眾多處于就緒狀態(tài)的進(jìn)程中，按一定的原則選擇一個進(jìn)程。 2. 分派 當(dāng)處理機(jī)空閑時，是移出就緒隊(duì)列中第一個進(jìn)程，并賦予它使用處理機(jī)的權(quán)利。,16,3. 調(diào)度分派結(jié)構(gòu)圖,17,二. 進(jìn)程調(diào)度的功能 1. 記錄進(jìn)程的有關(guān)情況和狀態(tài)特征 2. 決定調(diào)度策略 優(yōu)先調(diào)度原則 進(jìn)程就緒隊(duì)列按進(jìn)程優(yōu)先級高低排序 先來先服務(wù)原則 進(jìn)程就緒隊(duì)列按進(jìn)程來到的先后次序排序 3. 實(shí)施處理機(jī)的分配和回收,18,三. 進(jìn)程調(diào)度方式 1. 什么是調(diào)度方式 當(dāng)一進(jìn)程正在處理機(jī)上執(zhí)行時，若有某個更為“重要而緊迫”的進(jìn)程需要進(jìn)行運(yùn)行，系統(tǒng)如何分配處理機(jī)。 2. 非剝奪方式 一種

9、是讓正在執(zhí)行的進(jìn)程繼續(xù)執(zhí)行，直到該進(jìn)程完成或發(fā)生某事件而進(jìn)入“完成”或“阻塞”狀態(tài)時，才把處理機(jī)分配給“重要而緊迫”的進(jìn)程。 3. 剝奪方式 當(dāng)“重要而緊迫”的進(jìn)程一到，便暫停正在執(zhí)行的進(jìn)程，立即把處理機(jī)分配給優(yōu)先級更高的進(jìn)程。,19,四. 進(jìn)程調(diào)度算法 1. 進(jìn)程優(yōu)先數(shù)調(diào)度算法 (1) 什么是進(jìn)程優(yōu)先數(shù)調(diào)度算法 預(yù)先確定各進(jìn)程的優(yōu)先數(shù)，系統(tǒng)把處理機(jī)的使用權(quán)賦予就緒隊(duì)列中具備最高優(yōu)先權(quán)(優(yōu)先數(shù)和一定的優(yōu)先級相對應(yīng))的就緒進(jìn)程。 (2) 優(yōu)先數(shù)的分類及確定 靜態(tài)優(yōu)先數(shù) * 在進(jìn)程被創(chuàng)建時確定，且一經(jīng)確定后在整個進(jìn)程運(yùn)行期間不再改變。,20,* 靜態(tài)優(yōu)先數(shù)的確定 優(yōu)先數(shù)根據(jù)進(jìn)程所需使用的資源來計算

10、 優(yōu)先數(shù)基于程序運(yùn)行時間的估計 優(yōu)先數(shù)基于進(jìn)程的類型 動態(tài)優(yōu)先數(shù) * 進(jìn)程優(yōu)先數(shù)在進(jìn)程運(yùn)行期間可以改變。 * 動態(tài)優(yōu)先數(shù)的確定 進(jìn)程使用CPU超過一定數(shù)值時，降低優(yōu)先數(shù)； 進(jìn)程進(jìn)行I/O操作后，增加優(yōu)先數(shù) 進(jìn)程等待時間超過一定數(shù)值時，提高優(yōu)先數(shù),21,2. 循環(huán)輪轉(zhuǎn)調(diào)度算法 (1) 什么是循環(huán)輪轉(zhuǎn)調(diào)度算法 當(dāng)CPU空閑時，選取就緒隊(duì)列首元素，賦予一個時間片，當(dāng)時間片用完時，該進(jìn)程轉(zhuǎn)為就緒態(tài)并進(jìn)入就緒隊(duì)列末端。 該隊(duì)列排序的原則是什么？,CPU,完成,22,(2) 簡單循環(huán)輪轉(zhuǎn)調(diào)度 就緒隊(duì)列中的所有進(jìn)程以等速度向前進(jìn)展 q = t/n t 為響應(yīng)時間，n為進(jìn)入系統(tǒng)的進(jìn)程數(shù)目。 q值如何確定? (

11、3) 循環(huán)輪轉(zhuǎn)調(diào)度算法的發(fā)展 可變時間片輪轉(zhuǎn)調(diào)度、多重時間片循環(huán)調(diào)度,23,五. 調(diào)度用的進(jìn)程調(diào)度變遷圖,24,1. 隊(duì)列結(jié)構(gòu) I/O等待隊(duì)列 一個進(jìn)程如果請求I/O，進(jìn)入I/O等待隊(duì)列 低優(yōu)先就緒隊(duì)列 一個進(jìn)程如果在運(yùn)行中超過了它的時間量，進(jìn)入低優(yōu)先就緒隊(duì)列 高優(yōu)先就緒隊(duì)列 當(dāng)進(jìn)程從等待狀態(tài)變?yōu)榫途w狀態(tài)時，進(jìn)入高優(yōu)先就緒隊(duì)列 2. 進(jìn)程調(diào)度算法 優(yōu)先調(diào)度與時間片調(diào)度相結(jié)合的調(diào)度策略,25,(1) 當(dāng)CPU空閑時，若高優(yōu)先就緒隊(duì)列非空，則從高優(yōu)先就緒隊(duì)列中選擇一個進(jìn)程運(yùn)行，分配時間片為100ms。 (2) 當(dāng)CPU空閑時，若高優(yōu)先就緒隊(duì)列為空，則從低優(yōu)先就緒隊(duì)列中選擇一個進(jìn)程運(yùn)行，分配時間片為500ms。 3. 調(diào)度效果 優(yōu)先照顧了IO量大的進(jìn)程； 適當(dāng)照顧了計算量大的進(jìn)程。,26,第六章 小結(jié) 一. 處理機(jī)的兩級調(diào)度 二. 作業(yè)調(diào)度 1. 作業(yè)的四種狀態(tài) 2. 作業(yè)控制塊 3. 周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間：定義 物理意義