第三章處理機調度與死鎖3.1處理機調度的層次3.2調度隊列模型和調度準則3.3調度算法3.4實時調度

3.5產生死鎖的原因和必要條件3.6預防死鎖的方法

在多道程序環境下，進程數目往往多于處理機數目，致使它們爭用處理機。這就要求系統能按某種算法，動態地把處理機分配給就緒隊列中的一個進程，使之執行。分配處理機的任務是由進程調度程序完成的，算法的優劣直接影響整個系統的性能。它是操作系統設計的中心問題之一。進程調度要解決的問題:WHAT：按什么原則分配CPU—進程調度算法

WHEN：何時分配CPU—進程調度的時機

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

一、高級調度-作業調度1．作業的基本概念1）作業、作業步

作業：是用戶一次請求計算機系統為它完成任務所進行的工作總和。

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

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

。

作業管理:

一個作業從輸入到輸出的一個過程。大致分成：作業提交、作業調度、作業控制、和作業退出。作業步之間的關系：

·每個作業步運行的結果產生下一個作業步所需要的文件。

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

編輯編譯連接運行

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

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

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

程序作業由三部分組成數據作業說明書（說明用戶的控制意圖）

4）作業控制塊（JCB）：

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

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

內存

線程調度運行等待就緒外存

就緒等待提交后備完成作業輸入作業調度

交換調度

作業調度

執行7）作業的建立包括：作業的輸入；作業控制塊（JCB）的建立；多道批處理系統作業進入系統建立JCB調入后備隊列插入作業調度算法創建進程分配資源插入就緒隊列內存調度CPU完成收回資源撤消JCB合格作業審核2.作業調度—批處理系統需要，分時系統不需要

用戶希望：自己作業的周轉時間盡少。

系統希望：作業的平均周轉時間盡少。

執行作業調度考慮：

1)決定接納多少個作業。（取決于多道程序度）折衷：太多，影響到系統的服務質量，如周轉時間長。少時，系統的資源利用率和系統吞吐量太低。

2)決定接納哪些作業取決于所采用的調度算法。調度算法：先來先服務；簡單短作業優先，常用基于作業優先級較常用響應比高者優先比較好二、低級調度—進程調度

多道批處理、分時和實時OS都必須配置這級調度。系統按照某種算法把CPU動態地分配給某一就緒進程。進程調度工作是通過進程調度程序來完成的。1．低級調度的任務

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

PC（程序計數器）、通用寄存器內容等送入PCB。

(2)按某種算法選取進程。如：優先數算法、輪轉法。

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

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

(2)

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

(3)

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

1)非搶占方式(NonpreemptiveMode)

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

優點：實現簡單，系統開銷小，適用批處理系統。

缺點：難滿足緊急任務的要求，實時系統不宜采用。

2)搶占方式(PreemptiveMode)

當一個進程正在運行時，系統可以基于某種原則，剝奪已分配給它的處理機，將之分配給其它進程。

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

進程調度：運行頻率最高、不宜太復雜（避免占用太多的CPU時間）

作業調度：運行頻率低（一批一批）、作業調度的周期較長。中級調度：介于上述兩種調度之間。3.2調度隊列模型和調度準則

一、調度隊列模型1．僅有進程調度的調度隊列模型

適用：分時系統中。FIFO新進程僅有進程調度的調度隊列模型阻塞隊列交互用戶阻塞進程調度是最基本的調度，必須配置CPU進程調度就緒隊列結束時間片完/被中斷喚醒進程調度原因（調度時刻）阻塞隊列交互用戶阻塞進程調度就緒隊列結束時間片完喚醒現進程運行完畢現進程阻塞優先權高的進程進入就緒隊列現進程“超時”/被中斷CPU2．具有高級和低級調度的調度隊列模型

適用：批處理系統優先權隊列多個阻塞隊列3．同時具有三級調度的調度隊列模型引入中級調度后:就緒狀態:

內存就緒、外存就緒阻塞狀態：內存阻塞、外存阻塞換進時間片到執行就緒阻塞進程調度等待某事件發生阻塞所等待的事件發生喚醒

進程狀態轉換及進程控制

外存

內存就緒阻塞所等待的事件發生喚醒換出換出換進撤消創建創建掛起掛起激活激活活動阻塞靜止阻塞靜止就緒活動就緒圖

3-3具有三級調度時的調度隊列模型

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

(1)周轉時間短。

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

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

2、進程在就緒隊列上等待進程調度的時間（在就緒隊列排隊）

3、進程在CPU上執行的時間

4、進程等待I/O操作完成的時間。

（a）周轉時間

=完成時刻－提交時刻（到達時間）

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

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

平均帶權周轉時間W=（ΣWi）／n

i=1用于衡量同一調度算法對不同作業流的調度性能(長短任務差別)：平均帶權周轉時間越小，作業調度算法對該作業流的調度性能越好。

