計(jì)算機(jī)操作系統(tǒng)教程 PPT課件

1、 不同的CPU管理方法將為用戶提供不同性能的操作系統(tǒng)。 例如：在多道批處理系統(tǒng)中，為了提高處理機(jī)的效率和增加作業(yè)吞吐率，當(dāng)調(diào)度一批作業(yè)組織多道運(yùn)行時(shí)，要盡可能使作業(yè)搭配合理。 在分時(shí)系統(tǒng)中，在調(diào)度作業(yè)執(zhí)行時(shí)要首先考慮每個(gè)用戶作業(yè)得到處理機(jī)的均等性。 實(shí)時(shí)操作系統(tǒng)中,首選考慮的是處理機(jī)的響應(yīng)時(shí)間。 根據(jù)操作系統(tǒng)的要求不同，處理機(jī)管理的策略是不同的。第1頁(yè)/共67頁(yè)衡量調(diào)度策略的最常用的幾個(gè)指標(biāo)是： 周轉(zhuǎn)時(shí)間、吞吐率、響應(yīng)時(shí)間以及設(shè)備利用率等。 周轉(zhuǎn)時(shí)間： 是指將一個(gè)作業(yè)提交給計(jì)算機(jī)系統(tǒng)后到該作業(yè)的結(jié)果返回給用戶所需要的時(shí)間。吞吐率： 是指在給定的時(shí)間內(nèi)，一個(gè)計(jì)算機(jī)系統(tǒng)所完成的總工作量。響應(yīng)時(shí)間：

2、 是指從用戶向計(jì)算機(jī)發(fā)出一個(gè)命令到計(jì)算機(jī)把相應(yīng)的執(zhí)行結(jié)果返回給用戶所需要的時(shí)間。設(shè)備利用率： 主要指輸入輸出設(shè)備的使用情況。本章將以CPU 管理為核心，討論管理、控制用戶進(jìn)程執(zhí)行的方法。主要包括：(1) 作業(yè)與進(jìn)程的關(guān)系；(2) 作業(yè)調(diào)度策略與算法；(3) 進(jìn)程調(diào)度策略與算法；(4) 幾種調(diào)度策略的評(píng)價(jià)。另外，還介紹實(shí)時(shí)調(diào)度系統(tǒng)。第2頁(yè)/共67頁(yè) 本章將以CPU 管理為核心，討論管理、控制用戶進(jìn)程執(zhí)行的方法。主要包括： (1) 作業(yè)與進(jìn)程的關(guān)系； (2) 作業(yè)調(diào)度策略與算法； (3) 進(jìn)程調(diào)度策略與算法； (4) 幾種調(diào)度策略的評(píng)價(jià)。實(shí)時(shí)調(diào)度系統(tǒng)第3頁(yè)/共67頁(yè)4.1 分 級(jí) 調(diào) 度4.1.1

3、 作業(yè)的狀態(tài)及其轉(zhuǎn)換 一個(gè)作業(yè)從用戶提交開(kāi)始到真正占有處理機(jī)而被執(zhí)行，則要由系統(tǒng)經(jīng)過(guò)多級(jí)調(diào)度才能實(shí)現(xiàn)（在有些系統(tǒng)，例如分時(shí)系統(tǒng)中，也可以由單級(jí)調(diào)度實(shí)現(xiàn)）。 如圖4.1 所示，一個(gè)作業(yè)從提交給計(jì)算機(jī)系統(tǒng)到執(zhí)行結(jié)束退出系統(tǒng)，一般都要經(jīng)歷提交、收容、執(zhí)行和完成等4個(gè)狀態(tài)。第4頁(yè)/共67頁(yè)圖4.1 作業(yè)的狀態(tài)及其轉(zhuǎn)換第5頁(yè)/共67頁(yè)提交狀態(tài)： 一個(gè)作業(yè)在其處于從輸入設(shè)備進(jìn)入外部存儲(chǔ)設(shè)備的過(guò)程。收容狀態(tài)（后備狀態(tài)）： 輸入管理系統(tǒng)不斷地將作業(yè)輸入到外存中對(duì)應(yīng)部分（或稱輸入井，即專門(mén)用來(lái)存放待處理作業(yè)信息的一組外存分區(qū)）。若一個(gè)作業(yè)的全部信息已全部被輸入進(jìn)輸入井，那么，在它還未被調(diào)度去執(zhí)行之前，該作業(yè)處于

4、收容狀態(tài)。第6頁(yè)/共67頁(yè)執(zhí)行狀態(tài)： 作業(yè)調(diào)度程序從后備作業(yè)中選取若干個(gè)作業(yè)到內(nèi)存投入運(yùn)行。它為被選中作業(yè)建立進(jìn)程并分配必要的資源。完成狀態(tài)： 當(dāng)作業(yè)運(yùn)行完畢，但它所占用的資源尚未全部被系統(tǒng)回收時(shí)。在這種狀態(tài)下，系統(tǒng)需做諸如打印結(jié)果、回收資源等類的善后處理工作。第7頁(yè)/共67頁(yè)4.1.2 調(diào)度的層次 處理機(jī)調(diào)度問(wèn)題實(shí)際上也是處理機(jī)的分配問(wèn)題。在進(jìn)程有資格競(jìng)爭(zhēng)處理機(jī)之前，作業(yè)調(diào)度程序必須先調(diào)用存儲(chǔ)管理、外設(shè)管理程序，并按一定的選擇順序和策略從輸入井中選擇出幾個(gè)處于后備狀態(tài)的作業(yè)，為它們分配內(nèi)存等資源和創(chuàng)建進(jìn)程，使它們獲得競(jìng)爭(zhēng)處理機(jī)的資格。第8頁(yè)/共67頁(yè)處理機(jī)調(diào)度可以分為4級(jí)：(1) 作業(yè)調(diào)度：

