1、第三章 處理機調度與死鎖 第三章處理機調度與死鎖 3.1 處理機調度的層次與調度算法的目標處理機調度的層次與調度算法的目標3.2 作業與作業調度作業與作業調度3.3 進程調度進程調度3.4 實時調度實時調度 3.5 死鎖概述死鎖概述3.6 預防死鎖預防死鎖3.7 避免避免死鎖死鎖3.8 死鎖死鎖的檢測與解除的檢測與解除 第三章 處理機調度與死鎖 3.1 處理機調度的層次和調度算法的目標處理機調度的層次和調度算法的目標 3.1.1 處理機調度的層次處理機調度的層次1. 高級調度高級調度(High Level Scheduling) 又稱長程調度或作業調度，調度對象是作業。涉及兩個決定： 1) 接

2、納多少個作業 ； 2) 接納哪些作業。 l 在多道程序系統中，調度的實質是一種資源分配，處理機調度是對處理機資源進行分配。處理機調度算法是根據處理機分配策略所規定的處理機分配算法。第三章 處理機調度與死鎖 3.1.1 處理機調度的層次處理機調度的層次2. 低級調度低級調度(Low Level Scheduling) 又稱短程調度或進程調度，調度對象是進程。主要功能是根據算法，決定就緒隊列中的哪個進程應獲得處理機，并由分派程序將處理機分配給被選中的進程。3. 中級調度中級調度(Intermediate Scheduling) 又稱內存調度。主要目的是為了提高內存利用率和系統吞吐量。將那些暫時不能

3、運行的進程調至外存上去等待，稱為就緒駐外存狀態或掛起狀態；把外存上的又具備運行條件的就緒進程，重新調入內存，并修改其狀態為就緒狀態，掛在就緒隊列上等待進程調度。 第三章 處理機調度與死鎖 3.1.2 處理機調度算法的目標處理機調度算法的目標1. 處理機調度算法的共同目標處理機調度算法的共同目標(1) 資源利用率。為提高系統的資源利用率，應使系統中的處理機和其它所有資源都盡可能保持忙碌狀態。空閑等待時間有效工作時間有效工作時間的利用率CPUCPUCPUCPU(2) 公平性使諸進程都獲得合理的CPU時間，不會發生進程饑餓現象。(3) 平衡性 保持系統資源使用的平衡性。(4) 策略強制執行第三章 處

4、理機調度與死鎖 3.1.2 處理機調度算法的目標處理機調度算法的目標2. 批處理系統的目標批處理系統的目標(1) 平均周轉時間短 周轉時間，指從作業被提交給系統開始，到作業完成為止的這段時間間隔。包括四部分時間：作業在外存后備隊上等待調度的時間；進程在就緒隊列上等待進程調度的時間，進程在CPU上執行的時間，進程等待I/O操作完成的時間。(2) 系統吞吐量高 吞吐量，指在單位時間內系統所完成的作業數。(3) 處理機利用率高第三章 處理機調度與死鎖 3.1.2 處理機調度算法的目標處理機調度算法的目標3. 分時系統的目標分時系統的目標(1) 響應時間快 響應時間快是選擇分時系統中進程調度算法的重要

5、準則。響應時間，從用戶通過鍵盤提交一個請求開始，直到屏幕上顯示出處理結果為止的一段時間間隔。(2) 均衡性系統響應時間的快慢應與用戶所請求的復雜性相適應。第三章 處理機調度與死鎖 3.1.2 處理機調度算法的目標處理機調度算法的目標4. 實時系統的目標實時系統的目標(1) 截止時間的保證 截止時間：某任務必須開始執行的最遲時間，或必須完成的最遲時間。調度算法必須保證實時任務對截止時間的要求。(2) 可預測性第三章 處理機調度與死鎖 3.2 作業和作業調度作業和作業調度3.2.1 批處理系統中的作業批處理系統中的作業1. 作業和作業步作業和作業步在作業運行期間，每個作業都必須經過若干個相對獨立，

6、又相互關聯的順序加工步驟才能得到結果，每一個加工步驟稱為一個作業步。2. 作業控制塊（作業控制塊（Job Control Block, JCB）作業在系統中存在的標志，其中保存了系統對作業進行管理和調度所需的全部信息。第三章 處理機調度與死鎖 3.2.1 批處理系統中的作業批處理系統中的作業3. 作業運行的三個階段和三種狀態作業運行的三個階段和三種狀態（1）收容階段 用戶提交的作業輸入到硬盤上，再為該作業建立JCB，并把它放入作業后備隊列中。作業處于“后備狀態”。（2）運行階段作業調度選中作業后，為其分配必要的資源和建立進程，并放入就緒隊列。一個作業從第一次進入就緒狀態開始，直到它運行結束前，

