操作系統(tǒng)第3章(1)(第四版)

第三章處理機(jī)調(diào)度與死鎖3.1處理機(jī)調(diào)度的層次3.2調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則3.3調(diào)度算法3.4實(shí)時(shí)調(diào)度

3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法

在多道程序環(huán)境下，進(jìn)程數(shù)目往往多于處理機(jī)數(shù)目，致使它們爭(zhēng)用處理機(jī)。這就要求系統(tǒng)能按某種算法，動(dòng)態(tài)地把處理機(jī)分配給就緒隊(duì)列中的一個(gè)進(jìn)程，使之執(zhí)行。分配處理機(jī)的任務(wù)是由進(jìn)程調(diào)度程序完成的，算法的優(yōu)劣直接影響整個(gè)系統(tǒng)的性能。它是操作系統(tǒng)設(shè)計(jì)的中心問(wèn)題之一。進(jìn)程調(diào)度要解決的問(wèn)題:WHAT：按什么原則分配CPU—進(jìn)程調(diào)度算法

WHEN：何時(shí)分配CPU—進(jìn)程調(diào)度的時(shí)機(jī)

HOW：如何分配CPU—CPU調(diào)度過(guò)程（進(jìn)程的上下文切換）處理機(jī)調(diào)度可以分為3層：1）高級(jí)調(diào)度（作業(yè)調(diào)度、長(zhǎng)程調(diào)度）：按一定原則選擇若干個(gè)后備作業(yè)調(diào)入主存，分配資源，并建立相應(yīng)的進(jìn)程，投入運(yùn)行。當(dāng)該作業(yè)執(zhí)行完畢時(shí)，還負(fù)責(zé)回收資源。2）中級(jí)調(diào)度（交換調(diào)度、中程調(diào)度、均衡調(diào)度）：按照給定的原則實(shí)現(xiàn)進(jìn)程在主存和外存交換區(qū)之間的換進(jìn)換出，以解決內(nèi)存緊張問(wèn)題，特別是具有虛擬存儲(chǔ)器的系統(tǒng)中。3）低級(jí)調(diào)度（進(jìn)程調(diào)度、短程調(diào)度）：按照某種策略從進(jìn)程就緒隊(duì)列中選擇一個(gè)就緒進(jìn)程，使其占有處理機(jī)運(yùn)行。3.1處理機(jī)調(diào)度的層次

一、高級(jí)調(diào)度-作業(yè)調(diào)度1．作業(yè)的基本概念1）作業(yè)、作業(yè)步

作業(yè)：是用戶(hù)一次請(qǐng)求計(jì)算機(jī)系統(tǒng)為它完成任務(wù)所進(jìn)行的工作總和。

作業(yè)步：作業(yè)加工工作中的一個(gè)相對(duì)獨(dú)立的步驟稱(chēng)為作業(yè)步。對(duì)作業(yè)的處理一般有這樣幾個(gè)作業(yè)步：

編輯（修改）、編譯、連接、運(yùn)行

。

作業(yè)管理:

一個(gè)作業(yè)從輸入到輸出的一個(gè)過(guò)程。大致分成：作業(yè)提交、作業(yè)調(diào)度、作業(yè)控制、和作業(yè)退出。作業(yè)步之間的關(guān)系：

·每個(gè)作業(yè)步運(yùn)行的結(jié)果產(chǎn)生下一個(gè)作業(yè)步所需要的文件。

·一個(gè)作業(yè)步能否正確地執(zhí)行，依賴(lài)于前一個(gè)作業(yè)步是否成功的完成。例如：user.cuser.objuser.exe

編輯編譯連接運(yùn)行

對(duì)于被調(diào)度的作業(yè)，OS要對(duì)它在系統(tǒng)中整個(gè)運(yùn)行過(guò)程實(shí)行控制。編譯運(yùn)行裝配目標(biāo)程序段目標(biāo)程序裝配程序運(yùn)行程序源程序輸入數(shù)據(jù)輸出信息輸出信息輸出信息子程序庫(kù)函數(shù)動(dòng)態(tài)庫(kù)函數(shù)運(yùn)行結(jié)果編譯程序圖：作業(yè)的控制過(guò)程結(jié)束2）作業(yè)的類(lèi)型根據(jù)計(jì)算機(jī)系統(tǒng)的作業(yè)處理方式不同，可以把作業(yè)分成兩類(lèi)：

