操作系統(tǒng),處理機調度與死鎖教案

Page12023/2/6第三章處理機調度與死鎖操作系統(tǒng)Page22023/2/6第三章處理機調度與死鎖重點掌握進程調度算法，各適用于何種情況

理解常用的幾種實時調度算法

理解產生死鎖的原因

掌握銀行家算法避免死鎖難點多道程序設計中的各種調度算法

響應比高者優(yōu)先調度算法的計算過程

銀行家算法

Page32023/2/6第三章處理機調度與死鎖知識點處理機調度及調度算法多處理機環(huán)境下的進程（線程）調度方式產生死鎖的原因和必要條件預防死鎖的方法，死鎖的檢測與解除銀行家算法Page42023/2/6第三章處理機調度與死鎖處理機是計算機系統(tǒng)中的重要資源在多道程序環(huán)境下，進程數目通常多于處理機的數目系統(tǒng)必須按一定方法動態(tài)地把處理機分配給就緒隊列中的一個進程處理機利用率和系統(tǒng)性能（吞吐量、響應時間）在很大程度上取決于處理機調度分配處理機的任務是由處理機調度程序完成的。它是操作系統(tǒng)設計的中心問題之一。WHAT：按什么原則分配CPU—進程調度算法WHEN：何時分配CPU—進程調度的時機

HOW：如何分配CPU—CPU調度過程（進程的上下文切換）Page52023/2/6第三章處理機調度與死鎖

處理機調度的層次和調度算法的目標作業(yè)與作業(yè)調度進程調度實時調度死鎖概述預防死鎖避免死鎖死鎖的檢測與解除Page62023/2/6處理機調度的基本概念作業(yè)是用戶在一次解題或一個事務處理過程中要求計算機系統(tǒng)所做工作的集合，包括用戶程序、所需的數據及命令等作業(yè)的狀態(tài)：一個作業(yè)進入系統(tǒng)到運行結束，一般需要經歷收容、運行、完成三個階段，與之相對應的是作業(yè)的三種狀態(tài)后備狀態(tài)運行狀態(tài)完成狀態(tài)Page72023/2/6運行狀態(tài)處理機調度的基本概念后備狀態(tài)完成狀態(tài)就緒阻塞執(zhí)行I/O完成I/O請求時間片完作業(yè)注冊作業(yè)調度進程調度終止作業(yè)作業(yè)狀態(tài)間轉換Page82023/2/63.1.1處理機調度的層次1.高級調度(HighScheduling)2.低級調度(LowLevelScheduling)3.中級調度(Intermediate-LevelScheduling)處理機調度的層次和調度算法的目標

Page92023/2/6高級、中級和低級調度高級調度(HighScheduling)

作業(yè)調度或長程調度（Long-TermScheduling）主要任務是按一定的原則對外存上處于后備狀態(tài)的作業(yè)進行選擇，給選中的作業(yè)分配內存、輸入/輸出設備等必要的資源，并建立相應的進程，放入就緒隊列，以使該作業(yè)的進程獲得競爭處理機的權利也稱為接納調度（AdmissionScheduling）高級調度的時間尺度通常是分鐘、小時或天Page102023/2/6高級、中級和低級調度在每次作業(yè)調度時，須決定：接納多少個作業(yè)即允許多少個作業(yè)同時在內存中運行，取決于多道程序度（DegreeofMultiprogramming）作業(yè)太多服務質量下降作業(yè)太少資源利用率低接納哪些作業(yè)

取決于作業(yè)調度算法先來先服務短作業(yè)優(yōu)先作業(yè)優(yōu)先權調度響應比調度→周轉時間太長→系統(tǒng)吞吐量太低

適當的折衷多道程序度：即允許多少個作業(yè)同時在內存中運行。周轉時間：從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時間間隔。吞吐量：是指在單位時間內系統(tǒng)所完成的作業(yè)數。Page112023/2/6高級、中級和低級調度低級調度

進程調度或短程調度（Short-TermScheduling）主要任務是按照某種策略和方法選取一個處于就緒狀態(tài)的進程，將處理機分配給它常見的低級調度有非搶占式和搶占式兩種低級調度的時間尺度通常是毫秒級的。由于低級調度算法的頻繁使用，要求在實現(xiàn)時做到高效Page122023/2/6進程調度的任務

進程調度的任務是控制、協(xié)調進程對CPU的競爭,即按一定的調度算法從就緒隊列中選中一個進程，把CPU的使用權交給被選中的進程Page132023/2/6進程調度方式非搶占方式(Non-preemptiveMode)搶占方式(PreemptiveMode)Page142023/2/6進程調度方式非搶占方式(Non-preemptiveMode)

當某一進程正在處理機上執(zhí)行時，即使有某個更為重要或緊迫的進程進入就緒隊列，該進程仍繼續(xù)執(zhí)行，直到其完成或發(fā)生某種事件而進入完成或阻塞狀態(tài)時，才把處理機分配給更為重要或緊迫的進程引起進程調度的因素正在執(zhí)行的進程執(zhí)行完畢，或因發(fā)生某事件而不能再繼續(xù)執(zhí)行執(zhí)行中的進程因提出I/O請求而暫停執(zhí)行；在進程通信或同步過程中執(zhí)行了某種原語操作，如wait、Block、Wakeup原語優(yōu)點：算法簡單，系統(tǒng)開銷小缺點：緊急任務不能及時響應；短進程到達要等待長進程運行結束Page152023/2/6進程調度方式搶占方式(PreemptiveMode)

當某一進程正在處理機上執(zhí)行時，若有某個更為重要或緊迫的進程進入就緒隊列，則立即暫停正在執(zhí)行的進程，將處理機分配給這個更為重要或緊迫的進程搶占式調度主要有以下原則優(yōu)先權原則允許高優(yōu)先權的新到進程搶占當前進程的處理機短作業(yè)(進程)優(yōu)先原則允許執(zhí)行時間短的新到進程搶占當前進程的處理機時間片原則時間片用完后停止執(zhí)行，重新進行調度，適用于分時系統(tǒng)