7、處于“運行狀態”。 （3）完成階段 第三章 處理機調度與死鎖 3.2.3 先來先服務先來先服務(FCFS)和短作業優先和短作業優先(SJF)調度算法調度算法1. 先來先服務（先來先服務（first-come first-served,FCFS）調度算法）調度算法 最簡單的調度算法，既可用于作業調度，也可用于進程調度。當在作業調度中采用該算法時，系統將從后備隊列中選擇最先進入該隊列的作業，將它們調入內存；當在進程調度采用FCFS算法時，從就緒的進程隊列選擇最先進入的進程。第三章 處理機調度與死鎖 2. 短作業優先短作業優先(short job first, SJF)調度算法調度算法 SJF算法以

8、作業的長短計算優先級，作業越短，其優先級越高。3.2.3 先來先服務先來先服務(FCFS)和短作業優先和短作業優先(SJF)調度算法調度算法uSJF算法的缺點：(1) 必須預知作業的運行時間。(2) 對長作業非常不利，長作業的周轉時間會明顯地增長。(3) 在采用SJF算法時，人-機無法實現交互。(4) 該調度算法完全未考慮作業的緊迫程度，故不能保證緊迫性作業能得到及時處理。第三章 處理機調度與死鎖 3.2.4 優先級調度算法和高響應比優先調度算法優先級調度算法和高響應比優先調度算法1. 優先級調度算法優先級調度算法(priority-scheduling algorithm, PSA) PSA

9、基于作業的緊迫程度，由外部賦予作業相應的優先級，調度算法根據該優先級進行調度。PSA可作為作業調度算法，也可作為進程調度算法。第三章 處理機調度與死鎖 要求服務時間要求服務時間等待時間優先權優先權的變化規律可描述為： 由于等待時間與服務時間之和，就是系統對該作業的響應時間，故該優先權又相當于響應比RP。據此，又可表示為： 要求服務時間響應時間要求服務時間要求服務時間等待時間優先權2. 高響應比優先調度算法高響應比優先調度算法(Higher Response Ratio Next, HRRN)3.2.4 優先級調度算法和高響應比優先調度算法優先級調度算法和高響應比優先調度算法HRRN考慮了作業的

10、等待時間和作業運行時間。第三章 處理機調度與死鎖 3.3 進程調度進程調度3.3.1 進程調度的任務、機制和方式進程調度的任務、機制和方式1. 進程調度的任務進程調度的任務(1) 保存處理機的現場信息(2) 按某種算法選取進程(3) 把處理器分配給進程2. 進程調度機制進程調度機制 為了實現進程調度，應具有如下三個基本機制：(1)排隊器。將系統中所有的就緒進程按照一定的方式排成一個或多個隊列。第三章 處理機調度與死鎖 3.3.1 進程調度的任務、機制和方式進程調度的任務、機制和方式2. 進程調度機制進程調度機制(2) 分派器。從就緒隊列中取出由進程調度程序所選定的進程，然后進行從分派器到新選出

11、進程間的上下文切換，將處理機分配給該進程。 (3) 上下文切換機制。兩對上下文切換：操作系統將保存當前進程的上下文，而裝入分派程序的上下文，以便分派程序運行；移出分派程序的上下文，而把新選進程的CPU現場信息裝入到處理機的各個相應寄存器中。 第三章 處理機調度與死鎖 3進程調度方式進程調度方式 1) 非搶占方式(Nonpreemptive Mode)在采用這種調度方式時，一旦把處理機分配給某進程后，不管它要運行多長時間，都一直讓它運行下去，決不會因為時鐘中斷等原因而搶占正在運行進程的處理機，也不允許其它進程搶占已經分配給它的處理機。直至該進程完成，自愿釋放處理機，或發生某事件而被阻塞時，才再把

12、處理機分配給其他進程。 3.3.1 進程調度的任務、機制和方式進程調度的任務、機制和方式 自行分析：引起進程調度的原因。自行分析：引起進程調度的原因。第三章 處理機調度與死鎖 2) 搶占方式搶占方式(Preemptive Mode)允許調度程序根據某種原則去暫停某個正在執行的進程，將已分配給該進程的處理機重新分配給另一進程。搶占調度方式是基于一定原則的，主要有如下幾條： 3進程調度方式進程調度方式 優先權原則。允許優先權高的新到進程搶占當前進程的處理機。 短進程優先原則。允許新到的短進程短可以搶占當前較長進程的處理機。 時間片原則。各進程按時間片輪流運行，當一個時間片用完后，便停止該進程的執行

13、而重新進行調度。第三章 處理機調度與死鎖 3.3.2 輪轉調度算法輪轉調度算法1輪轉法的基本原理輪轉法的基本原理 基于時間片的輪轉(Round Robin, RR)調度算法。就緒隊列上的每個進程每次僅運行一個時間片。 系統將所有的就緒進程按FCFS策略排成一個就緒隊列,每次調度時，把CPU分配給隊首進程，并令其執行一個時間片。當執行的時間片用完時，調度程序便把處理機分配給就緒隊列中新的隊首進程，同時也讓它執行一個時間片。這樣就可以保證就緒隊列中的所有進程，在一給定的時間內，均能獲得一時間片的處理機執行時間。第三章 處理機調度與死鎖 3.3.2 輪轉調度算法輪轉調度算法2進程切換時機進程切換時機