脫機(jī)作業(yè)（批處理作業(yè)）：使用作業(yè)控制語(yǔ)言來(lái)書(shū)寫(xiě)一份作業(yè)控制說(shuō)明書(shū)，規(guī)定如何控制作業(yè)的執(zhí)行。

聯(lián)機(jī)作業(yè)（交互式作業(yè)或終端型作業(yè)）：使用OS提供的命令語(yǔ)言直接提出對(duì)作業(yè)的控制要求。3）作業(yè)的組織

程序作業(yè)由三部分組成數(shù)據(jù)作業(yè)說(shuō)明書(shū)（說(shuō)明用戶(hù)的控制意圖）

4）作業(yè)控制塊（JCB）：

為了管理和調(diào)度作業(yè)，在多道批處理系統(tǒng)中為每個(gè)作業(yè)設(shè)置了一個(gè)作業(yè)控制塊，作業(yè)控制塊JCB是作業(yè)存在的標(biāo)志，記錄與該作業(yè)有關(guān)的信息。作業(yè)控制塊（JCB）的主要內(nèi)容：(1)作業(yè)的基本情況用戶(hù)名、作業(yè)名、作業(yè)的狀態(tài)和使用的語(yǔ)言等。(2)作業(yè)的控制要求控制方式、類(lèi)型、優(yōu)先數(shù)、操作順序和出錯(cuò)處理等。(3)作業(yè)的資源要求作業(yè)建立的時(shí)間、要求運(yùn)行的時(shí)間、最遲完成的時(shí)間、需要的主存容量、外設(shè)的種類(lèi)及數(shù)量和資源使用情況。

作業(yè)名資源要求估計(jì)執(zhí)行時(shí)間最遲完成時(shí)間要求的主存量要求外設(shè)的類(lèi)型及臺(tái)數(shù)要求文件量和輸出量資源使用情況進(jìn)入系統(tǒng)時(shí)間開(kāi)始執(zhí)行時(shí)間已執(zhí)行時(shí)間主存地址外設(shè)臺(tái)號(hào)類(lèi)型控制方式作業(yè)類(lèi)型優(yōu)先級(jí)狀態(tài)聯(lián)機(jī)和脫機(jī)5）作業(yè)的狀態(tài)一個(gè)作業(yè)從提交給計(jì)算機(jī)系統(tǒng)到執(zhí)行結(jié)束退出系統(tǒng)，一般都要經(jīng)歷4個(gè)狀態(tài)：提交、后備（收容）、執(zhí)行和完成。（1）提交狀態(tài)：通過(guò)終端設(shè)備向計(jì)算機(jī)的磁盤(pán)輸入作業(yè)信息時(shí)所處的狀態(tài)。（2）后備狀態(tài)：作業(yè)的全部信息已輸入到磁盤(pán)的一個(gè)專(zhuān)用區(qū)(輸入井)中等待作業(yè)調(diào)度時(shí)所處的狀態(tài)。（3）執(zhí)行狀態(tài)：在后備作業(yè)隊(duì)列中的作業(yè)一旦被作業(yè)調(diào)度程序選中，為它分配了必要的資源，并且建立了進(jìn)程,開(kāi)始處理時(shí)所處的狀態(tài)。（4）完成狀態(tài)：作業(yè)完成其全部任務(wù)后，進(jìn)程撤消,做善后處理時(shí)的作業(yè)狀態(tài)稱(chēng)為完成狀態(tài)。106）作業(yè)狀態(tài)的及其轉(zhuǎn)換作業(yè)的狀態(tài)及其轉(zhuǎn)換執(zhí)行進(jìn)程調(diào)度

內(nèi)存

線(xiàn)程調(diào)度運(yùn)行等待就緒外存

就緒等待提交后備完成作業(yè)輸入作業(yè)調(diào)度

交換調(diào)度

作業(yè)調(diào)度

