3.2　課后習題詳解

1高級調度與低級調度的主要任務是什么？為什么要引入中級調度？

答：（1）高級調度和低級調度的主要任務

①高級調度又稱為作業調度或長程調度，其主要功能是根據某種算法，把外存上處于后備隊列中的那些作業調入內存，也就是說，它的調度對象是作業。

②低級調度用于決定就緒隊列中的哪個進程應獲得處理機，然后再由分派程序執行把處理機分配給該進程的具體操作。通常也把低級調度稱為進程調度或短程調度，它所調度的對象是進程（或內核級線程）。

（2）引入中級調度的目的

引入中級調度的主要目的是為了提高內存利用率和系統吞吐量，中級調度實際上就是存儲器管理中的對換功能。

2處理機調度算法的共同目標是什么？批處理系統的調度目標又是什么？

答：（1）處理機調度算法的共同目標

①資源利用率

為提高系統的資源利用率，應使系統中的處理機和其他所有資源都盡可能地保持忙碌狀態。

②公平性

公平性是指應使諸進程都獲得合理的CPU時間，不會發生進程饑餓現象。

③平衡性

為使系統中的CPU和各種外部設備都能經常處于忙碌狀態，調度算法應盡可能保持系統資源使用的平衡性。

④策略強制執行

對所制訂的策略其中包括安全策略，只要需要，就必須予以準確地執行，即使會造成某些工作的延遲也要執行。

（2）批處理系統的調度目標

①使程序的平均周轉時間短；

②提高系統吞吐量；

③提高處理機利用率。

3何謂作業、作業步和作業流？

答：（1）作業

作業是用戶提交給系統的一項相對獨立的工作，它不僅包含了通常的程序和數據，而且還應配有一份作業說明書，系統根據該說明書來對程序的運行進行控制。在批處理系統中，是以作業為基本單位從外存調入內存的。

（2）作業步

通常，在作業運行期間，每個作業都必須經過若干個相對獨立又相互關聯的順序加工步驟才能得到結果，我們把其中的每一個加工步驟稱為一個作業步。

（3）作業流

若干個作業進入系統后，被依次存放在外存上，這便形成了輸入的作業流；在操作系統的控制下，逐個對作業進行處理，于是便形成了處理作業流。

4在什么情況下需要使用作業控制塊JCB，其中包含了哪些內容？

答：（1）使用JCB的情況

每當作業進入系統時，系統便為每個作業建立一個JCB，根據作業類型將它插入相應的后備隊列中。作業調度程序依據一定的調度算法來調度它們，被調度到的作業將會被裝入內存。在作業運行期間，系統就按照JCB中的信息對作業進行控制。當一個作業執行結束進入完成狀態時，系統負責回收分配給它的資源，撤銷它的作業控制塊。

（2）JCB包含的內容

在JCB中所包含的內容因系統而異，通常應包含的內容有：作業標識、用戶名稱、用戶帳戶、作業類型（CPU繁忙型、I/O繁忙型、批量型、終端型）、作業狀態、調度信息（優先級、作業已運行時間）、資源需求（預計運行時間、要求內存大小、要求I/O設備的類型和數量等）、進入系統時間、開始處理時間、作業完成時間、作業退出時間、資源使用情況等。

5在作業調度中應如何確定接納多少個作業和接納哪些作業？

答：（1）作業調度每次要接納多少個作業進入內存，取決于多道程序度，即允許多少個作業同時在內存中運行。當內存中同時運行的作業數目太多時，可能會影響到系統的服務質量。但如果在內存中同時運行作業的數量太少時，又會導致系統的資源利用率和系統吞吐量太低，因此，多道程序度的確定應根據系統的規模和運行速度等情況做適當的折衷。

（2）應將哪些作業從外存調入內存，這將取決于所采用的調度算法。最簡單的是先來先服務調度算法，這是指將最早進入外存的作業最先調入內存：較常用的一種算法是短作業優先調度算法，是將外存上最短的作業最先調入內存；另一種較常用的是基于作業優先級的調度算法，該算法是將外存上優先級最高的作業優先調入內存；比較好的一種算法是“響應比高者優先”的調度算法。

6為什么要引入高響應比優先調度算法？它有何優點？