5、高級(jí)調(diào)度。 其主要任務(wù)是按一定的原則對(duì)外存輸入井上的大量后備作業(yè)進(jìn)行選擇，給選出的作業(yè)分配內(nèi)存、輸入輸出設(shè)備等必要的資源，并建立相應(yīng)的進(jìn)程，以使該作業(yè)的進(jìn)程獲得競(jìng)爭(zhēng)處理機(jī)的權(quán)利。另外，當(dāng)該作業(yè)執(zhí)行完畢時(shí)，還負(fù)責(zé)回收系統(tǒng)資源。(2) 交換調(diào)度：又稱中級(jí)調(diào)度。 其主要任務(wù)是按照給定的原則和策略，將處于外存交換區(qū)中的就緒狀態(tài)或就緒等待狀態(tài)的進(jìn)程調(diào)入內(nèi)存，或把處于內(nèi)存就緒狀態(tài)或內(nèi)存等待狀態(tài)的進(jìn)程交換到外存交換區(qū)。交換調(diào)度主要涉及到內(nèi)存管理與擴(kuò)充。(3) 進(jìn)程調(diào)度：又稱微觀調(diào)度或低級(jí)調(diào)度。 其主要任務(wù)是按照某種策略和方法選取一個(gè)處于就緒狀態(tài)的進(jìn)程占用處理機(jī)。在確定了占用處理機(jī)的進(jìn)程后，系統(tǒng)必須進(jìn)行進(jìn)程上

6、下文切換以建立與占用處理機(jī)進(jìn)程相適應(yīng)的執(zhí)行環(huán)境。(4) 線程調(diào)度第9頁(yè)/共67頁(yè)圖4.1 作業(yè)的狀態(tài)及其轉(zhuǎn)換第10頁(yè)/共67頁(yè) 在多道批處理系統(tǒng)中，存在著作業(yè)調(diào)度和進(jìn)程調(diào)度。 在分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)中，一般不存在作業(yè)調(diào)度，而只有進(jìn)程調(diào)度、交換調(diào)度和線程調(diào)度。第11頁(yè)/共67頁(yè)4.1.3 作業(yè)與進(jìn)程的關(guān)系 作業(yè)：可被看作是用戶向計(jì)算機(jī)提交任務(wù)的任務(wù)實(shí)體，例如一次計(jì)算、一個(gè)控制過(guò)程等。 進(jìn)程：是計(jì)算機(jī)為了完成用戶任務(wù)實(shí)體而設(shè)置的執(zhí)行實(shí)體，是系統(tǒng)分配資源的基本單位。作業(yè)怎樣分解為進(jìn)程呢？ 首先，系統(tǒng)必須為一個(gè)作業(yè)創(chuàng)建一個(gè)根進(jìn)程。 接著，在執(zhí)行作業(yè)控制語(yǔ)句時(shí)，根據(jù)任務(wù)要求，系統(tǒng)或根進(jìn)程為其創(chuàng)建相應(yīng)的子進(jìn)

7、程， 然后，為各子進(jìn)程分配資源和調(diào)度各子進(jìn)程執(zhí)行以完成作業(yè)要求的任務(wù)。第12頁(yè)/共67頁(yè)4.2 作 業(yè) 調(diào) 度作業(yè)調(diào)度主要是完成作業(yè)從后備狀態(tài)到執(zhí)行狀態(tài)的轉(zhuǎn)變，以及從執(zhí)行狀態(tài)到完成狀態(tài)的轉(zhuǎn)變。4.2.1 作業(yè)調(diào)度功能(1)記錄系統(tǒng)中各作業(yè)的狀況。 系統(tǒng)為每個(gè)作業(yè)建立一個(gè)作業(yè)控制表JCB記錄這些有關(guān)信息。系統(tǒng)通過(guò)JCB而感知作業(yè)的存在。當(dāng)該作業(yè)執(zhí)行完畢進(jìn)入完成狀態(tài)之后，系統(tǒng)又撤消其JCB而釋放有關(guān)資源并撤消該作業(yè)。每個(gè)作業(yè)在各階段所要求和分配的資源以該作業(yè)的狀態(tài)都記錄在它的JCB中。第13頁(yè)/共67頁(yè) 對(duì)于不同的批處理系統(tǒng)，其JCB的內(nèi)容也有所不同。圖4.2給出了JCB的主要內(nèi)容。作業(yè)名作業(yè)名作

8、業(yè)類型作業(yè)類型資源要求資源要求資源使用情況資源使用情況優(yōu)先級(jí)優(yōu)先級(jí)(數(shù)數(shù))當(dāng)前狀態(tài)當(dāng)前狀態(tài)其他其他第14頁(yè)/共67頁(yè)(2) 從后備隊(duì)列中挑選出一部分作業(yè)投入執(zhí)行。作業(yè)調(diào)度程序根據(jù)選定的調(diào)度算法，從后備作業(yè)隊(duì)列中挑選出若干作業(yè)去投入執(zhí)行。(3) 為被選中作業(yè)做好執(zhí)行前的準(zhǔn)備工作。作業(yè)調(diào)度程序?yàn)檫x中的作業(yè)建立相應(yīng)的進(jìn)程，并為這些進(jìn)程分配它們所需要的系統(tǒng)資源，如分配給它們內(nèi)存、外存、外設(shè)等。(4) 在作業(yè)執(zhí)行結(jié)束時(shí)做善后處理工作。主要是輸出作業(yè)管理信息，例如執(zhí)行時(shí)間等。再就是回收該作業(yè)所占用的資源，撤消與該作業(yè)有關(guān)的全部進(jìn)程和該作業(yè)的作業(yè)控制塊等等。作業(yè)從后備狀態(tài)到執(zhí)行狀態(tài)，又從執(zhí)行狀態(tài)到完成狀態(tài)的

9、轉(zhuǎn)換過(guò)程如圖4.3所示。第15頁(yè)/共67頁(yè)圖4.3 作業(yè)調(diào)度中狀態(tài)的轉(zhuǎn)換過(guò)程第16頁(yè)/共67頁(yè)4.2.2 作業(yè)調(diào)度目標(biāo)與性能衡量 作業(yè)調(diào)度的功能最主要的是從后備作業(yè)隊(duì)列中選取一批作業(yè)進(jìn)入執(zhí)行狀態(tài)。 根據(jù)不同的目標(biāo)，將會(huì)有不同的調(diào)度算法。這里先介紹調(diào)度目標(biāo)。調(diào)度目標(biāo)主要是以下4點(diǎn)：(1) 對(duì)所有作業(yè)應(yīng)該是公平合理的；(2) 應(yīng)使設(shè)備有高的利用率；(3) 每天執(zhí)行盡可能多的作業(yè)；(4) 有快的響應(yīng)時(shí)間。第17頁(yè)/共67頁(yè)怎樣來(lái)衡量一個(gè)作業(yè)調(diào)度算法是否滿足系統(tǒng)設(shè)計(jì)的要求呢？ 對(duì)于批處理系統(tǒng)，由于主要用于計(jì)算，對(duì)于作業(yè)的周轉(zhuǎn)時(shí)間要求較高。因此，作業(yè)的平均周轉(zhuǎn)時(shí)間或平均帶權(quán)周轉(zhuǎn)時(shí)間，被作為衡量調(diào)度算法優(yōu)

