2014.10.15操作系統(tǒng)第4章PPT課件

1、衡量調(diào)度策略的最常用的幾個(gè)指標(biāo)是：衡量調(diào)度策略的最常用的幾個(gè)指標(biāo)是：周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間:周轉(zhuǎn)時(shí)間是指將一個(gè)作業(yè)提交給計(jì)算機(jī)周轉(zhuǎn)時(shí)間是指將一個(gè)作業(yè)提交給計(jì)算機(jī)系統(tǒng)后到該作業(yè)的結(jié)果返回給用戶所需要的時(shí)間。系統(tǒng)后到該作業(yè)的結(jié)果返回給用戶所需要的時(shí)間。吞吐率吞吐率:吞吐率是指在給定的時(shí)間內(nèi)，一個(gè)計(jì)算機(jī)吞吐率是指在給定的時(shí)間內(nèi)，一個(gè)計(jì)算機(jī)系統(tǒng)所完成的總工作量。系統(tǒng)所完成的總工作量。響應(yīng)時(shí)間響應(yīng)時(shí)間:響應(yīng)時(shí)間則是指從用戶向計(jì)算機(jī)發(fā)出一響應(yīng)時(shí)間則是指從用戶向計(jì)算機(jī)發(fā)出一個(gè)命令到計(jì)算機(jī)把相應(yīng)的執(zhí)行結(jié)果返回給用戶所個(gè)命令到計(jì)算機(jī)把相應(yīng)的執(zhí)行結(jié)果返回給用戶所需要的時(shí)間。需要的時(shí)間。設(shè)備利用率設(shè)備利用率:設(shè)備利用率主

2、要指輸入輸出設(shè)備的使設(shè)備利用率主要指輸入輸出設(shè)備的使用情況。用情況。第1頁(yè)/共37頁(yè)圖圖4.1 作業(yè)的狀態(tài)及其轉(zhuǎn)換作業(yè)的狀態(tài)及其轉(zhuǎn)換4.1 分 級(jí) 調(diào) 度4.1.1 作業(yè)的狀態(tài)及其轉(zhuǎn)換第2頁(yè)/共37頁(yè)(1) 作業(yè)調(diào)度：又稱宏觀調(diào)度，或高級(jí)調(diào)度。作業(yè)調(diào)度：又稱宏觀調(diào)度，或高級(jí)調(diào)度。 (2) 交換調(diào)度：又稱中級(jí)調(diào)度。交換調(diào)度：又稱中級(jí)調(diào)度。(3) 進(jìn)程調(diào)度：又稱微觀調(diào)度或低級(jí)調(diào)度。進(jìn)程調(diào)度：又稱微觀調(diào)度或低級(jí)調(diào)度。 (4) 線程調(diào)度。線程調(diào)度。4.1.2 調(diào)度的層次第3頁(yè)/共37頁(yè)4.1.3 作業(yè)與進(jìn)程的關(guān)系作業(yè)與進(jìn)程的關(guān)系1.作業(yè)可被看作是用戶向計(jì)算機(jī)提交任務(wù)的任務(wù)作業(yè)可被看作是用戶向計(jì)算機(jī)提交

3、任務(wù)的任務(wù)實(shí)體，進(jìn)程則是計(jì)算機(jī)為了完成用戶任務(wù)實(shí)體而實(shí)體，進(jìn)程則是計(jì)算機(jī)為了完成用戶任務(wù)實(shí)體而設(shè)置的執(zhí)行實(shí)體，是系統(tǒng)分配資源的基本單位。設(shè)置的執(zhí)行實(shí)體，是系統(tǒng)分配資源的基本單位。2.一個(gè)作業(yè)總是由一個(gè)以上的多個(gè)進(jìn)程組成的。一個(gè)作業(yè)總是由一個(gè)以上的多個(gè)進(jìn)程組成的。3.作業(yè)的概念主要用在批處理系統(tǒng)中。而進(jìn)程的作業(yè)的概念主要用在批處理系統(tǒng)中。而進(jìn)程的概念則用在幾乎所有的多道系統(tǒng)中概念則用在幾乎所有的多道系統(tǒng)中第4頁(yè)/共37頁(yè)4.2 作作 業(yè)業(yè) 調(diào)調(diào) 度度作業(yè)調(diào)度主要是完成作業(yè)從后備狀態(tài)到執(zhí)行狀態(tài)作業(yè)調(diào)度主要是完成作業(yè)從后備狀態(tài)到執(zhí)行狀態(tài)的轉(zhuǎn)變，以及從執(zhí)行狀態(tài)到完成狀態(tài)的轉(zhuǎn)變。的轉(zhuǎn)變，以及從執(zhí)行狀態(tài)到

4、完成狀態(tài)的轉(zhuǎn)變。4.2.1 作業(yè)調(diào)度功能作業(yè)調(diào)度功能(1) 記錄系統(tǒng)中各作業(yè)的狀況。記錄系統(tǒng)中各作業(yè)的狀況。 系統(tǒng)通過(guò)系統(tǒng)通過(guò)JCB而感知作業(yè)的存在。而感知作業(yè)的存在。作業(yè)名作業(yè)名作業(yè)類型作業(yè)類型資源要求資源要求資源使用情況資源使用情況優(yōu)先級(jí)優(yōu)先級(jí)(數(shù)數(shù))當(dāng)前狀態(tài)當(dāng)前狀態(tài)其他其他第5頁(yè)/共37頁(yè)(2) 從后備隊(duì)列中挑選出一部分作業(yè)投入執(zhí)行。作從后備隊(duì)列中挑選出一部分作業(yè)投入執(zhí)行。作業(yè)調(diào)度程序根據(jù)選定的調(diào)度算法，從后備作業(yè)隊(duì)業(yè)調(diào)度程序根據(jù)選定的調(diào)度算法，從后備作業(yè)隊(duì)列中挑選出若干作業(yè)去投入執(zhí)行。列中挑選出若干作業(yè)去投入執(zhí)行。(3) 為被選中作業(yè)做好執(zhí)行前的準(zhǔn)備工作。作業(yè)調(diào)為被選中作業(yè)做好執(zhí)行前的

