1、第三章 進程的描述與控制處理機調度的層次和調度算法的目標處理機調度的層次和調度算法的目標作業與作業調度作業與作業調度2進程調度進程調度3 3實時調度實時調度4 4死鎖概述死鎖概述3 535142022-4-231預防死鎖預防死鎖4 4避免死鎖避免死鎖3 5 76死鎖的檢測與解除死鎖的檢測與解除4 4 8第三章 處理機調度與死鎖處理機調度的層次和調度算法的目標處理機調度的層次和調度算法的目標作業與作業調度作業與作業調度2進程調度進程調度3 3實時調度實時調度4 4死鎖概述死鎖概述3 535142022-4-232預防死鎖預防死鎖4 4避免死鎖避免死鎖3 5 76死鎖的檢測與解除死鎖的檢測與解除4

2、 4 82022-4-2333.1處理機調度的層次和調度算法的目標處理機調度的層次和調度算法的目標 3.1.13.1.1處理機調度的層次處理機調度的層次1 1高級調度高級調度（High level schedulingHigh level scheduling） - -作業調度作業調度, ,幾幾個作業調入內存，為它們創建進程、分配必要的資源。個作業調入內存，為它們創建進程、分配必要的資源。 ( (外外存存-內存內存) ) 2. 2. 低級調度低級調度（Low level schedulingLow level scheduling） - -進程調度，調進程調度，調度的對象是進程或內核級線程。度

3、的對象是進程或內核級線程。( (內存內存-處理機處理機) ) 3. 3. 中級調度中級調度（Intermediate schedulingIntermediate scheduling） - -內存調度，內存調度，暫時不能運行的進程調至外存等待。暫時不能運行的進程調至外存等待。 ( (外存外存內存內存) ) 2022-4-2343.1.13.1.1處理機調度算法的目標處理機調度算法的目標1 1處理機調度算法的共同目標處理機調度算法的共同目標- - （1 1）資源利用率資源利用率：主要是：主要是CPUCPU的利用率的利用率 （2 2）公平性公平性：獲得：獲得合理合理CPUCPU時間時間 （3 3

4、）平衡性平衡性：進程類型，計算型、輸入：進程類型，計算型、輸入/ /輸出型輸出型 （4 4）策略強制執行策略強制執行：系統的安全策略：系統的安全策略 2022-4-2353.1.13.1.1處理機調度算法的目標處理機調度算法的目標2. 2. 批處理系統的目標批處理系統的目標 （1 1）平均周轉時間平均周轉時間n n個進程周轉時間的算術平均個進程周轉時間的算術平均 （2 2）系統吞吐量系統吞吐量 單位時間內完成的作業數目、作業的平均長度單位時間內完成的作業數目、作業的平均長度 （3 3）處理機利用率處理機利用率CPUCPU工作時間、空閑時間的比例工作時間、空閑時間的比例2022-4-2363.1

5、.13.1.1處理機調度算法的目標處理機調度算法的目標3. 3. 分時系統的目標分時系統的目標 （1 1）響應時間快響應時間快時間間隔：提交請求時間間隔：提交請求- -顯示處理結果顯示處理結果 （2 2）均衡性均衡性 復雜任務的響應時間可適當長，復雜任務的響應時間可適當長，簡單任務響應時間要相對短。簡單任務響應時間要相對短。 2022-4-2373.1.13.1.1處理機調度算法的目標處理機調度算法的目標4. 4. 實時系統的目標實時系統的目標 （1 1）截止時間截止時間開始截止時間、完成截止時間，開始截止時間、完成截止時間，HRTHRT、SRTSRT任務任務 （2 2）可預測性可預測性 下一

6、步操作的可預測，下一步操作的可預測， 例如連續播放（多幀并行處理）。例如連續播放（多幀并行處理）。 第三章 進程的描述與控制處理機調度的層次和調度算法的目標處理機調度的層次和調度算法的目標作業與作業調度作業與作業調度2進程調度進程調度3 3實時調度實時調度4 4死鎖概述死鎖概述3 535142022-4-238預防死鎖預防死鎖4 4避免死鎖避免死鎖3 5 76死鎖的檢測與解除死鎖的檢測與解除4 4 82022-4-2393.2作業與作業調度作業與作業調度 3.2.13.2.1批處理系統中的作業批處理系統中的作業1 1作業和作業步作業和作業步(1) 作業作業(Job)。作業是一個比程序更為廣泛的

7、概念，它不僅包含了通常的程序和數據，而且還應配有一份作業說明書-specifications，系統根據該說明書來對程序的運行進行控制。在批處理系統中，是以作業為基本單位從外存調入內存的。 2022-4-2310(2) 作業步作業步(Job Step)。通常，在作業運行期間，每個作業都必須經過若干個相對獨立，又相互關聯的順序加工步驟才能得到結果，我們把其中的每一個加工步驟稱為一個作業步，各作業步之間存在著相互聯系，往往是把上一個作業步的輸出作為下一個作業步的輸入。例如，一個典型的作業可分成三個作業步： “編譯(Compile)”作業步，通過執行編譯程序對源程序進行編譯，產生若干個目標程序段； “

8、連結裝配(Link)”作業步，將“編譯”作業步所產生的若干個目標程序段裝配成可執行的目標程序； “運行(Running)”作業步，將可執行的目標程序讀入內存并控制其運行。(3) 作業流作業流。若干個作業進入系統后，被依次存放在外存上，這便形成了輸入的作業流；在操作系統的控制下，逐個作業進行處理，于是便形成了處理作業流。 2022-4-23112 2作業控制塊作業控制塊JCB(Job Control Block)JCB(Job Control Block)為了管理和調度作業，在多道批處理系統中為每個作業設置了一個作業控制塊，如同進程控制塊是進程在系統中存在的標志一樣，它是作業在系統中存在的標志標

