操作系統講義第三章

第三章處理機調度與死鎖2023/2/31操作系統講義主要內容

3.1處理機調度的層次

3.2調度隊列模型和調度準則

3.3幾種調度算法

3.4實時調度

3.5產生死鎖的原因和必要條件

3.6預防死鎖的方法

3.7

死鎖的檢測和解除2023/2/32第二章進程管理3.1處理機調度的層次作業的基本概念1.高級調度（HighLevelScheduling）主要功能：根據某種算法，把外存中把處于后備隊列中的那些作業調入內存，當作業完成時做善后處理。

作業（Job）：包含通常的程序和數據，并且配有作業說明書；作業步（JobStep）：“編譯”

->“連接裝配”->“運行”；作業流：若干個作業在系統外存形成的輸入流。

作業控制塊JCB（JobControlBlock）通常包含：作業標識、用戶名稱、用戶賬戶、作業類型（CPU繁忙，I/O繁忙，批量型，終端型）、作業狀態、調度信息（優先級，作業運行時間）、資源需求（運行時間，內存，I/O類型數量）、進入系統時間、開始處理時間、作業完成時間、作業退出時間、資源使用情況。2023/2/33第二章進程管理3.1處理機調度的層次1.高級調度（HighLevelScheduling）作業調度：是根據作業控制塊中的信息，審查系統能否滿足用戶作業的資源需求，以及按照一定的算法，從外存后備隊列中選取某些作業調入內存，為它們創建進程、分配必要的資源，然后將進程插入就緒隊列，準備執行。目的：提高內存利用率和系統吞吐量，使那些暫時不能運行的進程不再占用內存，把它們調至外存（存儲管理中的對換功能）。

1）接收多少個作業到內存：取決于多道程序度

2）接收哪些作業：取決于調度算法最簡單：先來先服務調度算法最常用：短作業優先調度算法較常用：優先級調度算法比較好：響應比高者優先調度算法2.中級調度（IntermediateLevelScheduling）2023/2/34第二章進程管理3.1處理機調度的層次3.低級調度（LowLevelScheduling）它所調度的對象是進程（或內核級線程），當CPU需要重新分配時，利用一定的算法把它分配給進程，它是最基本的調度。進程調度的功能

（1）保存處理機的現場信息；（2）按照某種算法選擇進程（如優先數算法，輪轉算法）

（3）把處理器分配給進程。進程調度的三個基本機制（1）排隊器：事先將系統所有就緒進程排成一個或多個隊列，方便調度程序最快找到它；（2）分派器（分派程序）：把進程調度程序選定的進程從就緒隊列移出，切換上下文，然后把CPU分配給它；（3）上下文切換機制：保存當前程序的上下文，裝入分派程序的上下文；移出分派程序，裝入新選進程的CPU信息；2023/2/35第二章進程管理3.1處理機調度的層次進程調度方式

3.低級調度（LowLevelScheduling）非搶占方式：一旦處理機分配給某個進程，不管它要運行多長時間，都讓它一直運行下去，決不會因為其它原因而搶占正在運行進程的處理機。這種方式下引起進程調度的因素包括：執行完畢或者發生某事件不能再執行執行進程提出I/O請求而暫停執行在進程通信或者同步過程中執行了某種原語操作，如P，Block等優點：實現簡單，系統開銷小，適用于大多數批處理系統；缺點：難以滿足緊急任務要求，可能造成難以預料的后果。2023/2/36第二章進程管理3.1處理機調度的層次進程調度方式

3.低級調度（LowLevelScheduling）搶占方式：允許調度程序根據某種原則去暫停某個正在執行的進程，這些原則主要包括：優先權原則：優先權高的進程可以搶占當前優先權低的進程的CPU；短作業（進程）優先原則：短作業（進程）可以搶占當前較長作業（進程的）CPU；時間片原則：時間片輪轉；優點：防止一個長進程長時間占用處理機，公平服務，適合實時任務的需求；缺點：需要付出較大的開銷。2023/2/37第二章進程管理3.2

