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

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

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

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

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

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

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

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

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

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

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

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

12、21頁/共67頁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)的隊列并進(jìn)行動態(tài)隊列轉(zhuǎn)接。進(jìn)程調(diào)度模塊通過PCB變化來掌握系統(tǒng)中所有進(jìn)程的執(zhí)行情況和狀態(tài)特征，并在適當(dāng)?shù)臅r機從就緒隊列中選擇出一個進(jìn)程占據(jù)處理機。第22頁/共67頁(2) 選擇占有處理機的進(jìn)程 進(jìn)程調(diào)度的主要功能是按照一定的策略選擇一個處于就緒狀態(tài)的進(jìn)程，使其獲得處理機執(zhí)行。根據(jù)不同的系統(tǒng)設(shè)計目的，有各種各樣的選擇策

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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