9、志，其中保存了系統對作業進行管理和調度所需的全部信息。在JCB中所包含的內容因系統而異，通常應包含的內容有：作業標識、用戶作業標識、用戶名稱、用戶帳戶、作業類型名稱、用戶帳戶、作業類型(CPU 繁忙型、I/O 繁忙型、批量型、終端型)、作業狀態、調度信息作業狀態、調度信息(優先級、作業已運行時間)、資源需求資源需求(預計運行時間、要求內存大小、要求I/O設備的類型和數量等)、進入系統時間、開始處理時間、作業完成進入系統時間、開始處理時間、作業完成時間時間、作業退出時間、資源使用退出時間、資源使用情況等。 2022-4-2312每當作業進入系統時，系統便為每個作業建立建立一個JCB，根據作業類型

10、作業類型將它插入相應的后備隊列后備隊列中。作業調度程序依據一定的調度算法來調度它們，被調度到的作業將會裝入內存。在作業運行期間，系統就按照JCB中的信息對作業進行控制。當一個作業執行結束進入完成狀態時，系統負責回收分配給它的資源，撤消撤消它的作業控制塊。 2022-4-23133. 3. 作業運行的作業運行的3 3種狀態種狀態 （1 1）收容階段收容階段SPOOLingSPOOLing系統，系統，后備隊列后備隊列, ,后備狀態后備狀態。 （2 2）運行階段運行階段 分配必要資源，分配必要資源，就緒隊列就緒隊列，就緒狀態就緒狀態。 （3 3）完成階段完成階段運行結束或異常結束，運行結束或異常結束

11、，完成狀態完成狀態。2022-4-23143.2.2 3.2.2 作業調度的主要任務作業調度的主要任務作業調度的主要功能是根據作業控制塊中的信息，審查系統能否滿足用戶作業的資源需求，以及按照一定的算法，從外存的后備隊列后備隊列中選取選取某些作業調入內存作業調入內存，并為它們創建創建進程進程、分配必要的資源、分配必要的資源。然后再將新創建的進程插入插入就緒隊就緒隊列列，準備執行。因此，有時也把作業調度稱為接納調度(Admission Scheduling)。 2022-4-2315對用戶用戶而言，總希望自己作業的周轉時間周轉時間盡可能的少，最好周轉時間最好周轉時間就等于等于作業的執行時間執行時間

12、。然而對系統系統來說，則希望作業的平均周轉時間平均周轉時間盡可能少，有利于提高提高CPU CPU 的利用的利用率和系統的吞吐量率和系統的吞吐量。為此，每個系統在選擇作業調度算法時，既既應考慮用戶的要求，又又能確保系統具有較高的效率。在每次執行作業調度時，都須做出以下兩個決定。 2022-4-23161) 決定接納多少個作業決定接納多少個作業作業調度每次要接納多少個作業進入內存，取決于多道多道程序程序度度(Degree of Multiprogramming)，即允許多少個作業同時在內存中運行。當內存中同時運行的作業數目太多時，可能會影響到系統的服務質量，比如，使周轉時間太長。但如果在內存中同時

13、運行作業的數量太少時，又會導致系統的資源利用率和系統吞吐量太低，因此，多道程序度的確定應根據系統的規模和運行速度等情況做適當的折衷。 2022-4-23172) 決定接納哪些作業決定接納哪些作業應將哪些作業從外存調入內存，這將取決于所采用的調度算法。最簡單的是先來先服務調度算法，這是指將最早進入外存的作業最先調入內存；較常用的一種算法是短作業優先調度算法，是將外存上最短的作業最先調入內存；另一種較常用的是基于作業優先級的調度算法，該算法是將外存上優先級最高的作業優先調入內存；比較好的一種算法是“響應比高者優先”的調度算法。我們將在后面對上述幾種算法作較為詳細的介紹。 2022-4-2318在批

14、處理系統批處理系統中，作業進入系統后，總是先駐留在外存外存的的后備隊列后備隊列上，因此需要有作業調度的過程，以便將它們分批地裝入內存。然而在分時系統分時系統中，為了做到及時響應及時響應，用戶通過鍵盤輸入的命令或數據等都是被直接送入內存直接送入內存的，因而無需再配置上述的作業調度機制無需再配置上述的作業調度機制，但也需要有某些限制性措施來限制進入系統的進入系統的用戶數用戶數。即，如果系統尚未飽和，將接納所有授權用戶，否則，將拒絕接納。類似地，在實時系統中通常也不需要作業調度。 2022-4-23193.2.33.2.3先來先服務和短作業先來先服務和短作業( (進程進程) )優先調度算法優先調度算

15、法1 1先來先服務調度算法先來先服務調度算法先來先服務先來先服務(First Come First Service, FCFS)調度算法是一種最簡單的調度算法，該算法既可用于作業調度作業調度，也可用于進程進程調度調度。當在作業調度中采用該算法時，每次調度都是從后備作后備作業隊列業隊列中選擇一個或多個最先進入該隊列的作業，將它們調入內存，為它們分配資源、創建進程，然后放入就緒隊列就緒隊列。在進程調度中采用FCFS算法時，則每次調度是從就緒隊列中選擇一個最先進入該隊列的進程，為之分配處理機，使之投入運行。該進程一直運行到完成或發生某事件而阻塞后才放棄處理機。 2022-4-2320FCFS算法比較