優(yōu)點：適于時間要求嚴格的實時系統(tǒng)缺點：調度算法復雜，系統(tǒng)開銷大Page162023/2/6高級、中級和低級調度中級調度(Intermediate-LevelScheduling)又稱為內存調度引入目的是為了提高內存利用率和系統(tǒng)吞吐量。使那些暫時不能運行的進程不再占用寶貴的內存資源，而將它們調至外存上去等待主要任務是按照給定的原則和策略，將處于外存對換區(qū)中的重又具備運行條件的就緒進程調入內存，或將處于內存就緒狀態(tài)或內存阻塞狀態(tài)的進程交換到外存對換區(qū)Page172023/2/63.1.2處理機調度算法的目標處理機調度算法的共同目標資源利用率為提高系統(tǒng)的資源利用率，應使系統(tǒng)中的處理機和其它所有資源盡可能地保持忙碌狀態(tài)。CPU的利用率=CPU有效工作時間/（CPU有效工作時間+CPU空閑等待時間）公平性。指應使諸進程都獲得合理的CPU時間，不會發(fā)生進程饑餓現(xiàn)象。對相同類型的進程應獲得相同的服務，對于不同類型的進程，由于其緊急程度或重要性的不同，則應提供不同的服務。平衡性。盡可能保持系統(tǒng)資源使用的平衡性，使內存、外存和I/O設備的利用率高策略強制執(zhí)行。對所制訂的策略其中包括安全策略，只要需要，必須予以準確地執(zhí)行，即使會造成某些工作的延遲也要執(zhí)行。Page182023/2/6(1)平均周轉時間短。

(2)系統(tǒng)吞吐量高。(3)處理機利用率高。3.1.2處理機調度算法的目標批處理系統(tǒng)的目標Page192023/2/6周轉時間是指從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時間間隔。由四部分組成：作業(yè)在外存后備隊列上等待（作業(yè)）調度的時間進程在就緒隊列上等待進程調度的時間進程在CPU上執(zhí)行的時間進程等待I/O操作完成的時間。后3項是在一個作業(yè)的整個處理過程中，可能發(fā)生多次。3.1.2處理機調度算法的目標周轉時間Page202023/2/6周轉時間短平均周轉時間帶權周轉時間：進程（或作業(yè)）的周轉時間T與系統(tǒng)為它提供服務的時間TS之比，即W=T/TS。而平均帶權周轉時間則可表示為:3.1.2處理機調度算法的目標Page212023/2/6系統(tǒng)吞吐量高吞吐量指單位時間內系統(tǒng)所完成的作業(yè)數作業(yè)調度的方式和算法對吞吐量的大小有較大影響處理機利用率高

對于大、中型計算機，CPU價格十分昂貴，致使處理機的利用率成為衡量系統(tǒng)性能的十分重要的指標。而調度方式和算法對處理機的利用率起著十分重要的作用。如果單純是為使處理機利用率高，應盡量多的選擇計算量大的作業(yè)運行。這些要求之間存在一定的矛盾。3.1.2處理機調度算法的目標Page222023/2/63.1.2處理機調度算法的目標分時系統(tǒng)的目標響應時間快響應時間是指從用戶通過鍵盤提交一個請求開始，直至系統(tǒng)中首次產生響應為止的時間包括三部分時間：一是請求信息從鍵盤輸入開始，直到將其傳送到處理機的時間；二是處理機對請求信息進行處理的時間；三是將所形成的響應信息回送到終端顯示器的時間。均衡性用戶對響應時間的要求并非完全相同。對較復雜任務的響應時間允許較長，而對簡單任務的響應時間要短。均衡性是指系統(tǒng)響應時間的快慢應與用戶所請求服務的復雜性相適應。Page232023/2/6實時系統(tǒng)的目標截止時間保證截止時間是指某任務必須開始執(zhí)行的最遲時間或必須完成的最遲時間截止時間是實時系統(tǒng)中的重要指標可預測性。在實時系統(tǒng)中，可預測性顯得非常重要。3.1.2處理機調度算法的目標Page242023/2/6選擇調度方式和調度算法的若干準則各種系統(tǒng)主要目標周轉時間短響應時間快截止時間保證批處理系統(tǒng)分時系統(tǒng)實時系統(tǒng)等待時間短優(yōu)先權Page252023/2/6選擇調度方式和調度算法的若干準則等待時間短等待時間是在就緒隊列中等待所花的時間調度算法并不影響進程運行和執(zhí)行I/O的時間量；只影響進程在就緒隊列中等待所花費的時間優(yōu)先權準則在批處理、實時和分時系統(tǒng)中都可以選擇優(yōu)先權準則，以便讓緊急任務先處理有時還選擇搶占式調度方式Page262023/2/6第三章處理機調度與死鎖處理機調度的層次和調度算法的目標

作業(yè)與作業(yè)調度

進程調度實時調度死鎖概述預防死鎖避免死鎖死鎖的檢測與解除Page272023/2/6作業(yè)與作業(yè)調度在OS中調度的實質是一種資源分配，因而調度算法是指：根據系統(tǒng)的資源分配策略所規(guī)定的資源分配算法問題提出如何制定分配策略：對不同的系統(tǒng)和系統(tǒng)目標，通常采用不同的算法，如短作業(yè)優(yōu)先，時間片輪轉等有些算法適用于作業(yè)調度，有些適用于進程調度，有些兩者皆可3.2.1批處理系統(tǒng)中的作業(yè)1.作業(yè)和作業(yè)步

⑴作業(yè)：作業(yè)是一個比程序更為廣泛的概念，它不僅包含了通常的程序和數據，而且還應配有一份作業(yè)說明書，系統(tǒng)根據該說明書來對程序的運行進行控制。在批處理系統(tǒng)中，是以作業(yè)為基本單位，從外存調入內存的。

⑵作業(yè)步：在作業(yè)運行期間，每個作業(yè)都必須經過若干個相對獨立，又相互關聯(lián)的順序加工步驟才能得到結果。我們把其中的每一個加工步驟稱一個作業(yè)步，各作業(yè)步之間存在著相互聯(lián)系，往往是上一個作業(yè)步的輸出作為下一個作業(yè)步的輸入。

