1、1 6.1 6.2 6.3 6.4 UNIX系統(tǒng)的進(jìn)程調(diào)度系統(tǒng)的進(jìn)程調(diào)度第六章第六章 處理機(jī)調(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)度批處理系統(tǒng)中的處理機(jī)調(diào)度 處理機(jī)調(diào)度分為兩級(jí)：作業(yè)調(diào)度和進(jìn)程調(diào)度。 1. 作業(yè)調(diào)度作業(yè)調(diào)度 作業(yè)調(diào)度又稱為宏觀調(diào)度。 任務(wù)任務(wù)對(duì)存放在輔存設(shè)備上的大量作業(yè)，以一定的策略進(jìn)行挑選，分配主存等必要的資源，建立作業(yè)對(duì)應(yīng)的進(jìn)程，使其投入運(yùn)行。 2. 進(jìn)程調(diào)度進(jìn)程調(diào)度 進(jìn)程調(diào)度又稱為微

2、觀調(diào)度 。 任務(wù)任務(wù)對(duì)進(jìn)入主存的所有進(jìn)程，確定哪個(gè)進(jìn)程在什么時(shí)候獲得處理機(jī)，使用多長時(shí)間。 4 三三. 多任務(wù)操作系統(tǒng)中的處理機(jī)調(diào)度多任務(wù)操作系統(tǒng)中的處理機(jī)調(diào)度 在分時(shí)系統(tǒng)或支持多任務(wù)并發(fā)執(zhí)行個(gè)人計(jì)算機(jī)操作系統(tǒng)中，系統(tǒng)將用戶提交的任務(wù)處理為進(jìn)程，一個(gè)進(jìn)程又可以創(chuàng)建多個(gè)子進(jìn)程，形成可以并發(fā)執(zhí)行的多進(jìn)程。 進(jìn)程調(diào)度的任務(wù)是：當(dāng)處理機(jī)空閑時(shí)，以某種策略選擇一個(gè)就緒進(jìn)程去運(yùn)行，并分配處理機(jī)的時(shí)間。 5 四四. 多線程操作系統(tǒng)中的處理機(jī)調(diào)度多線程操作系統(tǒng)中的處理機(jī)調(diào)度 在支持多線程運(yùn)行的系統(tǒng)中，一個(gè)進(jìn)程可以創(chuàng)建一個(gè)線程，也可以創(chuàng)建多個(gè)線程。系統(tǒng)為進(jìn)程分配它所需要的資源，而處理機(jī)的分配單位則為線程。 系統(tǒng)

3、提供線程調(diào)度程序，其功能是當(dāng)處理機(jī)空閑時(shí)，以某種策略選擇一個(gè)就緒線程去運(yùn)行，并分配處理機(jī)時(shí)間。 6 一一. 作業(yè)的狀態(tài)作業(yè)的狀態(tài)作業(yè)在整個(gè)活動(dòng)期間一共有四種狀態(tài)， 提交狀態(tài)：用戶將自己的程序和數(shù)據(jù)提交給系統(tǒng)，等待輸入。后備狀態(tài)：作業(yè)已存放在磁盤上，等待調(diào)度。執(zhí)行狀態(tài)：作業(yè)進(jìn)入主存開始運(yùn)行，到作業(yè)計(jì)算完成為止。 完成狀態(tài)：作業(yè)計(jì)算完成開始，到善后處理完成并退出系統(tǒng)為止。 7運(yùn)行就緒完成等待后備提交作業(yè)調(diào)度作業(yè)調(diào)度作業(yè)錄入執(zhí)行8 二二. 作業(yè)調(diào)度的功能作業(yè)調(diào)度的功能 1. 確定數(shù)據(jù)結(jié)構(gòu)確定數(shù)據(jù)結(jié)構(gòu) 建立作業(yè)控制塊jcb (job control block)。 作業(yè)控制塊記錄了每個(gè)作業(yè)類型、狀態(tài)、