14、 若一個時間片未用完，正在運行的進程便已經完成，則立即激活調度程序，將它從就緒隊列中刪除，再調度就緒隊列中隊首的進程運行，并啟動一個新的時間片。 在一個時間片用完時，計時器中斷處理程序被激活。3時間片大小的確定時間片大小的確定 時間片的大小對系統性能有很大的影響。可取的時間片大小是略大于一次典型的交互所需要的時間，使大多數交互式進程能在一個時間片內完成。第三章 處理機調度與死鎖 3.3.3 優先級調度算法優先級調度算法1. 優先級調度算法的類型優先級調度算法的類型(1) 非搶占式優先級調度算法(2) 搶占式優先級調度算法 把處理機分配給優先級最高的進程，使之執行。但在執行期間，只要出現了另一個

15、其優先級更高的進程，調度程序就將處理機分配給新到的優先級最高的進程。第三章 處理機調度與死鎖 3.3.3 優先級調度算法優先級調度算法2. 優先級的類型優先級的類型(1) 靜態優先級 靜態優先級是在創建進程時確定的，在進程的整個運行期間保持不變。確定優先級大小的依據有： 進程類型。通常系統進程的優先級高于一般用戶進程；進程對資源的需求。對資源要求少的進程應賦予較高的優先級；用戶要求。 (2) 動態優先級 在創建進程初賦予一個優先級，然后其值隨進程的推進或等待時間的增加而改變。第三章 處理機調度與死鎖 3.3.3 多隊列調度算法多隊列調度算法 該算法將系統中的進程就緒隊列從一個拆分為若干個，將不

16、同類型或性質的進程固定分配在不同的就緒隊列，不同的就緒隊列采用不同的調度算法，一個就緒隊列中的進程可以設置不同的優先級，不同的就緒隊列也可設置不同的優先級。第三章 處理機調度與死鎖 圖 3-5 多級反饋隊列調度算法 就緒隊列1就緒隊列2就緒隊列3就緒隊列nS1S2S3至CPU至CPU至CPU至CPU(時間片：S1S2S3)3.3.4 多級反饋隊列多級反饋隊列(multileved feedback queue)調度算法調度算法1. 調度機制調度機制第三章 處理機調度與死鎖 (1) 設置多個就緒隊列，并為各個隊列賦予不同的優先級。 第一個隊列的優先級最高，第二個隊列次之，其余各隊列的優先權逐個降

17、低。該算法賦予各個隊列中進程執行時間片的大小也各不相同。3.3.4 多級反饋隊列多級反饋隊列(multileved feedback queue)調度算法調度算法1. 調度機制調度機制第三章 處理機調度與死鎖 (2) 每個隊列都采用FCFS算法。當一個新進程進入內存后，首先將它放入第一隊列的末尾，按FCFS原則排隊等待調度。當輪到該進程執行時，如它能在該時間片內完成，便可準備撤離系統；否則，調度程序便將該進程轉入第二隊列的末尾，再同樣地按FCFS原則等待調度執行；如果它在第二隊列中運行一個時間片后仍未完成，再依次將它放入第三隊列，如此下去，當一個長進程從第一隊列依次降到第n隊列后，在第n隊列中

18、便采取按RR方式運行。3.3.4 多級反饋隊列多級反饋隊列(multileved feedback queue)調度算法調度算法1. 調度機制調度機制第三章 處理機調度與死鎖 (3) 按隊列優先級調度。僅當第一隊列空閑時，調度程序才調度第二隊列中的進程運行； 僅當第1(i-1) 隊列均空時，才會調度第i隊列中的進程運行。如果處理機正在第i隊列中為某進程服務時，又有新進程進入優先權較高的隊列，則此時新進程將搶占正在運行進程的處理機，即由調度程序把正在運行的進程放回到第i隊列的末尾，把處理機分配給新到的高優先權進程。 3.3.4 多級反饋隊列多級反饋隊列(multileved feedback q

19、ueue)調度算法調度算法1. 調度機制調度機制第三章 處理機調度與死鎖 3.3.6 基于公平原則的調度算法基于公平原則的調度算法1. 保證調度算法保證調度算法 向用戶所做出的保證并不是優先運行，而是明確的性能保證，該算法做到調度的公平性。在實施公平調度算法時系統須具有的功能：(1) 跟蹤計算每個進程自創建以來已經執行的處理時間。 (2) 計算每個進程應獲得的處理機時間。 (3) 計算進程獲得處理機時間的比率。 (4) 比較各進程獲得處理機時間的比率。 (5) 調度程序應選擇比率最小的進程將處理機分配給它，并讓該進程一直運行，直到超過最接近它的進程比率為止。第三章 處理機調度與死鎖 3.3.6