10、劣的標(biāo)準(zhǔn)。 對(duì)于分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)，外加平均響應(yīng)時(shí)間被作為衡量調(diào)度策略優(yōu)劣的標(biāo)準(zhǔn)。第18頁(yè)/共67頁(yè)1. 周轉(zhuǎn)時(shí)間：作業(yè)i的周轉(zhuǎn)時(shí)間Ti為T(mén)i=Tei-Tsi其中Tei為作業(yè)i的完成時(shí)間，Tsi為作業(yè)的提交時(shí)間。對(duì)于被測(cè)定作業(yè)流所含有的n（n=1）個(gè)作業(yè)來(lái)說(shuō)，其平均周轉(zhuǎn)時(shí)間為：一個(gè)作業(yè)的周轉(zhuǎn)時(shí)間說(shuō)明了該作業(yè)在系統(tǒng)內(nèi)停留的時(shí)間，包含兩部分：等待時(shí)間；執(zhí)行時(shí)間，即：Ti=TwiTri這里，Twi主要指作業(yè)i由后備狀態(tài)到執(zhí)行狀態(tài)的等待時(shí)間，它不包括作業(yè)進(jìn)入執(zhí)行狀態(tài)后的等待時(shí)間。nii = 11T =Tn第19頁(yè)/共67頁(yè)2. 帶權(quán)周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間是作業(yè)周轉(zhuǎn)時(shí)間與作業(yè)執(zhí)行時(shí)間的比：Wi=Ti/T

11、ri對(duì)于被測(cè)定作業(yè)流所含有的幾個(gè)作業(yè)來(lái)說(shuō)，其平均帶權(quán)周轉(zhuǎn)時(shí)間為： 對(duì)于分時(shí)系統(tǒng)，除了要保證系統(tǒng)吞吐量大、資源利用率高之外，還應(yīng)保證有用戶能夠容忍的響應(yīng)時(shí)間。因此，在分時(shí)系統(tǒng)中，僅僅用周轉(zhuǎn)時(shí)間或帶權(quán)周轉(zhuǎn)時(shí)間來(lái)衡量調(diào)度性能是不夠的。nii=11W =Wn第20頁(yè)/共67頁(yè)4.3 進(jìn) 程 調(diào) 度 無(wú)論是在批處理系統(tǒng)還是分時(shí)系統(tǒng)中，用戶進(jìn)程數(shù)一般都多于處理機(jī)數(shù)，這將導(dǎo)致用戶進(jìn)程互相爭(zhēng)奪處理機(jī)。另外，系統(tǒng)進(jìn)程也同樣需要使用處理機(jī)。這就要求進(jìn)程調(diào)度程序按一定的策略，動(dòng)態(tài)地把處理機(jī)分配給處于就緒隊(duì)列中的某一個(gè)進(jìn)程，以使之執(zhí)行。本節(jié)介紹進(jìn)程調(diào)度的功能、進(jìn)程調(diào)度發(fā)生的時(shí)機(jī)以及由進(jìn)程調(diào)度引起的進(jìn)程上下文切換等。第

12、21頁(yè)/共67頁(yè)4.3.1 進(jìn)程調(diào)度的功能進(jìn)程調(diào)度的具體功能可總結(jié)如下：(1) 記錄系統(tǒng)中所有進(jìn)程的執(zhí)行情況 作為進(jìn)程調(diào)度的準(zhǔn)備，進(jìn)程管理模塊必須將系統(tǒng)中各進(jìn)程的執(zhí)行情況和狀態(tài)特征記錄在各進(jìn)程的PCB表中。并且，進(jìn)程管理模式根據(jù)各進(jìn)程的狀態(tài)特征和資源需求，將各進(jìn)程的PCB表排成相應(yīng)的隊(duì)列并進(jìn)行動(dòng)態(tài)隊(duì)列轉(zhuǎn)接。進(jìn)程調(diào)度模塊通過(guò)PCB變化來(lái)掌握系統(tǒng)中所有進(jìn)程的執(zhí)行情況和狀態(tài)特征，并在適當(dāng)?shù)臅r(shí)機(jī)從就緒隊(duì)列中選擇出一個(gè)進(jìn)程占據(jù)處理機(jī)。第22頁(yè)/共67頁(yè)(2) 選擇占有處理機(jī)的進(jìn)程 進(jìn)程調(diào)度的主要功能是按照一定的策略選擇一個(gè)處于就緒狀態(tài)的進(jìn)程，使其獲得處理機(jī)執(zhí)行。根據(jù)不同的系統(tǒng)設(shè)計(jì)目的，有各種各樣的選擇策

13、略，例如系統(tǒng)開(kāi)銷較少的靜態(tài)優(yōu)先數(shù)調(diào)度法，適合于分時(shí)系統(tǒng)的輪轉(zhuǎn)法和多級(jí)反饋輪轉(zhuǎn)法等。這些選擇策略決定了調(diào)度算法的性能。第23頁(yè)/共67頁(yè)(3) 進(jìn)行進(jìn)程上下文切換 一個(gè)進(jìn)程的上下文（context）包括進(jìn)程的狀態(tài)、有關(guān)變量和數(shù)據(jù)結(jié)構(gòu)的值、硬件寄存器的值和PCB以及有關(guān)程序等。一個(gè)進(jìn)程的執(zhí)行是在進(jìn)程的上下文中執(zhí)行。當(dāng)正在執(zhí)行的進(jìn)程由于某種原因要讓出處理機(jī)時(shí)，系統(tǒng)要做進(jìn)程上下文切換，以使另一個(gè)進(jìn)程得以執(zhí)行。當(dāng)進(jìn)行上下文切換時(shí)，系統(tǒng)要首先檢查是否允許做上下文切換（。然后，系統(tǒng)要保留有關(guān)被切換進(jìn)程的足夠信息，以便以后切換回該進(jìn)程時(shí)，順利恢復(fù)該進(jìn)程的執(zhí)行。在系統(tǒng)保留了CPU現(xiàn)場(chǎng)之后，調(diào)度程序選擇一個(gè)新的處