16、有利于長作業(進程)，而不利于短作業(進程)。下表列出了A、B、C、D四個作業分別到達系統的時間、要求服務的時間、開始執行的時間及各自的完成時間，并計算出各自的周轉時間和帶權周轉時間。 2022-4-2321 從表上可以看出，其中短作業C的帶權周轉時間競高達100，這是不能容忍的；而長作業D的帶權周轉時間僅為1.99。據此可知，FCFS調度算法有利于CPU繁忙型的作業，而不利于I/O繁忙型的作業(進程)。CPU繁忙型作業是指該類作業需要大量的CPU時間進行計算，而很少請求I/O。通常的科學計算科學計算便屬于便屬于CPUCPU繁忙型作業繁忙型作業。I/O繁忙型作業是指CPU進行處理時需頻繁地請求

17、I/O。目前的大多數事務處理都屬于大多數事務處理都屬于I/OI/O繁忙型繁忙型作業。2022-4-23222 2短作業短作業( (進程進程) )優先調度算法優先調度算法短作業(進程)優先調度算法SJ(P)F（Shortest Job First），是指對短作業或短進程優先調度的算法。它們可以分別用于作作業調度和進程調度業調度和進程調度。短作業優先(SJF)的調度算法是從后備隊列中選擇一個或若干個估計運行時間最短的作業，將它們調入內存運行。而短進程優先(SPF)調度算法則是從就緒隊列中選出一個估計運行時間最短的進程，將處理機分配給它，使它立即執行并一直執行到完成，或發生某事件而被阻塞放棄處理機時

18、再重新調度。 2022-4-2323圖FCFS和SJF調度算法的性能 2022-4-2324為了和FCFS調度算法進行比較，我們仍利用FCFS算法中所使用的實例，并改用SJ(P)F算法重新調度，再進行性能分析。由比較圖中的(a)和(b)可以看出，采用SJ(P)F算法后，不論是平均周轉時間還是平均帶權周轉時間，都有較明顯的改善，尤其是對短作業D，其周轉時間由原來的(用FCFS算法時)11降為3；而平均帶權周轉時間是從5.5降到1.5。這說明SJF調度算法能有效地降低作業的平均等待時間，提高系統吞吐量。 2022-4-2325SJ(P)F調度算法也存在不容忽視的缺點：(1) 該算法對長作業不利該算

19、法對長作業不利，如作業C的周轉時間由10增至16，其帶權周轉時間由2增至3.1。更嚴重的是，如果有一長作業(進程)進入系統的后備隊列(就緒隊列)，由于調度程序總是優先調度那些(即使是后進來的)短作業(進程)，將導致長作業(進程)長期不被調度。(2) 該算法完全未考慮作業的緊迫程度算法完全未考慮作業的緊迫程度，因而不能保證緊迫性作業(進程)會被及時處理。(3) 由于作業由于作業( (進程進程) )的長短只是根據用戶所提供的估計的長短只是根據用戶所提供的估計執行時間執行時間而定的，而用戶又可能會有意或無意地縮短其作業的估計運行時間，致使該算法不一定能真正做到短作業優先調度。 2022-4-2326

20、3.2.3.2.4 4高優先權優先調度算法高優先權優先調度算法1 1優先權優先權(priority)(priority)調度算法的類型調度算法的類型為了照顧緊迫型緊迫型作業，使之在進入系統后便獲得優先處理，引入了最高優先權優先(FPF)調度算法。此算法常被用于批處理系統批處理系統中，作為作業調度算法，也作為多種操作系統中的進程調度算法，還可用于實時系統實時系統中。當把該算法用于作業調度時，系統將從后備隊列中選擇若干個優先權最高的作業裝入內存。當用于進程調度時，該算法是把處理機分配給就緒隊列中優先權最高的進程，這時，又可進一步把該算法分成如下兩種。 2022-4-23271) 非搶占(Non-p

21、reemptive)式優先權算法在這種方式下，系統一旦把處理機分配給就緒隊列中優優先權最高先權最高的進程后，該進程便一直執行下去，直至完成；或因發生某事件使該進程放棄處理機時，系統方可再將處理機重新分配給另一優先權最高的進程。這種調度算法主要用于批處理系統中；也可用于某些對實時性要求不嚴的實時系統中。 2022-4-23282) 搶占式(preemptive)優先權調度算法在這種方式下，系統同樣是把處理機分配給優先權最高的進程，使之執行。但在其執行期間，只要又出現了另一個只要又出現了另一個其優先權更高的進程其優先權更高的進程，進程調度程序就立即停止當前進程(原優先權最高的進程)的執行，重新將處

22、理機分配給新到的優先權最高的進程。因此，在采用這種調度算法時，是每當系統中出現一個新的就緒進程i時，就將其優先權Pi與正在執行的進程j的優先權Pj進行比較。如果PiPj，原進程Pj便繼續執行；但如果是PiPj，則立即停止Pj的執行，做進程切換，使i進程投入執行。顯然，這種搶占式的優先權調度算法能更好地滿搶占式的優先權調度算法能更好地滿足足緊迫緊迫作業的要求作業的要求，故而常用于要求比較嚴格的實時系統中，以及對性能要求較高的批處理和分時系統中。 2022-4-23292 2優先權的類型優先權的類型對于最高優先權優先調度算法，其關鍵在于：它是使用靜態優先權，還是用動態優先權，以及如何確定進程的優先

23、權。1) 靜態優先權靜態優先權靜態優先權是在創建進程時確定的，且在進程的整個運行期間保持不變。一般地，優先權是利用某一范圍內某一范圍內的一個整數整數來表示的，例如，07或0255中的某一整數，又把該整數稱為優先數優先數，只是具體用法各異：有的系統用“0”表示最高優先權，當數值愈大時，其優先權愈低；而有的系統恰恰相反。 2022-4-2330確定進程優先權的依據有如下三個方面：(1) 進程類型進程類型。通常，系統進程系統進程(如接收進程、對換進程、磁盤I/O進程)的優先權高于一般用戶進程的優先權。(2) 進程對資源的需求進程對資源的需求。如進程的估計執行時間及內存需要量的多少，對這些要求少要求少