執(zhí)行7）作業(yè)的建立包括：作業(yè)的輸入；作業(yè)控制塊（JCB）的建立；多道批處理系統(tǒng)作業(yè)進(jìn)入系統(tǒng)建立JCB調(diào)入后備隊(duì)列插入作業(yè)調(diào)度算法創(chuàng)建進(jìn)程分配資源插入就緒隊(duì)列內(nèi)存調(diào)度CPU完成收回資源撤消JCB合格作業(yè)審核2.作業(yè)調(diào)度—批處理系統(tǒng)需要，分時(shí)系統(tǒng)不需要

用戶(hù)希望：自己作業(yè)的周轉(zhuǎn)時(shí)間盡少。

系統(tǒng)希望：作業(yè)的平均周轉(zhuǎn)時(shí)間盡少。

執(zhí)行作業(yè)調(diào)度考慮：

1)決定接納多少個(gè)作業(yè)。（取決于多道程序度）折衷：太多，影響到系統(tǒng)的服務(wù)質(zhì)量，如周轉(zhuǎn)時(shí)間長(zhǎng)。少時(shí)，系統(tǒng)的資源利用率和系統(tǒng)吞吐量太低。

2)決定接納哪些作業(yè)取決于所采用的調(diào)度算法。調(diào)度算法：先來(lái)先服務(wù)；簡(jiǎn)單短作業(yè)優(yōu)先，常用基于作業(yè)優(yōu)先級(jí)較常用響應(yīng)比高者優(yōu)先比較好二、低級(jí)調(diào)度—進(jìn)程調(diào)度

多道批處理、分時(shí)和實(shí)時(shí)OS都必須配置這級(jí)調(diào)度。系統(tǒng)按照某種算法把CPU動(dòng)態(tài)地分配給某一就緒進(jìn)程。進(jìn)程調(diào)度工作是通過(guò)進(jìn)程調(diào)度程序來(lái)完成的。1．低級(jí)調(diào)度的任務(wù)

(1)保存處理機(jī)的現(xiàn)場(chǎng)信息。

PC（程序計(jì)數(shù)器）、通用寄存器內(nèi)容等送入PCB。

(2)按某種算法選取進(jìn)程。如：優(yōu)先數(shù)算法、輪轉(zhuǎn)法。

(3)把處理器分配給進(jìn)程。由分派程序(Dispatcher)把處理器分配給進(jìn)程。從選中的進(jìn)程PCB中恢復(fù)處理機(jī)現(xiàn)場(chǎng)。2．進(jìn)程調(diào)度中的三個(gè)基本機(jī)制

(1)排隊(duì)器。排成一個(gè)或多個(gè)隊(duì)列，調(diào)度程序能最快地找到它。

(2)

分派器(分派程序)。分派器把由進(jìn)程調(diào)度程序所選定的進(jìn)程，將處理機(jī)分配給它。

(3)

上下文切換機(jī)制。當(dāng)前進(jìn)程新選進(jìn)程分派程序切換第一個(gè)上下文切換第二個(gè)上下文切換PC…寄存器CPU硬件現(xiàn)場(chǎng)當(dāng)前程序分派程序新選進(jìn)程PCB現(xiàn)場(chǎng)保留區(qū)PCB現(xiàn)場(chǎng)保留區(qū)PCB現(xiàn)場(chǎng)保留區(qū)CPU3.確定算法的原則具有公平性資源利用率高（特別是CPU利用率）。在交互式系統(tǒng)情況下要追求響應(yīng)時(shí)間（越短越好）。在批處理系統(tǒng)情況下要追求系統(tǒng)吞吐量。4．進(jìn)程調(diào)度方式

1)非搶占方式(NonpreemptiveMode)

分派程序一旦把處理機(jī)分配給某進(jìn)程后便讓它一直運(yùn)行下去，直到進(jìn)程完成或發(fā)生某事件而阻塞時(shí)，才把處理機(jī)分配給另一個(gè)進(jìn)程。

優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單，系統(tǒng)開(kāi)銷(xiāo)小，適用批處理系統(tǒng)。

缺點(diǎn)：難滿(mǎn)足緊急任務(wù)的要求，實(shí)時(shí)系統(tǒng)不宜采用。

2)搶占方式(PreemptiveMode)

當(dāng)一個(gè)進(jìn)程正在運(yùn)行時(shí)，系統(tǒng)可以基于某種原則，剝奪已分配給它的處理機(jī)，將之分配給其它進(jìn)程。