20、 基于公平原則的調度算法基于公平原則的調度算法2. 公平分享調度算法公平分享調度算法 在該調度算法中，調度的公平性主要是針對用戶而言，使所有用戶能獲得相同的處理機時間，或所要求的時間比例。第三章 處理機調度與死鎖 3.4 實實 時時 調調 度度3.4.1實現實時調度的基本條件實現實時調度的基本條件1提供必要的信息提供必要的信息 (1) 就緒時間。該任務成為就緒狀態的起始時間； (2) 開始截止時間和完成截止時間；(3) 處理時間； (4) 資源要求；(5) 優先級。如果某任務的開始截止時間 已經錯過，則為該任務賦予“絕對”優先級；如果開始截 止時間的推遲對任務的繼續運行無重大影響，則可為該 任

21、務賦予“相對”優先級。 第三章 處理機調度與死鎖 2系統處理能力強系統處理能力強 在實時系統中，通常都有著多個實時任務。假定系統中有m個周期性的硬實時任務，它們的處理時間可表示為Ci，周期時間表示為Pi，則在單處理機情況下，必須滿足下面的限制條件： 3.4.1實現實時調度的基本條件實現實時調度的基本條件11miiiPC提高系統處理能力的途徑：其一是增強單處理機系統的處理能力，以顯著地減少對每一個任務的處理時間；其二是采用多處理機系統。NPCmiii1第三章 處理機調度與死鎖 3.4.1實現實時調度的基本條件實現實時調度的基本條件3采用搶占式調度機制采用搶占式調度機制在含有硬實時任務的實時系統中

22、，廣泛采用搶占機制。當一個優先權更高的任務到達時，允許將當前任務暫時掛起，而令高優先權任務立即投入運行，這樣便可滿足該硬實時任務對截止時間的要求。4具有快速切換機制具有快速切換機制(1)對外部中斷的快速響應能力。具有快速硬件中斷機構(2) 快速的任務分派能力。適當地減小每個運行功能單位，以減少任務切換的時間開銷。第三章 處理機調度與死鎖 3.4.2實時調度算法的分類實時調度算法的分類1非搶占式調度算法非搶占式調度算法1) 非搶占式輪轉調度算法該算法常用于工業生產的群控系統中，由一臺計算機控制若干個相同的(或類似的)對象，為每一個被控對象建立一個實時任務，并將它們排成一個輪轉隊列。 2) 非搶占

23、式優先調度算法針對較為嚴格的實時任務，采用該算法為這些任務賦予較高的優先級。當這些實時任務到達時，把它們安排在就緒隊列的隊首，等待當前任務自我終止或運行完成后才能被調度執行。第三章 處理機調度與死鎖 3.4.2實時調度算法的分類實時調度算法的分類2搶占式調度算法搶占式調度算法1) 基于時鐘中斷的搶占式優先權調度算法 在某實時任務到達后，如果該任務的優先級高于當前任務的優先級，這時并不立即搶占當前任務的處理機，而是等到時鐘中斷到來時，調度程序才剝奪當前任務的執行，將處理機分配給新到的高優先權任務。第三章 處理機調度與死鎖 3.4.2實時調度算法的分類實時調度算法的分類2搶占式調度算法搶占式調度算

24、法2) 立即搶占(Immediate Preemption)的優先權調度算法在這種調度策略中，要求操作系統具有快速響應外部事件中斷的能力。一旦出現外部中斷，只要當前任務未處于臨界區，便立即剝奪當前任務的執行，把處理機分配給請求中斷的緊迫任務。第三章 處理機調度與死鎖 圖3-5 實時進程調度 (a) 非搶占式輪轉調度當前進程實時進程實時進程請求調度實時進程搶占當前進程并立即執行(d) 立即搶占的優先權調度調度時間進程 1進程 2實時進程要求調度進程 n實時進程調度實時進程運行(b) 非搶占式優先權調度當前進程實時進程實時進程請求調度當前進程運行完成調度時間當前進程實時進程請求調度時鐘中斷到來時調

25、度時間(c) 基于時鐘中斷搶占的優先權搶占調度調度時間實時進程第三章 處理機調度與死鎖 3.4.3最早截止時間優先最早截止時間優先EDF(Earliest Deadline First)算法算法該算法是根據任務的開始截止時間來確定任務的優先級。截止時間愈早，其優先級愈高。該算法要求在系統中保持一個實時任務就緒隊列，該隊列按各任務截止時間的早晚排序；當然，具有最早截止時間的任務排在隊列的最前面。調度程序在選擇任務時，總是選擇就緒隊列中的第一個任務，為之分配處理機，使之投入運行。最早截止時間優先算法既可用于搶占式調度，也可用于非搶占式調度方式中。 第三章 處理機調度與死鎖 圖 3-6EDF算法用于

26、非搶占調度的調度方式1342開始截止時間任務執行任務到達12 341342t3.4.3最早截止時間優先最早截止時間優先EDF(Earliest Deadline First)算法算法1. 非搶占式調度方式用于非周期實時任務第三章 處理機調度與死鎖 2. 搶占式調度方式用于周期實時任務搶占式調度方式用于周期實時任務A1B1A2B1A3 B2 A4B2A5B1A2A3B2A5A1B1B1A2B1A3B2A4B2A5 B2A1A2B2A3A4A5B1最后期限B2最后期限A1最后期限A2最后期限A3最后期限A4最后期限A5最后期限到達時間、執行時間和最后期限A1固定優先級調度固定優先級調度A2B1A3