2.作業(yè)控制塊JCB

在多道批處理系統(tǒng)中，為每個作業(yè)設置了一個作業(yè)控制塊JCB，它是作業(yè)在系統(tǒng)中存在的標志，其中保存了系統(tǒng)對作業(yè)進行管理和調度所需的全部信息。在作業(yè)運行期間，系統(tǒng)就按照JCB中的信息，和作業(yè)說明書對作業(yè)進行控制。3.作業(yè)運行的三個階段和三種狀態(tài)作業(yè)從進入系統(tǒng)到運行結束，通常需要經歷收容、運行和完成三個階段。相應的作業(yè)也就有“后備狀態(tài)”、“運行狀態(tài)”和“完成狀態(tài)”。

⑴收容階段：操作員把用戶提交的作業(yè)，通過某種輸入方式或SPOOLing系統(tǒng)，輸入到硬盤上，再為該作業(yè)建立JCB，并把它放入作業(yè)后備隊列中，相應的，此時作業(yè)的狀態(tài)為“后備狀態(tài)”。

⑵運行階段：當作業(yè)被作業(yè)調度選中后，便為它分配必要的資源和建立進程，并將它放入就緒隊列。一個作業(yè)從第一次進入就緒狀態(tài)開始，直到它運行結束前，在此期間都處于“運行狀態(tài)”。⑶完成階段：當作業(yè)運行完成、或發(fā)生異常情況而提前結束時，作業(yè)便進入完成階段，相應的作業(yè)狀態(tài)為“完成狀態(tài)”。此時系統(tǒng)中的“終止作業(yè)”程序，將會回收已分配給該作業(yè)的作業(yè)控制塊和所有資源，并將作業(yè)運行結果信息形成輸出文件后輸出。3.2.1批處理系統(tǒng)中的作業(yè)Page302023/2/63.2.1批處理系統(tǒng)中的作業(yè)SPOOLing（即外部設備聯(lián)機并行操作），它是關于慢速字符設備如何與計算機主機交換信息的一種技術，通常稱為“假脫機技術”。spooling系統(tǒng)的三大組成部分：<1>.輸入井和輸出井<2>.輸入緩沖和輸出緩沖<3>.輸入進程SPi和輸出進程Spo例如：若有進程要求對它打印輸出時，SPOOLing系統(tǒng)并不是將這臺打印機直接分配給SPOOLING進程，而是在共享設備（磁盤）上的輸出SPOOLing存儲區(qū)中為其分配一塊存儲空間，進程的輸出數據以文件形式存放于此。各進程的數據輸出文件形成了一個輸出隊列，由輸出SPOOLing系統(tǒng)控制這臺打印機進程，依次將隊列中的輸出文件實際打印輸出。在SPOOLing系統(tǒng)中，實際上并沒有為任何進程分配，而只是在輸入井和輸出井中，為進程分配一存儲區(qū)和建立一張I/O請求表。這樣，便把獨占設備改造為共享設備。

作業(yè)調度的主要任務

也稱為接納調度，根據JCB中的信息，檢查系統(tǒng)中的資源，能否滿足作業(yè)對資源的需求，以及按照一定的調度算法，從外存的后備隊列中，選取某些作業(yè)調入內存，并為它們創(chuàng)建進程、分配必要的資源。然后再將新創(chuàng)建的進程，排在就緒隊列上等待調度。因此，也把作業(yè)調度（AdmissionScheduling）。

★在每次執(zhí)行作業(yè)調度時，都須做出以下兩個決定

①接納多少個作業(yè)取決于多道程序度，即允許多少個作業(yè)同時在內存中運行。

②接納哪些作業(yè)取決于所采用的調度算法。3.2.2作業(yè)調度的主要任務Page322023/2/6先來先服務(FCFS)/先進先出(FIFO)調度算法按照作業(yè)/進程進入系統(tǒng)的先后次序進行調度，先進入系統(tǒng)者先調度；即啟動等待時間最長的作業(yè)/進程是一種最簡單的調度算法，即可用于作業(yè)調度，也可用于進程調度幾個術語到達時間、服務時間、開始時間完成時間、等待時間周轉時間：完成時間-到達時間帶權周轉時間：周轉時間/服務時間①3.2.3先來先服務和短作業(yè)優(yōu)先調度算法

Page332023/2/6先來先服務和短作業(yè)優(yōu)先算法進程名到達時間服務時間開始時間完成時間周轉時間帶權周轉時間平均04A13B25C32D44E044476先來先服務（先進先出）：712101214111418141225.53.592.8AAAABBBCCCCCDDEEEE05101518tPage342023/2/6先來先服務和短作業(yè)優(yōu)先算法

先來先服務（先進先出）優(yōu)缺點

比較有利于長作業(yè)（進程），而不利于短作業(yè)（進程）有利于CPU繁忙型作業(yè)（進程），而不利于I/O繁忙型作業(yè)（進程）用于批處理系統(tǒng)，不適于分時系統(tǒng)Page352023/2/6先來先服務和短作業(yè)優(yōu)先算法短作業(yè)(進程)優(yōu)先調度算法SJ(P)F短作業(yè)(進程)優(yōu)先調度算法SJ(P)F，以要求運行時間長短進行調度，即啟動要求運行時間最短的作業(yè)可以分別用于作業(yè)調度和進程調度短作業(yè)優(yōu)先(SJF)的調度算法，是從后備隊列中選擇一個或若干個估計運行時間最短的作業(yè)，將它們調入內存運行；而短進程優(yōu)先(SPF)調度算法，則是從就緒隊列中選出一估計運行時間最短的進程，將處理機分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機時，再重新調度②Page362023/2/6先來先服務和短作業(yè)優(yōu)先算法進程名到達時間服務時間開始時間完成時間周轉時間帶權周轉時間平均04A13B25C32D44E0441短作業(yè)/短進程優(yōu)先（SJF/SPF）：4633/26988/391399/413181616/540/52.1AAAABBBCCCCCDDEEEE05101518tPage372023/2/6FCFS/SJF調度算法的性能先來先服務和短作業(yè)優(yōu)先算法SJF能有效地降低作業(yè)的平均等待時間，提高系統(tǒng)吞吐量