4、資源請(qǐng)求及分配情況 。 2. 確定調(diào)度策略與調(diào)度算法確定調(diào)度策略與調(diào)度算法 3. 分配資源分配資源 為選中的作業(yè)分配所需要的系統(tǒng)資源。 4. 善后處理善后處理 收回該作業(yè)所占用的全部資源，撤消作業(yè)控制塊以及與該作業(yè)有關(guān)的全部進(jìn)程。 9 三三. 作業(yè)控制塊作業(yè)控制塊 作業(yè)控制塊jcb存在于系統(tǒng)的整個(gè)過程中，jcb是一個(gè)作業(yè)存在的標(biāo)志。jcb的主要內(nèi)容如下： 作作 業(yè)業(yè) 名名 資資 源源 要要 求求 資資 源源 使使 用用 情況情況 估計(jì)執(zhí)行時(shí)間 進(jìn)入系統(tǒng)時(shí)間 最遲完成時(shí)間 開始執(zhí)行時(shí)間 要求的主存量 已執(zhí)行時(shí)間 要求外設(shè)的類型及臺(tái)數(shù) 主存地址 要求文件量和輸出量 外設(shè)臺(tái)號(hào) 類類 型型 優(yōu)優(yōu) 先先

5、 級(jí)級(jí) 控制方式 狀狀 態(tài)態(tài) 作業(yè)類型 10 四四. 作業(yè)調(diào)度算法性能的衡量作業(yè)調(diào)度算法性能的衡量 采用平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間來衡量作業(yè)調(diào)度算法性能的好壞。 1. 周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間 一個(gè)作業(yè)提交給計(jì)算機(jī)系統(tǒng)到該作業(yè)的結(jié)果返回給用戶所需要的時(shí)間。 (1) 定義定義 ti = tci - tsi ti作業(yè)i的周轉(zhuǎn)時(shí)間 tsi作業(yè)i的提交時(shí)間， tci作業(yè)i的完成時(shí)間。 (2) 意義意義 說明作業(yè)i在系統(tǒng)中停留時(shí)間的長短。 (3)平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間 t = niti1n111 2. 帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間 (1) 定義定義 一個(gè)作業(yè)的周轉(zhuǎn)時(shí)間與其運(yùn)行時(shí)間的比值。 wi = tri為作

6、業(yè)i的實(shí)際執(zhí)行時(shí)間 (2) 意義意義 說明作業(yè)i在系統(tǒng)中相對(duì)等待時(shí)間。 (3) 平均帶權(quán)周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間 w= tritiniwi1n112 五五. 作業(yè)調(diào)度算法作業(yè)調(diào)度算法 1. 先來先服務(wù)調(diào)度算法先來先服務(wù)調(diào)度算法(FCFS) (1) 策略：按作業(yè)來到的先后次序進(jìn)行調(diào)度。 (2) 特點(diǎn)： 簡(jiǎn)單，易實(shí)現(xiàn)。 (3) 討論在先來先服調(diào)度算法下的周轉(zhuǎn)時(shí)間與帶權(quán)周轉(zhuǎn)時(shí)間 作業(yè) 提交時(shí)間 執(zhí)行時(shí)間 開始時(shí)間 完成時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間 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

7、.00 4 10.50 10.60 1.60 16 10.60 10.80 1.30 6.5 平均周轉(zhuǎn)時(shí)間 t = 平均帶權(quán)周轉(zhuǎn)時(shí)間 w=1.7256.87513 五五. 作業(yè)調(diào)度算法作業(yè)調(diào)度算法 2. 短作業(yè)優(yōu)先調(diào)度算法短作業(yè)優(yōu)先調(diào)度算法 (1) 策略：按作業(yè)請(qǐng)求運(yùn)行的時(shí)間長短進(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)時(shí)間與帶權(quán)周轉(zhuǎn)時(shí)間 作業(yè) 提交時(shí)間 執(zhí)行時(shí)間 開始時(shí)間 完成時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間 1 8.00 2.00 28.50 0.50 39.00 0.10 4 9.50 0.20 平均周