27、A4A5，B2A5，B2A4A1(錯過)A2B1A3(錯過)A1A2B1(錯過)A3A4A5，B20102030405060708090100時間t/ms使用完成最后期限最早和最后期限調度(A有較高優先級)(B有較高優先級)圖3-7 EDF算法用于搶占調度方式第三章 處理機調度與死鎖 3.4.4 最低松弛度優先最低松弛度優先LLF(Least Laxity First)算法算法 該算法是根據任務緊急的程度，來確定任務的優先級。任務的緊急程度愈高，為該任務所賦予的優先級就愈高，以使之優先執行。 在實現該算法時要求系統中有一個按松弛度排序的實時任務就緒隊列，松弛度最低的任務排在隊列最前面，調度程序

28、總是選擇就緒隊列中的隊首任務執行。 該算法主要用于可搶占調度方式中。第三章 處理機調度與死鎖 A1A2A3A4A5A6A7A820406080100120140160B1B2B3t03.4.4 最低松弛度優先最低松弛度優先LLF(Least Laxity First)算法算法圖 3-8A和B任務每次必須完成的時間 u例：假如在一個實時系統中，有兩個周期性實時任務A和B，任務A要求每20ms執行一次，執行時間為10ms；任務B只要求每50ms執行一次，執行時間為25ms。第三章 處理機調度與死鎖 t1A1(10)10203040506080t0t10B1(20)t2t370A2(10)A3(10

29、)A4(10)t4t5t6t7t8B1(5)B2(15)B2(10)圖 3-9利用LLF算法進行調度的情況 3.4.4 最低松弛度優先最低松弛度優先LLF(Least Laxity First)算法算法 為保證不遺漏任何一次截止時間，應采用最低松弛度優先的搶占調度策略。 松弛度=必須完成時間-其本身的運行時間-當前時間第三章 處理機調度與死鎖 u調度算法總結調度算法總結1.1.先來閑服務算法（先來閑服務算法（FCFSFCFS）2.2.短作業優先（短作業優先（SJFSJF）3. 優先級調度算法（優先級調度算法（PSA）4.高響應比優先調度算法（高響應比優先調度算法（HRRN）5.時間片輪轉法（時

30、間片輪轉法（RR）6.多級隊列調度算法多級隊列調度算法7.多級反饋隊列調度算法多級反饋隊列調度算法第三章 處理機調度與死鎖 u問題分析問題分析1. 有一個內存中只能裝入兩道作業的批處理系統，作業調度采用短作業優先的調度算法，進程調度采用以優先數為基礎的搶占式調度算法。有下表所示的作業序列，表中所列的優先數是指進程調度的優先數，且優先數越小優先級越高。 作業數作業數 到達時間到達時間估計運行時間估計運行時間優先數優先數A BCD 10: 00 10: 20 10: 30 10: 50 40分分 30分分 50分分 20分分 5 3 4 6(1) 列出所有作業進入內存的時刻以及結束的時刻。(2)

31、計算作業的平均周轉時間。第三章 處理機調度與死鎖 u問題分析問題分析2. 對下面的5個非周期性實時任務，按最早開始截止時間優先調度算法應如何進行CPU調度？進程 到達時間執行時間開始截止時間A BCDE 10 20 40 50 60 20 20 20 20 20 110 20 50 90 70第三章 處理機調度與死鎖 u問題分析問題分析3. 若有3個周期性任務，任務A要求每20ms執行一次，執行時間為10ms；任務B要求每50ms執行一次，執行時間為15ms，應如何按最低松弛優先算法對它們進行CPU調度？第三章 處理機調度與死鎖 3.5死死 鎖鎖 概概 述述3.5.1 資源問題資源問題 系統中

32、有許多不同類型的資源，其中需要采用互斥方法訪問的、不可以被搶占的資源常常會引起死鎖。1. 可重用性資源和消耗性資源可重用性資源和消耗性資源2. 可搶占性資源和不可搶占性資源可搶占性資源和不可搶占性資源l可重用性資源，一種可供用戶重復使用多次的資源。其請求和釋放通常利用系統調用，系統大多數資源屬于可重用性資源。l消耗性資源，又稱臨時性資源。是在進程運行期間，由進程動態地創建和消耗。如進程間通信的消息。第三章 處理機調度與死鎖 3.5.2 計算機系統中的死鎖計算機系統中的死鎖 死鎖的起因源于多個進程對不可搶占資源或可消耗資源的爭奪。1. 競爭不可搶占性資源引起死鎖競爭不可搶占性資源引起死鎖 系統中