作業(yè)調度情況算法進程名ABCDE平均到達時間01234服務時間43524FCFS完成時間47121418周轉時間461011149帶權周轉時間1225.53.52.8SJF完成時間4918613周轉時間4816398帶權周轉時間12.673.11.52.252.1SJF平均周轉時間和平均帶權周轉時間明顯改善Page382023/2/6先來先服務和短作業(yè)優(yōu)先算法SJ(P)F調度算法也存在不容忽視的缺點對長作業(yè)不利。嚴重的是，若一長作業(yè)(進程)進入系統(tǒng)的后備隊列(就緒隊列)，由于調度程序總是優(yōu)先調度那些(即使是后進來的)短作業(yè)(進程)，將導致長作業(yè)(進程)長期不被調度——饑餓完全未考慮作業(yè)(進程)的緊迫程度，因而不能保證緊迫性作業(yè)(進程)會被及時處理由于作業(yè)(進程)的長短只是根據用戶所提供的估計執(zhí)行時間而定的，而用戶又可能會有意或無意地縮短其作業(yè)的估計運行時間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調度。2023/2/6391、在單道批處理系統(tǒng)中，有五個作業(yè)進入輸入井的時間及需要執(zhí)行的時間如下表所示，并約定當這五個作業(yè)全部進入輸入井后立即進行調度，忽略調度的時間開銷。要求：寫出分別采用先來先服務和最短執(zhí)行時間優(yōu)先調度算法時的調度次序和作業(yè)平均周轉時間。課堂練習作業(yè)號進入輸入井時間需執(zhí)行時間（分鐘）開始執(zhí)行時間結束執(zhí)行時間周轉時間（分鐘）110∶0040

210∶1030

310∶2020

410∶3025

510∶4010

2023/2/640(1)先來先服務調度算法(FCFS)作業(yè)號進入輸入井時間需執(zhí)行時間（分鐘）開始執(zhí)行時間結束執(zhí)行時間周轉時間（分鐘）110∶0040

210∶1030

310∶2020

410∶3025

510∶4010

2023/2/641(1)先來先服務調度算法(FCFS)作業(yè)號進入輸入井時間需執(zhí)行時間（分鐘）開始執(zhí)行時間結束執(zhí)行時間周轉時間（分鐘）110∶004010:40

11:2080

210∶1030

11:2011:50

100

310∶2020

11:5012:10

110

410∶3025

12:1012:35

125

510∶4010

12:3512:45

125

調度次序：1-2-3-4-5平均周轉時間為（80+100+110+125+125)/5=108分鐘2023/2/642(2)短作業(yè)優(yōu)先調度算法(SJF)作業(yè)號進入輸入井時間需執(zhí)行時間（分鐘）開始執(zhí)行時間結束執(zhí)行時間周轉時間（分鐘）110∶0040

210∶1030

310∶2020

410∶3025

510∶4010

2023/2/643(2)短作業(yè)優(yōu)先調度算法(SJF)作業(yè)號進入輸入井時間需執(zhí)行時間（分鐘）開始執(zhí)行時間結束執(zhí)行時間周轉時間（分鐘）110∶0040

12:0512:45

165

210∶1030

11:3512:05

115

310∶2020

10:5011:10

50

410∶3025

11:1011:35

65

510∶401010:40

10:50

10調度次序：5-3-4-2-1平均周轉時間為（165+115+50+65+10)/5=81分鐘3.2.4優(yōu)先級調度算法和高響應比優(yōu)先調度算法1.優(yōu)先級調度算法(priority-schedulingalgorithm)

基于作業(yè)的緊迫程度，由外部賦予作業(yè)相應的優(yōu)先級，調度算法是根據該優(yōu)先級進行調度的。這樣就可以保證緊迫性作業(yè)優(yōu)先運行。

2.高響應比優(yōu)先調度算法

高響應比優(yōu)先調度算法則是既考慮了作業(yè)的等待時間，又考慮作業(yè)運行時間的調度算法，因此既照顧了短作業(yè)，又不致使長作業(yè)的等待時間過長，從而改善了處理機調度的性能。