5、準(zhǔn)備工作。作業(yè)調(diào)度程序?yàn)檫x中的作業(yè)建立相應(yīng)的進(jìn)程，并為這些度程序?yàn)檫x中的作業(yè)建立相應(yīng)的進(jìn)程，并為這些進(jìn)程分配它們所需要的系統(tǒng)資源進(jìn)程分配它們所需要的系統(tǒng)資源.(4) 在作業(yè)執(zhí)行結(jié)束時(shí)做善后處理工作。在作業(yè)執(zhí)行結(jié)束時(shí)做善后處理工作。第6頁(yè)/共37頁(yè)圖圖4.3 作業(yè)調(diào)度中狀態(tài)的轉(zhuǎn)換過(guò)程作業(yè)調(diào)度中狀態(tài)的轉(zhuǎn)換過(guò)程第7頁(yè)/共37頁(yè)4.2.2 作業(yè)調(diào)度目標(biāo)與性能衡量作業(yè)調(diào)度目標(biāo)與性能衡量調(diào)度目標(biāo)主要是以下調(diào)度目標(biāo)主要是以下4點(diǎn)：點(diǎn)：(1) 對(duì)所有作業(yè)應(yīng)該是公平合理的；對(duì)所有作業(yè)應(yīng)該是公平合理的；(2) 應(yīng)使設(shè)備有高的利用率；應(yīng)使設(shè)備有高的利用率；(3) 每天執(zhí)行盡可能多的作業(yè)；每天執(zhí)行盡可能多的作業(yè)；(4

6、) 有快的響應(yīng)時(shí)間。有快的響應(yīng)時(shí)間。第8頁(yè)/共37頁(yè)1. 周轉(zhuǎn)時(shí)間：周轉(zhuǎn)時(shí)間：作業(yè)作業(yè)i的周轉(zhuǎn)時(shí)間的周轉(zhuǎn)時(shí)間Ti為為T(mén)i=Tei-Tsi其中其中Tei為作業(yè)為作業(yè)i的完成時(shí)間，的完成時(shí)間，Tsi為作業(yè)的提交時(shí)間。為作業(yè)的提交時(shí)間。對(duì)于被測(cè)定作業(yè)流所含有的對(duì)于被測(cè)定作業(yè)流所含有的n（n=1）個(gè)作業(yè)來(lái)）個(gè)作業(yè)來(lái)說(shuō)，其平均周轉(zhuǎn)時(shí)間為：說(shuō)，其平均周轉(zhuǎn)時(shí)間為：一個(gè)作業(yè)的周轉(zhuǎn)時(shí)間說(shuō)明了該作業(yè)在系統(tǒng)內(nèi)停留一個(gè)作業(yè)的周轉(zhuǎn)時(shí)間說(shuō)明了該作業(yè)在系統(tǒng)內(nèi)停留的時(shí)間，包含兩部分：等待時(shí)間；執(zhí)行時(shí)間，即：的時(shí)間，包含兩部分：等待時(shí)間；執(zhí)行時(shí)間，即：Ti=TwiTri這里，這里，Twi主要指作業(yè)主要指作業(yè)i由后備狀態(tài)到執(zhí)行狀

7、態(tài)的等由后備狀態(tài)到執(zhí)行狀態(tài)的等待時(shí)間，它不包括作業(yè)進(jìn)入執(zhí)行狀態(tài)后的等待時(shí)待時(shí)間，它不包括作業(yè)進(jìn)入執(zhí)行狀態(tài)后的等待時(shí)間。間。nii = 11T =Tn第9頁(yè)/共37頁(yè)2. 帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間作業(yè)的周轉(zhuǎn)時(shí)間包含了兩個(gè)部分，即等待時(shí)間和作業(yè)的周轉(zhuǎn)時(shí)間包含了兩個(gè)部分，即等待時(shí)間和執(zhí)行時(shí)間。帶權(quán)周轉(zhuǎn)時(shí)間是作業(yè)周轉(zhuǎn)時(shí)間與作業(yè)執(zhí)行時(shí)間。帶權(quán)周轉(zhuǎn)時(shí)間是作業(yè)周轉(zhuǎn)時(shí)間與作業(yè)執(zhí)行時(shí)間的比：執(zhí)行時(shí)間的比：Wi=Ti/Tri對(duì)于被測(cè)定作業(yè)流所含有的幾個(gè)作業(yè)來(lái)說(shuō)，其平對(duì)于被測(cè)定作業(yè)流所含有的幾個(gè)作業(yè)來(lái)說(shuō)，其平均帶權(quán)周轉(zhuǎn)時(shí)間為：均帶權(quán)周轉(zhuǎn)時(shí)間為：nii= 11W =Wn第10頁(yè)/共37頁(yè)4.3.1 進(jìn)程調(diào)度的功能進(jìn)程