調度隊列模型和調度準則僅有進程調度的調度隊列模型通常在分時系統中只設置進程調度，每個用戶建立一個進程，系統利用堆棧、樹或者鏈表來管理就緒進程隊列，就緒進程以FIFO隊列形式組織。

1.調度隊列模型進程執行時可能出現的三種情況：在給定時間片完成，釋放處理機進入完成狀態；本次時間片內未完成，放入就緒隊列尾部；因為某事件被阻塞，放入阻塞隊列。就緒隊列CPU阻塞隊列交互用戶時間片完進程調度等待事件進程完成事件出現2023/2/38第二章進程管理3.2

調度隊列模型和調度準則具有高級和低級調度的調度隊列模型在批處理系統中，作業調度按照一定的算法從外存的后備隊列選擇一批作業調入內存，建立進程，送入就緒隊列，然后按照一定的進程調度算法選擇進程，分配CPU。

1.調度隊列模型就緒隊列CPU阻塞隊列作業調度時間片完進程調度等待事件1進程完成事件1出現隊列后備阻塞隊列阻塞隊列等待事件2等待事件n事件2出現事件n出現……隊……2023/2/39第二章進程管理3.2

調度隊列模型和調度準則

1.調度隊列模型具有高級和低級調度的調度隊列模型的特點：（1）采用優先權就緒隊列，隊首進程優先權最高，或者采用無序鏈表方式；（2）設置多個阻塞隊列，每個隊列對應于某一種進程阻塞事件；2023/2/310第二章進程管理3.2

調度隊列模型和調度準則同時具有三級調度的調度隊列模型可把進程的就緒狀態分成內存就緒和外存就緒，類似地，阻塞狀態也可進一步分成內存阻塞和外存阻塞，調出操作可使進程狀態由內存就緒轉為外存就緒，內存阻塞轉為外存阻塞；中級調度可使外存就緒轉為內存就緒。

1.調度隊列模型就緒隊列CPU緒掛起隊列就作業調度時間片完進程調度進程完成事件出現隊列后備塞掛隊隊列阻阻塞隊列等待事件起批量作業掛起事件出現中級調度2023/2/311第二章進程管理3.2

調度隊列模型和調度準則面向用戶的準則

（1）周轉時間短（批處理系統）

平均周轉時間T的計算如下：平均帶權周轉時間W的計算如下：

（2）響應時間快（分時系統）：是指從用戶通過鍵盤提交一個請求開始，直到系統首次響應為止的時間必須快；

（3）截止時間的保證（實時系統）：是指某任務必須開始執行的最遲時間，或必須完成的最遲時間必須有保證；

（4）優先權準則：遵循優先權準則讓某些緊急的作業得到及時處理。2.選擇調度方式和算法的若干準則2023/2/312第二章進程管理3.2

調度隊列模型和調度準則面向系統的準則

2.選擇調度方式和算法的若干準則（1）系統吞吐量高：這個是評價批處理系統性能的另一個重要指標，因此是選擇批處理作業調度的重要準則。吞吐量是指單位時間內系統完成的作業數，它直接和作業的平均長度有關；（2）處理機利用率好：CPU價格昂貴，利用率成為衡量系統性能的重要指標；（3）各類資源的平衡利用：不僅要使處理機利用率高，還要有效地利用其它各類資源，如內存、外存和I/O設備，適當的調度方式和算法可以使系統中的各類資源處于忙碌狀態。2023/2/313第二章進程管理3.3

調度算法是一種最簡單的調度算法，適用于作業調度和進程調度，每次調度都是從后備隊列中選擇一個或者多個最先進入該隊列的作業，將它們調入內存，分配資源，創建進程，然后放入就緒隊列。

1.先來先服務調度算法FCFS（FirstComeFirstService）FCFS算法比較有利于長作業（進程），不利于短作業（進程）進程名到達時間服務時間開始執行時間完成時間周轉時間帶權周轉時間A010111B110011011001C21101102100100D31001022021991.992023/2/314第二章進程管理3.3