★高響應比優(yōu)先算法的實現(xiàn)優(yōu)先級的變化規(guī)律可描述為：由于等待時間與服務時間之和，就是系統(tǒng)對該作業(yè)的響應時間，故該優(yōu)先級又相當于響應比RP。據此，又可表示為：Page452023/2/6優(yōu)先權調度算法的類型非搶占式優(yōu)先權調度算法搶占式優(yōu)先權調度算法③3.2.4優(yōu)先級調度算法和高響應比優(yōu)先調度算法Page462023/2/6高優(yōu)先權優(yōu)先（HPF，HighestPriorityFirst）調度算法優(yōu)先權調度算法的類型（P92）非搶占式優(yōu)先權調度算法特點：系統(tǒng)一旦把處理機分配給就緒隊列中優(yōu)先權最高的進程后，該進程便一直執(zhí)行下去，直至完成，或因發(fā)生某事件使該進程放棄處理機時，系統(tǒng)才將處理機重新分配給另一優(yōu)先權最高的進程主要用于批處理系統(tǒng)中，也可用于某些對實時性要求不嚴的實時系統(tǒng)中Page472023/2/6高優(yōu)先權優(yōu)先（HPF—HighestPriorityFirst）調度算法優(yōu)先權調度算法的類型搶占式優(yōu)先權調度算法把處理機分配給優(yōu)先權最高的進程，但在執(zhí)行期間，只要出現(xiàn)另一個優(yōu)先權更高的進程，則進程調度程序就立即停止當前進程的執(zhí)行，并將處理機分配給新到的優(yōu)先權最高的進程注意：只要系統(tǒng)中出現(xiàn)一個新的就緒進程，就進行優(yōu)先權比較該調度算法，能更好地滿足緊迫作業(yè)的要求，故而常用于要求比較嚴格的實時系統(tǒng)中，以及對性能要求較高的批處理和分時系統(tǒng)中Page482023/2/6高優(yōu)先權優(yōu)先調度算法優(yōu)先權的類型（P94）靜態(tài)優(yōu)先權靜態(tài)優(yōu)先權在創(chuàng)建進程時確定，且在進程的整個運行期間保持不變。一般地，優(yōu)先權是利用某一范圍內的一個整數來表示的，例如，07或0255，又把該整數稱為優(yōu)先數確定進程靜態(tài)優(yōu)先權的依據進程類型:系統(tǒng)進程，用戶進程進程對資源的需求用戶要求靜態(tài)優(yōu)先權特點系統(tǒng)開銷小、不夠精確、一般用在要求不高的系統(tǒng)中問題：用戶將優(yōu)先權設的較高，對其他進程不利?。《踢M程優(yōu)先對長進程不利??！Page492023/2/6高優(yōu)先權優(yōu)先調度算法動態(tài)優(yōu)先權隨進程的推進或隨其等待時間的增加而改變，以獲得更好的調度性能可規(guī)定，在就緒隊列中的進程，隨其等待時間的增長，其優(yōu)先權以速率a提高具有相同優(yōu)先權初值的進程，則最先進入就緒隊列，其將因其動態(tài)優(yōu)先權變得最高而優(yōu)先獲得處理機，此即FCFS算法具有各不相同的優(yōu)先權初值的就緒進程，則優(yōu)先權初值低的進程，在等待了足夠的時間后，其優(yōu)先權便可能升為最高，從而可以獲得處理機當采用搶占式優(yōu)先權調度算法時，如果再規(guī)定當前進程的優(yōu)先權以速率b下降，則可防止一個長作業(yè)長期地壟斷處理機Page502023/2/6進程名到達時間服務時間靜態(tài)優(yōu)先權開始時間完成時間周轉時間帶權周轉時間平均靜態(tài)優(yōu)先權，非搶占式（1為高優(yōu)先權）高優(yōu)先權優(yōu)先調度算法04A413B225C332D544E1044148418111010/311161414/516181515/29.42.93考慮一下?lián)屨际?，情況如何？Page512023/2/6進程調度算法—優(yōu)先權、搶占式其中，RQ為就緒隊列指針，EP為運行隊列指針。Page522023/2/6進程名到達時間服務時間靜態(tài)優(yōu)先權開始時間完成時間周轉時間帶權周轉時間平均高優(yōu)先權優(yōu)先調度算法04A413B225C332D544E1016164484114318131111/516181515/29.83.14靜態(tài)優(yōu)先權，搶占式（1為高優(yōu)先權）ABBBEEEECCCCCAAADD05101518tBAACDEACD練習作業(yè)到達時間運行時間優(yōu)先級A082B141C264（高）Page532023/2/6假定在單CPU條件下有下列要執(zhí)行的作業(yè)：（1）用一個執(zhí)行時間圖描述在采用非搶占優(yōu)先級算法時執(zhí)行這些作業(yè)的情況；

（2）對于上述算法，各個作業(yè)的周轉時間是多少？平均周轉時間是多少？

（3）對于上述算法，各個作業(yè)的帶權周轉時間是多少？

平均帶權周轉時間是多少Page542023/2/6ACB01281418T任務執(zhí)行任務到達ABC（2）平均周轉時間：（8+12+17）/3＝12.33（3）平均帶權周轉時間：（8/8+12/6+17/3）/3＝2.22Page552023/2/6高優(yōu)先權優(yōu)先調度算法高響應比優(yōu)先調度算法（HRF）是FCFS和SJF的結合，克服了兩種算法的缺點調度策略：響應比最高的作業(yè)優(yōu)先啟動因等待時間+服務時間=該作業(yè)的響應時間，故該優(yōu)先權又相當于響應比RP。據此，又可表示為④Page562023/2/6高優(yōu)先權優(yōu)先調度算法對HRF的小結等待時間相同的作業(yè)，則要求服務的時間愈短，其優(yōu)先權愈高，要求服務的時間相同的作業(yè)，則等待時間愈長，其優(yōu)先權愈高，長作業(yè)，優(yōu)先權隨等待時間的增加而提高，其等待時間足夠長時，其優(yōu)先權便可升到很高，從而也可獲得處理機是一種折衷，既照顧了短作業(yè)，又考慮了作業(yè)到達的先后次序，又不會使長作業(yè)長期得不到服務。缺點：要進行響應比計算，增加了系統(tǒng)開銷——對短作業(yè)有利——是先來先服務——對長作業(yè)有利Page572023/2/6進程名到達時間服務時間響應比開始時間完成時間周轉時間帶權周轉時間平均高優(yōu)先權優(yōu)先調度算法04A13B25C32D44E044114181414/447629141212/579638.42.38高響應比優(yōu)先，非搶占式21.41.51231.752.42.25=當前時間-到達時間服務時間+服務時間練習Page582023/2/6假定在單CPU條件下有下列要執(zhí)行的作業(yè)：（1）用一個執(zhí)行時間圖描述在采用響應比高者優(yōu)先調度算法

執(zhí)行這些作業(yè)的情況；（2）計算各作業(yè)的周轉時間和平均周轉時間。作業(yè)到達時間運行時間A08B14C26假設有三個同時到達的作業(yè)J1、J2和J3，它們的執(zhí)行時間分別是T1、T2和T3，且T1<T2<T3。單處理機系統(tǒng)采用短作業(yè)優(yōu)先算法運行，則平均周轉時間是（

）。Page592023/2/6Page602023/2/6第三章處理機調度與死鎖處理機調度的層次和調度算法的目標

作業(yè)與作業(yè)調度進程調度實時調度死鎖概述預防死鎖避免死鎖死鎖的檢測與解除3.3.1進程調度的任務、機制和方式

1.進程調度任務

①保存處理機的現(xiàn)場信息：在進行調度時首先需要保存當前進程的處理機的現(xiàn)場信息，如程序計數器、多個通用寄存器中的內容等。