搶占原則有：優(yōu)先權(quán)原則、短進(jìn)程優(yōu)先原則、時(shí)間片原則。5．進(jìn)程調(diào)度的時(shí)機(jī)當(dāng)一個(gè)進(jìn)程運(yùn)行完畢，或由于某種錯(cuò)誤而終止運(yùn)行。當(dāng)前運(yùn)行進(jìn)程執(zhí)行了I/O指令（要求I/O）。當(dāng)前運(yùn)行進(jìn)程請(qǐng)求資源，若得不到滿(mǎn)足，只好調(diào)用阻塞原語(yǔ)，將自己阻塞。分時(shí)系統(tǒng)中時(shí)間片到。當(dāng)有一個(gè)優(yōu)先級(jí)更高的進(jìn)程就緒（可搶占式）。例如：新創(chuàng)建一個(gè)進(jìn)程；一個(gè)等待進(jìn)程變成就緒。在進(jìn)程通信中，執(zhí)行中的進(jìn)程執(zhí)行了某種原語(yǔ)操作（P操作，阻塞原語(yǔ)，喚醒原語(yǔ)）。三、中級(jí)調(diào)度中級(jí)調(diào)度的主要目的是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。暫時(shí)不能運(yùn)行的進(jìn)程將它們調(diào)至外存上去等待，此時(shí)的進(jìn)程狀態(tài)稱(chēng)為就緒駐外存狀態(tài)或掛起狀態(tài)。進(jìn)程重又具備運(yùn)行條件且內(nèi)存又稍有空閑時(shí)，由中級(jí)調(diào)度來(lái)決定把外存上的那些又具備運(yùn)行條件的就緒進(jìn)程重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)。三種調(diào)度方式的比較：

進(jìn)程調(diào)度：運(yùn)行頻率最高、不宜太復(fù)雜（避免占用太多的CPU時(shí)間）

作業(yè)調(diào)度：運(yùn)行頻率低（一批一批）、作業(yè)調(diào)度的周期較長(zhǎng)。中級(jí)調(diào)度：介于上述兩種調(diào)度之間。3.2調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則

一、調(diào)度隊(duì)列模型1．僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型

適用：分時(shí)系統(tǒng)中。FIFO新進(jìn)程僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型阻塞隊(duì)列交互用戶(hù)阻塞進(jìn)程調(diào)度是最基本的調(diào)度，必須配置CPU進(jìn)程調(diào)度就緒隊(duì)列結(jié)束時(shí)間片完/被中斷喚醒進(jìn)程調(diào)度原因（調(diào)度時(shí)刻）阻塞隊(duì)列交互用戶(hù)阻塞進(jìn)程調(diào)度就緒隊(duì)列結(jié)束時(shí)間片完喚醒現(xiàn)進(jìn)程運(yùn)行完畢現(xiàn)進(jìn)程阻塞優(yōu)先權(quán)高的進(jìn)程進(jìn)入就緒隊(duì)列現(xiàn)進(jìn)程“超時(shí)”/被中斷CPU2．具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型

適用：批處理系統(tǒng)優(yōu)先權(quán)隊(duì)列多個(gè)阻塞隊(duì)列3．同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型引入中級(jí)調(diào)度后:就緒狀態(tài):

內(nèi)存就緒、外存就緒阻塞狀態(tài)：內(nèi)存阻塞、外存阻塞換進(jìn)時(shí)間片到執(zhí)行就緒阻塞進(jìn)程調(diào)度等待某事件發(fā)生阻塞所等待的事件發(fā)生喚醒

進(jìn)程狀態(tài)轉(zhuǎn)換及進(jìn)程控制

外存

內(nèi)存就緒阻塞所等待的事件發(fā)生喚醒換出換出換進(jìn)撤消創(chuàng)建創(chuàng)建掛起掛起激活激活活動(dòng)阻塞靜止阻塞靜止就緒活動(dòng)就緒圖

3-3具有三級(jí)調(diào)度時(shí)的調(diào)度隊(duì)列模型