調度算法是指對短作業或者短進程優先調度的算法，適用于作業調度和進程調度，SJF算法就是從后備隊列中選擇一個運行時間最短的作業，然后把它們調入內存運行。

2.短作業優先調度算法SJF（ShortJobFirst）SJF的優點：能有效地降低作業的平均等待時間，提高系統吞吐量；進程名到達時間服務時間開始執行時間完成時間周轉時間帶權周轉時間A030331B145982C223531.5D35914112.2SJF的缺點：1）對長作業不利；2）未考慮作業的緊迫度；3）用戶估計執行時間的不準確性。2023/2/315第二章進程管理3.3

調度算法

3.FCFS和SJF的性能比較算法進程名ABCDE平均到達時間01234服務時間43524FCFS完成時間47121418周轉時間461011149帶權周轉時間1225.53.52.8SJF完成時間4918613周轉時間4816398帶權周轉時間12.673.21.52.252.12023/2/316第二章進程管理3.3

調度算法是為了照顧緊迫型作業，使之在進入系統后便獲得優先處理，該算法會把處理機分配給優先級最高的作業（或者進程）。1）非搶占式優先權調度算法，適用于批處理系統或實時性要求不高的系統；

2）搶占式優先權調度算法，能更好地滿足緊迫作業，適合于嚴格的實時系統或者對性能要求較高的批處理和分時系統中。

4.高優先權優先調度算法（PriorityJobFirst）2023/2/317第二章進程管理3.3

調度算法

4.高優先權優先調度算法（PriorityJobFirst）優先權的類型靜態優先權：創建進程時確定，在整個運行期間保持不變；進程類型，系統進程要比用戶進程優先級高；進程對資源的要求，要求少的優先級高；用戶要求，用戶進程的緊迫程度。優點：簡單易行，系統開銷小缺點：不夠精確，可能使優先權低的作業（進程）長期得不到調度動態優先權：創建時賦予，可以隨著進程的推進或隨其等待時間的增加而改變，以便獲得更好的調度性能。優點：使調度更加公平，調度性能高缺點：系統開銷稍大2023/2/318第二章進程管理3.3

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

每個作業的優先級動態計算，作業的優先級隨等待時間的增加而不斷提高。

4.高優先權優先調度算法（PriorityJobFirst）結論：如果作業等待時間相同，要求服務時間越短，優先級越高，該算法利于短作業；如果要求服務時間相同，那么等待時間越長，優先權越高，它實現的是先來先服務；對于長作業，作業的優先級隨著等待時間的增加而提高，如果等待時間足夠長也可以獲得處理機。優點：既照顧了短作業，又考慮了作業的先后順序，使長作業也可以得到服務；缺點：但優先級的計算增加了系統的開銷。響應比RP=等待時間+要求服務時間要求服務時間=響應時間要求服務時間2023/2/319第二章進程管理3.3

調度算法基本原理系統將所有就緒進程按照先來先服務的原則排成一個隊列，每次調度把CPU分配給隊首進程，并令其執行一個時間片，當執行時間片用完，調度程序停止其執行，并把它送到隊列尾部。

5.基于時間片的輪轉調度算法（RoundRobin）時間片大小如果太小利于短作業，但是會頻繁中斷，進程上下文切換，增加系統開銷；如果太大則每個進程都能在時間片內完成，則退化為FCFS算法，無法滿足交互式用戶的需求。2023/2/320第二章進程管理3.3

調度算法

5.基于時間片的輪轉調度算法（RoundRobin）(a)q=1(b)q=4123456789101112131415161718ABACBDAECBDAECABCDEECECC2023/2/321第二章進程管理3.3