24、的進程應賦予較高的優先權。(3) 用戶要求用戶要求。這是由用戶進程的緊迫程度用戶進程的緊迫程度及用戶所付費用的多少來確定優先權的。靜態優先權法簡單易行，系統開銷小，但不夠精確，很可能出現優先權低的作業優先權低的作業( (進程進程) )長期沒有被調度長期沒有被調度的情況。因此，僅在要求不高的系統中才使用靜態優先權。 2022-4-23312) 動態優先權動態優先權是指在創建進程時所賦予的優先權，是可以隨進程的推進或隨其等待時間的增加而改變隨進程的推進或隨其等待時間的增加而改變的，以便獲得更好的調度性能。例如，我們可以規定，在就緒隊列中的進程，隨其等待時間的增長，其優先權以速率優先權以速率a a提

25、高提高。若所有的進程都具有相同的優先權初值，則顯然是最先進入就緒隊列的進程將因其動態優先權變得最高而優先獲得處理機，此即FCFS算法。若所有的就緒進程具有各不相同的優先權初值，那么，對于優先權初值低的進程，在等待了足夠的時間后，其優先權便可能升為最高，從而可以獲得處理機。當采用搶占式優先權調度算法時，如果再規定當前進程的優先權以速率當前進程的優先權以速率b b下降下降，則可防止一個長作業長期地壟斷處理機。 2022-4-23322 2高響應比優先調度算法高響應比優先調度算法在批處理系統中，短作業優先算法是一種比較好的算法，其主要的不足之處是長作業的運行得不到保證。如果我們能為每個作業引入前面所

26、述的動態優先權，并使作業的優先級隨著等待時間的增加而以速率速率a提高，則長作業在等待一定的時間后，必然有機會分配到處理機。該優先權的變化規律可描述為： 要求服務時間要求服務時間等待時間優先權2022-4-2333由于等待時間與服務時間之和就是系統對該作業的響應時間，故該優先權又相當于響應比RP。據此，又可表示為： 要求服務時間響應時間要求服務時間要求服務時間等待時間PR2022-4-2334由上式可以看出：(1) 如果作業的作業的等待時間相同等待時間相同，則要求服務的時間愈短，其優先權愈高，因而該算法有利于短作業有利于短作業。(2) 當要求服務的時間相同服務的時間相同時，作業的優先權決定于其等

27、待時間，等待時間愈長，其優先權愈高，因而它實現的是先先來先服務來先服務。 2022-4-2335(3) 對于長作業，作業的優先級可以隨等待時間的增加隨等待時間的增加而提高而提高，當其等待時間足夠長時，其優先級便可升到很高，從而也可獲得處理機。簡言之，該算法既照顧了短作業，又考慮了作業到達的先后次序，不會使長作業長期得不到服務。因此，該算法實現了一種較好的折衷折衷。當然，在利用該算法時，每要進行調度之前，都須先做響應比的計算，這會增加系統開銷。 第二章 進程的描述與控制處理機調度的層次和調度算法的目標處理機調度的層次和調度算法的目標作業與作業調度作業與作業調度2進程調度進程調度3 3實時調度實時

28、調度4 4死鎖概述死鎖概述3 535142022-4-2336預防死鎖預防死鎖4 4避免死鎖避免死鎖3 5 76死鎖的檢測與解除死鎖的檢測與解除4 4 82022-4-23373.33.3 進程調度進程調度通常也把低級調度(Low Level Scheduling)稱為進程調度或短程調度(ShortTerm Scheduling)，它所調度的對象是調度的對象是進程進程( (或內核級線程)。進程調度是最基本的一種調度，在多道批處理、分時和實時三種類型的OS中，都必須配置這級調度。1 1進程調度的任務進程調度的任務低級調度用于決定就緒隊列中的哪個進程(或內核級線程，為敘述方便，以后只寫進程)應獲得

29、處理機獲得處理機，然后再由分派程分派程序序執行把處理機分配給該進程的具體操作。2022-4-2338低級調度的主要功能如下： (1) 保存處理機的現場信息保存處理機的現場信息。在進程調度進行調度時，首先需要保存當前進程的處理機的現場信息，如程序計數器、多個通用寄存器中的內容等，將它們送入該進程的進程控制塊(PCB)中的相應單元。(2) 按某種算法選取進程按某種算法選取進程。低級調度程序按某種算法如優先數算法、輪轉法等，從就緒隊列中選取一個進程，把它的狀態改為運行狀態，并準備把處理機分配給它。 (3) 把處理器分配給進程把處理器分配給進程。由分派程序(Dispatcher)把處理器分配給進程。此

30、時需為選中的進程恢復處理機現場，即把選中進程的進程控制塊內有關處理機現場的信息裝入處理器相應的各個寄存器中，把處理器的控制權交給該進程，讓它從取出的斷點處開始繼續運行。 2022-4-23392 2進程調度中的三個進程調度中的三個基本機制基本機制為了實現進程調度，應具有如下三個基本機制：(1) 排隊器排隊器。為了提高進程調度的效率，應事先將系統中所有的就緒進程按照一定的方式排成一個或多個隊列一個或多個隊列，以便調度程序能最快地找到它。(2) 分派器分派器(分派程序)。分派器把由進程調度程序所選定的進程，從就緒隊列中取出該進程，然后進行上下文切換上下文切換，將處理機分配給它。 2022-4-23

31、40(3) 上下文切換機制上下文切換機制。當對處理機進行切換時，會發生兩對上下文切換操作。在第一對上下文切換時，操作系統將保存當前進程的上下文，而裝入分派程序的上下文，以便分派程序運行；在第二對上下文切換時，將移出分派程序，而把新選進程的CPU現場信息裝入到處理機的各個相應寄存器中。上下文切換上下文切換（Context Switch）：多任務系統中，上下文切換是指CPU的控制權由運行任務轉移到另外一個就緒任務時所發生的事件。 2022-4-2341應當指出，上下文切換將花去不少的處理機時間，即使是現代計算機，每一次上下文切換大約需要花費幾毫秒的時間，該時間大約可執行上千條指令。為此，現在已有通

32、過硬硬件件(采用兩組或多組寄存器)的方法來減少上下文切換的時間減少上下文切換的時間。一組寄存器供處理機在系統態時使用，另一組寄存器供應用程序使用。在這種條件下的上下文切換只需改變指針，使其指向當前寄存器組即可。 2022-4-23423 3進程調度方式進程調度方式進程調度可采用下述兩種調度方式。1) 非搶占方式非搶占方式(Non-preemptiveNon-preemptivepremptv Mode)在采用這種調度方式時，一旦把處理機分配給某進程后，不管它要運行多長時間，都一直讓它運行下去，決不會因為時鐘中斷等原因而搶占正在運行進程的處理機，也不允許其它進程搶占已經分配給它的處理機。直至該進