8、調(diào)度的功能進(jìn)程調(diào)度的具體功能可總結(jié)如下：進(jìn)程調(diào)度的具體功能可總結(jié)如下：(1) 記錄系統(tǒng)中所有進(jìn)程的執(zhí)行情況記錄系統(tǒng)中所有進(jìn)程的執(zhí)行情況(2) 選擇占有處理機(jī)的進(jìn)程選擇占有處理機(jī)的進(jìn)程(3) 進(jìn)行進(jìn)程上下文切換進(jìn)行進(jìn)程上下文切換4.3 進(jìn) 程 調(diào) 度第11頁(yè)/共37頁(yè)4.3.2 進(jìn)程調(diào)度的時(shí)機(jī)進(jìn)程調(diào)度的時(shí)機(jī)引起進(jìn)程調(diào)度的原因有以下幾類：引起進(jìn)程調(diào)度的原因有以下幾類：正在執(zhí)行的進(jìn)程執(zhí)行完畢。正在執(zhí)行的進(jìn)程執(zhí)行完畢。 (2) 執(zhí)行中進(jìn)程自己調(diào)用阻塞原語(yǔ)將自己阻塞起來(lái)進(jìn)入睡執(zhí)行中進(jìn)程自己調(diào)用阻塞原語(yǔ)將自己阻塞起來(lái)進(jìn)入睡眠等待狀態(tài)。眠等待狀態(tài)。(3) 執(zhí)行中進(jìn)程調(diào)用了執(zhí)行中進(jìn)程調(diào)用了P原語(yǔ)操作，從而因資

9、源不足而被阻原語(yǔ)操作，從而因資源不足而被阻塞；或調(diào)用了塞；或調(diào)用了V原語(yǔ)操作激活了等待資源的進(jìn)程隊(duì)列。原語(yǔ)操作激活了等待資源的進(jìn)程隊(duì)列。(4) 執(zhí)行中進(jìn)程提出執(zhí)行中進(jìn)程提出IO請(qǐng)求后被阻塞。請(qǐng)求后被阻塞。(5) 在分時(shí)系統(tǒng)中時(shí)間片已經(jīng)用完。在分時(shí)系統(tǒng)中時(shí)間片已經(jīng)用完。(6) 在執(zhí)行完系統(tǒng)調(diào)用，在系統(tǒng)程序返回用戶進(jìn)程時(shí)，可在執(zhí)行完系統(tǒng)調(diào)用，在系統(tǒng)程序返回用戶進(jìn)程時(shí)，可認(rèn)為系統(tǒng)進(jìn)程執(zhí)行完畢，從而可調(diào)度選擇一新的用戶認(rèn)為系統(tǒng)進(jìn)程執(zhí)行完畢，從而可調(diào)度選擇一新的用戶進(jìn)程執(zhí)行。進(jìn)程執(zhí)行。(7) 就緒隊(duì)列中的某進(jìn)程的優(yōu)先級(jí)變得高于當(dāng)前執(zhí)行進(jìn)程就緒隊(duì)列中的某進(jìn)程的優(yōu)先級(jí)變得高于當(dāng)前執(zhí)行進(jìn)程的優(yōu)先級(jí)，從而也將引

10、發(fā)進(jìn)程調(diào)度。的優(yōu)先級(jí)，從而也將引發(fā)進(jìn)程調(diào)度。第12頁(yè)/共37頁(yè)4.3.3 進(jìn)程上下文切換進(jìn)程上下文切換進(jìn)程上下文由正文段、數(shù)據(jù)段、硬件寄存器的內(nèi)進(jìn)程上下文由正文段、數(shù)據(jù)段、硬件寄存器的內(nèi)容以及有關(guān)數(shù)據(jù)結(jié)構(gòu)等組成。容以及有關(guān)數(shù)據(jù)結(jié)構(gòu)等組成。進(jìn)程上下文切換包括進(jìn)程上下文切換包括4個(gè)步驟：個(gè)步驟：(1) 決定是否做上下文切換以及是否允許做上下文決定是否做上下文切換以及是否允許做上下文切換。切換。(2) 保存當(dāng)前執(zhí)行進(jìn)程的上下文。保存當(dāng)前執(zhí)行進(jìn)程的上下文。 (3) 使用進(jìn)程調(diào)度算法，選擇一個(gè)處于就緒狀態(tài)進(jìn)使用進(jìn)程調(diào)度算法，選擇一個(gè)處于就緒狀態(tài)進(jìn)程。程。(4) 恢復(fù)或裝配所選進(jìn)程的上下文，將恢復(fù)或裝配所

11、選進(jìn)程的上下文，將CPU控制權(quán)控制權(quán)交給所選進(jìn)程。交給所選進(jìn)程。第13頁(yè)/共37頁(yè)進(jìn)程調(diào)度性能的衡量方法可分為定性和定量?jī)煞N。進(jìn)程調(diào)度性能的衡量方法可分為定性和定量?jī)煞N。定性衡量方面，調(diào)度的可靠性定性衡量方面，調(diào)度的可靠性,簡(jiǎn)潔性簡(jiǎn)潔性進(jìn)程調(diào)度的定量評(píng)價(jià)包括進(jìn)程調(diào)度的定量評(píng)價(jià)包括CPU的利用率評(píng)價(jià)、進(jìn)程的利用率評(píng)價(jià)、進(jìn)程在就緒隊(duì)列中的等待時(shí)間與執(zhí)行時(shí)間之比等。實(shí)在就緒隊(duì)列中的等待時(shí)間與執(zhí)行時(shí)間之比等。實(shí)際上，由于進(jìn)程進(jìn)入就緒隊(duì)列的隨機(jī)模型很難確際上，由于進(jìn)程進(jìn)入就緒隊(duì)列的隨機(jī)模型很難確定，而且進(jìn)程上下文切換等也將影響進(jìn)程的執(zhí)行定，而且進(jìn)程上下文切換等也將影響進(jìn)程的執(zhí)行效率，從而對(duì)進(jìn)程調(diào)度進(jìn)行解