調度算法——隊列（q=1）時間隊列狀態時間隊列狀態0A10DAECB完成1BA11AECD完成2ACB12ECA完成3CBDA13CE4BDAEC14EC5DAECB15CE6AECBD16EC7ECBDA17CE完成8CBDAE18C完成9BDAEC2023/2/322第二章進程管理3.3

調度算法——隊列（q=4）時間隊列狀態0A4BCDEA完成7CDEB完成11DEC13ECD完成17CE完成18C完成2023/2/323第二章進程管理3.3

調度算法

5.時間片輪轉法RR算法進程名ABCDE平均到達時間01234服務時間43524RRq=1完成時間1210181117周轉時間1291681311.6帶權周轉時間333.243.253.29RRq=4完成時間47181317周轉時間461610139.8帶權周轉時間123.253.252.892023/2/324第二章進程管理3.3

調度算法調度算法的實施過程設置多個就緒隊列，賦予不同的優先級，各個隊列優先級遞減，時間片遞增；新進程放入第一個隊列尾部，FCFS原則排隊調度，時間片內完成則撤離系統，如果沒完則轉入下個隊列尾部，以此類推，在第n個隊列采取時間片輪轉調度；第一隊列空閑，調度第二隊列，以此類推，新進程如果優先級高，可搶占處理機。

6.多級反饋隊列調度算法（RoundRobinWithMultipleFeedback）2023/2/325第二章進程管理3.3

調度算法

6.多級反饋隊列調度算法（RoundRobinWithMultipleFeedback）算法的性能終端型作業用戶，大多屬于交互型作業，作業小；短批處理作業用戶，周轉時間短；長批處理用戶，不用擔心作業長期得不到處理。就緒隊列1就緒隊列2就緒隊列3就緒隊列4至CPU至CPU至CPU至CPUS1S2S3（時間片：S1<S2<

S3）新進程2023/2/326第二章進程管理3.4

實時調度提供必要的信息就緒時間，任務就緒的起始時間；開始截止時間和完成截止時間；處理時間，一個任務從開始執行直至完成所需的時間；資源要求，任務執行的時候需要的一組資源；優先級，對緊迫任務設置“絕對”優先級，松弛任務設置“相對”優先級。

1.實現實時調度的基本條件2023/2/327第二章進程管理3.4

實時調度

1.實現實時調度的基本條件具有快速切換機制對外部中斷的快速響應能力；快速的任務分派能力。系統處理能力強采用搶占式調度機制采用單處理機系統，增強處理能力，減少每個任務處理時間；采用多處理機調度單處理機實時調度條件：2023/2/328第二章進程管理3.4

實時調度非搶占式調度算法非搶占式輪轉調度算法；非搶占式優先級調度算法。搶占式調度算法基于時鐘中斷的搶占式優先權調度算法立即搶占的優先權調度算法

2.實時調度算法分類最早截止時間優先EDF（EarliestDeadlineFirst）算法

3.常用的幾種實時調度算法最低松弛度優先級LLF（LeastLaxityFirst）算法

任務的松弛度=必須完成時間-其本身運行時間-當前時間

松弛度=0表示該任務必須馬上執行，否則會造成嚴重后果。2023/2/329第二章進程管理3.5

產生死鎖的原因和必要條件競爭資源：多個進程共享資源，資源數目不足所引起進程對資源的競爭；可剝奪資源和非剝奪性資源競爭非剝奪性資源競爭臨時性資源

1.產生死鎖的原因死鎖（Deadlock）：是指多個進程在運行過程中因爭奪資源而造成的一種僵局（DeadlyEmbrace），當進程出現這種僵持狀態時，若無外力作用，它們將無法再向前推進。2023/2/330第二章進程管理3.5

產生死鎖的原因和必要條件

1.產生死鎖的原因進程推進順序非法：請求和釋放資源順序不當。1）進程推進順序合法2）進程推進順序非法P1：Request(R1);Request(R2);P1：Release(R1);Release(R2);P2：Request(R1);Request(R2);P2：Release(R1);Release(R2);P1：Request(R1);P2：Request(R2);P1：Request(R2);P2：Request(R1);P1P2R1R22023/2/331第二章進程管理3.5