答：（1）引入高響應比優先調度算法的原因

①在批處理系統中，FCFS算法所考慮的只是作業的等待時間，而忽視了作業的運行時間。

②SJF算法只考慮作業的運行時間，而忽視了作業的等待時間。

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

（2）高響應度優先調度算法的優點

①如果作業（進程）的等待時間相同，則要求服務時間最短的作業（進程）的優先權最高，因此它有利于短作業（進程），從而可降低作業（進程）的平均周轉時間，提高系統吞吐量。

②如果作業（進程）的要求服務時間相同，則其優先權將取決于作業到達（或進程進入就緒狀態）的先后次序，因此體現了公平的原則。

③如果作業（進程）較長，它的優先權將隨著等待時間的增長而提高，從而使長作業（進程）不會長期得不到服務。

7試說明低級調度的主要功能。

答：低級調度又稱為進程調度或短程調度，其所調度的對象是進程（或內核級線程），它的主要功能如下：

（1）保存處理機的現場信息

在進行進程調度時，首先需要保存當前進程的處理機的現場信息，將它們送入該進程的進程控制塊（PCB）中的相應單元。

（2）按某種算法選取進程

低級調度程序按某種算法如優先數算法、輪轉法等，從就緒隊列中選取一個進程，把它的狀態改為運行狀態，并準備把處理機分配給它。

（3）把處理器分配給進程

由分派程序（Dispatcher）把處理器分配給進程。此時需為選中的進程恢復處理機現場，即把選中進程的進程控制塊內有關處理機現場的信息裝入處理器相應的各個寄存器中，把處理器的控制權交給該進程，讓它從取出的斷點處開始繼續運行。

8在搶占調度方式中，搶占的原則是什么？

答：搶占調度方式允許調度程序根據某種原則，去暫停某個正在執行的進程，將已分配給該進程的處理機重新分配給另一進程。搶占的原則有：優先權原則，短作業（進程）優先原則，時間片原則。

9在選擇調度方式和調度算法時，應遵循的準則是什么？

答：調度的準則包括：CPU利用率、系統吞吐量、進程周轉時間、進程等待時間以及響應時間的長短。

10在批處理系統、分時系統和實時系統中，各采用哪幾種進程（作業）調度算法？

答：（1）適合批處理系統的調度算法有短作業優先、優先權、高響應比優先和多級反饋隊列調度算法；

（2）分時系統的調度算法有時間片輪轉法和多級反饋隊列調度算法；

（3）實時系統的調度算法有優先級調度算法、最早截止時間優先即EDF算法和最低松弛度優先即LLF算法。

11何謂靜態和動態優先級？確定靜態優先級的依據是什么？

答：（1）靜態優先級是在創建進程時確定的，且在進程的整個運行期間保持不變。一般地，優先權是利用某一范圍內的一個整數來表示的。

（2）動態優先級是指在創建進程時所賦予的優先權，是可以隨進程的推進或隨其等待時間的增加而改變的，以便獲得更好的調度性能。

（3）確定靜態優先級的依據

①進程類型，通常，系統進程（如接收進程、對換進程、磁盤I/O進程）的優先權高于一般用戶進程的優先權；

②進程對資源的需求；

③用戶要求。

12試比較FCFS和SJF兩種進程調度算法。

答：（1）先來先服務（FCFS）調度算法

①調度過程

當在作業調度中采用該算法時，每次調度都是從后備作業隊列中選擇一個或多個最先進入該隊列的作業，將它們調入內存，為它們分配資源、創建進程，然后放入就緒隊列。

②適用范圍

FCFS算法比較有利于長作業（進程），而不利于短作業（進程）。

（2）短作業優先（SJF）調度算法

①調度過程

短作業優先（SJF）的調度算法是從后備隊列中選擇一個或若干個估計運行時間最短的作業，將它們調入內存運行。而短進程優先（SPF）調度算法則是從就緒隊列中選出一個估計運行時間最短的進程，將處理機分配給它，使它立即執行并一直執行到完成，或發生某事件而被阻塞放棄處理機時再重新調度。

②適用范圍

有利于短作業（進程）、不利于長作業（進程）。

