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

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

理解產生死鎖的原因

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

響應比高者優先調度算法的計算過程

銀行家算法

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

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

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

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

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

取決于作業調度算法先來先服務短作業優先作業優先權調度響應比調度→周轉時間太長→系統吞吐量太低

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

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

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

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

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

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

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

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

作業與作業調度

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

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

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

2.作業控制塊JCB

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

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

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

作業調度的主要任務

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

★在每次執行作業調度時，都須做出以下兩個決定

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

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

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

先來先服務（先進先出）優缺點

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

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

210∶1030

310∶2020

410∶3025

510∶4010

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

210∶1030

310∶2020

410∶3025

510∶4010

2023/2/641(1)先來先服務調度算法(FCFS)作業號進入輸入井時間需執行時間（分鐘）開始執行時間結束執行時間周轉時間（分鐘）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)短作業優先調度算法(SJF)作業號進入輸入井時間需執行時間（分鐘）開始執行時間結束執行時間周轉時間（分鐘）110∶0040

210∶1030

310∶2020

410∶3025

510∶4010

2023/2/643(2)短作業優先調度算法(SJF)作業號進入輸入井時間需執行時間（分鐘）開始執行時間結束執行時間周轉時間（分鐘）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優先級調度算法和高響應比優先調度算法1.優先級調度算法(priority-schedulingalgorithm)

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

2.高響應比優先調度算法

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

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

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

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

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

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

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

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

1.進程調度任務

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

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

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

2.進程調度機制

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

3.進程調度方式

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

優點：是實現簡單、系統開銷小，適用于大多數的批處理系統。

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

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

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

2.進程切換時機

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

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

3.3.3優先級調度算法

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

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

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

2.優先級的類型

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

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

★算法思想

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

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

★算法要點

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

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

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

作業與作業調度進程調度

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

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

一個周期為15ms,執行10ms,

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

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

1進程

2實時進程要求調度進程

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