②按某種算法選取進程：調度程序按某種算法，從就緒隊列中選取一個進程，將其狀態(tài)改為運行狀態(tài)，并準備把處理機分配給它。

③把處理器分配給進程：由分派程序把處理器分配給該進程。此時需要將選中進程的進程控制塊內有關處理機現(xiàn)場的信息，裝入處理器相應的各個寄存器中，把處理器的控制權交予該進程，讓它從上次的斷點處恢復運行。3.3.1進程調度的任務、機制和方式

2.進程調度機制

⑴排隊器：事先將系統(tǒng)中的所有就緒進程，按照一定的策略，排成一個或多個隊列。以便調度程序能最快地找到它。以后每當有一個進程轉變?yōu)榫途w狀態(tài)時，排隊器便將它插入到相應的就緒隊列。⑵分派器：依據進程調度程序所選定的進程，將其從就緒隊列中取出，然后進行進程間的上下文切換，將處理機分配給新選出的進程。⑶上下文切換器：在對處理機進行切換時，會發(fā)生：①第一對上下文切換時，OS將保存當前進程的上下文，裝入分派程序的上下文，以便分派程序運行；②第二對上下文切換是移出分派程序的上下文，裝入新選進程上下文。3.3.1進程調度的任務、機制和方式

3.進程調度方式

⑴非搶占方式一旦把處理機分配給某進程后，就一直讓它運行下去，決不會因為時鐘中斷，或任何其它原因，去搶占該正在運行進程的處理機，直至該進程完成，或發(fā)生某事件而被阻塞時，才把處理機分配給其它進程。采用這種方式時，可能引起進程調度的因素可歸結為：①正在執(zhí)行的進程運行完畢，或因發(fā)生某事件而使其無法再繼續(xù)運行；②正在執(zhí)行中的進程，因提出I/O請求而暫停執(zhí)行；③在進程通信或同步過程中，執(zhí)行了某種原語操作，如Block原語。

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

缺點：但它不能用于分時系統(tǒng)和大多數實時系統(tǒng)。3.進程調度方式⑵搶占方式允許調度程序根據某種原則，去暫停某個正在執(zhí)行的進程，將已分配給該進程的處理機，重新分配給另一進程。搶占方式能滿足實時任務的需求。但搶占方式比較復雜，所需付出統(tǒng)開銷也較大。

★“搶占”必須遵循的原則①優(yōu)先權原則：允許優(yōu)先級高的新到進程，搶占當前進程的處理機；②短進程優(yōu)先原則：許新到的短進程，可以搶占當前長進程的處理機；③時間片原則：各進程按時間片輪轉運行時，當正在執(zhí)行的進程的一個時間片用完后，便停止該進程的執(zhí)行而重新進行調度。3.3.2輪轉調度算法1.輪轉法的基本原理

系統(tǒng)將所有的就緒進程按FCFS策略，排成一個就緒隊列。系統(tǒng)可設置每隔一定時間（如30ms），便產生一次中斷，去激活進程調度程序進行調度，把CPU分配給隊首進程，并令其執(zhí)行一個時間片。當它運行完后，又把處理機分配給就緒隊列中新的隊首進程，也讓它執(zhí)行一個時間片。

2.進程切換時機

①若一個時間片尚未用完，正在運行的進程便已經完成，就立即激活調度程序，將它從就緒隊列中刪除，再調度就緒隊列中隊首進程運行，并啟動一個新的時間片。②在一個時間片用完時，此時計時器中斷處理程序被激活。如果進程尚未運行完畢，調度程序把它送往就緒隊列的末尾。

Page662023/2/6基于時間片的輪轉調度算法簡單的時間片輪轉法(RR—RoundRobin)系統(tǒng)將所有的就緒進程按先來先服務的原則排成一個隊列，每次調度時，把CPU分配給隊首進程，并令其執(zhí)行一個時間片當執(zhí)行的時間片用完時，由一個計時器發(fā)出時鐘中斷請求，調度程序便停止該進程的執(zhí)行，并將其放就緒隊列尾；然后，再把處理機分配給就緒隊列中新的隊首時間片的大小從幾ms到幾百ms優(yōu)點：公平。保證就緒隊列中所有進程在一給定的時間內，均能獲得一時間片的處理機執(zhí)行時間缺點：緊迫任務響應慢。UNIX中采用：時間片+優(yōu)先權⑤Page672023/2/6基于時間片的輪轉調度算法進程名到達時間服務時間開始時間完成時間周轉時間帶權周轉時間平均ABCDEABCDEABCEACEC05101518t04A03B05C02D04E012349121517181515/41212/31818/599/21717/414.24.02若到達時間為0、1、2、3、4，又如何？Page682023/2/6基于時間片的輪轉調度算法進程名到達時間服務時間開始時間完成時間周轉時間帶權周轉時間平均ABACBDAECBDAECECEC05101518t04A13B25C32D44E013571110121718123931616/5841313/411.63.293.3.2輪轉調度算法3.時間片大小的確定在輪轉算法中，時間片的大小，對系統(tǒng)性能有很大的影響。若選擇很小的時間片，將有利于短作業(yè)，因為它能在該時間片內完成。但時間片小，意味著會頻繁地執(zhí)行進程調度，和進程上下文的切換，這無疑會增加系統(tǒng)的開銷。若時間片選擇得太長，且為使每個進程，都能在一個時間片內完成，RR算法便退化為FCFS算法，無法滿足短作業(yè)和交互式用戶的需求。一個較為可取的時間片大小是，略大于一次典型的交互所需要的時間，使大多數交互式進程，能在一個時間片內完成，從而可以獲得很小的響應時間。3.時間片大小的確定3.時間片大小的確定下左圖示出了時間片大小對響應時間的影響，其中圖a是時間片略大于典型交互的時間，其中圖b是時間片小于典型交互的時間。下右圖示出了時間片分別為q=1和q=4時對平均周轉時間的影響。Page712023/2/6基于時間片的輪轉調度算法分時系統(tǒng)中常用時間片輪轉法時間片選擇問題固定時間片可變時間片時間片大小與時間片大小有關的因素系統(tǒng)響應時間就緒進程個數CPU能力