12、析是很困難的。一效率，從而對(duì)進(jìn)程調(diào)度進(jìn)行解析是很困難的。一般情況下，大多利用模擬或測(cè)試系統(tǒng)響應(yīng)時(shí)間的般情況下，大多利用模擬或測(cè)試系統(tǒng)響應(yīng)時(shí)間的方法來(lái)評(píng)價(jià)進(jìn)程調(diào)度的性能。方法來(lái)評(píng)價(jià)進(jìn)程調(diào)度的性能。4.3.4 進(jìn)程調(diào)度性能評(píng)價(jià)第14頁(yè)/共37頁(yè)4.4 調(diào)調(diào) 度度 算算 法法進(jìn)程調(diào)度算法進(jìn)程調(diào)度算法:先來(lái)先服務(wù)（先來(lái)先服務(wù)（FCFS）調(diào)度算法調(diào)度算法2. 輪轉(zhuǎn)法（輪轉(zhuǎn)法（round robin）時(shí)間片長(zhǎng)度的選擇是根據(jù)系統(tǒng)對(duì)響應(yīng)時(shí)間的要求時(shí)間片長(zhǎng)度的選擇是根據(jù)系統(tǒng)對(duì)響應(yīng)時(shí)間的要求R和就緒隊(duì)列中所允許的最大進(jìn)程數(shù)和就緒隊(duì)列中所允許的最大進(jìn)程數(shù)Nmax確定確定的。它可表示為：的。它可表示為： q=R/Nm

13、ax思考思考:時(shí)間片長(zhǎng)度選取不當(dāng)?shù)挠绊憰r(shí)間片長(zhǎng)度選取不當(dāng)?shù)挠绊?第15頁(yè)/共37頁(yè)3. 多級(jí)反饋輪轉(zhuǎn)法多級(jí)反饋輪轉(zhuǎn)法思考思考:加入到就緒隊(duì)列的進(jìn)程有幾種情況加入到就緒隊(duì)列的進(jìn)程有幾種情況?如果對(duì)這些進(jìn)程區(qū)別對(duì)待，給予不同的優(yōu)先級(jí)和如果對(duì)這些進(jìn)程區(qū)別對(duì)待，給予不同的優(yōu)先級(jí)和時(shí)間片時(shí)間片,每個(gè)隊(duì)列按每個(gè)隊(duì)列按FCFS原則排列，各隊(duì)列之間原則排列，各隊(duì)列之間的進(jìn)程享有不同的優(yōu)先級(jí)，但同一隊(duì)列內(nèi)優(yōu)先級(jí)的進(jìn)程享有不同的優(yōu)先級(jí)，但同一隊(duì)列內(nèi)優(yōu)先級(jí)相同。不同進(jìn)程進(jìn)入不同的就緒隊(duì)列。相同。不同進(jìn)程進(jìn)入不同的就緒隊(duì)列。例如：線性優(yōu)先級(jí)調(diào)度策略（例如：線性優(yōu)先級(jí)調(diào)度策略（selfish round robin）線