33、所擁有的不可搶占性資源不能滿足諸進程運行的需要，會使得進程在運行過程中，因爭奪這些資源而陷入僵局。例：兩進程P1和P2準備寫兩文件f1和f2. P1 P2 Open(f1, w) Open(f2, w)Open(f2, w) Open(f1, w)第三章 處理機調度與死鎖 R1R2P1P21. 競爭不可搶占性資源引起死鎖競爭不可搶占性資源引起死鎖例：兩進程P1和P2準備寫兩文件R1和R2. P1 P2 Open(R1, w) Open(R2, w)Open(R2, w) Open(R1, w)圖3-12共享文件時的死鎖情況 第三章 處理機調度與死鎖 2. 競爭可消耗資源引起死鎖競爭可消耗資源引

34、起死鎖3.5.2 計算機系統中的死鎖計算機系統中的死鎖S2P1S3P3S1P2 圖中S1、S2和S3是臨時性資源。進程P1產生消息S1，利用Send(P2, S1)原語將它發送給P2；又要求從P3接收消息S3；進程P2產生消息S2，利用Send(P3, S2)原語將它發送給P3，又需要接收進程P1所產生的消息S1；進程P3產生消息S3，又要求從進程P2接收其所產生的消息S2；P1： send(P2, S1)； receive(P3, S3)； P2： send(P3, S2)； receive(P1, S1)； P3： send(P1, S3)； receive(P2, S2)； 如果三個進程

35、間的消息通信如下：如果三個進程間的消息通信如下：P1： receive (P3, S3)； send(P2, S1)； P2： receive(P1, S1)； send(P3, S2)； P3： receive(P2, S2)； send(P1, S3)； 第三章 處理機調度與死鎖 3 3進程推進順序不當引起死鎖進程推進順序不當引起死鎖進程在運行過程中，對資源進行申請和釋放的順序是否合法，也是系統中是否會產生死鎖的一個重要因素。3.5.2 計算機系統中的死鎖計算機系統中的死鎖1) 進程推進順序合法進程推進順序合法P1：Request(R1)P1：Request(R2) P1：Release(

36、R1) P1：Release(R2) P2：Request(R2) P2：Request(R1) P2：Release(R2) P2：Release(R1)； 舉例：系統中只有一臺打印機R1和一臺磁帶機R2，供進程P1和P2共享.第三章 處理機調度與死鎖 圖3-14進程推進順序對死鎖的影響 P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1) P1Rel(R2)D3.5.2 計算機系統中的死鎖計算機系統中的死鎖若并發進程若并發進程P1和和P2按曲線按曲線所示的順序推進，它們所示的順序推進，它們將進入不安全區將進入不安全區

37、D內。內。第三章 處理機調度與死鎖 2) 進程推進順序非法進程推進順序非法若并發進程P1和P2按曲線所示的順序推進，它們將進入不安全區D內。此時P1保持了資源R1，P2保持了資源R2，系統處于不安全狀態。因為這時兩進程再向前推進，便可能發生死鎖。例如，當P1運行到P1：Request(R2)時，將因R2已被P2占用而阻塞；當P2運行到P2：Request(R1)時，也將因R1已被P1占用而阻塞，于是發生了進程死鎖。 3 3進程推進順序不當引起死鎖進程推進順序不當引起死鎖3.5.2 計算機系統中的死鎖計算機系統中的死鎖第三章 處理機調度與死鎖 3.5.3 死鎖的定義、必要條件和處理方法死鎖的定義

38、、必要條件和處理方法 如果一組進程中的每一個進程都在等待僅由該組進程中的其它進程才能引發的事件，則該組進程是死鎖的。2. 產生死鎖的必要條件產生死鎖的必要條件(1)互斥條件：指進程對所分配到的資源進行排它性使用，即在一段時間內某資源只由一個進程占用。如果此時還有其它進程請求該資源，則請求者只能等待，直至占有該資源的進程用畢釋放。1.死鎖（死鎖（Deadlock）的定義）的定義第三章 處理機調度與死鎖 (2) 請求和保持條件 指進程已經保持了至少一個資源，但又提出了新的資源請求，而該資源又已被其它進程占有，此時請求進程阻塞，但又對自己已獲得的其它資源保持不放。(3) 不可搶占條件 指進程已獲得的

39、資源，在未使用完之前，不能被剝奪，只能在使用完時由自己釋放。2. 產生死鎖的必要條件產生死鎖的必要條件(4) 循環等待條件 指在發生死鎖時，必然存在一個進程資源的環形鏈。3.5.3 死鎖的定義、必要條件和處理方法死鎖的定義、必要條件和處理方法第三章 處理機調度與死鎖 3. 處理死鎖的方法處理死鎖的方法3.5.3 死鎖的定義、必要條件和處理方法死鎖的定義、必要條件和處理方法(1) 預防死鎖。通過設置某些限制條件，破壞產生死鎖的四個必要條件中的一個或幾個條件。(2) 避免死鎖。在資源的動態分配過程中，用某種方法去防止系統進入不安全狀態，從而避免發生死鎖。(3) 檢測死鎖。通過系統所設置的檢測機構，