3.3.3優(yōu)先級調度算法

1.優(yōu)先級調度算法的類型把處理機分配給就緒隊列中優(yōu)先級最高的進程。

⑴非搶占式優(yōu)先級調度算法：一旦把處理機分配給就緒隊列中優(yōu)先級最高的進程后，該進程便一直執(zhí)行下去直至完成，或者因該進程發(fā)生某事件而放棄處理機時，系統(tǒng)方可將處理機重新分配給另一優(yōu)先級最高的進程。

⑵搶占式優(yōu)先級調度算法：把處理機分配給優(yōu)先級最高的進程，使之執(zhí)行。但在其執(zhí)行期間，只要出現(xiàn)了另一個其優(yōu)先級更高的進程，調度程序就將處理機分配給新到的優(yōu)先級最高的進程。

2.優(yōu)先級的類型

⑴靜態(tài)優(yōu)先級：靜態(tài)優(yōu)先級是在創(chuàng)建進程時確定的，在進程的整個運行期間保持不變。優(yōu)先級是利用某一范圍內的一個整數來表示的，例如0～255中的某一整數，又把該整數稱為優(yōu)先數。確定進程優(yōu)先級大小的依據有如下三個：進程類型、進程對資源的需求、用戶要求。

⑵動態(tài)優(yōu)先級：動態(tài)優(yōu)先級是指在創(chuàng)建進程之初，先賦予其一個優(yōu)先級，然后其值隨進程的推進，或等待時間的增加而改變，以便獲得更好的調度性能。3.3.4多級隊列調度算法

★算法思想

將系統(tǒng)中的進程就緒隊列從一個拆分為若干個，將不同類型或性質的進程固定分配在不同的就緒隊列，不同的就緒隊列采用不同的調度算法，一個就緒隊列中的進程可以設置不同的優(yōu)先級，不同的就緒隊列本身也可以設置不同的優(yōu)先級。3.3.5多級反饋隊列調度算法

★算法思想將就緒隊列分為N級，每個就緒隊列分配給不同的時間片，隊列級別越高，時間越長，級別越小，時間片越小，最后一級采用時間片輪轉，其他隊列采用先進先出；系統(tǒng)從第一級調度，當第一級為空時，系統(tǒng)轉向第二個隊列，當運行進程用完一個時間片，放棄CPU時，進入下一級隊列；等待進程被喚醒時，進入原來的就緒隊列；當進程第一次就緒時，進入第一級隊列。

★算法要點

*首先系統(tǒng)中設置多個就緒隊列；*每個就緒隊列分配給不同時間片，優(yōu)先級高的為第一級隊列，時間片最小，隨著隊列級別的降低，時間片加大；*各個隊列按照先進先出調度算法；*一個新進程就緒后進入第一級隊列；*進程由于等待而放棄CPU后，進入等待隊列，一旦等待的事件發(fā)生，則回到原來的就緒隊列；*當有一個優(yōu)先級更高的進程就緒時，可以搶占CPU，被搶占進程回到原來一級就緒隊列末尾；*當第一級隊列空時，就去調度第二級隊列，如此類推；*當時間片到后，進程放棄CPU，回到下一級隊列。Page752023/2/6就緒隊列1就緒隊列2就緒隊列3就緒隊列nS1S2S3至CPU至CPU至CPU至CPU(時間片：S1＜S2＜S3)調度方式高低優(yōu)先級時間片小大Sn按FIFO原則排隊等待調度尚未完成轉入第二隊列的末尾，按FIFO原則等待調度采取按時間片輪轉的方式運行因等待而放棄CPU后，進入阻塞隊列，一旦等待的事件發(fā)生，則回到原來的就緒隊列3.3.5多級反饋隊列調度算法Page762023/2/6多級反饋隊列調度算法的性能終端型作業(yè)用戶終端型作業(yè)用戶所提交的作業(yè)多屬于交互型作業(yè)，通常較小，系統(tǒng)只要能使這些作業(yè)在第一隊列所規(guī)定的時間片內完成即可短批處理作業(yè)用戶若在第1隊列中執(zhí)行一個時間片即可完成，便可獲得與終端型作業(yè)一樣的響應時間如在第一個隊列中不能完成，只需在第2、3隊列中各執(zhí)行一個時間片長批處理作業(yè)用戶長作業(yè)將依次在第1，2，3…，n隊列中執(zhí)行，最終按輪轉方式運行3.3.5多級反饋隊列調度算法3.3.6基于公平原則的調度算法

1.保證調度算法保證調度算法向用戶所做出的是明確的性能保證，該算法可以做到調度的公平性，如處理機分配的公平性。在實施公平調度算法時系統(tǒng)中必須具有這樣一些功能：（1）跟蹤計算每個進程自創(chuàng)建以來已經執(zhí)行的處理時間；（2）計算每個進程應獲得的處理機時間，即自創(chuàng)建以來的時間除以n。（3）計算進程獲得處理機時間的比率。（4）比較各進程獲得處理機時間的比率。（5）調度程序應選擇比率最小的進程，將處理機分配給它，并讓該進程一直運行，直到超過最接近它的進程比率為止。

2.公平分享調度算法在該調度算法中，調度的公平性主要是針對用戶，使所有用戶能獲得相同的處理機時間，或所要求的時間比例。然而調度又是以進程為基本單位。為此，必須考慮到每一個用戶所擁有的進程數目。Page782023/2/6進程調度的時機當一個進程運行完畢或由于某種錯誤而終止運行當一個進程在運行中處于等待狀態(tài)（等待I/O）分時系統(tǒng)中時間片到當有一個優(yōu)先級更高的進程就緒（可搶占式）例如：新創(chuàng)建一個進程，一個阻塞進程變成就緒在進程通信中，執(zhí)行中的進程執(zhí)行了某種原語操作（P操作，阻塞原語，喚醒原語）Page792023/2/6何時切換進程只要OS取得對CPU的控制，進程切換就可能發(fā)生:超級用戶調用來自程序的顯式請求(如：打開文件)，該進程通常會被阻塞陷阱最末一條指令導致出錯，會引起進程移至退出狀態(tài)中斷外部因素影響當前指令的執(zhí)行，控制被轉移至IH（中斷處理程序）Page802023/2/6引起進程調度的原因正在執(zhí)行的進程執(zhí)行完畢或因發(fā)生某事件而不能再繼續(xù)執(zhí)行；執(zhí)行中的進程因提出I/O請求而暫停執(zhí)行；在進程通信或同步過程中執(zhí)行了某種原語操作如P操作、阻塞、掛起原語等；在可剝奪式調度中，有比當前進程優(yōu)先權更高的進程進入就緒隊列；在時間片輪轉法中，時間片完。通常系統(tǒng)是按先來先服務或優(yōu)先權形式來組織調度隊列。Page812023/2/6第三章處理機調度與死鎖處理機調度的層次和調度算法的目標