33、程完成，自愿釋放處理機，或發生某事件而被阻塞時，才再把處理機分配給其他進程。 2022-4-2343在采用非搶占調度方式時，可能引起進程調度的因素引起進程調度的因素可歸結為如下幾個：(1) 正在執行的進程執行完畢正在執行的進程執行完畢，或因發生某事件而不能再繼續執行；(2) 執行中的進程因提出執行中的進程因提出I/OI/O請求請求而暫停執行；(3) 在進程通信或同步過程在進程通信或同步過程中執行了某種原語操作原語操作，如P操作(wait操作)、Block原語、Wakeup原語等。這種調度方式的優點優點是實現簡單，系統開銷小，適用于大多數的批處理系統環境。但它難以滿足緊急任務的要求立即執行，因而

34、可能造成難以預料的后果。顯然，在要求比較嚴格的實時系統中，不宜采用這種調度方式。 2022-4-23442) 搶占方式(Preemptive Mode)這種調度方式允許調度程序根據某種原則某種原則去暫停某個正在執行的進程，將已分配給該進程的處理機重新分配給另一將已分配給該進程的處理機重新分配給另一進程進程。搶占方式的優點優點是，可以防止一個長進程長時間占用處理機，能為大多數進程提供更公平的服務，特別是能滿足對響應時間有著較嚴格要求的實時任務的需求。但搶占方式比非搶占方式調度所需付出的開銷較大。搶占調度方式是基于一定原則的，主要有如下幾條： 2022-4-2345(1) 優先權原則優先權原則。通

35、常是對一些重要的和緊急的作業賦予較高的優先權。當這種作業到達時，如果其優先權比正在執行進程的優先權高，便停止正在執行(當前)的進程，將處理機分配給優先權高的新到的進程，使之執行；或者說，允許優先權高的新到進程搶占當前進程的處理機。(2) 短作業短作業( (進程進程) )優先原則優先原則。當新到達的作業(進程)比正在執行的作業(進程)明顯的短時，將暫停當前長作業(進程)的執行，將處理機分配給新到的短作業(進程)，使之優先執行； 或者說，短作業(進程)可以搶占當前較長作業(進程)的處理機。(3) 時間片原則時間片原則。各進程按時間片輪流運行，當一個時間片用完后，便停止該進程的執行而重新進行調度。這

36、種原則適用于分時系統、大多數的實時系統，以及要求較高的批處理系統。 2022-4-23463.3.23.3.2基于時間片的輪轉調度算法基于時間片的輪轉調度算法1 1時間片輪轉法時間片輪轉法(Round robin scheduling)1) 基本原理基本原理在早期的時間片輪轉法中，系統將所有的就緒進程按先來先服務的原則排成一個隊列，每次調度時，把CPU分配給隊首隊首進程進程，并令其執行一個時間片。時間片的大小從幾ms到幾百ms。當執行的時間片用完時，由一個計時器計時器發出時鐘中斷請中斷請求求，調度程序便據此信號來停止該進程的執行，并將它送往就緒隊列的末尾；然后，再把處理機分配給就緒隊列中新的隊

37、首進程，同時也讓它執行一個時間片。這樣就可以保證就緒隊列中的所有進程在一給定的時間內均能獲得一時間片的處理機執行時間。換言之，系統能在給定的時間內響應所有用戶的請求。 2022-4-23472) 時間片大小時間片大小的確定在時間片輪轉算法中，時間片的大小對系統性能有很大的影響，如選擇很小的時間片將有利于短作業，因為它能較快地完成，但會頻繁地發生中斷、進程上下文的切換，從而增加系統的開銷；反之，如選擇太長的時間片，使得每個進程都能在一個時間片內完成，時間片輪轉算法便退化為FCFS算法，無法滿足交互式用戶交互式用戶的需求。一個較為可取的大小是，時間片略大時間片略大于一次典型的交互所需要的時間于一次

38、典型的交互所需要的時間。這樣可使大多數進程在一個時間片內完成。圖3-3示出了時間片分別為q=1和q=4時，A、B、C、D、E五個進程的運行情況，而圖3-6為q=1和q=4時各進程的平均周轉時間和帶權平均周轉時間。圖中的RR(Round Robin)表示輪轉調度算法。 2022-4-2348圖3-3 3 q=1和q=4時進程的周轉時間 2022-4-23493.3.53.3.5多級反饋隊列調度算法多級反饋隊列調度算法(multilevel feedback queue)(multilevel feedback queue)不必事先知道各種進程所需的執行時間不必事先知道各種進程所需的執行時間。1.