就緒隊(duì)列進(jìn)程調(diào)度CPU就緒，掛起隊(duì)列（外存）中級(jí)調(diào)度(調(diào)入內(nèi)存)阻塞，掛起隊(duì)列（外存）阻塞隊(duì)列（內(nèi)存）等待事件進(jìn)程完成時(shí)間片完作業(yè)調(diào)度交互型作業(yè)后備隊(duì)列批量作業(yè)掛起事件出現(xiàn)事件出現(xiàn)活動(dòng)阻塞靜止阻塞靜止就緒活動(dòng)就緒二、選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則1．面向用戶(hù)的準(zhǔn)則

(1)周轉(zhuǎn)時(shí)間短。

周轉(zhuǎn)時(shí)間是指從作業(yè)被提交給系統(tǒng)開(kāi)始，到作業(yè)完成為止的這段時(shí)間間隔(稱(chēng)為作業(yè)周轉(zhuǎn)時(shí)間)。包括四部分：

1、作業(yè)在外存后備隊(duì)列上等待(作業(yè))調(diào)度的時(shí)間（作業(yè)等待）

2、進(jìn)程在就緒隊(duì)列上等待進(jìn)程調(diào)度的時(shí)間（在就緒隊(duì)列排隊(duì)）

3、進(jìn)程在CPU上執(zhí)行的時(shí)間

4、進(jìn)程等待I/O操作完成的時(shí)間。

（a）周轉(zhuǎn)時(shí)間

=完成時(shí)刻－提交時(shí)刻（到達(dá)時(shí)間）

=等待時(shí)間+運(yùn)行時(shí)間(CPU)對(duì)于進(jìn)入系統(tǒng)的n個(gè)作業(yè)而言，平均周轉(zhuǎn)時(shí)間T為:i＝1用于衡量不同調(diào)度算法對(duì)同一作業(yè)流的調(diào)度性能：平均周轉(zhuǎn)時(shí)間越小，該作業(yè)調(diào)度算法的性能越好。等待時(shí)間越長(zhǎng)，用戶(hù)的滿(mǎn)意度越低。(b)帶權(quán)周轉(zhuǎn)時(shí)間

W=作業(yè)周轉(zhuǎn)時(shí)間T／提供服務(wù)時(shí)間（CPU)它能說(shuō)明作業(yè)i的相對(duì)等待時(shí)間。n

平均帶權(quán)周轉(zhuǎn)時(shí)間W=（ΣWi）／n

i=1用于衡量同一調(diào)度算法對(duì)不同作業(yè)流的調(diào)度性能(長(zhǎng)短任務(wù)差別)：平均帶權(quán)周轉(zhuǎn)時(shí)間越小，作業(yè)調(diào)度算法對(duì)該作業(yè)流的調(diào)度性能越好。

對(duì)于批處理系統(tǒng)，主要依據(jù)平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間來(lái)作為衡量調(diào)度算法性能的指標(biāo)；而對(duì)于分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)，外加平均響應(yīng)時(shí)間作為衡量調(diào)度算法性能的指標(biāo)。

(2)響應(yīng)時(shí)間快。評(píng)價(jià)分時(shí)系統(tǒng)的性能。

響應(yīng)時(shí)間:

是從用戶(hù)通過(guò)鍵盤(pán)提交一個(gè)請(qǐng)求開(kāi)始，直至系統(tǒng)首次產(chǎn)生響應(yīng)為止的時(shí)間。包括三部分：

1、從鍵盤(pán)輸入的請(qǐng)求信息傳送到處理機(jī)的時(shí)間。

2、處理機(jī)對(duì)請(qǐng)求信息進(jìn)行處理的時(shí)間。

3、響應(yīng)信息回送到終端顯示器的時(shí)間。

(3)截止時(shí)間的保證。評(píng)價(jià)實(shí)時(shí)系統(tǒng)。(4)優(yōu)先權(quán)準(zhǔn)則。批處理、分時(shí)、實(shí)時(shí)系統(tǒng)中都可遵循。面向系統(tǒng)的準(zhǔn)則

系統(tǒng)吞吐量高；處理機(jī)利用率好；各類(lèi)資源的平衡利用;3.3調(diào)

度

算

法

一、先來(lái)先服務(wù)調(diào)度算法(FCFS)

算法:也稱(chēng)為先進(jìn)先出（FIFO），或嚴(yán)格排隊(duì)方式。