8、轉(zhuǎn)時(shí)間 t = 平均帶權(quán)周轉(zhuǎn)時(shí)間 w=1.555.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 143. 響應(yīng)比高者優(yōu)先調(diào)度算法響應(yīng)比高者優(yōu)先調(diào)度算法 響應(yīng)比=響應(yīng)時(shí)間/ 執(zhí)行時(shí)間 =（等待時(shí)間+執(zhí)行時(shí)間）/ 執(zhí)行時(shí)間 =1+等待時(shí)間 /執(zhí)行時(shí)間4. 優(yōu)先調(diào)度算法優(yōu)先調(diào)度算法 優(yōu)先數(shù)：作業(yè)緩急程度、作業(yè)大小、等待時(shí)間長短、外設(shè)使用情況等15 一一. 調(diào)度調(diào)度/分派結(jié)構(gòu)分派結(jié)構(gòu) 1. 調(diào)度調(diào)度 在眾多處于就緒狀態(tài)的進(jìn)程中，按一定的原則選擇一個(gè)進(jìn)程。 2. 分派分派 當(dāng)處理機(jī)空閑時(shí)，

9、是移出就緒隊(duì)列中第一個(gè)進(jìn)程，并賦予它使用處理機(jī)的權(quán)利。 16 3. 調(diào)度調(diào)度分派結(jié)構(gòu)圖分派結(jié)構(gòu)圖 ready_q scheduler susp wakeup receive Lpcb6Lpcb4pcb3pcb2pcb1 dispatcher CPU17 二二. 進(jìn)程調(diào)度的功能進(jìn)程調(diào)度的功能 1. 記錄進(jìn)程的有關(guān)情況和狀態(tài)特征記錄進(jìn)程的有關(guān)情況和狀態(tài)特征 2. 決定調(diào)度策略決定調(diào)度策略 優(yōu)先調(diào)度原則優(yōu)先調(diào)度原則 進(jìn)程就緒隊(duì)列按進(jìn)程優(yōu)先級(jí)高低排序 先來先服務(wù)原則先來先服務(wù)原則 進(jìn)程就緒隊(duì)列按進(jìn)程來到的先后次序排序 3. 實(shí)施處理機(jī)的分配和回收實(shí)施處理機(jī)的分配和回收 18 三三. 進(jìn)程調(diào)度方式進(jìn)程調(diào)

10、度方式 1. 什么是調(diào)度方式什么是調(diào)度方式 當(dāng)一進(jìn)程正在處理機(jī)上執(zhí)行時(shí)，若有某個(gè)更為“重要而緊迫”的進(jìn)程需要進(jìn)行運(yùn)行，系統(tǒng)如何分配處理機(jī)。 2. 非剝奪方式非剝奪方式 一種是讓正在執(zhí)行的進(jìn)程繼續(xù)執(zhí)行，直到該進(jìn)程完成或發(fā)生某事件而進(jìn)入“完成”或“阻塞”狀態(tài)時(shí)，才把處理機(jī)分配給“重要而緊迫”的進(jìn)程。 3. 剝奪方式剝奪方式 當(dāng)“重要而緊迫”的進(jìn)程一到，便暫停正在執(zhí)行的進(jìn)程，立即把處理機(jī)分配給優(yōu)先級(jí)更高的進(jìn)程。 19 四四. 進(jìn)程調(diào)度算法進(jìn)程調(diào)度算法 1. 進(jìn)程優(yōu)先數(shù)調(diào)度算法進(jìn)程優(yōu)先數(shù)調(diào)度算法 (1) 什么是進(jìn)程優(yōu)先數(shù)調(diào)度算法什么是進(jìn)程優(yōu)先數(shù)調(diào)度算法 預(yù)先確定各進(jìn)程的優(yōu)先數(shù)，系統(tǒng)把處理機(jī)的使用權(quán)賦予