39、 調度機制(1) 應設置多個就緒隊列多個就緒隊列，并為各個隊列賦予不同的優先級隊列賦予不同的優先級。第一個隊列的優先級最高，第二個隊列次之，其余各隊列的優先權逐個降低。該算法賦予各個隊列中進程執行時間片的大小也各不相同，在優先權愈高的隊列中，為每個進程所規定的執行時間片就愈小。例如，第二個隊列的時間片要比第一個隊列的時間片長一倍，第i+1個隊列的時間片要比第i個隊列的時間片長一倍。圖3-4是多級反饋隊列算法的示意。 2022-4-2350圖 3-4多級反饋隊列調度算法 就緒隊列 1就緒隊列 2就緒隊列 3就緒隊列 nS1S2S3至CPU至CPU至CPU至CPU(時間片： S1 S2 S3)20

40、22-4-2351(2) 當一個新進程進入新進程進入內存后，首先將它放入第一隊列的末尾，按FCFS原則排隊等待調度。當輪到該進程執行時，如它能在該時間片內完成，便可準備撤離系統；如果它在一個時間片結束時尚未完成，調度程序便將該進程轉入第二隊列的末尾，再同樣地按FCFS原則等待調度執行；如果它在第二隊列中運行一個時間片后仍未完成，再依次將它放入第三隊列，如此下去，當一個長作業(進程)從第一隊列依次降到第n隊列后，在第n隊列中便采取按時間片輪轉的方式運行。 2022-4-2352(3) 僅當第一隊列空閑時僅當第一隊列空閑時，調度程序才調度第二隊列中的進程運行；僅當第1(i-1)隊列均空時，才會調度

41、第i隊列中的進程運行。如果處理機正在第i隊列中為某進程服務時，又有新進程進入優先權較高的隊列(第1(i-1)中的任何一個隊列)，則此時新進程將搶占正在運行進程的處理機，即由調度程序把正在運行的進程放回到第i隊列的末尾，把處理機分配給新到的高優先權進程。 2022-4-23533 3多級反饋隊列調度算法的性能多級反饋隊列調度算法的性能多級反饋隊列調度算法具有較好的性能較好的性能，能很好地滿足滿足各種類型用戶各種類型用戶的需要。(1) 終端型作業用戶終端型作業用戶。由于終端型作業用戶所提交的作業大多屬于交互型作業，作業通常較小，系統只要能使這些作業(進程)在第一隊列所規定的時間片內完成，便可使終端

42、型作業用戶都感到滿意。 2022-4-2354(2) 短批處理作業用戶短批處理作業用戶。對于很短的批處理型作業，開始時像終端型作業一樣，如果僅在第一隊列中執行一個時間片即可完成，便可獲得與終端型作業一樣的響應時間。對于稍長的作業，通常也只需在第二隊列和第三隊列各執行一個時間片即可完成，其周轉時間仍然較短。(3) 長批處理作業用戶長批處理作業用戶。對于長作業，它將依次在第1，2，n個隊列中運行，然后再按輪轉方式運行，用戶不必擔心其作業長期得不到處理。 2022-4-23553.3.6 3.3.6 基于公平原則的調度算法基于公平原則的調度算法 保證調度算法從進程角度進程角度保證處理機分配的公平性；

43、 公平分享調度算法從用戶角度用戶角度保證每個用戶獲得相同的處理機時間； 2022-4-23563.2 調度隊列模型和調度準則調度隊列模型和調度準則 3.2.13.2.1調度隊列模型調度隊列模型1 1僅有進程調度僅有進程調度的調度隊列模型的調度隊列模型在分時系統分時系統中，通常僅設置了進程調度，用戶鍵入的命令和數據都直接送入內存。對于命令，是由OS為之建立一個進程。系統可以把處于就緒狀態的進程組織成棧、樹或一個無序鏈表，至于到底采用其中哪種形式，則與OS類型和所采用的調度算法有關。例如，在分時系統中，常把就緒進程組織成FIFOFIFO隊列隊列形式。每當OS創建一個新進程時，便將它掛在就緒隊列的末

44、尾，然后按時間片輪轉方式運行。 2022-4-2357每個進程在執行時都可能出現以下三種情況三種情況：(1) 任務在給定的時間片內已經完成，該進程便在釋放處理機后進入完成狀態；(2) 任務在本次分得的時間片內尚未完成，OS便將該任務再放入就緒隊列的末尾；(3) 在執行期間，進程因為某事件而被阻塞后，被OS放入阻塞隊列。圖3-1示出了僅具有進程調度的調度隊列模型。 2022-4-2358圖圖 3-1僅具有進程調度的調度隊列模型僅具有進程調度的調度隊列模型 就 緒 隊 列阻 塞 隊 列進程調度CPU進程完成等待事件交互用戶事件出現時間片完2022-4-23592 2具有具有高級和低級調度高級和低級

45、調度的調度隊列模型的調度隊列模型在批處理系統批處理系統中，不僅需要進程調度，而且還需有作業調度，由后者按一定的作業調度算法，從外存的后備隊列中選擇一批作業調入內存，并為它們建立進程，送入就緒隊列，然后才由進程調度按照一定的進程調度算法選擇一個進程，把處理機分配給該進程。圖3-2示出了具有高、低兩級調度的調度隊列模型。該模型與上一模型的主要區別在于如下兩個方面。 2022-4-2360(1) 就緒隊列的形式就緒隊列的形式。在批處理系統中，最常用的是最高優先權優先調度算法，相應地，最常用的就緒隊列形式是優優先權隊列先權隊列。進程在進入優先級隊列時，根據其優先權的高低，優先權的高低，被插入具有相應優