14、于就緒狀態(tài)的進(jìn)程，并裝配該進(jìn)程的上下文，使CPU的控制權(quán)轉(zhuǎn)換到被選中進(jìn)程中。第24頁(yè)/共67頁(yè)4.3.2 進(jìn)程調(diào)度的時(shí)機(jī)進(jìn)程調(diào)度發(fā)生在什么時(shí)機(jī)呢？這與引起進(jìn)程調(diào)度的原因以及進(jìn)程調(diào)度的方式有關(guān)。引起進(jìn)程調(diào)度的原因有以下幾類：(1)正在執(zhí)行的進(jìn)程執(zhí)行完畢。 (2) 執(zhí)行中進(jìn)程自己調(diào)用阻塞原語(yǔ)將自己阻塞起來(lái)進(jìn)入睡眠等待狀態(tài)。(3) 執(zhí)行中進(jìn)程調(diào)用了P原語(yǔ)操作，從而因資源不足而被阻塞；或調(diào)用了V原語(yǔ)操作激活了等待資源的進(jìn)程隊(duì)列。(4) 執(zhí)行中進(jìn)程提出IO請(qǐng)求后被阻塞。(5) 在分時(shí)系統(tǒng)中時(shí)間片已經(jīng)用完。第25頁(yè)/共67頁(yè)(6) 在執(zhí)行完系統(tǒng)調(diào)用，在系統(tǒng)程序返回用戶進(jìn)程時(shí)，可認(rèn)為系統(tǒng)進(jìn)程執(zhí)行完畢，從而可

15、調(diào)度選擇一新的用戶進(jìn)程執(zhí)行。以上都是在CPU執(zhí)行不可剝奪方式下所引起進(jìn)程調(diào)度的原因。在CPU執(zhí)行方式是可剝奪時(shí)，還有：(7) 就緒隊(duì)列中的某進(jìn)程的優(yōu)先級(jí)變得高于當(dāng)前執(zhí)行進(jìn)程的優(yōu)先級(jí)，從而也將引發(fā)進(jìn)程調(diào)度。所謂可剝奪方式： 即就緒隊(duì)列中一旦有優(yōu)先級(jí)高于當(dāng)前執(zhí)行進(jìn)程優(yōu)先級(jí)的進(jìn)程存在時(shí)，便立即發(fā)生進(jìn)程調(diào)度，轉(zhuǎn)讓處理機(jī)。非剝奪方式或不可剝奪方式： 即使在就緒隊(duì)列存在有優(yōu)先級(jí)高于當(dāng)前執(zhí)行進(jìn)程時(shí)，當(dāng)前進(jìn)程仍將繼續(xù)占有處理機(jī)，直到該進(jìn)程自己因調(diào)用原語(yǔ)操作或等待IO而進(jìn)入阻塞、睡眠狀態(tài)，或時(shí)間片用完時(shí)才重新發(fā)生調(diào)度讓出處理機(jī)。第26頁(yè)/共67頁(yè)4.3.3 進(jìn)程調(diào)度性能評(píng)價(jià) 進(jìn)程調(diào)度雖然是系統(tǒng)內(nèi)部的低級(jí)調(diào)度，但

16、進(jìn)程調(diào)度的優(yōu)劣直接影響作業(yè)調(diào)度的性能。反映作業(yè)調(diào)度優(yōu)劣的周轉(zhuǎn)時(shí)間和平均周轉(zhuǎn)時(shí)間只在某種程度上反映了進(jìn)程調(diào)度的性能，例如，其執(zhí)行時(shí)間部分中實(shí)際上包含有進(jìn)程等待（包括就緒狀態(tài)時(shí)的等待）時(shí)間，而進(jìn)程等待時(shí)間的多少是要依靠進(jìn)程調(diào)度策略和等待事件何時(shí)發(fā)生來(lái)決定的。因此，進(jìn)程調(diào)度性能的衡量是操作系統(tǒng)設(shè)計(jì)的一個(gè)重要指標(biāo)。第27頁(yè)/共67頁(yè)進(jìn)程調(diào)度性能的衡量方法： 定性、定量在定性衡量方面： 首先是調(diào)度的可靠性。另外，簡(jiǎn)潔性也是衡量進(jìn)程調(diào)度的一個(gè)重要指標(biāo)。進(jìn)程調(diào)度的定量評(píng)價(jià)： 包括CPU的利用率評(píng)價(jià)、進(jìn)程在就緒隊(duì)列中的等待時(shí)間與執(zhí)行時(shí)間之比等。實(shí)際上，由于進(jìn)程進(jìn)入就緒隊(duì)列的隨機(jī)模型很難確定，而且進(jìn)程上下文切換

17、等也將影響進(jìn)程的執(zhí)行效率，從而對(duì)進(jìn)程調(diào)度進(jìn)行解析是很困難的。一般情況下，大多利用模擬或測(cè)試系統(tǒng)響應(yīng)時(shí)間的方法來(lái)評(píng)價(jià)進(jìn)程調(diào)度的性能。第28頁(yè)/共67頁(yè)4.4 調(diào) 度 算 法1. 先來(lái)先服務(wù)（FCFS）調(diào)度算法 將用戶作業(yè)和就緒進(jìn)程按提交順序或變?yōu)榫途w狀態(tài)的先后排成隊(duì)列，并按照先來(lái)先服務(wù)的方式進(jìn)行調(diào)度處理，是一種最普遍和最簡(jiǎn)單的方法。 例如基于優(yōu)先級(jí)的調(diào)度算法就是對(duì)具有同樣優(yōu)先級(jí)的作業(yè)或進(jìn)程采用的FCFS方式。第29頁(yè)/共67頁(yè)2. 輪轉(zhuǎn)法（round robin） 輪轉(zhuǎn)法的基本思路是讓每個(gè)進(jìn)程在就緒隊(duì)列中的等待時(shí)間與享受服務(wù)的時(shí)間成比例。 輪轉(zhuǎn)法的基本概念是將CPU的處理時(shí)間分成固定大小的時(shí)間片

