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

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

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

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

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

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

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

作業(yè)步：作業(yè)加工工作中的一個相對獨立的步驟稱為作業(yè)步。對作業(yè)的處理一般有這樣幾個作業(yè)步：

編輯（修改）、編譯、連接、運行

。

作業(yè)管理:

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

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

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

編輯編譯連接運行

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

脫機作業(yè)（批處理作業(yè)）：使用作業(yè)控制語言來書寫一份作業(yè)控制說明書，規(guī)定如何控制作業(yè)的執(zhí)行。

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

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

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

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

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

內(nèi)存

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

就緒等待提交后備完成作業(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)入后備隊列插入作業(yè)調(diào)度算法創(chuàng)建進(jìn)程分配資源插入就緒隊列內(nèi)存調(diào)度CPU完成收回資源撤消JCB合格作業(yè)審核2.作業(yè)調(diào)度—批處理系統(tǒng)需要，分時系統(tǒng)不需要

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

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

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

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

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

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

(1)保存處理機的現(xiàn)場信息。

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

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

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

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

(2)

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

(3)

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

1)非搶占方式(NonpreemptiveMode)

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

優(yōu)點：實現(xiàn)簡單，系統(tǒng)開銷小，適用批處理系統(tǒng)。

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

2)搶占方式(PreemptiveMode)

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

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

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

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

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

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

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

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

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

外存

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

3-3具有三級調(diào)度時的調(diào)度隊列模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

響應(yīng)時間:

是從用戶通過鍵盤提交一個請求開始，直至系統(tǒng)首次產(chǎn)生響應(yīng)為止的時間。包括三部分：

1、從鍵盤輸入的請求信息傳送到處理機的時間。

2、處理機對請求信息進(jìn)行處理的時間。

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

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

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

度

算

法

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

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

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

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

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

優(yōu)點:實現(xiàn)簡單

缺點:

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

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

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

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

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

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

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

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

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

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

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

分類：

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

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

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

依據(jù)：

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

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

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

優(yōu)點：簡單易行，系統(tǒng)開銷小；

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

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

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

到達(dá)時間

服務(wù)時間

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

P1 0.0 73

P2 2.0 42

P3 4.0 14

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

到達(dá)時間

服務(wù)時間

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

P1 0.0 73

P2 2.0 42

P3 4.0 14

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

）

響應(yīng)比是指作業(yè)的響應(yīng)時間與作業(yè)估計運行時間的比值。

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

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

=2.14039151339132015TA=3TB=7TC=9TD=14TE=7=8.008364522046ABCDE→→→→WE=3.50WA=1WB=1.17WC=2.25WD=2.80ECDAB周轉(zhuǎn)時間T=結(jié)束時間Tc-到達(dá)時間Tin=3-0=3周轉(zhuǎn)時間T帶權(quán)周轉(zhuǎn)時間W=周轉(zhuǎn)時間T/服務(wù)時間Tr=3/3=1帶權(quán)周轉(zhuǎn)時間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）五、基于時間片的輪轉(zhuǎn)調(diào)度算法（RR）

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

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

a.對系統(tǒng)性能有很大影響：如：時間片很小：有利短作業(yè)、頻繁地發(fā)生中斷、進(jìn)程上下文的切換。時間片太長，每個進(jìn)程都能在一個時間片內(nèi)完成，退化為FCFS算法，無法滿足交互式用戶的需求。

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

時間片的大小應(yīng)根據(jù)進(jìn)程要求系統(tǒng)給出應(yīng)答的時間和進(jìn)入系統(tǒng)的進(jìn)程數(shù)來決定。可以表示為：

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

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

第3輪(A,B,E)

第4輪(A,E)

第5輪(A)

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

優(yōu)點：簡單、方便。缺點：

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

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

a.將固定時間片方式改為可變時間片方式；

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