14、性優(yōu)先級(jí)調(diào)度策略采用如下方式，即新創(chuàng)建的線性優(yōu)先級(jí)調(diào)度策略采用如下方式，即新創(chuàng)建的進(jìn)程按進(jìn)程按FCFS方式排成就緒隊(duì)列，而其他已得到方式排成就緒隊(duì)列，而其他已得到過(guò)時(shí)間片服務(wù)的進(jìn)程也按過(guò)時(shí)間片服務(wù)的進(jìn)程也按FCFS方式排成另一個(gè)方式排成另一個(gè)就緒隊(duì)列或稱享受服務(wù)隊(duì)列就緒隊(duì)列或稱享受服務(wù)隊(duì)列(圖）。圖）。第16頁(yè)/共37頁(yè)圖圖4.5 線性優(yōu)先級(jí)調(diào)度線性優(yōu)先級(jí)調(diào)度新創(chuàng)建進(jìn)程就緒隊(duì)列優(yōu)先級(jí)新創(chuàng)建進(jìn)程就緒隊(duì)列優(yōu)先級(jí)P以以P=a*t (a0)的速的速率增加。率增加。享受服務(wù)隊(duì)列中進(jìn)程的優(yōu)先級(jí)享受服務(wù)隊(duì)列中進(jìn)程的優(yōu)先級(jí)P以以 P=b*t (ab0) 的速率增長(zhǎng)。設(shè)某一進(jìn)程在時(shí)刻的速率增長(zhǎng)。設(shè)某一進(jìn)程在時(shí)刻

15、t1時(shí)時(shí)被創(chuàng)建，在時(shí)刻被創(chuàng)建，在時(shí)刻t時(shí)，該進(jìn)程的優(yōu)先級(jí)為時(shí)，該進(jìn)程的優(yōu)先級(jí)為P(t)=a*(t-t1) (t1tt1)第17頁(yè)/共37頁(yè)又設(shè)該進(jìn)程在又設(shè)該進(jìn)程在t1時(shí)刻轉(zhuǎn)入享受服務(wù)隊(duì)列，則在時(shí)時(shí)刻轉(zhuǎn)入享受服務(wù)隊(duì)列，則在時(shí)刻刻t，該進(jìn)程的優(yōu)先級(jí)變?yōu)?，該進(jìn)程的優(yōu)先級(jí)變?yōu)镻(t)=a*(t1-t1)+b*(t-t1) (t1tb0 的條的條件是必要的。否則，當(dāng)件是必要的。否則，當(dāng)ba0 時(shí)，兩個(gè)不同隊(duì)時(shí)，兩個(gè)不同隊(duì)列中的就緒態(tài)進(jìn)程的優(yōu)先級(jí)將永遠(yuǎn)不會(huì)相等，從列中的就緒態(tài)進(jìn)程的優(yōu)先級(jí)將永遠(yuǎn)不會(huì)相等，從而，在享受服務(wù)進(jìn)程隊(duì)列中永遠(yuǎn)只有一個(gè)進(jìn)程。而，在享受服務(wù)進(jìn)程隊(duì)列中永遠(yuǎn)只有一個(gè)進(jìn)程。因此，上述線性優(yōu)先

16、級(jí)調(diào)度策略退回到因此，上述線性優(yōu)先級(jí)調(diào)度策略退回到FCFS方方式。另外，如果式。另外，如果ab=0，則線性優(yōu)先級(jí)調(diào)度策略，則線性優(yōu)先級(jí)調(diào)度策略退回到輪轉(zhuǎn)法調(diào)度方式。事實(shí)上，線性優(yōu)先級(jí)調(diào)退回到輪轉(zhuǎn)法調(diào)度方式。事實(shí)上，線性優(yōu)先級(jí)調(diào)度策略是一種介于輪轉(zhuǎn)法和度策略是一種介于輪轉(zhuǎn)法和FCFS方式之間的調(diào)方式之間的調(diào)度策略。度策略。第20頁(yè)/共37頁(yè)4. 優(yōu)先級(jí)法優(yōu)先級(jí)法系統(tǒng)或用戶按某種原則為作業(yè)或進(jìn)程指定一個(gè)優(yōu)系統(tǒng)或用戶按某種原則為作業(yè)或進(jìn)程指定一個(gè)優(yōu)先級(jí)來(lái)表示該作業(yè)或進(jìn)程所享有的調(diào)度優(yōu)先權(quán)。先級(jí)來(lái)表示該作業(yè)或進(jìn)程所享有的調(diào)度優(yōu)先權(quán)。靜態(tài)優(yōu)先級(jí)：靜態(tài)優(yōu)先級(jí)：按進(jìn)程的類型給予不同的優(yōu)先級(jí)。按進(jìn)程的類型給予

17、不同的優(yōu)先級(jí)。(2) 將作業(yè)的靜態(tài)優(yōu)先級(jí)作為它所屬進(jìn)程的優(yōu)先級(jí)。將作業(yè)的靜態(tài)優(yōu)先級(jí)作為它所屬進(jìn)程的優(yōu)先級(jí)。動(dòng)態(tài)優(yōu)先級(jí)動(dòng)態(tài)優(yōu)先級(jí):(1) 根據(jù)進(jìn)程占有根據(jù)進(jìn)程占有CPU時(shí)間的長(zhǎng)短來(lái)決定。時(shí)間的長(zhǎng)短來(lái)決定。 (2) 根據(jù)就緒進(jìn)程等待根據(jù)就緒進(jìn)程等待CPU的時(shí)間長(zhǎng)短來(lái)決定。的時(shí)間長(zhǎng)短來(lái)決定。思考思考:多級(jí)反饋輪轉(zhuǎn)法與優(yōu)先級(jí)法在原理上的區(qū)別多級(jí)反饋輪轉(zhuǎn)法與優(yōu)先級(jí)法在原理上的區(qū)別第21頁(yè)/共37頁(yè)作業(yè)調(diào)度算法作業(yè)調(diào)度算法:1.先來(lái)先服務(wù)調(diào)度算法先來(lái)先服務(wù)調(diào)度算法2.優(yōu)先級(jí)法優(yōu)先級(jí)法(1) 由用戶自己根據(jù)作業(yè)的緊急程度輸入一個(gè)適當(dāng)由用戶自己根據(jù)作業(yè)的緊急程度輸入一個(gè)適當(dāng)?shù)膬?yōu)先級(jí)。的優(yōu)先級(jí)。(2) 由系統(tǒng)或

18、操作員根據(jù)作業(yè)類型指定優(yōu)先級(jí)。由系統(tǒng)或操作員根據(jù)作業(yè)類型指定優(yōu)先級(jí)。(3) 系統(tǒng)根據(jù)作業(yè)要求資源情況確定優(yōu)先級(jí)。系統(tǒng)根據(jù)作業(yè)要求資源情況確定優(yōu)先級(jí)。3. 最短作業(yè)優(yōu)先法（最短作業(yè)優(yōu)先法（shortest job first）4. 最高響應(yīng)比優(yōu)先法（最高響應(yīng)比優(yōu)先法（highest responseratio next）R=(W+T)/T=1+W/T其中其中T為該作業(yè)估計(jì)需要的執(zhí)行時(shí)間，為該作業(yè)估計(jì)需要的執(zhí)行時(shí)間，W為作業(yè)在后備狀態(tài)隊(duì)列中的等待時(shí)為作業(yè)在后備狀態(tài)隊(duì)列中的等待時(shí)間。間。第22頁(yè)/共37頁(yè)例例1：在單道批處理系統(tǒng)中，有五個(gè)作業(yè)進(jìn)入輸入井的時(shí)間及需要執(zhí)行：在單道批處理系統(tǒng)中，有五個(gè)作業(yè)

19、進(jìn)入輸入井的時(shí)間及需要執(zhí)行的時(shí)間如下表所示，約定當(dāng)這五個(gè)作業(yè)全部進(jìn)入輸入井后立即進(jìn)行調(diào)的時(shí)間如下表所示，約定當(dāng)這五個(gè)作業(yè)全部進(jìn)入輸入井后立即進(jìn)行調(diào)度，忽略調(diào)度的時(shí)間開(kāi)銷。要求：寫(xiě)出分別采用先來(lái)先服務(wù)和最短執(zhí)度，忽略調(diào)度的時(shí)間開(kāi)銷。要求：寫(xiě)出分別采用先來(lái)先服務(wù)和最短執(zhí)行時(shí)間優(yōu)先調(diào)度算法時(shí)的調(diào)度次序和作業(yè)平均周轉(zhuǎn)時(shí)間。行時(shí)間優(yōu)先調(diào)度算法時(shí)的調(diào)度次序和作業(yè)平均周轉(zhuǎn)時(shí)間。作業(yè)號(hào)作業(yè)號(hào)進(jìn)入輸進(jìn)入輸入井時(shí)入井時(shí)間間需執(zhí)行需執(zhí)行時(shí)間時(shí)間（分鐘）（分鐘）開(kāi)始執(zhí)開(kāi)始執(zhí)行時(shí)間行時(shí)間結(jié)束執(zhí)結(jié)束執(zhí)行時(shí)間行時(shí)間周轉(zhuǎn)時(shí)周轉(zhuǎn)時(shí)間（分間（分鐘）鐘）110：0040210：1030310：2020410：3025510：401