作業(yè)與作業(yè)調度進程調度

實時調度死鎖概述預防死鎖避免死鎖死鎖的檢測與解除Page822023/2/6實時調度

實現(xiàn)實時調度的基本條件實時調度算法的分類常用的幾種實時調度算法Page832023/2/6實現(xiàn)實時調度的基本條件提供必要的信息開始截止時間和完成截止時間就緒時間該任務成為就緒狀態(tài)的起始時間處理時間資源要求優(yōu)先級Page842023/2/6實現(xiàn)實時調度的基本條件系統(tǒng)處理能力強在實時系統(tǒng)中，通常都有著多個實時任務。若處理機的處理能力不夠強，則有可能因處理機忙不過來而使某些實時任務不能得到及時處理，從而導致發(fā)生難以預料的后果。假定系統(tǒng)中有m個周期性的硬實時任務，它們的處理時間可表示為Ci，周期時間表示為Pi，則在單處理機情況下，必須滿足下面的限制條件例：一個周期為10ms，執(zhí)行5ms,

一個周期為15ms,執(zhí)行10ms,

則：(5/10)+(10/15)=35/30Page852023/2/6實現(xiàn)實時調度的基本條件系統(tǒng)處理能力強若上式不能滿足，則系統(tǒng)是不可調度的解決的方法是提高系統(tǒng)的處理能力采用單處理機系統(tǒng)但須增強其處理能力，以顯著地減少對每一個任務的處理時間采用多處理機系統(tǒng)假定系統(tǒng)中的處理機數為N，則應將上述的限制條件改為Page862023/2/6實現(xiàn)實時調度的基本條件采用搶占式調度機制當一個優(yōu)先權更高的任務到達時，允許將當前任務暫時掛起，而令高優(yōu)先權任務立即投入運行，以滿足該硬實時任務對截止時間的要求。但這種調度機制比較復雜小的實時系統(tǒng)，若能預知任務的開始截止時間，則可采用非搶占調度機制，以簡化調度程序和對任務調度時所花費的系統(tǒng)開銷注意：設計這種調度機制時，應使所有的實時任務都比較小，并在執(zhí)行完關鍵性程序和臨界區(qū)后，能及時地將自己阻塞起來，以便釋放處理機，供調度程序調度那些開始截止時間即將到達的任務Page872023/2/6實現(xiàn)實時調度的基本條件具有快速切換機制該機制應具有如下兩方面的能力對外部中斷的快速響應能力為使在緊迫的外部事件請求中斷時系統(tǒng)能及時響應，要求系統(tǒng)具有快速硬件中斷機構，還應使禁止中斷的時間間隔盡量短，以免耽誤時機(其它緊迫任務)快速的任務分派能力在完成任務調度后，便應進行任務切換。為了提高分派程序進行任務切換時的速度，應使系統(tǒng)中的每個運行功能單位適當的小，以減少任務切換的時間開銷Page882023/2/6實時調度實現(xiàn)實時調度的基本條件實時調度算法的分類常用的幾種實時調度算法Page892023/2/6實時調度算法的分類非搶占式調度算法（實時任務?。┓菗屨际捷嗈D調度算法

常用于工業(yè)生產的群控系統(tǒng)中調度程序每次選擇隊列中的第一個任務運行一個任務運行后排在輪轉隊列的末尾，等待下次調度非搶占式優(yōu)先調度算法為時間要求嚴格的任務分配較高優(yōu)先級當優(yōu)先權高的實時任務到來時，排在就緒隊列的隊首等待調度Page902023/2/6實時調度算法的分類搶占式調度算法基于時鐘中斷的搶占式優(yōu)先權調度算法某實時任務到達后，若優(yōu)先級高于當前正在執(zhí)行任務的優(yōu)先級，并不立即搶占當前任務的處理機，而是等到時鐘中斷到來后調度程序才剝奪當前任務的執(zhí)行立即搶占(ImmediatePreemption)的優(yōu)先權調度算法一旦有外部中斷，只要當前任務不在臨界區(qū)內，便立即剝奪當前任務的執(zhí)行，交處理機分配給要求中斷的緊迫任務Page912023/2/6實時調度算法的分類(a)非搶占輪轉調度調度時間進程

1進程

2實時進程要求調度進程

n實時進程調度實時進程運行(b)非搶占優(yōu)先權調度當前進程實時進程實時進程請求調度當前進程運行完成調度時間在就緒隊列尾在就緒隊列首xs--xxsxs--xxxmsPage922023/2/6實時調度算法的分類當前進程實時進程請求調度時鐘中斷到來時調度時間(c)基于時鐘中斷搶占的優(yōu)先權搶占調度實時進程當前進程實時進程實時進程請求調度實時進程搶占當前進程，并立即執(zhí)行(d)立即搶占的優(yōu)先權調度調度時間xms--xxsPage932023/2/6實時調度實現(xiàn)實時調度的基本條件實時調度算法的分類常用的幾種實時調度算法Page942023/2/6常用的幾種實時調度算法最早截止時間優(yōu)先EDF(EarliestDeadlineFirst)算法根據任務的開始截止時間來確定任務的優(yōu)先級，截止時間越早優(yōu)先級越高既可用于搶占式調度