46、先權的位置上被插入具有相應優先權的位置上，這樣，調度程序總是把處理機分配給就緒隊列中的隊首進程。在最高優先權優先的調度算法中，也可采用無序鏈無序鏈表方式，即每次把新到的進程掛在鏈尾，而調度程序每次調度時，是依次比較該鏈中各進程比較該鏈中各進程的優先權的優先權，從中找出優先權最高的進程，將之從鏈中摘下，并把處理機分配給它。顯然，無序鏈表方式與優先權隊列相比，這種方式的調度效率較低。 2022-4-2361(2) 設置多個阻塞隊列設置多個阻塞隊列。對于小型系統，可以只設置一個阻塞隊列；但當系統較大時，若仍只有一個阻塞隊列，其長度必然會很長，隊列中的進程數可以達到數百個，這將嚴重影響對阻塞隊列操作的

47、效率效率。故在大、中型系統中通常都設置了若干個阻塞隊列若干個阻塞隊列，每個隊列對應于某一種進程阻塞事件某一種進程阻塞事件。 2022-4-2362圖 3-2具有高、低兩級調度的調度隊列模型 就 緒 隊 列進程調度CPU進程完成等待事件1作業調度事件1出現時間片完等待事件2事件2出現等待事件n事件n出現后 備 隊 列2022-4-23633 3同時同時具有三級調度具有三級調度的調度隊列模型的調度隊列模型當在OS中引入中級調度后，人們可把進程的就緒狀態分為內存就緒內存就緒(表示進程在內存中就緒)和外存就緒外存就緒(進程在外存中就緒)。類似地，也可把阻塞狀態進一步分成內存阻塞和外存阻塞兩種狀態。在調

48、出操作的作用下，可使進程狀態由內存就緒轉為外存就緒，由內存阻塞轉為外存阻塞；在中級調度的作用下，又可使外存就緒轉為內存就緒。圖3-3示出了具有三級調度的調度隊列模型。 2022-4-2364圖 3-3具有三級調度時的調度隊列模型 就緒隊列進程調度CPU就緒，掛起隊列中級調度阻塞，掛起隊列阻塞隊列等待事件進程完成時間片完作業調度交互型作業后備隊列批量作業掛起事件出現事件出現2022-4-23653.2.23.2.2選擇調度方式和調度算法的若干準則選擇調度方式和調度算法的若干準則1 1面向用戶的準則面向用戶的準則 (1) 周轉時間短周轉時間短。通常把周轉時間的長短作為評價批處理系統的性能、選擇作業

49、調度方式與算法的重要準則之一。所謂周轉時間周轉時間，是指從作業被提交給系統開始，到作業完成為止的這段時間間隔(稱為作業周轉時間)。它包括四部分時間：作業在外存后備隊列上等待等待(作業)調度的時間，進程在就緒隊列上等待等待進程調度的時間，進程在CPU上執行執行的時間，以及進程等待等待I/O操作完成的時間。其中的后三項在一個作業的整個處理過程中可能會發生多次。 2022-4-2366對每個用戶而言，都希望自己作業的周轉時間最短。但作為計算機系統的管理者，則總是希望能使平均周轉時間最短，這不僅會有效地提高系統資源的利用率，而且還可使大大多數用戶多數用戶都感到滿意。可把平均周轉時間平均周轉時間描述為：

50、 niiTnT112022-4-2367作業的周轉時間周轉時間T T與系統為它提供服務的時間服務的時間TsTs之比，即W = T/Ts，稱為帶權周轉時間帶權周轉時間，而平均帶權周轉時間則可表示為： niiTTnW1s12022-4-2368(2) 響應時間快響應時間快。常把響應時間的長短用來評價分時系分時系統統的性能，這是選擇分時系統中進程調度算法的重要準則之一。所謂響應時間，是從用戶通過鍵盤提交一個請求開始，直至系統首次產生響應為止的時間，或者說，直到屏幕上顯示出結果為止的一段時間間隔。它包括三部分時間三部分時間：從鍵盤輸入的請求信息傳送到處理機的時間，處理機對請求信息進行處理的時間，以及將

51、所形成的響應信息回送到終端顯示器的時間。 2022-4-2369(3) 截止時間截止時間的保證。這是評價實時系統性能實時系統性能的重要指標，因而是選擇實時調度算法的重要準則。所謂截止時間，是指某任務必須開始執行的最遲時間開始執行的最遲時間，或必須完成的最遲時完成的最遲時間間。對于嚴格的實時系統，其調度方式和調度算法必須能保證這一點，否則將可能造成難以預料的后果。(4) 優先權準則優先權準則。在批處理、分時和實時系統中選擇調度算法時，都可遵循優先權準則，以便讓某些緊急的作業能得到及時處理。在要求較嚴格的場合，往往還須選擇搶占式調度方式，才能保證緊急作業得到及時處理。 2022-4-23702 2

52、面向系統的準則面向系統的準則這是為了滿足系統要求而應遵循的一些準則。其中，較重要的有以下幾點：(1) 系統吞吐量高系統吞吐量高。這是用于評價批處理系統性能的另一個重要指標，因而是選擇批處理作業調度的重要準則。由于吞吐量是指在單位時間內系統所完成的作業數，因而它與批處理作業的平均長度具有密切關系。對于大型作業，一般吞吐量約為每小時一道作業；對于中、小型作業，其吞吐量則可能達到數十道作業之多。作業調度的方式和算法對吞吐量的大小也將產生較大影響。事實上，對于同一批作業，若采用了較好的調度方式和算法，則可顯著地提高系統的吞吐量。 2022-4-2371(2) 處理機利用率好處理機利用率好。對于大、中型

53、多用戶系統，由于CPU價格十分昂貴，致使處理機的利用率成為衡量系統性能的十分重要的指標；而調度方式和算法對處理機的利用率起著十分重要的作用。在實際系統中，CPU的利用率一般在40%(系統負荷較輕)到90%之間。在大、中型系統大、中型系統中，在選擇調度方式和算法時，應考慮到這一準則。但對于單用戶微機或某些實時系統，則此準則就不那么重要了。 2022-4-2372(3) 各類資源的平衡利用各類資源的平衡利用。在大、中型系統中，不僅要使處理機的利用率高，而且還應能有效地利用其它各類資源，如內存、外存和I/O設備等。選擇適當的調度方式和算法可以保持系統中各類資源都處于忙碌狀態。但對于微型機和某些實時系