對(duì)于作業(yè)調(diào)度：從后備作業(yè)隊(duì)列中（按進(jìn)入的時(shí)間順序排隊(duì)）選擇隊(duì)首一個(gè)或幾個(gè)作業(yè)，調(diào)入內(nèi)存，創(chuàng)建進(jìn)程，放入就緒隊(duì)列。

對(duì)于進(jìn)程調(diào)度：從就緒隊(duì)列中選擇一個(gè)最先進(jìn)入隊(duì)列的進(jìn)程，將CPU分配于它。

適用：進(jìn)程調(diào)度、作業(yè)調(diào)度

優(yōu)點(diǎn):實(shí)現(xiàn)簡(jiǎn)單

缺點(diǎn):

沒(méi)考慮進(jìn)程的優(yōu)先級(jí)

例1：有四個(gè)作業(yè)（或進(jìn)程），他們相應(yīng)的時(shí)間見(jiàn)下表：

表：比較極端作業(yè)類(lèi)型的FCFS的調(diào)度性能作業(yè)到達(dá)時(shí)間

Tin服務(wù)時(shí)間Tr開(kāi)始時(shí)間TS結(jié)束時(shí)間Tc周轉(zhuǎn)時(shí)間T帶權(quán)周轉(zhuǎn)時(shí)間WA0101TA=1WA=1B11001101TB=100WB=1C21101102TC=100WC=100D3100102202TD=199WD=1.99平均=100=26問(wèn)題：C的周轉(zhuǎn)時(shí)間是所需要處理時(shí)間的100倍！作業(yè)D的周轉(zhuǎn)時(shí)間近乎是C的兩倍，但它的帶權(quán)周轉(zhuǎn)時(shí)間卻低于2.0。先來(lái)先服務(wù)（FCFS）

例2．更一般的情況，設(shè)有五個(gè)作業(yè)，見(jiàn)下表。表：更一般作業(yè)類(lèi)型的FCFS的調(diào)度性能

作業(yè)到達(dá)時(shí)間Tin服務(wù)時(shí)間Tr開(kāi)始時(shí)間Ts結(jié)束時(shí)間Tc周轉(zhuǎn)時(shí)間T帶權(quán)周轉(zhuǎn)時(shí)間WA0303TA=3WA=1B2639TB=7WB=1.17C44913TC=9WC=2.25D651318TD=12WD=2.40.E821820TE=12WE=6平均=8.60=2.56同樣，看到作業(yè)E的不利情況。結(jié)論：有利于長(zhǎng)作業(yè)(進(jìn)程)，不利于短作業(yè)(進(jìn)程)。即：有利于CPU繁忙型的作業(yè)，不利于I/O繁忙型的作業(yè)(進(jìn)程)。二、短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法（SJ(P)F）

降低對(duì)長(zhǎng)作業(yè)有利的一種方法就是短作業(yè)優(yōu)先策略，見(jiàn)下表：表:SJF的調(diào)度性能作業(yè)到達(dá)時(shí)間Tin服務(wù)時(shí)間Tr開(kāi)始時(shí)間Ts結(jié)束時(shí)間Tc

=1.84031115939152011TA=3TB=7TC=11TD=14TE=3=7.608364522046ABCDE→→→→WE=1.50WA=1WB=1.17WC=2.75WD=2.80ECDAB周轉(zhuǎn)時(shí)間T=結(jié)束時(shí)間Tc-到達(dá)時(shí)間Tin=3-0=3周轉(zhuǎn)時(shí)間T帶權(quán)周轉(zhuǎn)時(shí)間W=周轉(zhuǎn)時(shí)間T/服務(wù)時(shí)間Tr=3/3=1帶權(quán)周轉(zhuǎn)時(shí)間W平均結(jié)束下一步下一步下一步下一步下一步下一步下一步適用：適用：進(jìn)程調(diào)度、作業(yè)調(diào)度優(yōu)點(diǎn)：易于實(shí)現(xiàn)，效率比較高，降低作業(yè)的平均等待時(shí)間。缺點(diǎn)：1、只照顧短作業(yè)而不考慮長(zhǎng)作業(yè)的利益，長(zhǎng)作業(yè)長(zhǎng)時(shí)間等待而“餓死”。