40、及時地檢測出死鎖的發生，并精確地確定與死鎖有關的進程和資源； 然后，采取適當措施，從系統中將已發生的死鎖清除掉。 (4) 解除死鎖，與檢測死鎖相配套。第三章 處理機調度與死鎖 3.6預預 防防 死死 鎖鎖3.6.1破壞破壞“請求和保持請求和保持”條件條件 系統保證：當一個進程在請求資源時，它不能持有不可搶占資源。可采用兩種協議：1 1第一種協議第一種協議系統規定所有進程在開始運行之前，都必須一次性地申請其在整個運行過程所需的全部資源。通過破壞產生死鎖的四個必要條件中的一個或幾個。第三章 處理機調度與死鎖 3.6.1摒棄摒棄“請求和保持請求和保持”條件條件2 2第二種協議第二種協議 允許一個進程

41、只獲得運行初期所需的資源后，便開始運行。進程運行過程中再逐步釋放已分配給自己的、且已用畢的餓全部資源，然后再請求新的所需資源。問題討論問題討論：有一個進程，它所要完成的任務是，先將數據從磁帶尚復制到磁盤文件上，然后對磁盤文件進行排序，最后把結果打印出來。第三章 處理機調度與死鎖 3.6.2破壞破壞“不可搶占不可搶占”條件條件在采用這種方法時系統規定，進程是逐個地提出對資源的要求的。當一個已經保持了某些資源的進程，再提出新的資源請求而不能立即得到滿足時，必須釋放它已經保持了的所有資源，待以后需要時再重新申請。 這意味著某一進程已經占有的資源，在運行過程中會被暫時地釋放掉，也可認為是被剝奪了，從而

42、摒棄了“不可搶占”條件。 第三章 處理機調度與死鎖 3.6.3破壞破壞“循環循環等待等待”條件條件系統將所有資源按類型進行線性排隊，并賦予不同的序號。所有進程對資源的請求必須嚴格按照：資源序號遞增的次序提出。例如：一個進程在開始時，可以請求某類資源Ri的單元。以后，當且僅當F(Rj)F(Ri)時，進程才可以請求資源Rj的單元。這樣，不可能再出現環路，破壞了“循環等待”條件。 在采用這種策略時，應如何來規定每種資源的序號十分重要。第三章 處理機調度與死鎖 3.7避免死鎖避免死鎖3.7.1系統安全狀態系統安全狀態1 1安全狀態安全狀態在資源動態分配過程中，防止系統進入不安全狀態。安全狀態安全狀態指

43、系統能按某種進程順序(P1,P2,Pn) 來為每個進程Pi分配其所需資源，直至滿足每個進程對資源的最大需求，使每個進程都可順利地完成。如果系統無法找到這樣一個安全序列，則稱系統處于不安全狀態不安全狀態。第三章 處理機調度與死鎖 2 2安全狀態舉例安全狀態舉例假定系統中有三個進程P1、P2和P3，共有12臺磁帶機。進程P1總共要求10臺磁帶機，P2和P3分別要求4臺和9臺。在T0時刻，資源分配如下表所示： 進 程 最 大 需 求 已 分 配 可 用 P1 10 5 3 P2 4 2 P3 9 2 3.7.1系統安全狀態系統安全狀態u在T0時刻，存在一個安全序列，因此是安全的。u若在T0時刻以后P

44、3又請求1個資源，系統將資源分配給P3，則進入不安全狀態。第三章 處理機調度與死鎖 3.7.2利用銀行家算法避免死鎖利用銀行家算法避免死鎖 銀行家算法是一種最有代表性的避免死鎖的算法，該算法原本為銀行系統設計的，以確保銀行在發放現金貸款時，不會發生不能滿足所有客戶需求的情況。在避免死鎖方法中允許進程動態地申請資源，但系統在進行資源分配之前，應先計算此次分配資源的安全性，若分配不會導致系統進入不安全狀態，則分配，否則等待。第三章 處理機調度與死鎖 3.7.2利用銀行家算法避免死鎖利用銀行家算法避免死鎖1 1銀行家算法中的數據結構銀行家算法中的數據結構 (1)可利用資源向量Available，是一

45、個含有m個元素的數組。其中每一個元素代表一類可利用的資源數目，其數值隨該類資源的分配和回收而動態地改變。如Availablej=K.(3) 分配矩陣Allocation，nm的矩陣。如果Allocationi,j=K，則表示進程i當前已分得R j類資源的數目為K。(4) 需求矩陣Need，nm的矩陣。如果Needi,j=K，則表示進程i還需要R j類資源K個，方能完成其任務。(2)最大需求矩陣Max，一個nm的矩陣。如果Maxi,j=K，則表示進程i需要Rj類資源的最大數目為K。 第三章 處理機調度與死鎖 2銀行家算法銀行家算法設Request i是進程Pi的請求向量。當P i發出資源請求后，

46、系統按下述步驟進行檢查：(3) 系統試探著把資源分配給進程Pi，并修改： Availablej= Availablej-Request ij； Allocationi,j=Allocationi,j+Request ij；Needi,j=Needi,j-Request ij； (4) 系統執行安全性算法，檢查此次資源分配后系統是否處于安全狀態。(1) 如果Request ijNeedi,j，轉向步驟(2)；否則認為出錯。(2) 如果RequestijAvailablej，轉向步驟(3)；否則，Pi須等待。 3.7.2利用銀行家算法避免死鎖利用銀行家算法避免死鎖第三章 處理機調度與死鎖 3 3安