13在時間片輪轉法中，應如何確定時間片的大小？

答：選擇時間片大小時，一般應考慮以下三個因素：

（1）系統對響應時間的要求；

（2）就緒隊列中進程的數目；

（3）系統的處理能力。

14通過一個例子來說明通常的優先級調度算法為什么不能適用于實時系統？

答：有兩個周期性任務，任務A的周期時間為20ms，每個周期的處理時間為10ms，任務B的周期時間為50ms，每個周期的處理時間為25ms。如表3-1中所示第一行顯示出了兩個任務的到達時間、最后期限和執行時間圖。其中任務A的到達時間為0、20、40、…；任務A的最后期限為20、40、60、…；任務B的到達時間為0、50、100、…（注：單位皆為ms）。

為了說明通常的優先級調度不適用于實時系統，如表3-2所示增加了第二行。在第二行中假定任務A具有較高的優先級，所以在t=0ms時，先調度A1執行，在A1完成后（t=10ms）才調度B1執行；在t=20ms時，調度A2執行；在t=30ms時，A2完成，又調度B1執行；在t=40ms時，調度A3執行；在t=50ms時，雖然A3已完成，但B1已錯過了它的最后期限，這說明利用通常的優先級調度已經失敗。

表3-1　到達時間，執行時間和最后期限

表3-2　A具有較高優先級

實時系統的調度算法很多，主要是基于任務的開始截止時間和任務緊急/松弛程度的任務優先級調度算法，通常的優先級調度算法不能滿足實時系統的調度實時性要求因此不適用于實時系統。

15為什么說多級反饋隊列調度算法能較好地滿足各方面用戶的需要？

答：（1）終端型作業用戶

由于終端型作業用戶所提交的作業大多屬于交互型作業，作業通常較小，系統只要能使這些作業（進程）在第一隊列所規定的時間片內完成，便可使終端型作業用戶都感到滿意。

（2）短批處理作業用戶

對于很短的批處理型作業，開始時像終端型作業一樣，如果僅在第一隊列中執行一個時間片即可完成，便可獲得與終端型作業一樣的響應時間。對于稍長的作業，通常也只需在第二隊列和第三隊列各執行一個時間片即可完成，其周轉時間仍然較短。

（3）長批處理作業用戶

對于長作業，它將依次在第1，2，…，n個隊列中運行，然后再按輪轉方式運行，用戶不必擔心其作業長期得不到處理。

16為什么說傳統的幾種調度算法都不能算是公平調度算法？

答：傳統的幾種調度算法所保證的只是優先運行，如優先級算法是優先級最高的作業優先運行，但并不保證作業占用了多少處理機時間。另外也未考慮到調度的公平性。

17保證調度算法是如何做到調度的公平性的？

答：保證調度算法是另外一種類型的調度算法，它向用戶所做出的保證并不是優先運行，而是明確的性能保證，該算法可以做到調度的公平性。一種比較容易實現的性能保證是處理機分配的公平性。如果在系統中有n個相同類型的進程同時運行，為公平起見，須保證每個進程都獲得相同的處理機時間1/n。

18公平分享調度算法又是如何做到調度的公平性的？

答：在公平分享調度算法中，調度的公平性主要是針對用戶而言，使所有用戶能獲得相同的處理機時間，或所要求的時間比例。

19為什么在實時系統中，要求系統（尤其是CPU）具有較強的處理能力？

答：在實時系統中，通常都有著多個實時任務。若處理機的處理能力不夠強，則有可能因處理機忙不過來而使某些實時任務不能及時得到處理，從而導致難以預料的后果。解決的方法是提高系統的處理能力，其途徑有二：其一仍是采用單處理機系統，但須增強其處理能力，以顯著地減少對每一個任務的處理時間；其二是采用多處理機系統，使其并行從而減少對對個實時任務的總處理時間。

20按調度方式可將實時調度算法分為哪幾種？

答：按調度方式的不同，實時調度算法可分為非搶占調度算法和搶占調度算法。由于非搶占式調度算法比較簡單，易于實現，故在一些小型實時系統或要求不太嚴格的實時控制系統中經常采用之，可以分為非搶占式輪轉調度算法和非搶占式優先調度算法；在要求較嚴格的（響應時間為數十毫秒以下）的實時系統中，應采用搶占式優先權調度算法，可根據搶占發生時間的不同而進一步分成基于時鐘中斷的搶占式優先權調度算法和立即搶占的優先權調度算法。