對于批處理系統，主要依據平均周轉時間和平均帶權周轉時間來作為衡量調度算法性能的指標；而對于分時系統和實時系統，外加平均響應時間作為衡量調度算法性能的指標。

(2)響應時間快。評價分時系統的性能。

響應時間:

是從用戶通過鍵盤提交一個請求開始，直至系統首次產生響應為止的時間。包括三部分：

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

2、處理機對請求信息進行處理的時間。

3、響應信息回送到終端顯示器的時間。

(3)截止時間的保證。評價實時系統。(4)優先權準則。批處理、分時、實時系統中都可遵循。面向系統的準則

系統吞吐量高；處理機利用率好；各類資源的平衡利用;3.3調

度

算

法

一、先來先服務調度算法(FCFS)

算法:也稱為先進先出（FIFO），或嚴格排隊方式。

對于作業調度：從后備作業隊列中（按進入的時間順序排隊）選擇隊首一個或幾個作業，調入內存，創建進程，放入就緒隊列。

對于進程調度：從就緒隊列中選擇一個最先進入隊列的進程，將CPU分配于它。

適用：進程調度、作業調度

優點:實現簡單

缺點:

沒考慮進程的優先級

例1：有四個作業（或進程），他們相應的時間見下表：

表：比較極端作業類型的FCFS的調度性能作業到達時間

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

例2．更一般的情況，設有五個作業，見下表。表：更一般作業類型的FCFS的調度性能

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

降低對長作業有利的一種方法就是短作業優先策略，見下表：表:SJF的調度性能作業到達時間Tin服務時間Tr開始時間Ts結束時間Tc

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

2、未考慮作業的緊迫程度3、估計執行時間不足，算法無法真正實現有利短作業不利長作業三、高優先權優先調度算法（HPF）

算法：總是把處理機分配給就緒隊列中具有最高優先權的進程。

適用：作業調度、進程調度

分類：

1)非搶占式優先權算法用于批處理系統中、實時性不高的實時系統中。

2）搶占式優先權調度算法原進程新進程CPU運行Pi>Pj,進程切換適用：分時系統實時系統PiPj優先權的類型

1)靜態優先權靜態優先權是在創建進程時確定的，且在進程的整個運行期間保持不變。如:0～7或0～255中的某一整數表示優先權。

依據：

(1)進程類型。系統進程（接收進程）：高；用戶進程：低。

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

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

優點：簡單易行，系統開銷?。?/p>

缺點：不夠精確，優先權低的長作業長期沒有被調度的情況。

適用：要求不高的系統中。2)動態優先權

在進程創建時創立一個優先權，但在其生命周期內優先數可以動態變化。如:等待時間長優先數可改變。非搶占式優先權算法—例（1：優先權最高）EG： 進程

到達時間

服務時間

優先權

P1 0.0 73

P2 2.0 42

P3 4.0 14

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

到達時間

服務時間

優先權

P1 0.0 73

P2 2.0 42

P3 4.0 14

P4 5.0 41Gantt圖平均周轉時間=((15-0)+(10-2)+(16-4)+(9-5))/4=9.75P1P202459101516P4P3P2P1四、高響應比優先調度算法（HRP

）

響應比是指作業的響應時間與作業估計運行時間的比值。

選擇原則：優先選取響應比值最大的作業。即兼顧等待時間長和運行時間短的作業，它是FCFS和SJF算法的結合?？朔损囸I狀態，兼顧了長作業。響應比＝1＋等待時間/要求服務時間

表：HRP的調度性能作業到達時間Tin服務時間Tr開始時間Ts完成時間Tc

=2.14039151339132015TA=3TB=7TC=9TD=14TE=7=8.008364522046ABCDE→→→→WE=3.50WA=1WB=1.17WC=2.25WD=2.80ECDAB周轉時間T=結束時間Tc-到達時間Tin=3-0=3周轉時間T帶權周轉時間W=周轉時間T/服務時間Tr=3/3=1帶權周轉時間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結束下一步下一步下一步下一步下一步最高響應比（HRP）五、基于時間片的輪轉調度算法（RR）

在分時系統中，為了滿足系統對響應時間的要求，通常采用時間片輪轉調度算法。1.簡單輪轉法(固定時間片輪轉法）--早期

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

a.對系統性能有很大影響：如：時間片很?。河欣套鳂I、頻繁地發生中斷、進程上下文的切換。時間片太長，每個進程都能在一個時間片內完成，退化為FCFS算法，無法滿足交互式用戶的需求。

b.可行選?。簳r間片略大于一次典型的交互所需要的時間，可使大多數進程在一個時間片內完成。

時間片的大小應根據進程要求系統給出應答的時間和進入系統的進程數來決定?？梢员硎緸椋?/p>

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

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

第3輪(A,B,E)

第4輪(A,E)

第5輪(A)

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

優點：簡單、方便。缺點：

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

b.服務質量不夠理想。改進：

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

ⅰ.固定周期輪轉法:每一輪調度中所得