20、0先來(lái)先服務(wù)：12345 108分鐘最短作業(yè)優(yōu)先：53421 81分鐘第23頁(yè)/共37頁(yè)例例2：一個(gè)多道程序系統(tǒng)，有一個(gè)作業(yè)序列，作業(yè)的提：一個(gè)多道程序系統(tǒng)，有一個(gè)作業(yè)序列，作業(yè)的提交時(shí)間及運(yùn)行時(shí)間在下表中所列，當(dāng)?shù)谝粋€(gè)作業(yè)進(jìn)入交時(shí)間及運(yùn)行時(shí)間在下表中所列，當(dāng)?shù)谝粋€(gè)作業(yè)進(jìn)入系統(tǒng)后開(kāi)始調(diào)度，假定作業(yè)都是僅作計(jì)算。請(qǐng)列出在系統(tǒng)后開(kāi)始調(diào)度，假定作業(yè)都是僅作計(jì)算。請(qǐng)列出在分別采用先來(lái)先服務(wù)算法和計(jì)算時(shí)間短的優(yōu)先算法管分別采用先來(lái)先服務(wù)算法和計(jì)算時(shí)間短的優(yōu)先算法管理作業(yè)時(shí)各個(gè)作業(yè)的開(kāi)始時(shí)間、完成時(shí)間和周轉(zhuǎn)時(shí)間。理作業(yè)時(shí)各個(gè)作業(yè)的開(kāi)始時(shí)間、完成時(shí)間和周轉(zhuǎn)時(shí)間。注意注意:忽略系統(tǒng)開(kāi)銷。忽略系統(tǒng)開(kāi)銷。作業(yè)號(hào)作

21、業(yè)號(hào)到達(dá)輸入井時(shí)刻到達(dá)輸入井時(shí)刻需計(jì)算時(shí)間需計(jì)算時(shí)間110：002小時(shí)小時(shí)210：101小時(shí)小時(shí)310：200.5小時(shí)小時(shí)410：300.2小時(shí)小時(shí)第24頁(yè)/共37頁(yè)4.6 實(shí)時(shí)系統(tǒng)調(diào)度方法實(shí)時(shí)系統(tǒng)調(diào)度方法4.6.1 實(shí)時(shí)系統(tǒng)的特點(diǎn)實(shí)時(shí)系統(tǒng)的特點(diǎn)根據(jù)對(duì)處理外部事件的時(shí)限要求，實(shí)時(shí)系統(tǒng)中處根據(jù)對(duì)處理外部事件的時(shí)限要求，實(shí)時(shí)系統(tǒng)中處理的外部事件可分為理的外部事件可分為硬實(shí)時(shí)任務(wù)和軟實(shí)時(shí)任務(wù)硬實(shí)時(shí)任務(wù)和軟實(shí)時(shí)任務(wù)。硬實(shí)時(shí)任務(wù)要求系統(tǒng)必須完全滿足任務(wù)的時(shí)限要硬實(shí)時(shí)任務(wù)要求系統(tǒng)必須完全滿足任務(wù)的時(shí)限要求。軟實(shí)時(shí)任務(wù)則允許系統(tǒng)對(duì)任務(wù)的時(shí)限要求有求。軟實(shí)時(shí)任務(wù)則允許系統(tǒng)對(duì)任務(wù)的時(shí)限要求有一定的延遲，其時(shí)限要

22、求只是一個(gè)相對(duì)條件。一定的延遲，其時(shí)限要求只是一個(gè)相對(duì)條件。實(shí)時(shí)系統(tǒng)的另一個(gè)特點(diǎn)是它所處理的外部任務(wù)可實(shí)時(shí)系統(tǒng)的另一個(gè)特點(diǎn)是它所處理的外部任務(wù)可分為分為周期性的與非周期性周期性的與非周期性的兩大類。對(duì)于非周期的兩大類。對(duì)于非周期性任務(wù)來(lái)說(shuō)，存在有一個(gè)完成或開(kāi)始進(jìn)行處理時(shí)性任務(wù)來(lái)說(shuō)，存在有一個(gè)完成或開(kāi)始進(jìn)行處理時(shí)限，而周期性任務(wù)只要求在周期限，而周期性任務(wù)只要求在周期T內(nèi)完成或開(kāi)始內(nèi)完成或開(kāi)始進(jìn)行處理。進(jìn)行處理。第25頁(yè)/共37頁(yè)一般來(lái)說(shuō)，實(shí)時(shí)操作系統(tǒng)具有以下特點(diǎn)：一般來(lái)說(shuō)，實(shí)時(shí)操作系統(tǒng)具有以下特點(diǎn)：(1) 有限等待時(shí)間（決定性）有限等待時(shí)間（決定性）(2) 有限響應(yīng)時(shí)間有限響應(yīng)時(shí)間(3) 用戶