47、全性算法安全性算法3.7.2利用銀行家算法避免死鎖利用銀行家算法避免死鎖(2)(2)從進程集合中找到一個能滿足下述條件的進程：從進程集合中找到一個能滿足下述條件的進程： Finishi=false； Needi,jWorkj； 若找到，執行步驟若找到，執行步驟(3)(3) 否則，執行步驟否則，執行步驟(4)(4)。(1)(1)設置兩個向量：工作向量設置兩個向量：工作向量Work，Work=Available; Finish，它表示系統是否有足夠的資源分配給進程，使之運行完成。它表示系統是否有足夠的資源分配給進程，使之運行完成。(3)(3)當進程當進程Pi獲得資源，可順利執行，直至完成，并釋放出

48、分配給它獲得資源，可順利執行，直至完成，并釋放出分配給它 的資源，故應執行：的資源，故應執行：Workj=Workj+Allocationi,j； Finishi=true； go to step 2； (4)(4)如果所有進程的如果所有進程的Finishi=true都滿足，則表示系統處于安全狀態；都滿足，則表示系統處于安全狀態； 否則，系統處于不安全狀態。否則，系統處于不安全狀態。 第三章 處理機調度與死鎖 4銀行家算法之例銀行家算法之例假定系統中有五個進程P0,P1,P2,P3,P4和三類資源A,B,C，各資源的數量分別為10、5、7，在T0時刻的資源分配情況如圖。 3.7.2利用銀行家算

49、法避免死鎖利用銀行家算法避免死鎖Max Allocation Need Available 資源 情況 進 程 A B C A B C A B C A B C P0 7 5 3 0 1 0 7 4 3 3 3 2 (2 3 0) P1 3 2 2 2 0 0 1 2 2 (3 0 2) (0 2 0) P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 圖3-15 T0時刻的資源分配表 第三章 處理機調度與死鎖 (1) T0時刻的安全性：利用安全性算法對T0時刻的資源分配情況進行分析可知，在T0時刻存在著一個安全序列P1

50、，P3，P4，P2，P0，故系統是安全的。 圖3-16T0時刻的安全序列 Work Need Allocation Work+Allocation 資源 情況 進 程 A B C A B C A B C A B C Finish P1 3 3 2 1 2 2 2 0 0 5 3 2 true P3 5 3 2 0 1 1 2 1 1 7 4 3 true P4 7 4 3 4 3 1 0 0 2 7 4 5 true P2 7 4 5 6 0 0 3 0 2 10 4 7 true P0 10 4 7 7 4 3 0 1 0 10 5 7 true 4銀行家算法之例銀行家算法之例第三章 處理機

51、調度與死鎖 再利用安全性算法檢查此時系統是否安全。如圖3-17所示。 圖3-17P1申請資源時的安全性檢查 Work Need Allocation Work+Allocation 資源 情況 進 程 A B C A B C A B C A B C Finish P1 2 3 0 0 2 0 3 0 2 5 3 2 true P3 5 3 2 0 1 1 2 1 1 7 4 3 true P4 7 4 3 4 3 1 0 0 2 7 4 5 true P0 7 4 5 7 4 3 0 1 0 7 5 5 true P2 7 5 5 6 0 0 3 0 2 10 5 7 true 4銀行家算法之

52、例銀行家算法之例(2) P1 請求資源： P1 發出請求向量Request1(1,0,2)，系統按銀行家算法進行檢查： Request1(1,0,2) Need1(1,2,2); Request1(1,0,2) Available1(3,3,2); 系統先假定可為P1分配資源，并修改Available, Allocation1和Need1向量。第三章 處理機調度與死鎖 (3)P4請求資源：P4發出請求向量Request4(3,3,0)，系統按銀行家算法進行檢查： Request4(3,3,0)Need4(4,3,1)； Request4(3,3,0)Available(2,3,0)，讓P4等待

53、。 (4)P0請求資源：P0發出請求向量Requst0(0,2,0)，系統按銀行家算法進行檢查： Request0(0,2,0)Need0(7,4,3)； Request0(0,2,0)Available(2,3,0)；系統暫時先假定可為P0分配資源，并修改有關數據，如圖4銀行家算法之例銀行家算法之例Allocation Need Available 資源 情況 進 程 A B C A B C A B C P0 0 3 0 7 3 2 2 1 0 P1 3 0 2 0 2 0 P2 3 0 2 6 0 0 P3 2 1 1 0 1 1 P4 0 0 2 4 3 1 第三章 處理機調度與死鎖 (5)進行安全性檢查：可用資源Available(2,1,0)已不能滿足任何進程的需要，故系統進入不安全狀態，此時系統不分配資源。思考：思考：如果在銀行家算法中，把P0發出的請求向量改為Request0(0,1,0)，系統是否能將資源分配給它？4銀行