54、統而言，該準則并不重要。 第三章 進程的描述與控制處理機調度的層次和調度算法的目標處理機調度的層次和調度算法的目標作業與作業調度作業與作業調度2進程調度進程調度3 3實時調度實時調度4 4死鎖概述死鎖概述3 535142022-4-2373預防死鎖預防死鎖4 4避免死鎖避免死鎖3 5 76死鎖的檢測與解除死鎖的檢測與解除4 4 82022-4-23743.4實實 時時 調調 度度 3.4.13.4.1實現實現實時調度的基本條件實時調度的基本條件1 1提供提供必要的信息必要的信息為了實現實時調度，系統應向調度程序提供有關任務的下述一些信息：(1) 就緒時間就緒時間。這是該任務成為就緒狀態的起始時

55、間，在周期任務的情況下，它就是事先預知的一串時間序列一串時間序列；而在非周期任務的情況下，它也可能是預知的。 2022-4-2375(2) 開始截止時間和完成截止時間開始截止時間和完成截止時間。對于典型的實時應用，只須知道開始截止時間，或者知道完成截止時間。(3) 處理時間處理時間。這是指一個任務從開始執行直至完成所需的時間。在某些情況下，該時間也是系統提供的。(4) 資源要求資源要求。這是指任務執行時所需的一組資源。(5) 優先級優先級。如果某任務的開始截止時間已經錯過，就會引起故障，則應為該任務賦予“絕對絕對”優先級；如果開始截止時間的推遲對任務的繼續運行無重大影響無重大影響，則可為該任務

56、賦予“相對相對”優先級，供調度程序參考。 2022-4-23762 2系統處理能力強系統處理能力強( (系統處理能力與實時任務之間的計算關系系統處理能力與實時任務之間的計算關系) )在實時系統中，通常都有著多個實時任務。若處理機的處理能力不夠強，則有可能因處理機忙不過來而使某些實時任務不能得到及時處理，從而導致發生難以預料的后果。假定系統中有m個周期性的硬實時任務個周期性的硬實時任務，它們的處理時間處理時間可表示為CiCi，周期時間周期時間表示為PiPi，則在單處理機情況下，必須滿足下面的限制條件限制條件： 11miiiPC2022-4-2377系統才是可調度的。假如系統中有6個硬實時任務，它

57、們的周期時間都是 50 ms，而每次的處理時間為 10 ms，則不難算出，此時是不能滿足上式的，因而系統是不可調度的。解決的方法是提高系統的處理能力，其途徑有二：其一仍是采用單處理機系統，但須增強其處理能力增強其處理能力，以顯著地減少對每一個任務的處理時間；其二是采用多處理機系統多處理機系統。假定系統中的處理機數為處理機數為N N，則應將上述的限制條件改為： NPCmiii12022-4-23783 3采用采用搶占式調度機制搶占式調度機制在含有硬實時任務(HRT)(HRT)的實時系統中，廣泛采用搶占機搶占機制制。當一個優先權更高的任務到達時，允許將當前任務暫時掛起，而令高優先權任務立即投入運行

58、，這樣便可滿足該硬實時任務對截止時間的要求。但這種調度機制比較復雜。對于一些小型實時系統，如果能預知任務的開始截止時預知任務的開始截止時間間，則對實時任務的調度可采用非搶占調度機制非搶占調度機制，以簡化調度程序和對任務調度時所花費的系統開銷。但在設計這種調度機制時，應使所有的實時任務都比較小，并在執行完關鍵性程序和臨界區后，能及時地將自己阻塞起來，以便釋放出處理機，供調度程序去調度那種開始截止時間即將到達的任務。 2022-4-23794 4具有具有快速切換機制快速切換機制為保證要求較高的硬實時任務能及時運行，在實時系統中還應具有快速切換機制，以保證能進行任務的快速切換。該機制應具有如下兩方面

59、的能力：(1) 對外部中斷的快速響應能力外部中斷的快速響應能力。為使在緊迫的外部事件請求中斷時系統能及時響應，要求系統具有快速硬件中斷機構快速硬件中斷機構，還應使禁止中斷的時間間隔盡量短，以免耽誤時機(其它緊迫任務)。(2) 快速的任務分派能力快速的任務分派能力。在完成任務調度后，便應進行任務切換。為了提高分派程序進行任務切換時的速度，應使系統中的每個運行功能單位適當地小，以減少任務切換的時間開銷。 2022-4-23803.4.23.4.2實時調度算法的分類實時調度算法的分類1 1非搶占式調度算法非搶占式調度算法1) 非搶占式輪轉調度算法非搶占式輪轉調度算法該算法常用于工業生產的群控系統工業

60、生產的群控系統中，由一臺計算機控制若干個相同的(或類似的)對象，為每一個被控對象建立一個實時任務，并將它們排成一個輪轉隊列輪轉隊列。調度程序每次選擇隊列中的第一個任務投入運行。當該任務完成后，便把它掛在輪轉隊列的末尾，等待下次調度運行，而調度程序再選擇下一個(隊首)任務運行。這種調度算法可獲得數秒至數十秒的響應時間，可用于要求不太嚴格的實時控制系統要求不太嚴格的實時控制系統中。 2022-4-23812) 非搶占式優先調度算法如果在實時系統中存在著要求較為嚴格較為嚴格(響應時間為數百毫秒)的任務任務，則可采用非搶占式優先調度算法為這些任務賦賦予較高的優先級予較高的優先級。當這些實時任務到達時，