第3章　處理機調度與死鎖

3.1　復習筆記

一、處理機調度的層次和調度算法的目標

調度的實質是一種資源分配，處理機調度是對處理機資源進行分配。

1處理機調度的層次

（1）高級調度（作業調度）。

（2）中級調度（內存調度）。

（3）低級調度（進程調度）。

2處理機調度算法的目標

（1）資源利用率。

（2）公平性。

（3）平衡性。

（4）策略強制執行。

二、作業與進程的基本概念

1批處理系統中的作業

（1）作業和作業步

①作業

作業是用戶提交給系統的一項相對獨立的工作，它不僅包含了通常的程序和數據，而且還應配有一份作業說明書，系統根據該說明書來對程序的運行進行控制。

②作業步

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

（2）作業控制塊（JCB）

①定義

作業控制塊是作業在系統中存在的標志，其中保存了系統對作業進行管理和調度所需的全部信息。

②內容

JCB中包含的內容有：作業標識、用戶名稱、用戶賬號、作業類型（CPU繁忙型、I/O繁忙型、批量型、終端型）、作業狀態、調度信息（優先級、作業運行時間）、資源需求（預計運行時間、要求內存大小等）、資源使用情況等。

2進程調度的任務和方式

（1）進程調度的任務

①保存處理機的現場信息。

②按某種算法選取進程。

③把處理器分配給進程。

（2）進程調度方式

①非搶占方式。

②搶占方式。

【說明】“搶占”必須遵循一定的原則，主要原則有：優先權原則、短進程優先原則、時間片原則。

（3）不能進行進程調度的情況

①在處理中斷的過程中。

②進程在操作系統內核程序臨界區中。

③需要完全屏蔽中斷的原子操作過程中。

3調度的基本準則

（1）CPU利用率，其中計算公式為：

（2）系統吞吐量

（3）周轉時間，需掌握以下公式：

①周轉時間=作業完成時間-作業提交時間

②平均周轉時間=(作業1的周轉時間+…+作業n的周轉時間)/n

③帶權周轉時間=作業周轉時間/作業實際運行時間

（4）等待時間

（5）響應時間

三、典型調度算法

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

（1）FCFS算法既可用于作業調度，也可用于進程調度。

（2）每次選擇最早進入隊列的作業（或進程）調入內存（或分配處理機）。

（3）屬于不可剝奪算法。

（4）有利于CPU繁忙型作業，不利于I/O繁忙型作業；有利于長作業，不利于短作業。

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

（1）SJF算法既可用于作業調度，也可用于進程調度。

（2）每次選擇運行時間最短的作業（或進程）調入內存（或分配處理機）。

（3）對長作業不利，且未考慮作業的緊迫程度。

（4）SJF算法的平均等待時間、平均周轉時間最少。

3優先級調度算法

（1）既可用于作業調度，也可用于進程調度。

（2）每次選擇優先級最高的作業（或進程）調入內存（或分配處理機）。

（3）根據更高優先級進程是否可以搶占正在執行的進程，分類為：

①搶占式優先級調度算法。

②非搶占式優先級調度算法。

（4）根據進程的優先級是否可以改變，將進程的優先級分類為：

①靜態優先級。

②動態優先級。

4高響應比優先調度算法（HRRN）

（1）該算法主要用于作業調度。

（2）既考慮了作業的等待時間，又考慮了作業運行時間。

（3）響應比R_P的計算公式為：

由上式可以看出：

a．如果作業的等待時間相同，則要求服務的時間愈短，其優先權愈高，有利于短作業。

b．當要求服務的時間相同時，作業的優先權又決定于其等待時間，類似于FCFS算法。

c．長作業的優先級可以隨等待時間的增加而提高，當其等待時間足夠長時，也可獲得處理機，避免“饑餓”。

5時間片輪轉調度算法

（1）主要適用于分時系統。

（2）每次選擇就緒隊列中的第一個進程，但是只能運行一個時間片大小。

（3）時間片長短的選擇參考因素：系統的響應時間、就緒隊列中的進程數目、系統的處理能力。

6多級反饋隊列調度算法

（1）調度機制

①設置多個就緒隊列，并為每個隊列賦予不同的優先級。第一隊列優先級最高，其余隊列優先級依次降低。

②各個隊列中進程執行時間片大小不同。優先級越高的隊列中進程運行的時間片越小。

③除第n隊列外，每個隊列都采用FCFS算法，第n隊列中按RR方式運行。

（2）調度算法的優勢

①終端型用戶：短作業優先。

②短批處理作業用戶：周轉時間短。

③長批處理作業用戶：經過前面隊列的部分執行，不會出現“饑餓”。

四、死鎖

1死鎖的定義、必要條件和處理方法

（1）死鎖的定義

死鎖是指多個進程因競爭資源而造成的一種相互等待，若無外力作用，這些進程都將無法繼續運行。

（2）產生死鎖的原因

①競爭不可搶占性資源。

②進程推進順序不當。

（3）產生死鎖的必要條件（填空題重要考點）

產生死鎖必須同時具備下面四個必要條件，只要其中一個條件不成立，死鎖就不會發生。

①互斥條件。

②請求和保持條件。

③不可搶占條件。

④循環等待條件。

2死鎖的處理方法

（1）預防死鎖

預防死鎖的方法是通過破壞產生死鎖的四個必要條件中的一個或幾個，從而避免死鎖的產生。

【說明】互斥條件是非共享設備所必須的，不僅不能改變，還應加以保護。

①破壞“請求和保持”條件

方法：所有進程在開始運行之前，必須一次性地申請其在整個運行過程中所需的全部資源。

②破壞“不可搶占”條件

方法：當一個進程，提出新的資源請求而不能得到滿足時，它必須釋放已經保持的所有資源。

③破壞“循環等待”條件

方法：對系統所有資源類型進行線性排序，并賦予不同的序號。每個進程必須按序號遞增的順序請求資源。

（2）死鎖避免

①系統安全狀態

a．安全狀態是指系統能按某種進程推進順序為每個進程P_i分配其所需資源，直至滿足每個進程對資源的最大需求，使每個進程都可順利地完成。此時稱（P₁，P₂，…，P_n）為安全序列。

b．如果系統無法找到這樣一個安全序列，則稱系統處于不安全狀態。

②利用銀行家算法避免死鎖

（3）死鎖檢測

①資源分配圖

資源分配圖中的符號表示：

a．圓圈代表一個進程。

b．方框代表一類資源。

c．方框中的一個點代表一類資源中的一個資源。

d．由進程出發到資源的有向邊表示請求邊。

e．由資源出發到進程的有向邊表示分配邊。

【說明】資源分配圖中有環不一定存在死鎖，無環一定沒有死鎖。

②死鎖定理

狀態S為死鎖狀態的充分條件是當且僅當S狀態的資源分配圖不可完全簡化。

（4）死鎖解除

①資源剝奪法。

②終止（或撤消）進程法。

③進程回退法。