產生死鎖的原因和必要條件（1）互斥條件，一段時間內某資源只能由一個進程占用；（2）請求和保持條件，部分分配資源；（3）不剝奪條件，進程已獲得資源不能被剝奪，直至使用完畢；（4）環路等待條件，發生死鎖時必然存在進程-資源的環形鏈。

2.產生死鎖的必要條件（1）預防死鎖：通過設置某些限制條件，去破壞產生死鎖的四個必要條件中的一個或者幾個，預防死鎖的發生；（2）避免死鎖：在資源的動態分配過程中，用某種方法去防止系統進入不安全狀態，從而避免發生死鎖；（3）檢測死鎖：通過系統所設置的檢測機制，及時地檢測出死鎖的發生，并精確地確定與死鎖有關的進程和資源；（4）解除死鎖：與死鎖檢測配合，通過撤銷和掛起一些進程，以便回收一些資源，再將這些資源分配給處于阻塞狀態的進程，使之就緒，以繼續運行。

3.處理死鎖的基本方法2023/2/332第二章進程管理3.6

預防死鎖的方法（1）摒棄“請求和保持”條件，要么全部分配，要么一個也不分配；（2）摒棄“不剝奪”條件，資源在進程運行過程中可被暫時釋放；（3）摒棄“環路等待”條件，進程對資源的請求按照某種順序依次進行。

1.預防死鎖安全狀態是指系統能按某種進程順序（P1，P2，…，Pn），來為每個進程Pi分配其所需資源，直至滿足每個進程對資源的最大需求，使每個進程都順利執行。安全狀態實例:假設系統中有三個進程P1，P2，P3，共12臺磁帶機。2.系統安全狀態進程最大需求已分配可用P11053P242P3922023/2/333第二章進程管理3.6

預防死鎖的方法數據結構

3.銀行家算法（1）可利用資源向量Available（m個元素的數組），其中Available[j]=k，表示系統中Rj類資源有k個。（2）最大需求矩陣Max（n×m）的矩陣，Max[i,j]=k，表示進程Pi需要Rj類資源的最大數目是k個。（3）分配矩陣Allocation（n×m）的矩陣，Allocation[i,j]=k，表示Pi已經分得Rj類資源的數目是k個。（4）需求矩陣Need（n×m）的矩陣，Need[i,j]=k，表示Pi還需要Rj類資源的數目是k個。上述關系：Need[i,j]=Max[i,j]-Allocation[i,j]；2023/2/334第二章進程管理3.6

預防死鎖的方法算法描述

3.銀行家算法假設Requesti

是Pi的請求向量，Requesti[j]=k表示Pi請求k個Rj類資源，Pi申請后，系統進行檢查：（1）如果Requesti[j]

≤Need

[i,j]

，則轉（2），否則出錯（需要資源超過它宣布的最大值）。（2）如果Requesti[j]

≤Available

[j]

，則轉（3），否則尚無足夠的資源，Pi必須等待。（3）系統為Pi分配資源（試探性的分配）：

Available[j]:=Available[j]-Requesti[j]

;Allocation[i,j]:=Allocation[i,j]+Requesti[j];Need[i,j]:=Need[i,j]-Requesti[j];（4）執行安全性算法，若安全則分配（為Pi），否則不分配，令Pi等待。2023/2/335第二章進程管理3.6

預防死鎖的方法安全性算法

3.銀行家算法（1）設置兩個向量：工作向量Work，表示系統可提供給進程繼續運行所需的各類資源數目，含有m個元素，初始work:=Available；向量Finish，表示系統是否有足夠的資源分配給進程，使之運行完成，初始時Finish:=false，有足夠資源分配時，Finish:=true；（2）在進程集合中找到一個能滿足下述條件的進程：

a）Finish[i]=false;b）Need[i,j]≤Work[j]；如果找到則轉（3），否則轉（4）；（3）進程Pi獲得資源可順利完成，并釋放資源，則執行