18、。輪轉(zhuǎn)法的原理見(jiàn)圖4.4。第30頁(yè)/共67頁(yè) 顯然，輪轉(zhuǎn)法只能用來(lái)調(diào)度分配那些可以搶占的資源。將它們隨時(shí)剝奪再分配給別的進(jìn)程。CPU是可搶占資源的一種。但如打印機(jī)等資源是不可搶占的。 由于作業(yè)調(diào)度是對(duì)除了CPU之外的所有系統(tǒng)硬件資源的分配，其中包含有不可搶占資源，所以作業(yè)調(diào)度不使用輪轉(zhuǎn)法。 時(shí)間片長(zhǎng)度的選擇是根據(jù)系統(tǒng)對(duì)響應(yīng)時(shí)間的要求R和就緒隊(duì)列中所允許的最大進(jìn)程數(shù)Nmax確定的。它可表示為： q=R/Nmax第31頁(yè)/共67頁(yè) CPU的整個(gè)執(zhí)行時(shí)間等于各進(jìn)程執(zhí)行時(shí)間加上系統(tǒng)開(kāi)銷。 例如，在一個(gè)用戶進(jìn)程的情況下，如果q 值增大到足夠該進(jìn)程執(zhí)行完畢的話，則進(jìn)程調(diào)度所引起的系統(tǒng)開(kāi)銷就沒(méi)有了。 一種可

19、行的辦法是: 每當(dāng)一輪調(diào)度開(kāi)始時(shí)，系統(tǒng)便根據(jù)就緒隊(duì)列中已有進(jìn)程數(shù)目計(jì)算一次q值，作為新一輪調(diào)度的時(shí)間片。這種方法得到的時(shí)間片隨就緒隊(duì)列中的進(jìn)程數(shù)變化。第32頁(yè)/共67頁(yè) 在輪轉(zhuǎn)法中，加入到就緒隊(duì)列的進(jìn)程有三種情況： 一種是分給它的時(shí)間片用完，但進(jìn)程還未完成，回到就緒隊(duì)列的末尾等待下次調(diào)度去繼續(xù)執(zhí)行 另一種情況是分給該進(jìn)程的時(shí)間片并未用完，只是因?yàn)檎?qǐng)求IO或由于進(jìn)程的互斥與同步關(guān)系而被阻塞。當(dāng)阻塞解除之后再回到就緒隊(duì)列。 再有一種情況就是新創(chuàng)建進(jìn)程進(jìn)入就緒隊(duì)列。 如果對(duì)這些進(jìn)程區(qū)別對(duì)待，給予不同的優(yōu)先級(jí)和時(shí)間片，從直觀上看，可望進(jìn)一步改善系統(tǒng)服務(wù)質(zhì)量和效率。第33頁(yè)/共67頁(yè)3. 多級(jí)反饋輪轉(zhuǎn)法

20、 例如，可把就緒隊(duì)列按照進(jìn)程到達(dá)就緒隊(duì)列的類型和進(jìn)程被阻塞時(shí)的阻塞原因分成不同的就緒隊(duì)列，每個(gè)隊(duì)列按FCFS原則排列，各隊(duì)列之間的進(jìn)程享有不同的優(yōu)先級(jí)，但同一隊(duì)列內(nèi)優(yōu)先級(jí)相同。 這樣，當(dāng)一個(gè)進(jìn)程在執(zhí)行完它的時(shí)間片之后，或從睡眠中被喚醒以及被創(chuàng)建之后，將進(jìn)入不同的就緒隊(duì)列。多級(jí)反饋輪轉(zhuǎn)法與優(yōu)先級(jí)法在原理上的區(qū)別是： 一個(gè)進(jìn)程在它執(zhí)行結(jié)束之前，可能需要反復(fù)多次通過(guò)反饋循環(huán)執(zhí)行，而不是優(yōu)先級(jí)法中的一次執(zhí)行。第34頁(yè)/共67頁(yè)4. 優(yōu)先級(jí)法 優(yōu)先級(jí)法可被用作作業(yè)或進(jìn)程的調(diào)度策略。首先，系統(tǒng)或用戶按某種原則為作業(yè)或進(jìn)程指定一個(gè)優(yōu)先級(jí)來(lái)表示該作業(yè)或進(jìn)程所享有的調(diào)度優(yōu)先權(quán)。 該算法的核心：是確定進(jìn)程或作業(yè)的

21、優(yōu)先級(jí)確定優(yōu)先級(jí)的方法：靜態(tài)法和動(dòng)態(tài)法靜態(tài)法：根據(jù)作業(yè)或進(jìn)程的靜態(tài)特性，在作業(yè)或進(jìn)程開(kāi)始執(zhí)行之前就確定它們的優(yōu)先級(jí)，一旦開(kāi)始執(zhí)行之后就不能改變。動(dòng)態(tài)法：它把作業(yè)或進(jìn)程的靜態(tài)特性和動(dòng)態(tài)特性結(jié)合起來(lái)確定作業(yè)或進(jìn)程的優(yōu)先級(jí)，隨著作業(yè)或進(jìn)程的執(zhí)行過(guò)程，其優(yōu)先級(jí)不斷變化。第35頁(yè)/共67頁(yè)靜態(tài)優(yōu)先級(jí)作業(yè)調(diào)度中的靜態(tài)優(yōu)先級(jí)大多按以下原則確定：(1) 由用戶自己根據(jù)作業(yè)的緊急程度輸入一個(gè)適當(dāng)?shù)膬?yōu)先級(jí)。(2) 由系統(tǒng)或操作員根據(jù)作業(yè)類型指定優(yōu)先級(jí)。作業(yè)類型一般由用戶約定或由操作員指定。例如：可將作業(yè)分為： IO繁忙的作業(yè)， CPU繁忙的作業(yè)， IO與CPU均衡的作業(yè)，一般作業(yè)等系統(tǒng)或操作員可以給每類作業(yè)指定不