23、控制用戶控制(4) 可靠性高可靠性高(5) 系統(tǒng)出錯(cuò)處理能力強(qiáng)系統(tǒng)出錯(cuò)處理能力強(qiáng)實(shí)時(shí)系統(tǒng)要求所有的進(jìn)程在處理事件時(shí)，都必須實(shí)時(shí)系統(tǒng)要求所有的進(jìn)程在處理事件時(shí)，都必須在有限時(shí)間內(nèi)開(kāi)始處理。這一特性又被稱為實(shí)時(shí)在有限時(shí)間內(nèi)開(kāi)始處理。這一特性又被稱為實(shí)時(shí)系統(tǒng)的系統(tǒng)的決定性特性決定性特性。實(shí)時(shí)系統(tǒng)的實(shí)時(shí)系統(tǒng)的有限響應(yīng)時(shí)間特性有限響應(yīng)時(shí)間特性是指從系統(tǒng)響應(yīng)外是指從系統(tǒng)響應(yīng)外部事件開(kāi)始，必須在有限時(shí)間內(nèi)處理完畢。部事件開(kāi)始，必須在有限時(shí)間內(nèi)處理完畢。第26頁(yè)/共37頁(yè)實(shí)時(shí)系統(tǒng)要求很高的實(shí)時(shí)系統(tǒng)要求很高的可靠性可靠性。實(shí)時(shí)操作系統(tǒng)具有下述能力：實(shí)時(shí)操作系統(tǒng)具有下述能力：(1) 很快的進(jìn)程或線程切換速度很快的

24、進(jìn)程或線程切換速度(2) 快速的外部中斷響應(yīng)能力快速的外部中斷響應(yīng)能力(3) 基于優(yōu)先級(jí)的隨時(shí)搶先式調(diào)度策略基于優(yōu)先級(jí)的隨時(shí)搶先式調(diào)度策略基于優(yōu)先級(jí)的調(diào)度策略大致有以下基于優(yōu)先級(jí)的調(diào)度策略大致有以下4種。即：種。即： 優(yōu)先級(jí)優(yōu)先級(jí)+時(shí)間片輪轉(zhuǎn)調(diào)度策略；時(shí)間片輪轉(zhuǎn)調(diào)度策略； 基于優(yōu)先級(jí)的非搶先式調(diào)度策略；基于優(yōu)先級(jí)的非搶先式調(diào)度策略； 基于優(yōu)先級(jí)的固定點(diǎn)搶先式調(diào)度策略；基于優(yōu)先級(jí)的固定點(diǎn)搶先式調(diào)度策略； 基于優(yōu)先級(jí)的隨時(shí)搶先式調(diào)度策略?；趦?yōu)先級(jí)的隨時(shí)搶先式調(diào)度策略。基于優(yōu)先級(jí)的固定點(diǎn)搶先式調(diào)度方式與基于優(yōu)先基于優(yōu)先級(jí)的固定點(diǎn)搶先式調(diào)度方式與基于優(yōu)先級(jí)的隨時(shí)搶先式調(diào)度策略是實(shí)時(shí)系統(tǒng)的主要調(diào)度級(jí)的

25、隨時(shí)搶先式調(diào)度策略是實(shí)時(shí)系統(tǒng)的主要調(diào)度策略。策略。第27頁(yè)/共37頁(yè)4.6.2 實(shí)時(shí)調(diào)度算法的分類實(shí)時(shí)調(diào)度算法的分類4類實(shí)時(shí)調(diào)度算法：類實(shí)時(shí)調(diào)度算法：(1) 靜態(tài)表格驅(qū)動(dòng)類靜態(tài)表格驅(qū)動(dòng)類靜態(tài)表格驅(qū)動(dòng)類的實(shí)時(shí)調(diào)度算法，對(duì)可能的調(diào)度條件和參數(shù)進(jìn)行靜態(tài)靜態(tài)表格驅(qū)動(dòng)類的實(shí)時(shí)調(diào)度算法，對(duì)可能的調(diào)度條件和參數(shù)進(jìn)行靜態(tài)分析，并將分析結(jié)果作為實(shí)際調(diào)度結(jié)果。這類調(diào)度方法多用于調(diào)度分析，并將分析結(jié)果作為實(shí)際調(diào)度結(jié)果。這類調(diào)度方法多用于調(diào)度處理周期性任務(wù)處理周期性任務(wù)(2) 靜態(tài)優(yōu)先級(jí)驅(qū)動(dòng)搶先式調(diào)度算法類靜態(tài)優(yōu)先級(jí)驅(qū)動(dòng)搶先式調(diào)度算法類該類算法的靜態(tài)分析不直接產(chǎn)生調(diào)度結(jié)果，而只用來(lái)指定任務(wù)的優(yōu)先該類算法的靜態(tài)分析不直

26、接產(chǎn)生調(diào)度結(jié)果，而只用來(lái)指定任務(wù)的優(yōu)先級(jí)。頻率單調(diào)調(diào)度算法就是一種靜態(tài)優(yōu)先級(jí)驅(qū)動(dòng)的搶先式調(diào)度算法。級(jí)。頻率單調(diào)調(diào)度算法就是一種靜態(tài)優(yōu)先級(jí)驅(qū)動(dòng)的搶先式調(diào)度算法。(3) 動(dòng)態(tài)計(jì)劃調(diào)度算法類動(dòng)態(tài)計(jì)劃調(diào)度算法類動(dòng)態(tài)計(jì)劃調(diào)度算法在調(diào)度任務(wù)執(zhí)行之前排出調(diào)度計(jì)劃，并分析計(jì)劃的動(dòng)態(tài)計(jì)劃調(diào)度算法在調(diào)度任務(wù)執(zhí)行之前排出調(diào)度計(jì)劃，并分析計(jì)劃的調(diào)度結(jié)果是否使得任務(wù)所要求的處理時(shí)限得到滿足。如果能夠滿足，調(diào)度結(jié)果是否使得任務(wù)所要求的處理時(shí)限得到滿足。如果能夠滿足，則按調(diào)度計(jì)劃執(zhí)行，否則修改調(diào)度計(jì)劃。則按調(diào)度計(jì)劃執(zhí)行，否則修改調(diào)度計(jì)劃。(4) 盡力而為調(diào)度算法類盡力而為調(diào)度算法類這一類算法不進(jìn)行可能性分析，只對(duì)到達(dá)的事件