2、未考慮作業(yè)的緊迫程度3、估計(jì)執(zhí)行時(shí)間不足，算法無(wú)法真正實(shí)現(xiàn)有利短作業(yè)不利長(zhǎng)作業(yè)三、高優(yōu)先權(quán)優(yōu)先調(diào)度算法（HPF）

算法：總是把處理機(jī)分配給就緒隊(duì)列中具有最高優(yōu)先權(quán)的進(jìn)程。

適用：作業(yè)調(diào)度、進(jìn)程調(diào)度

分類(lèi)：

1)非搶占式優(yōu)先權(quán)算法用于批處理系統(tǒng)中、實(shí)時(shí)性不高的實(shí)時(shí)系統(tǒng)中。

2）搶占式優(yōu)先權(quán)調(diào)度算法原進(jìn)程新進(jìn)程CPU運(yùn)行Pi>Pj,進(jìn)程切換適用：分時(shí)系統(tǒng)實(shí)時(shí)系統(tǒng)PiPj優(yōu)先權(quán)的類(lèi)型

1)靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時(shí)確定的，且在進(jìn)程的整個(gè)運(yùn)行期間保持不變。如:0～7或0～255中的某一整數(shù)表示優(yōu)先權(quán)。

依據(jù)：

(1)進(jìn)程類(lèi)型。系統(tǒng)進(jìn)程（接收進(jìn)程）：高；用戶(hù)進(jìn)程：低。

(2)進(jìn)程對(duì)資源的需求。進(jìn)程估計(jì)CPU時(shí)間、內(nèi)存需要量少：高。

(3)用戶(hù)要求。進(jìn)程緊迫程度、用戶(hù)所付費(fèi)用確定。

優(yōu)點(diǎn)：簡(jiǎn)單易行，系統(tǒng)開(kāi)銷(xiāo)?。?/p>

缺點(diǎn)：不夠精確，優(yōu)先權(quán)低的長(zhǎng)作業(yè)長(zhǎng)期沒(méi)有被調(diào)度的情況。

適用：要求不高的系統(tǒng)中。2)動(dòng)態(tài)優(yōu)先權(quán)

在進(jìn)程創(chuàng)建時(shí)創(chuàng)立一個(gè)優(yōu)先權(quán)，但在其生命周期內(nèi)優(yōu)先數(shù)可以動(dòng)態(tài)變化。如:等待時(shí)間長(zhǎng)優(yōu)先數(shù)可改變。非搶占式優(yōu)先權(quán)算法—例（1：優(yōu)先權(quán)最高）EG： 進(jìn)程

到達(dá)時(shí)間

服務(wù)時(shí)間

優(yōu)先權(quán)

P1 0.0 73

P2 2.0 42

P3 4.0 14

P4 5.0 41Gantt圖平均周轉(zhuǎn)時(shí)間=((7-0)+(15-2)+(16-4)+(11-5))/4=8.5P1P202457111516P4P3搶占式優(yōu)先權(quán)算法—例（1：優(yōu)先權(quán)最高）EG： 進(jìn)程

到達(dá)時(shí)間

服務(wù)時(shí)間

優(yōu)先權(quán)

P1 0.0 73

P2 2.0 42

P3 4.0 14

P4 5.0 41Gantt圖平均周轉(zhuǎn)時(shí)間=((15-0)+(10-2)+(16-4)+(9-5))/4=9.75P1P202459101516P4P3P2P1四、高響應(yīng)比優(yōu)先調(diào)度算法（HRP

）

響應(yīng)比是指作業(yè)的響應(yīng)時(shí)間與作業(yè)估計(jì)運(yùn)行時(shí)間的比值。

選擇原則：優(yōu)先選取響應(yīng)比值最大的作業(yè)。即兼顧等待時(shí)間長(zhǎng)和運(yùn)行時(shí)間短的作業(yè)，它是FCFS和SJF算法的結(jié)合?？朔损囸I狀態(tài)，兼顧了長(zhǎng)作業(yè)。響應(yīng)比＝1＋等待時(shí)間/要求服務(wù)時(shí)間