11、就緒隊(duì)列中具備最高優(yōu)先權(quán)(優(yōu)先數(shù)和一定的優(yōu)先級(jí)相對(duì)應(yīng))的就緒進(jìn)程。 (2) 優(yōu)先數(shù)的分類及確定優(yōu)先數(shù)的分類及確定 靜態(tài)優(yōu)先數(shù) * 在進(jìn)程被創(chuàng)建時(shí)確定，且一經(jīng)確定后在整個(gè)進(jìn)程運(yùn)行期間不再改變。20 * 靜態(tài)優(yōu)先數(shù)的確定 優(yōu)先數(shù)根據(jù)進(jìn)程所需使用的資源來計(jì)算 優(yōu)先數(shù)基于程序運(yùn)行時(shí)間的估計(jì) 優(yōu)先數(shù)基于進(jìn)程的類型 動(dòng)態(tài)優(yōu)先數(shù) * 進(jìn)程優(yōu)先數(shù)在進(jìn)程運(yùn)行期間可以改變。 * 動(dòng)態(tài)優(yōu)先數(shù)的確定 進(jìn)程使用CPU超過一定數(shù)值時(shí)，降低優(yōu)先數(shù)； 進(jìn)程進(jìn)行I/O操作后，增加優(yōu)先數(shù) 進(jìn)程等待時(shí)間超過一定數(shù)值時(shí)，提高優(yōu)先數(shù)21 2. 循環(huán)輪轉(zhuǎn)調(diào)度算法循環(huán)輪轉(zhuǎn)調(diào)度算法 (1) 什么是循環(huán)輪轉(zhuǎn)調(diào)度算法什么是循環(huán)輪轉(zhuǎn)調(diào)度算法 當(dāng)C

12、PU空閑時(shí)，選取就緒隊(duì)列首元素，賦予一個(gè)時(shí)間片，當(dāng)時(shí)間片用完時(shí)，該進(jìn)程轉(zhuǎn)為就緒態(tài)并進(jìn)入就緒隊(duì)列末端。 該隊(duì)列排序的原則是什么？該隊(duì)列排序的原則是什么？ pcb1pcb2pcbnCPU完成22 (2) 簡(jiǎn)單循環(huán)輪轉(zhuǎn)調(diào)度簡(jiǎn)單循環(huán)輪轉(zhuǎn)調(diào)度 就緒隊(duì)列中的所有進(jìn)程以等速度向前進(jìn)展 q = t/n t 為響應(yīng)時(shí)間，n為進(jìn)入系統(tǒng)的進(jìn)程數(shù)目。 q值如何確定? (3) 循環(huán)輪轉(zhuǎn)調(diào)度算法的發(fā)展循環(huán)輪轉(zhuǎn)調(diào)度算法的發(fā)展 可變時(shí)間片輪轉(zhuǎn)調(diào)度、多重時(shí)間片循環(huán)調(diào)度23 五五. 調(diào)度用的進(jìn)程調(diào)度變遷圖調(diào)度用的進(jìn)程調(diào)度變遷圖運(yùn)行500ms100ms因 IO而等待高優(yōu)先 就緒 低優(yōu)先 就緒進(jìn)程調(diào)度進(jìn)程調(diào)度時(shí)間片到請(qǐng)求I/OI/O

13、完成24 1. 隊(duì)列結(jié)構(gòu)隊(duì)列結(jié)構(gòu) I/O等待隊(duì)列 一個(gè)進(jìn)程如果請(qǐng)求I/O，進(jìn)入I/O等待隊(duì)列 低優(yōu)先就緒隊(duì)列 一個(gè)進(jìn)程如果在運(yùn)行中超過了它的時(shí)間量，進(jìn)入低優(yōu)先就緒隊(duì)列 高優(yōu)先就緒隊(duì)列 當(dāng)進(jìn)程從等待狀態(tài)變?yōu)榫途w狀態(tài)時(shí)，進(jìn)入高優(yōu)先就緒隊(duì)列 2. 進(jìn)程調(diào)度算法進(jìn)程調(diào)度算法 優(yōu)先調(diào)度與時(shí)間片調(diào)度相結(jié)合的調(diào)度策略25 (1) 當(dāng)CPU空閑時(shí)，若高優(yōu)先就緒隊(duì)列非空，則從高優(yōu)先就緒隊(duì)列中選擇一個(gè)進(jìn)程運(yùn)行，分配時(shí)間片為100ms。 (2) 當(dāng)CPU空閑時(shí)，若高優(yōu)先就緒隊(duì)列為空，則從低優(yōu)先就緒隊(duì)列中選擇一個(gè)進(jìn)程運(yùn)行，分配時(shí)間片為500ms。 3. 調(diào)度效果調(diào)度效果 優(yōu)先照顧了IO量大的進(jìn)程； 適當(dāng)照顧了計(jì)算量大的進(jìn)程。26 第六章第六章 小結(jié)小結(jié)一. 處理機(jī)的兩級(jí)調(diào)度 二. 作業(yè)調(diào)度 1. 作業(yè)的四種狀態(tài) 2