27、和相關(guān)任務(wù)指定相應(yīng)這一類算法不進(jìn)行可能性分析，只對(duì)到達(dá)的事件和相關(guān)任務(wù)指定相應(yīng)的優(yōu)先級(jí)，并進(jìn)行調(diào)度。盡力而為調(diào)度方式開(kāi)銷較小，實(shí)現(xiàn)容易。的優(yōu)先級(jí)，并進(jìn)行調(diào)度。盡力而為調(diào)度方式開(kāi)銷較小，實(shí)現(xiàn)容易。但是，該算法不一定滿足用戶要求的處理時(shí)限。但是，該算法不一定滿足用戶要求的處理時(shí)限。第28頁(yè)/共37頁(yè)4.6.3 時(shí)限調(diào)度算法與頻率單調(diào)調(diào)度算法時(shí)限調(diào)度算法與頻率單調(diào)調(diào)度算法時(shí)限調(diào)度算法是一種以滿足用戶要求的時(shí)限為調(diào)時(shí)限調(diào)度算法是一種以滿足用戶要求的時(shí)限為調(diào)度原則的算法。在實(shí)時(shí)系統(tǒng)中的用戶要求時(shí)限度原則的算法。在實(shí)時(shí)系統(tǒng)中的用戶要求時(shí)限有兩種，即處理開(kāi)始時(shí)限和處理結(jié)束時(shí)限。時(shí)有兩種，即處理開(kāi)始時(shí)限和處理

28、結(jié)束時(shí)限。時(shí)限調(diào)度算法可以使用任一種時(shí)限。時(shí)限調(diào)度算限調(diào)度算法可以使用任一種時(shí)限。時(shí)限調(diào)度算法不可用于周期性調(diào)度與非周期性調(diào)度兩種。法不可用于周期性調(diào)度與非周期性調(diào)度兩種。時(shí)限調(diào)度算法所需要的相關(guān)輸入信息包括以下幾時(shí)限調(diào)度算法所需要的相關(guān)輸入信息包括以下幾種：種：任務(wù)就緒時(shí)間或事件到達(dá)時(shí)間任務(wù)就緒時(shí)間或事件到達(dá)時(shí)間(2) 開(kāi)始時(shí)限開(kāi)始時(shí)限(3) 完成時(shí)限完成時(shí)限(4) 處理時(shí)間處理時(shí)間(5) 資源需求資源需求(6) 優(yōu)先級(jí)優(yōu)先級(jí)第29頁(yè)/共37頁(yè)時(shí)限調(diào)度算法的基本思想是：按用戶的時(shí)限要求時(shí)限調(diào)度算法的基本思想是：按用戶的時(shí)限要求順序設(shè)置優(yōu)先級(jí)，優(yōu)先級(jí)高者占據(jù)處理機(jī)，也就順序設(shè)置優(yōu)先級(jí)，優(yōu)先級(jí)高

29、者占據(jù)處理機(jī)，也就是說(shuō)，時(shí)限要求最近的任務(wù)優(yōu)先占有處理機(jī)。是說(shuō)，時(shí)限要求最近的任務(wù)優(yōu)先占有處理機(jī)。時(shí)限調(diào)度是搶先式的。下面是用時(shí)限調(diào)度算法調(diào)時(shí)限調(diào)度是搶先式的。下面是用時(shí)限調(diào)度算法調(diào)度周期性實(shí)時(shí)任務(wù)的例子。度周期性實(shí)時(shí)任務(wù)的例子。設(shè)實(shí)時(shí)系統(tǒng)從兩個(gè)不同的數(shù)據(jù)源設(shè)實(shí)時(shí)系統(tǒng)從兩個(gè)不同的數(shù)據(jù)源DA和和D周期性周期性地收集數(shù)據(jù)并進(jìn)行處理，其中地收集數(shù)據(jù)并進(jìn)行處理，其中DA的時(shí)限要求以的時(shí)限要求以30 ms為周期，為周期，DB的時(shí)限要求以的時(shí)限要求以75 ms為周期。為周期。設(shè)設(shè)DA所需處理時(shí)限為所需處理時(shí)限為15 ms，DB所需處理時(shí)限所需處理時(shí)限為為38 ms，則與，則與DA和和DB有關(guān)進(jìn)程的事件發(fā)生

30、時(shí)有關(guān)進(jìn)程的事件發(fā)生時(shí)限（就緒時(shí)限），執(zhí)行時(shí)限以及結(jié)束時(shí)限如圖所限（就緒時(shí)限），執(zhí)行時(shí)限以及結(jié)束時(shí)限如圖所示。示。第30頁(yè)/共37頁(yè)圖圖4.11 周期性任務(wù)的預(yù)計(jì)發(fā)生、執(zhí)行與結(jié)束時(shí)限周期性任務(wù)的預(yù)計(jì)發(fā)生、執(zhí)行與結(jié)束時(shí)限第31頁(yè)/共37頁(yè)如果使用時(shí)限調(diào)度算法，并按最近結(jié)束時(shí)限優(yōu)先如果使用時(shí)限調(diào)度算法，并按最近結(jié)束時(shí)限優(yōu)先級(jí)最高的方法進(jìn)行排列，可以給出圖所示各進(jìn)程級(jí)最高的方法進(jìn)行排列，可以給出圖所示各進(jìn)程的調(diào)度順序和相對(duì)時(shí)間。（如圖）的調(diào)度順序和相對(duì)時(shí)間。（如圖）圖圖4.12 時(shí)限調(diào)度算法給出的調(diào)度順序時(shí)限調(diào)度算法給出的調(diào)度順序第32頁(yè)/共37頁(yè)頻率單調(diào)調(diào)度算法是一種被廣泛用于多周期性實(shí)頻率單調(diào)調(diào)度算法是一種被廣泛用于多周期性實(shí)時(shí)處理的調(diào)度算法。