Work[j]:=Work[j]+Allocation[i,j];Finish[i]:=true;轉（2）；（4）如果所有進程的Finish[i]=true都滿足，表示系統處于安全狀態，否則系統進入不安全狀態。2023/2/336第二章進程管理3.6

預防死鎖的方法假設系統中有五個進程{P0,P1,P2,P3,P4}和三類資源{A,B,C}，各種資源的數量分別為10、5、7，在T0時刻的資源分配情況下表：

4.銀行家算法的實例進程/資源MaxAllocationNeedAvailableABCABCABCABCP0P1P2P3P4753322902222433010200(302)302211002743122(020)600011431332(230)2023/2/337第二章進程管理3.6

預防死鎖的方法

4.銀行家算法的實例進程/資源WorkNeedAllocationWork+AllocationFinishABCABCABCABCP1P3P4P2P0332532743745104712201143160074320021100230201053274374510471057truetruetruetruetrue(1)T0時刻的安全性：存在安全序列{P1,P3,P4,P2,P0}。2023/2/338第二章進程管理3.6

預防死鎖的方法

4.銀行家算法的實例進程/資源WorkNeedAllocationWork+AllocationFinishABCABCABCABCP1P3P4P0P2230532743745755020011431743600302211002010302

5327437457551057truetruetruetruetrue(2)P1請求資源，發出請求向量Request1(1,0,2)，進行檢查Request1(1,0,2)≤

Need1(1,2,2);Request1(1,0,2)≤

Available1(3,3,2);存在安全序列{P1,P3,P4,P0,P2}。(3)P4請求資源，發出請求向量Request4(3,3,0)，檢查Request4(3,3,0)≤

Need4(4,3,1);Request4(3,3,0)≤

Available4(2,3,0);讓P4等待。2023/2/339第二章進程管理3.6

預防死鎖的方法

4.銀行家算法的實例進程/資源AllocationNeedAvailableABCABCABCP0P1P2P3P4030302302211002723020600011431210(4)P0請求資源，發出請求向量Request0(0,2,0)，進行檢查Request0(0,2,0)≤

Need0(7,4,3);Request0(0,2,0)≤

Available0(2,3,0);假定為P0分配資源，修改相關數據如下。(5)進行安全性檢查，Available(2,1,0)已不能滿足任何進程需要，故系統進入不安全狀態。2023/2/340第二章進程管理3.7

死鎖的檢測與解除資源分配圖（ResourceAllocationGraph）RAG是由一組結點N和一組邊E組成的一個對偶RAG=（N，E），對它的約定如下：

（1）P={p1,p2,…,pn}R={r1,r2,…,rn}P和R是兩個互斥的子集，N=P∪R

（2）e∈E，它連接P中的一個結點和R中的一個結點

e=（pi,rj)–資源請求邊（pi指向rj

）表示pi請求一個單位的rj

；

e=（rj,pi)–資源分配邊（rj

指向pi

）表示pi分配到一個單位的rj

；

1.死鎖的檢測P1P2R1R22023/2/341第二章進程管理3.7

死鎖的檢測與解除資源分配圖的簡化

（1）從RAG中找出既不阻塞又不是孤點的進程Pi，消去由Pi出發的和指向Pi的所有邊（請求邊和分配邊），這等價于Pi獲得它所需的資源，不斷向前推進，一直運行完畢，釋放出它所占有的全部資源。（2）進程Pi所釋放的資源可以喚醒某些阻塞于該資源的進程Pj，消去Pj所有的邊，使之成為孤點。（3）如此下去，最后，若消去圖中所有的邊，則稱該圖是可完全化簡的。（4）若有向圖不能通過任何過程予以簡化，則稱該圖是不可完全簡化的。

1.死鎖的檢測死鎖定理

引理：一個給定的進程資源分配圖，對所有的簡化順序，將導致相同的結果（再也不能簡化）。