表：HRP的調(diào)度性能作業(yè)到達(dá)時(shí)間Tin服務(wù)時(shí)間Tr開(kāi)始時(shí)間Ts完成時(shí)間Tc

=2.14039151339132015TA=3TB=7TC=9TD=14TE=7=8.008364522046ABCDE→→→→WE=3.50WA=1WB=1.17WC=2.25WD=2.80ECDAB周轉(zhuǎn)時(shí)間T=結(jié)束時(shí)間Tc-到達(dá)時(shí)間Tin=3-0=3周轉(zhuǎn)時(shí)間T帶權(quán)周轉(zhuǎn)時(shí)間W=周轉(zhuǎn)時(shí)間T/服務(wù)時(shí)間Tr=3/3=1帶權(quán)周轉(zhuǎn)時(shí)間W平均=[(9-4)+4]/4=2.25=[(9-6)+5]/5=1.6=[(9-8)+2]/2=1.5RCRDRERD=[(13-6)+5]/5=2.4RE=[(13-8)+2]/2=3.5結(jié)束下一步下一步下一步下一步下一步最高響應(yīng)比（HRP）五、基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法（RR）

在分時(shí)系統(tǒng)中，為了滿(mǎn)足系統(tǒng)對(duì)響應(yīng)時(shí)間的要求，通常采用時(shí)間片輪轉(zhuǎn)調(diào)度算法。1.簡(jiǎn)單輪轉(zhuǎn)法(固定時(shí)間片輪轉(zhuǎn)法）--早期

1）原理：系統(tǒng)把所有就緒進(jìn)程按到達(dá)的先后順序（FIFO）形成一個(gè)就緒隊(duì)列，就緒隊(duì)列中的所有進(jìn)程按時(shí)間片依次輪流獲得處理機(jī)。系統(tǒng)能在給定的時(shí)間內(nèi)響應(yīng)所有用戶(hù)的請(qǐng)求。2)時(shí)間片大小的確定

a.對(duì)系統(tǒng)性能有很大影響：如：時(shí)間片很?。河欣套鳂I(yè)、頻繁地發(fā)生中斷、進(jìn)程上下文的切換。時(shí)間片太長(zhǎng)，每個(gè)進(jìn)程都能在一個(gè)時(shí)間片內(nèi)完成，退化為FCFS算法，無(wú)法滿(mǎn)足交互式用戶(hù)的需求。

b.可行選取：時(shí)間片略大于一次典型的交互所需要的時(shí)間，可使大多數(shù)進(jìn)程在一個(gè)時(shí)間片內(nèi)完成。

時(shí)間片的大小應(yīng)根據(jù)進(jìn)程要求系統(tǒng)給出應(yīng)答的時(shí)間和進(jìn)入系統(tǒng)的進(jìn)程數(shù)來(lái)決定?？梢员硎緸椋?/p>

其中，q是時(shí)間片的大小，T是系統(tǒng)的響應(yīng)時(shí)間，N是進(jìn)入系統(tǒng)的進(jìn)程數(shù)。例：有五個(gè)任務(wù)A,B,C,D,E，它們幾乎同時(shí)先后到達(dá)，預(yù)計(jì)它們運(yùn)行時(shí)間為10，6，2，4，8min，采用時(shí)間片輪轉(zhuǎn)算法，令時(shí)間片為2min，計(jì)算其平均進(jìn)程周轉(zhuǎn)時(shí)間。（進(jìn)程切換可不考慮）解：5個(gè)任務(wù)輪流執(zhí)行的情況為：第1輪(A,B,C,D,E)

第2輪(A,B,D,E)

第3輪(A,B,E)

第4輪(A,E)

第5輪(A)

平均周轉(zhuǎn)時(shí)間T=(30+22+6+16+28)/5=20.4min3)簡(jiǎn)單輪轉(zhuǎn)法的優(yōu)缺點(diǎn):

優(yōu)點(diǎn)：簡(jiǎn)單、方便。缺點(diǎn)：

a.由于采用固定時(shí)間片的方式，調(diào)度欠靈活。

b.服務(wù)質(zhì)量不夠理想。改進(jìn)：

a.將固定時(shí)間片方式改為可變時(shí)間片方式；

ⅰ.固定周期輪轉(zhuǎn)法:每一輪調(diào)度中所得