22、同的優(yōu)先級(jí)。第36頁(yè)/共67頁(yè)(3) 系統(tǒng)根據(jù)作業(yè)要求資源情況確定優(yōu)先級(jí)。 例如:根據(jù)估計(jì)所需處理機(jī)時(shí)間、內(nèi)存量大小、IO設(shè)備類型及數(shù)量等，確定作業(yè)的優(yōu)先級(jí)。進(jìn)程的靜態(tài)優(yōu)先級(jí)確定原則可以是：(1)按進(jìn)程的類型給予不同的優(yōu)先級(jí)。例如，在有些系統(tǒng)中，進(jìn)程被劃分為系統(tǒng)進(jìn)程和用戶進(jìn)程。系統(tǒng)進(jìn)程享有比用戶進(jìn)程高的優(yōu)先級(jí)。 用戶進(jìn)程，則可以分為： IO繁忙的進(jìn)程，CPU繁忙的進(jìn)程，IO與CPU均衡的進(jìn)程，其他進(jìn)程。第37頁(yè)/共67頁(yè)系統(tǒng)進(jìn)程，也可以根據(jù)其所要完成的功能劃分為不同的類型 例如，調(diào)度進(jìn)程、IO進(jìn)程、中斷處理進(jìn)程、存儲(chǔ)管理進(jìn)程等。 例如，在操作系統(tǒng)中，對(duì)于鍵盤(pán)中斷的處理優(yōu)先級(jí)和對(duì)于電源掉電中斷的

23、處理優(yōu)先級(jí)是不相同的。(2) 將作業(yè)的靜態(tài)優(yōu)先級(jí)作為它所屬進(jìn)程的優(yōu)先級(jí)。第38頁(yè)/共67頁(yè)動(dòng)態(tài)優(yōu)先級(jí)進(jìn)程的動(dòng)態(tài)優(yōu)先級(jí)一般根據(jù)以下原則確定：(1)根據(jù)進(jìn)程占有CPU時(shí)間的長(zhǎng)短來(lái)決定。 一個(gè)進(jìn)程占有處理機(jī)的時(shí)間愈長(zhǎng)，則在被阻塞之后再次獲得調(diào)度的優(yōu)先級(jí)就越低，反之，其獲得調(diào)度的可能性就會(huì)越大。(2) 根據(jù)就緒進(jìn)程等待CPU的時(shí)間長(zhǎng)短來(lái)決定。 一個(gè)就緒進(jìn)程在就緒隊(duì)列中等待的時(shí)間越長(zhǎng)，則它獲得調(diào)度選中的優(yōu)先級(jí)就越高。第39頁(yè)/共67頁(yè)例如：線性優(yōu)先級(jí)調(diào)度策略（selfish round robin） 使用輪轉(zhuǎn)法調(diào)度進(jìn)程時(shí)，新創(chuàng)建的進(jìn)程也放入就緒隊(duì)列末尾享受平等的處理機(jī)時(shí)間片。這對(duì)于執(zhí)行時(shí)間長(zhǎng)的進(jìn)程來(lái)說(shuō)是

24、有點(diǎn)不公平的，因?yàn)樗鼈冃枰鄠€(gè)時(shí)間片才能完成。 因此，線性優(yōu)先級(jí)調(diào)度策略采用如下方式，即新創(chuàng)建的進(jìn)程按FCFS方式排成就緒隊(duì)列，而其他已得到過(guò)時(shí)間片服務(wù)的進(jìn)程也按FCFS方式排成另一個(gè)就緒隊(duì)列或稱享受服務(wù)隊(duì)列(圖4.5）。第40頁(yè)/共67頁(yè) 對(duì)于這兩個(gè)不同隊(duì)列中的進(jìn)程，設(shè)新創(chuàng)建進(jìn)程就緒隊(duì)列中進(jìn)程的優(yōu)先級(jí)P以 P=a*t (a0) 的速率增加。另外，享受服務(wù)隊(duì)列中進(jìn)程的優(yōu)先級(jí)P以 P=b*t (ab0) 的速率增長(zhǎng)。設(shè)某一進(jìn)程在時(shí)刻t1時(shí)被創(chuàng)建，在時(shí)刻t時(shí)，該進(jìn)程的優(yōu)先級(jí)為P(t)=a*(t-t1) (t1tt1) 又設(shè)該進(jìn)程在t1時(shí)刻轉(zhuǎn)入享受服務(wù)隊(duì)列，則在時(shí)刻t，該進(jìn)程的優(yōu)先級(jí)變?yōu)镻(t)=a

