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

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

理解常用的幾種實時調(diào)度算法

理解產(chǎn)生死鎖的原因

掌握銀行家算法避免死鎖難點多道程序設(shè)計中的各種調(diào)度算法

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

銀行家算法

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

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

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

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

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

取決于作業(yè)調(diào)度算法先來先服務(wù)短作業(yè)優(yōu)先作業(yè)優(yōu)先權(quán)調(diào)度響應(yīng)比調(diào)度→周轉(zhuǎn)時間太長→系統(tǒng)吞吐量太低

適當(dāng)?shù)恼壑远嗟莱绦蚨龋杭丛试S多少個作業(yè)同時在內(nèi)存中運行。周轉(zhuǎn)時間：從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時間間隔。吞吐量：是指在單位時間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)。Page112023/2/6高級、中級和低級調(diào)度低級調(diào)度

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

作業(yè)調(diào)度的主要任務(wù)

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

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

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

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

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

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

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

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

210∶1030

310∶2020

410∶3025

510∶4010

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

210∶1030

310∶2020

410∶3025

510∶4010

2023/2/641(1)先來先服務(wù)調(diào)度算法(FCFS)作業(yè)號進入輸入井時間需執(zhí)行時間（分鐘）開始執(zhí)行時間結(jié)束執(zhí)行時間周轉(zhuǎn)時間（分鐘）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

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

210∶1030

310∶2020

410∶3025

510∶4010

2023/2/643(2)短作業(yè)優(yōu)先調(diào)度算法(SJF)作業(yè)號進入輸入井時間需執(zhí)行時間（分鐘）開始執(zhí)行時間結(jié)束執(zhí)行時間周轉(zhuǎn)時間（分鐘）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調(diào)度次序：5-3-4-2-1平均周轉(zhuǎn)時間為（165+115+50+65+10)/5=81分鐘3.2.4優(yōu)先級調(diào)度算法和高響應(yīng)比優(yōu)先調(diào)度算法1.優(yōu)先級調(diào)度算法(priority-schedulingalgorithm)

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

2.高響應(yīng)比優(yōu)先調(diào)度算法

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

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

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

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

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

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

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

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

1.進程調(diào)度任務(wù)

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

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

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

2.進程調(diào)度機制

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

3.進程調(diào)度方式

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

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

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

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

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

2.進程切換時機

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

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

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

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

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

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

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

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

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

★算法思想

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

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

★算法要點

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

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

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

作業(yè)與作業(yè)調(diào)度進程調(diào)度

實時調(diào)度死鎖概述預(yù)防死鎖避免死鎖死鎖的檢測與解除Page822023/2/6實時調(diào)度

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

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

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

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

1進程

2實時進程要求調(diào)度進程

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