21什么是最早截止時間優先調度算法？舉例說明之。

答：（1）最早截止時間優先調度算法的定義

最早截止時間優先調度算法是根據任務的開始截止時間來確定任務的優先級。截止時間愈早，其優先級愈高。該算法要求在系統中保持一個實時任務就緒隊列，該隊列按各任務截止時間的早晚排序；當然，具有最早截止時間的任務排在隊列的最前面。調度程序在選擇任務時，總是選擇就緒隊列中的第一個任務，為之分配處理機，使之投入運行。最早截止時間優先調度算法既可用于搶占式調度，也可用于非搶占式調度方式中。

（2）舉例說明

圖3-1所示是將該算法用于非搶占調度方式的例子。該例中有四個非周期任務，它們先后到達。系統首先調度任務1執行，在任務1執行期間，任務2、3又先后到達。由于任務3的開始截止時間早于任務2，故系統在任務1后將調度任務3執行。在此期間又到達作業4，其開始截止時間仍是早于任務2的，故在任務3執行完后，系統又調度任務4執行，最后才調度任務2執行。

圖3-1　EDF算法用非搶占調度的調度方式

22什么是最低松弛度優先調度算法？舉例說明之。

答：（1）最低松弛度優先調度算法的定義

最低松弛度優先調度算法是根據任務緊急（或松弛）的程度，來確定任務的優先級。任務的緊急程度愈高，為該任務所賦予的優先級就愈高，以使之優先執行。

（2）舉例說明

①一個任務在200ms時必須完成，而它本身所需的運行時間就有100ms，因此，調度程序必須在100ms之前調度執行，該任務的緊急程度（松弛程度）為100ms。

②一任務在400ms時必須完成，它本身需要運行150ms，則其松弛程度為250ms。在實現該算法時要求系統中有一個按松弛度排序的實時任務就緒隊列，松弛度最低的任務排在隊列最前面，調度程序總是選擇就緒隊列中的隊首任務執行。

23何謂“優先級倒置”現象，可采取什么方法來解決？

答：當前OS廣泛采用優先級調度算法和搶占方式，然而在系統中存在著影響進程運行的資源而可能產生“優先級倒置”的現象，即高優先級進程（或線程）被低優先級進程（或線程）延遲或阻塞。

24試分別說明可重用資源和可消耗資源的性質。

答：（1）可重用性資源

每一個可重用性資源中的單元只能分配給一個進程使用，不允許多個進程共享。進程在使用可重用性資源時，須按照這樣的順序：請求資源、使用資源、釋放資源。系統中每一類可重用性資源中的單元數目是相對固定的，進程在運行期間既不能創建也不能刪除它。

（2）可消耗性資源

每一類可消耗性資源的單元數目在進程運行期間是可以不斷變化的，有時它可以有許多，有時可能為0。進程在運行過程中，可以不斷創造可消耗性資源的單元，將它們放入該資源類的緩沖區中，以增加該資源類的單元數目。進程在運行過程中，可以請求若干個可消耗性資源單元，用于進程自己的消耗，不再將它們返回給該資源類中。

25試舉例說明競爭不可搶占資源所引起的死鎖。

答：例如，系統中有兩個進程P₁和P₂，它們都準備寫兩個文件F₁和F₂，而這兩者都屬于可重用和不可搶占性資源。進程P₁先打開F₁，然后再打開文件F₂；進程P₂先打開文件F₂，后打開F₁，在P₁打開F₁的同時，P₂去打開F₂，每個進程都占有一個打開的文件，此時就可能出現問題。因為當P₁試圖去打開F₂，而P₂試圖去打開F₁時，這兩個進程都會因文件已被打開而阻塞，它們希望對方關閉自己所需要的文件，但誰也無法運行，因此這兩個進程將會無限期地等待下去，而形成死鎖。

26為了破壞“請求和保持”條件而提出了兩種協議，試比較這兩種協議。