25、*(t1-t1)+b*(t-t1) (t1tb0 的條件是必要的。否則，當(dāng)ba0 時(shí)，兩個(gè)不同隊(duì)列中的就緒態(tài)進(jìn)程的優(yōu)先級(jí)將永遠(yuǎn)不會(huì)相等 如果ba0, 線性優(yōu)先級(jí)調(diào)度策略退回到FCFS方式。 如果ab=0，則線性優(yōu)先級(jí)調(diào)度策略退回到輪轉(zhuǎn)法調(diào)度方式。 線性優(yōu)先級(jí)調(diào)度策略是一種介于輪轉(zhuǎn)法和FCFS方式之間的調(diào)度策略。這幾種方式的調(diào)度性能，將在下一節(jié)中更進(jìn)一步討論。第44頁(yè)/共67頁(yè)5. 最短作業(yè)優(yōu)先法（shortest job first）最短作業(yè)優(yōu)先法（SJF）: 就是選擇那些估計(jì)需要執(zhí)行時(shí)間最短的作業(yè)投入執(zhí)行，為它們創(chuàng)建進(jìn)程和分配資源。 采用最短作業(yè)優(yōu)先的調(diào)度算法，可使得系統(tǒng)在同一時(shí)間內(nèi)處理的作

26、業(yè)個(gè)數(shù)最多，從而吞吐量也就大于其他調(diào)度方式。但是，對(duì)于一個(gè)不斷有短作業(yè)進(jìn)入的批處理系統(tǒng)來(lái)說(shuō)，最短作業(yè)優(yōu)先法有可能使得那些長(zhǎng)作業(yè)永遠(yuǎn)得不到調(diào)度執(zhí)行的機(jī)會(huì)。6. 最高響應(yīng)比優(yōu)先法（highest responseratio next）最高響應(yīng)比優(yōu)先法（HRN）: 是對(duì)FCFS方式和SJF 方式的一種綜合平衡。HRN調(diào)度策略同時(shí)考慮每個(gè)作業(yè)的等待時(shí)間長(zhǎng)短和估計(jì)需要的執(zhí)行時(shí)間長(zhǎng)短，從中選出響應(yīng)比最高的作業(yè)投入執(zhí)行。第45頁(yè)/共67頁(yè)響應(yīng)比R定義如下： R=(W+T)/T=1+W/T 其中: T為該作業(yè)估計(jì)需要的執(zhí)行時(shí)間 W為作業(yè)在后備狀態(tài)隊(duì)列中的等待時(shí)間 這種算法是介于FCFS和SJF 之間的一種折中

27、算法。由于長(zhǎng)作業(yè)也有機(jī)會(huì)投入運(yùn)行，在同一時(shí)間內(nèi)處理的作業(yè)數(shù)顯然要少于SJF 法，從而采用HRN 方式時(shí)其吞吐量將小于采用SJF 法時(shí)的吞吐量。另外，由于每次調(diào)度前要計(jì)算響應(yīng)比，系統(tǒng)開(kāi)銷也要相應(yīng)增加。第46頁(yè)/共67頁(yè)4.5 算 法 評(píng) 價(jià)本節(jié)主要利用解析技術(shù)從數(shù)學(xué)上分析幾種主要調(diào)度方法的性能。4.5.1 FCFS方式的調(diào)度性能分析設(shè)處理機(jī)或系統(tǒng)資源為服務(wù)器，一個(gè)進(jìn)程或一個(gè)作業(yè)為享受該服務(wù)器服務(wù)的顧客。當(dāng)這些顧客按FCFS方式排隊(duì)享受服務(wù)的系統(tǒng)模型如圖4.7。圖4.7 FCFS方式的評(píng)價(jià)模型第47頁(yè)/共67頁(yè)把按FCFS方式排列和調(diào)度,并只有一個(gè)服務(wù)器的系統(tǒng)稱為M/M/1系統(tǒng)。第1個(gè)字母M表示顧

28、客至達(dá)時(shí)間間隔的指數(shù)分布具有馬爾可夫性質(zhì)第2個(gè)字母M表示從服務(wù)器離開(kāi)的顧客的時(shí)間間隔服從的指數(shù)分布具有馬爾可夫性質(zhì)第個(gè)字母表示個(gè)服務(wù)器下面再來(lái)看看M/M/1系統(tǒng)對(duì)短作業(yè)或短進(jìn)程的影響。證明略經(jīng)數(shù)學(xué)上分析得出結(jié)論: 短作業(yè)在系統(tǒng)中的駐留平均時(shí)間與長(zhǎng)作業(yè)的駐留平均時(shí)間相同，這對(duì)短作業(yè)是不利的。第48頁(yè)/共67頁(yè)4.5.2 輪轉(zhuǎn)法調(diào)度性能評(píng)價(jià)輪轉(zhuǎn)法調(diào)度時(shí)的顧客到達(dá)率要大大高于FCFS方式。證明略結(jié)論: 響應(yīng)時(shí)間與服務(wù)時(shí)間成正比。從而，所需服務(wù)時(shí)間短的顧客的響應(yīng)時(shí)間將會(huì)小于所需服務(wù)時(shí)間長(zhǎng)的顧客的響應(yīng)時(shí)間。 因此，輪轉(zhuǎn)法在響應(yīng)時(shí)間上要優(yōu)于FCFS調(diào)度方式。第49頁(yè)/共67頁(yè)4.5.3 線性優(yōu)先級(jí)法的調(diào)度

29、性能 線性優(yōu)先級(jí)調(diào)度策略（SRR）是介于FCFS方式和輪轉(zhuǎn)法之間的一種調(diào)度策略。SRR方式把新到達(dá)的顧客首先送入等待室休息一段時(shí)間后，再送到等待服務(wù)隊(duì)列。（如圖4.10） 由4.4 節(jié)可知，有ab，且a和b分別為等待室內(nèi)顧客和等待隊(duì)列中顧客優(yōu)先級(jí)的線性增加系數(shù)。 證明略圖4.10 線性優(yōu)先級(jí)調(diào)度的評(píng)價(jià)模型第50頁(yè)/共67頁(yè)比較一下FCFS方式、SRR方式以及輪轉(zhuǎn)法等三種調(diào)度方式的平均響應(yīng)時(shí)間:FCFS方式時(shí)有： fc(k)1 (-)輪轉(zhuǎn)法時(shí)有： rr(k)k q(-)SRR方式時(shí)：sr(k)1 (-) -(1 -k q)(-) 當(dāng)顧客的服務(wù)時(shí)間同其平均服務(wù)時(shí)間相等的話 (即 kq1): fc(

30、k)rr(k)sr(k) 對(duì)于服務(wù)時(shí)間短的顧客其響應(yīng)時(shí)間： rrsrfc 對(duì)于服務(wù)時(shí)間長(zhǎng)的顧客來(lái)說(shuō)，其響應(yīng)時(shí)間則為： fcsrrr上面只是從響應(yīng)時(shí)間的角度對(duì)幾種常見(jiàn)的調(diào)度策略進(jìn)行了評(píng)價(jià)分析。除了響應(yīng)時(shí)間之外，CPU利用率也是評(píng)價(jià)調(diào)度性能的另一個(gè)標(biāo)準(zhǔn)。 第51頁(yè)/共67頁(yè)4.6 實(shí)時(shí)系統(tǒng)調(diào)度方法4.6.1 實(shí)時(shí)系統(tǒng)的特點(diǎn) 實(shí)時(shí)系統(tǒng)與其他系統(tǒng)的最大區(qū)別在于: 其處理和控制的正確性不僅僅取決于計(jì)算的邏輯結(jié)果，而且取決于計(jì)算和處理結(jié)果產(chǎn)生的時(shí)間 因此，實(shí)時(shí)系統(tǒng)的調(diào)度與工業(yè)生產(chǎn)中的生產(chǎn)過(guò)程調(diào)度有許多相同之處，即把給定的任務(wù)，按所要求的時(shí)限調(diào)配到相應(yīng)的設(shè)備上去處理完成。第52頁(yè)/共67頁(yè) 根據(jù)對(duì)處理外部事

31、件的時(shí)限要求，實(shí)時(shí)系統(tǒng)中處理的外部事件可分為: 硬實(shí)時(shí)任務(wù)和軟實(shí)時(shí)任務(wù)。硬實(shí)時(shí)任務(wù): 要求系統(tǒng)必須完全滿足任務(wù)的時(shí)限要求軟實(shí)時(shí)任務(wù): 則允許系統(tǒng)對(duì)任務(wù)的時(shí)限要求有一定的延遲，其時(shí)限要求只是一個(gè)相對(duì)條件。實(shí)時(shí)系統(tǒng)的另一個(gè)特點(diǎn)是它所處理的外部任務(wù)可分: 周期性、非周期性非周期性任務(wù)：存在有一個(gè)完成或開(kāi)始進(jìn)行處理時(shí)限周期性任務(wù)：只要求在周期T內(nèi)完成或開(kāi)始進(jìn)行處理第53頁(yè)/共67頁(yè)實(shí)時(shí)操作系統(tǒng)具有以下特點(diǎn)：(1) 有限等待時(shí)間（決定性）(2) 有限響應(yīng)時(shí)間(3) 用戶控制(4) 可靠性高(5) 系統(tǒng)出錯(cuò)處理能力強(qiáng)第54頁(yè)/共67頁(yè)與分時(shí)系統(tǒng)的多個(gè)進(jìn)程并發(fā)執(zhí)行相比，分時(shí)系統(tǒng)中并發(fā)執(zhí)行的進(jìn)程具有不確定性，

32、其執(zhí)行順序與執(zhí)行環(huán)境有關(guān)。實(shí)時(shí)系統(tǒng)則不然，它要求所有的進(jìn)程在處理事件時(shí)，都必須在有限時(shí)間內(nèi)開(kāi)始處理。這一特性又被稱為實(shí)時(shí)系統(tǒng)的決定性特性。實(shí)時(shí)系統(tǒng)的有限響應(yīng)時(shí)間特性是指從系統(tǒng)響應(yīng)外部事件開(kāi)始，必須在有限時(shí)間內(nèi)處理完畢。另外，在分時(shí)系統(tǒng)的非實(shí)時(shí)系統(tǒng)中，用戶不能參與對(duì)進(jìn)程調(diào)度的控制。在實(shí)時(shí)系統(tǒng)中，用戶可以控制進(jìn)程的優(yōu)先級(jí)并選擇相應(yīng)的調(diào)度算法，從而達(dá)到對(duì)進(jìn)程執(zhí)行先后順序的控制。第55頁(yè)/共67頁(yè)實(shí)時(shí)系統(tǒng)要求很高的可靠性實(shí)時(shí)系統(tǒng)要求系統(tǒng)在出錯(cuò)時(shí)，既能夠處理所發(fā)生的錯(cuò)誤，又不影響當(dāng)前正在執(zhí)行的用戶應(yīng)用。上述特性要求實(shí)時(shí)操作系統(tǒng)具有下述能力：(1) 很快的進(jìn)程或線程切換速度 進(jìn)程或線程切換速度是實(shí)時(shí)系統(tǒng)設(shè)

33、計(jì)的核心。調(diào)度算法的設(shè)計(jì)原則是滿足所有硬實(shí)時(shí)任務(wù)的處理時(shí)限和盡可能多地滿足軟實(shí)時(shí)任務(wù)的處理時(shí)限。(2) 快速的外部中斷響應(yīng)能力(3) 基于優(yōu)先級(jí)的隨時(shí)搶先式調(diào)度策略第56頁(yè)/共67頁(yè)基于優(yōu)先級(jí)的調(diào)度策略大致有以下4種。即： 優(yōu)先級(jí)+時(shí)間片輪轉(zhuǎn)調(diào)度策略； 基于優(yōu)先級(jí)的非搶先式調(diào)度策略； 基于優(yōu)先級(jí)的固定點(diǎn)搶先式調(diào)度策略； 基于優(yōu)先級(jí)的隨時(shí)搶先式調(diào)度策略。第57頁(yè)/共67頁(yè)4.6.2 實(shí)時(shí)調(diào)度算法的分類(1) 靜態(tài)表格驅(qū)動(dòng)類 對(duì)可能的調(diào)度條件和參數(shù)進(jìn)行靜態(tài)分析，并將分析結(jié)果作為實(shí)際調(diào)度結(jié)果。這類調(diào)度方法多用于調(diào)度處理周期性任務(wù)，其主要分析參數(shù)為周期，執(zhí)行時(shí)間、周期行結(jié)束時(shí)限和任務(wù)優(yōu)先級(jí)等。 (2) 靜態(tài)優(yōu)先級(jí)驅(qū)動(dòng)搶先式調(diào)度算法類 不直接產(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)度算法。第58頁(yè)/共67頁(yè)(3) 動(dòng)態(tài)計(jì)劃調(diào)度算法類 在調(diào)度任務(wù)執(zhí)行之前排出調(diào)度計(jì)劃，并分析計(jì)劃的調(diào)度結(jié)果是否使得任務(wù)所要求的處理時(shí)限得到滿足。如果能夠滿足，則按調(diào)度計(jì)劃執(zhí)行，否則修改調(diào)度計(jì)劃。(4) 盡力而為調(diào)度算法類 這一類算法不進(jìn)行可能性分析，只對(duì)到達(dá)的事件和相關(guān)任務(wù)指定相應(yīng)的優(yōu)先級(jí)，并進(jìn)行調(diào)度。盡力而為調(diào)度方式開(kāi)銷較小，實(shí)現(xiàn)容易。但是，該算法不一定滿足用戶要求的處理時(shí)限。第59頁(yè)/共67頁(yè)4.6.3 時(shí)限調(diào)度算法與