答：（1）第一種協議在所有進程開始運行之前，必須一次性地申請其在整個運行過程中所需的全部資源，并且在分配資源時，只要有一種資源不能滿足進程的要求，即使其他所需的各種資源都空閑也不分配給該進程，而讓該進程等待。因此有資源被嚴重浪費、進程經常會發生饑餓現象等缺點。

（2）第二種協議是對第一種協議的改進，它允許一個進程只獲得運行初期所需的資源后，便開始運行。進程運行過程中再逐步釋放已分配給自己的，且已用畢的全部資源，然后再請求新的所需資源。如此便可提高設備的利用率，還可減少進程發生饑餓的概率。

27何謂死鎖？產生死鎖的原因和必要條件是什么？

答：（1）死鎖的定義

死鎖是指多個進程因爭奪資源而造成的一種僵局（相互等待），若無外力作用，它們都將無法再向前推進。

（2）產生死鎖的原因

產生死鎖的原因可歸結為競爭不可剝奪資源引起進程死鎖和進程推進順序不當引起死鎖兩個方面。

（3）產生死鎖的必要條件

①互斥條件；

②請求和保持條件；

③不剝奪條件；

④環路等待條件。

28在解決死鎖問題的幾個方法中，哪種方法最易于實現？哪種方法使資源利用率最高？

答：目前，處理死鎖的方法可歸結為以下四種：

（1）預防死鎖；

（2）避免死鎖；

（3）檢測死鎖；

（4）解除死鎖。

其中，預防死鎖最容易實現，避免死鎖使資源利用率最高。

29請詳細說明可通過哪些途徑預防死鎖。

答：預防死鎖的方法破壞產生死鎖的四個必要條件的一個或幾個，而互斥條件是由設備的固有特性所決定的，不僅不能改變，還應加以保證。因此，可以從以下三個方面預防死鎖：

（1）破壞“請求和保持”條件

在采用這種方法時，系統規定所有進程在開始運行前，都必須一次性地申請其在整個運行過程所需的全部資源。

（2）破壞“不剝奪”條件

在采用這種方法時，系統規定進程是逐個地提出對資源的要求的。當一個已經保持了某些資源的進程，再提出新的資源請求而不能立即滿足時，必須釋放它已保持的所有資源，待以后需要時再重新申請。

（3）破壞“環路等待”條件

這種方法中規定，系統將所有資源按照類型進行線性排隊，并賦予不同的序號。所有進程對資源的請求必須嚴格按資源序號遞增的次序提出。

30在銀行家算法的例子中，如果P₀發出的請求向量由Request（0，2，0）改為Request（0，1，0），問系統可否將資源分配給它？

答：可以。銀行家算法中各種資源的總數量分別為10、5、7，在T0時刻的資源分配如表3-3所示。

表3-3　資源分配情況

具體分析如下：

（1）Requst0（0，1，0）＜=Need0（7，4，3）；

（2）Requst0（0，1，0）＜=Available（3，3，2）；

系統先假定可為P0分配資源，并修改Available，Allocation0和Need0向量，由此形成的資源變化情況如表3-4所示。

表3-4　資源變化情況

系統按銀行家算法進行檢查，如表3-5所示。

表3-5　按銀行家算法檢查結果

得到安全序列＜P1，P3，P4，P0，P2＞，因此系統是安全的，可以將資源分配給它。

31在銀行家算法中，若出現下述資源分配情況，試問：

（1）該狀態是否安全？

（2）若進程P₂提出請求Request（1，2，2，2）后，系統能否將資源分配給它？

答：（1）安全，因為存在安全序列{P₀，P₃，P₄，P₁，P₂}，如表3-6所示。

表3-6　資源分配情況

（2）分析如下。

①Request（1，2，2，2）＜=Need2（2，3，5，6）；

②Request（1，2，2，2）＜=改成Available2（1，6，2，2）；

③系統先假定可為P2分配資源，并修改Available2，Allocation2和Need2向量，由此形成的資源變化情況如表3-7所示。

表3-7　資源變化情況

④再利用安全性算法檢查此時系統是否安全。此時（0，4，0，0）不能滿足任何進程的資源請求，因此，在進程P₂提出請求Request（1，2，2，2）后，系統不能將資源分配給它。