处理机调度与死锁课件2

處理機調度與死鎖

高級調度：又稱為作業調度或長程調度。用於決定把後備佇列中的哪些作業調入記憶體，為它們創建進程、分配必要的資源，再將新創建的進程排在就緒佇列上，準備執行。在批處理系統中，大多配有作業調度，但在分時和即時系統中，卻往往不配置作業調度。作業調度的運行頻率較低，通常為幾分鐘一次。3.1.1高級、中級和低級調度——調度的類型執行作業調度時，需要解決：（1）一次接納多少作業：即允許多少個作業同時在內存中運行。（2）接納哪些作業：即哪些作業調入記憶體，取決於所採用的演算法。比如先來先服務調度演算法；或者是短作業優先調度演算法；還有基於作業優先權的調度演算法，回應比高者優先調度演算法等。2.低級調度：又稱為進程調度、短程調度。用於決定就緒佇列中的哪個進程能獲得處理器,並將處理機分配給該進程。進程調度程式是操作系統最為核心的部分，進程調度策略的優劣直接影響到整個系統的性能。三種類型的操作系統中，都必須配置此級調度。有兩類低級調度方式：(1)非搶佔方式一旦把處理機分配給某個進程後，讓該進程一直執行，直到該進程完成或者發生某事件而阻塞。引起進程調度的因素：正在執行的進程執行完畢；執行中的進程因為提出I/O請求而暫停執行；進程通信或同步過程中執行了原語操作。(2)搶佔方式當一進程正在處理機上執行時，系統可根據某種原則暫停它的執行，並將已分配給它的處理機重新分配給另一個進程。搶佔的原則有：

優先權原則：就緒的高優先權進程有權搶佔低優先權進程的CPU。

短作業優先原則：就緒的短作業(進程)有權搶佔長作業(進程)的CPU。

時間片原則：一個時間片用完後，系統重新進行進程調度。3.中級調度又稱平衡負載調度、中程調度。目的是為了提高記憶體利用率和系統吞吐量。

實質是進程的內外存對換功能：將外存中已具備運行條件的進程換入記憶體，而將記憶體中處於阻塞狀態的某些進程換出至外存。

在三種調度中，進程調度的運行頻率最高，作業調度的週期較長，中級調度的運行頻率在上述兩者之間。3.1.2調度佇列模型

根據os中所引入的調度的類型，形成了三種類型的調度佇列模型：僅有進程調度的調度佇列模型；具有高級和低級調度的調度佇列模型；同時具有三級調度的調度佇列模型。1.

僅具有進程調度的調度佇列模型就緒隊列阻塞隊列進程調度CPU進程完成等待事件交互用戶事件出現時間片完2.具有高級和低級調度的調度佇列模型就緒隊列進程調度CPU進程完成等待事件1作業調度事件1出現時間片完等待事件2事件2出現……等待事件n事件n出現後備隊列……3.同時具有三級調度的調度佇列模型就緒佇列進程調度CPU就緒，掛起佇列中級調度阻塞，掛起佇列阻塞佇列等待事件進程完成時間片完作業調度交互型作業後備佇列批量作業掛起事件出現事件出現3.1.3選擇調度方式和調度演算法的若干原則面向用戶的準則(1)周轉時間短作業周轉時間：作業提交電腦到道作業完成為止的時間間隔。它是作業在系統裏的等待時間與運行時間之和。平均作業周轉時間：帶權周轉時間：W=T/Ts

注意：帶權周轉時間總大於1。平均作業帶權周轉時間：主要用於評價批處理系統。T

:作業的周轉時間，Ts:作業的運行時間。(2)

回應時間快從用戶通過鍵盤提交一個請求到系統首次產生回應之間的時間間隔稱回應時間。主要用於評價分時系統。(3)

截止時間的保證任務必須開始執行的最遲時間或必須完成的最遲時間稱截止時間。主要用於評價即時系統。(4)

優先權準則在三種OS中，都可遵循。2.面向系統的準則系統吞吐量高吞吐量:單位時間內系統所完成的作業數。(2)

處理機利用率好

CPU利用率=CPU有效工作時間/CPU總的運行時間

CPU總的運行時間=CPU有效工作時間+CPU空閒等待時間(3)

各類資源的平衡利用3.2調度演算法3.2.1先來先服務和短作業優先調度演算法3.2.2高優先權優先調度演算法3.2.3基於時間片輪轉調度演算法調度演算法:根據系統的資源分配策略所規定的資源分配演算法稱為調度演算法。通常將作業或進程歸入各種就緒或阻塞佇列。有的演算法適用於作業調度，有的演算法適用於進程調度，有的兩者都適應。3.2.1先來先服務和短作業優先調度演算法最簡單的調度演算法。用於作業調度時：按照作業進入系統的先後次序來挑選作業，先進入系統的作業優先被挑選。用於進程調度時：按照進程就緒的先後次序來調度進程。演算法容易實現，效率不高，只顧及作業等候時間，沒考慮作業要求服務時間的長短，不利於短作業而優待了長作業。1.先來先服務調度演算法（FCFS）例：在單道環境下，某批處理顯然有四道作業，已知他們的進入系統的時刻、估計運算時間如下：作業進入時刻(h)運行時間(h)ABCD012311001100

用FCFS演算法計算作業的運行情況、平均周轉時間和平均帶權周轉時間：作業進入時刻運行時間開始時刻完成時刻周轉時間帶權周轉時間ABCD0123110011000110110211011022021100100199111001.99平均周轉時間T＝100（h）平均帶權周轉時間T’＝26.00（h）2.短作業(進程)優先調度演算法（SJF/SPF）用於作業調度時：

SJF調度演算法。以進入系統的作業所要求的CPU時間為標準，總選取估計計算時間最短的作業投入運行。用於進程調度時：

SPF調度演算法。從就緒佇列中選出估計運行時間最短的進程，將處理機分配給它。演算法易於實現，能有效降低作業的平均等待時間。缺點是：對長作業不利，有可能導致長作業（進程）長期不被調度；未能依據作業的緊迫程度來劃分執行的優先順序；難以準確估計作業（進程）的執行時間，從而影響調度性能。13524運行步驟例：3.2.2高優先權優先調度演算法用於作業調度時：系統將從後備佇列中選擇若干個優先權最高的作業裝入記憶體。用於進程調度時：該演算法把處理機分配給就緒佇列中優先權最高的進程。非搶佔式優先權演算法搶佔式優先權調度演算法優先權的類型：靜態優先權在創建進程時確定的，且在進程的整個運行期間保持不變。靜態優先權法簡單易行，但隨著進程的推進，其優先權可能與進程的情況不再相符。動態優先權在創建進程時所確定的優先權，可以隨著進程的推進而改變。

例如：可以規定就緒進程的優先權隨著等待時間的增長以速度a增加；正在執行進程的優先權以速度b下降，這樣便可防止一個長作業長期壟斷處理機。3.高回應比優先調度演算法（HRRF）：

實際上是一種動態優先權調度演算法。

FCFS與SJF/SPF是片面的調度演算法。FCFS只考慮作業等候時間而忽視了作業的計算時間，SJF/SPF只考慮用戶估計的作業計算時間而忽視了作業等待時間。

HRRF是介乎這兩者之間的折衷演算法，既考慮作業等待時間，又考慮作業的運行時間，既照顧短作業又不使長作業的等待時間過長，改進了調度性能。但每次調度前，都要進行回應比的計算，會增加系統開銷。要求服務時間要求服務時間等待時間優先權+=優先權的變化規律可描述為：由於等待時間與服務時間之和，就是系統對該作業的回應時間，故該優先權又相當於回應比RP。據此，又可表示為：要求服務時間回應時間要求服務時間要求服務時間等待時間RP=+=

如果等待時間相同，短作業容易得到較高優先權。

長作業等待時間足夠長後，也將獲得足夠高的優先順序。

如果要求服務時間相同時，作業的優先權決定與其等待時間，實現的是先來先服務。例如：以下四個作業先後到達系統進入調度：作業名到達時間所需CPU時間作業10 20

作業25 15

作業3105

作業415 10FCFS調度演算法：平均作業周轉時間T=(20+30+30+35)/4=38.75平均帶權作業周轉時間W=(20/20+30/15+30/5+35/10)/4=3.13SJF調度演算法：調度順序為作業1、3、4、2，平均作業周轉時間T=(20+15+20+45)/4=25平均帶權作業周轉時間W=(20/20+15/5+25/10+45/15)/4=2.25

高回應比調度演算法：開始只有作業1，被選中執行時間20；作業1執行完畢，回應比依次為1+15/15、1+10/5、1+5/10，作業3被選中，執行時間5；作業3執行完畢，回應比依次為1+20/15、1+10/10，作業2被選中，執行時間15；作業2執行完畢，作業4被選中，執行時間10；平均作業周轉時間T=(20+15+35+35)/4=26.25平均帶權作業周轉時間W=(20/20+15/5+35/15+35/10)/4=2.423.2.3基於時間片輪轉調度演算法把CPU劃分成若干時間片,並且按順序賦給就緒佇列中的每一個進程，進程輪流佔有CPU，當時間片用完時，即使進程未執行完畢，系統也剝奪該進程的CPU，將該進程排在就緒佇列末尾。同時系統選擇另一個進程運行。時間片長度的選取非常重要，時間片長度的選擇會直接影響系統開銷和回應時間。1.時間片輪轉法（RR）2.多級回饋佇列調度演算法（FB）將就緒佇列分為N級，每個就緒佇列分配給不同的時間片，佇列級別越高，時間片越長，級別越小，時間片越短；新進程進入記憶體後，放入第一佇列末尾，按FCFS原則等待調度，如果在一個時間片結束時沒完成，將該進程轉入第二佇列末尾重新等待調度執行……如此下去，當一個長作業從第一級佇列降到最後一級佇列時，便在該隊列中採取時間片輪轉方式運行。僅當第一佇列空閒時，調度程式才調度第二佇列中的進程運行……類推之，僅當第1～(i-1)級佇列均空時，才調度第i級佇列上的進程執行。如果處理機正在為某佇列的進程服務，又有新進程插入到較高優先順序的佇列中，則新進程將搶佔正在運行進程的處理機。多級回饋佇列調度演算法就緒佇列1就緒佇列2就緒佇列3就緒佇列nS1S2S3至CPU至CPU至CPU至CPU(時間片：S1＜S2＜S3)多級回饋佇列調度演算法性能：較好的性能，能夠較好地滿足各種類型用戶的需要。終端型作業用戶短批處理作業用戶長批處理作業用戶3.3實時調度3.3.1實現即時調度的基本條件3.3.2即時調度演算法的分類3.3.3常用的兩種即時調度演算法1.即時調度

根據即時系統的特點，對即時系統中的調度有特殊的要求，故引入一種新的調度方式——即時調度。3.3.1實現即時調度的基本條件2.即時系統的特點

有限等待時間（決定性）有限回應時間用戶控制可靠性高系統出錯處理能力強3.實現即時調度的基本條件

提供必要的資訊如：就緒時間、開始或完成截止時間、處理時間、資源要求、絕對或相對優先順序（硬實時或軟即時）系統處理能力強採用搶佔式調度機制具有快速切換機制對外部中斷的快速回應能力、快速的任務分派能力3.3.2即時調度演算法的分類根據時實任務性質，分為硬實時調度演算法軟即時調度演算法根據調度方式，分為（√）非搶佔式調度演算法搶佔式調度演算法根據調度程式調度時間，分為靜態調度演算法動態調度演算法在多處理機環境下，分為集中式調度演算法分佈式調度演算法1.非搶佔式調度演算法非搶佔式輪轉調度演算法將即時任務排成輪轉佇列，調度程式每次選擇佇列中的第一個任務運行，當任務自我終止或運行完成後，此時調度程式選擇下一個隊首任務運行；未完成的任務被掛在輪轉佇列的隊尾。用於要求不太嚴格的即時控制系統。非搶佔式優先調度演算法在就緒佇列中，優先順序高的任務位於隊首，當任務自我終止或運行完成後，調度程式選擇下一個隊首任務運行。用於有一定要求的即時控制系統。2.搶佔式調度演算法基於時鐘中斷的搶佔式優先權調度演算法當新到來的即時任務的優先順序高於當前任務，則等到時鐘中斷到來時，調度程式剝奪當前任務的執行，將處理機分配給新到的高優先權任務。用於大多數的即時系統。立即搶佔的優先權調度演算法操作系統能快速相應外部時間中斷，一旦出現外部中斷，只要當前任務未處於臨界區，便立即剝奪當前任務的執行，將處理機分配給請求中斷的緊迫任務。用於即時要求比較嚴格的即時控制系統。(a)非搶佔輪轉調度當前進程即時進程即時進程請求調度即時進程槍占當前進程，並立即執行(d)立即搶佔的優先權調度調度時間進程

1進程

2即時進程要求調度進程

n即時進程調度即時進程運行(b)非搶佔優先權調度當前進程即時進程即時進程請求調度當前進程運行完成調度時間當前進程即時進程請求調度時鐘中斷到來時調度時間(c)基於時鐘中斷搶佔的優先權搶佔調度調度時間即時進程圖3-6即時進程調度回應時間：數秒至數十秒回應時間：幾十毫秒至幾毫秒回應時間：數秒至數百毫秒回應時間：幾百毫秒至幾毫秒3.3.3常用的兩種即時調度演算法1.最早截止時間優先演算法（即EDF演算法）

根據任務的開始截止時間來確定任務的優先順序。該調度演算法首先運行隊首進程，即開始截止時間最近的那個進程。演算法即可採用非搶佔調度方式，也可採用搶佔調度方式。13421234開始截止時間執行任務任務到達t1342例：非搶佔調度方式下的EDF演算法。2.最低鬆弛度優先演算法（即LLF演算法）

根據任務的緊迫程度（或鬆弛程度）來確定任務的優先順序。鬆弛度最低的任務排在就緒佇列的最前面，調度程式總是選擇佇列中的首任務執行。演算法主要用於可搶佔調度方式中。鬆弛度=必須完成時間-其本身的運行時間-當前時間例：如果系統中有兩個週期性的即時任務A和B：任務A要求每20ms執行一次，執行時間為10ms；任務B要求每50ms執行一次，執行時間為25ms；任務A和B每次的開始截止時間分別為A1、A2、A3…和B1、B2、B3…見圖。

A1(10)A2(30)A3(50)A4(70)A5(90)A6(110)A7(130)A80102030405060708090100110120130140150160tB1(25)B2(75)B3(125)01030404555708090100110130140A1A2A3A4A5A6A7B1(20)B1(5)B2(15)B2(10)B3(20)調度情況：3.4多處理機系統中的調度3.4.1多處理機系統的類型3.4.2進程分配方式3.4.3進程(線程)調度方式多處理機系統MPS，MultiProcessorSystem20世紀70年代出現多處理機系統：是一個具有兩個或多個處理機並能相互進行通信以協同一個大的給定問題求解的電腦系統。3.4.1多處理機系統的類型根據多處理器之間耦合的緊密程度，分為緊密耦合MPS

鬆散耦合MPS根據系統中所用處理器的相同與否，分為對稱多處理器系統SMPS

非對稱多處理器系統3.4.2進程分配方式1.對稱式多處理系統中的進程分配方式：靜態分配方式 每個CPU設立一個就緒佇列，進程從開始執行到完成，都在同一個CPU上。優點：調度演算法開銷小。缺點：容易出現處理機忙閑不均。動態分配方式各個CPU採用一個公共就緒佇列，隊首進程每次分派到當前空閒的CPU上執行。

優點：消除個處理機忙閑不均的現象。

缺點：對鬆散耦合系統，會增加調度開銷。2.非對稱式多處理系統中的進程分配方式

主－從處理機系統。操作系統核心駐留在主機上，由主處理機執行調度，從機上只是用戶程式；主機管理一個公共就緒佇列，並分派進程給從處理機執行；各個處理機有固定分工，如執行OS的系統功能，I/O處理，應用程式。優點：系統處理較簡單。缺點：存在不可靠性；當主機太忙時，會出現系統瓶頸。克服方法：利用多臺處理機（而非一臺）來管理整個系統。注重整體運行效率（而不是個別處理機的利用率）。更多樣的調度演算法。多處理機訪問OS數據結構時的互斥（對於共用記憶體系統）。調度單位廣泛採用線程。3.多處理機調度與單處理機調度的區別3.4.3進程(線程)調度方式

指在系統中設置一個公用的進程(或線程)佇列，所有的處理器在空閒時，都可自己到該隊列中取一進程(或線程)來執行。是最簡單、最常用的調度方式，採用單處理機環境下的調度方式。

需要對就緒佇列的數據結構進行互斥訪問控制。1.自調度(self-scheduling)方式：優點：易將單處理機系統的調度機制移植到多處理機系統。避免處理機忙閑不均的現象。缺點：瓶頸問題低效性線程切換頻繁為了解決自調度方式中線程被頻繁切換的問題。是指將一組相互合作的進程或隸屬於同一個進程的一組線程分配到一組處理器上去同時執行。分配處理機時間時，可採用兩種方式：面向所有應用程式平均分配處理機時間面向所有線程平均分配處理機時間2.成組調度(gangscheduling)方式兩種分配處理器時間的方式：面向所有應用程式平均分配處理機時間面向所有線程平均分配處理機時間優點：對於一組相互合作的線程，成組調度能夠提高這些線程的執行並行度，有利於減少阻塞和加快推進速度，最終提高系統的吞吐量。每次調度可以完成多個線程的分派，能夠減少調度次數，從而減少調度的開銷。是指在一個應用程式執行期間，專門為該應用程式分配一組處理器，每個線程分配一個CPU。這組處理器僅供該應用程式專用，直至該應用程式執行完成。適用於CPU數量眾多的高度並行系統，單個CPU利用率已不太重要。線程的總和不應超過系統中的處理機數目。缺點：有線程阻塞時，造成CPU的閒置優點：線程執行時不需切換，相應的開銷可以大大減小，推進速度更快。3.專用處理機分配(dedicatedprocessorassignment)方式以下是線程數對加速比的影響：1234567891011121314151617181920212223241234567加速比線程數矩陣相乘FFT0例：具有16個處理器的系統，運行兩個應用程式：

矩陣相乘、快速傅立葉變換。3.5產生死鎖的原因和必要條件3.5.1產生死鎖的原因3.5.2產生死鎖的必要條件3.5.3處理死鎖的基本方法死鎖的定義

所謂死鎖，是指多個進程因競爭資源而造成的一種僵局，若無外力作用，這些進程都將不能再向前推進。

注意：如果死鎖發生，會浪費大量系統資源，甚至導致系統崩潰。3.5.1產生死鎖的原因

一個操作系統基本上是一個資源管理者，它負責分配不同類型的資源給進程使用。系統中的資源分兩類：

可剝奪性資源—指資源佔有進程雖然需要使用該資源，但另一個進程卻能強行把資源從佔有者進程處搶來。

不可剝奪性資源—指只有佔用者進程不再需要使用該資源而主動釋放資源外，其他進程不得在佔有者進程使用資源過程中強行搶佔。1.資源資源可剝奪：CPU、主存、硬碟，該資源可為幾個進程共同使用。不可剝奪：印表機、讀卡機、磁帶驅動器，該資源為某個進程獨享。永久性資源和臨時性資源：永久性資源——可順序重複使用的資源：如印表機；臨時性資源——由一個進程產生，被另一進程使用一短暫時間後便無用的資源：如消息，故也稱之為消耗性資源。

競爭資源（不可剝奪性、臨時性）當系統中供多個進程共用的資源不足時，將引起進程對資源的競爭而產生死鎖。

進程推進順序不合理進程在運行過程中具有非同步性特徵，如果它們之間的請求和釋放資源的順序不當，也同樣會導致進程產生死鎖。2.死鎖產生的根本原因(1)競爭資源產生的死鎖：請求邊分配邊進程資源進程資源請求邊分配邊請求邊分配邊進程進程資源請求邊分配邊………生產出一產品；P（empty）P（mutex

）將產品放入緩衝區；V（mutex

）V（full）

………(2)進程推進順序不合理產生的死鎖：例1：生產者—消費者問題中，若PV操作使用不當，把生產者進程兩個P操作次序互換，先執行P(mutex)，後執行P(empty)，則會引起死鎖。………P（full）P（mutex

）從緩衝區取出產品；V（mutex

）V（empty）消費該產品；

………生產者消費者P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)①②③④D

例2：（見書P91）3.5.2產生死鎖的必要條件四個必要條件：互斥條件：涉及的資源是非共用的。請求和保持條件：進程在等待一新資源時繼續佔有已分配的資源。不剝奪條件：不能強行剝奪進程擁有的資源。環路等待條件：存在一種進程的迴圈鏈，鏈中的每一個進程已獲得的資源同時被鏈中的下一個進程所請求。

以上四個條件須同時具備。3.5.3處理死鎖的基本方法(1)

預防死鎖：

通過設置某些限制條件，去破壞死鎖四個必要條件中的一個或多個，來防止死鎖。較易實現，廣泛使用，但由於所施加的限制往往太嚴格，可能導致系統資源利用率和系統吞吐量的降低。(2)

避免死鎖：

不事先採取限制去破壞產生死鎖的條件，而是在資源的動態分配過程中，用某種方法去防止系統進入不安全狀態，從而避免死鎖的發生。實現較難，只需要較弱的限制條件，可獲得較高的資源利用率和系統吞吐量。

事先並不採取任何限制，允許發生死鎖，但可以通過系統的檢測機構及時檢測出死鎖的發生，並精確確定與死鎖有關的進程和資源。(3)

檢測死鎖：

與檢測死鎖相配套，用於將進程從死鎖狀態解脫出來。常用的方法是撤銷或掛起一些進程。以回收一些資源，再將它們分配給處於阻塞狀態的進程，使之轉為就緒狀態。實現難度大，但可獲得較好的資源利用率和系統吞吐量。(4)

解除死鎖：3.6死鎖的預防和避免3.6.1預防死鎖3.6.2避免死鎖3.6.3利用銀行家演算法避免死鎖1.摒棄“請求和保持”條件

系統要求所有進程在開始運行之前，要一次性地申請在整個運行過程中所需的全部資源。若系統有足夠資源則完全分配；否則，進程等待。3.6.1預防死鎖優點：簡單、易於實現且安全。

基本思想：打破產生死鎖的四個必要條件中的一個或幾個。

缺點：實用性不強：在許多情況下，一個進程在執行之前不可能知道它所需要的全部資源。這是由於進程在執行時是動態的，不可預測的；資源利用率低：無論所分資源何時用到，一個進程只有在佔有所需的全部資源後才能執行。即使有些資源最後才被該進程用到一次，但該進程在生存期間卻一直佔有它們，造成長期占著不用的狀況。造成極大的資源浪費；延遲進程的運行：因為進程只有獲得了其所需的全部資源才開始運行，但有些資源可能長期被其他進程佔用，導致該進程遲遲不能運行。2.摒棄“不剝奪”條件

一個已擁有資源的進程，若它再提出新資源要求而不能立即得到滿足時，它必須釋放已經擁有的所有資源。以後需要時再重新申請。

缺點：實現複雜、要付出很大的代價。原因：一個資源在使用一段時間後被釋放，可能會造成前階段工作的失效；反復地申請和釋放資源，又會使進程的執行無限推遲，從而進一步增加系統的開銷，降低系統的吞吐量。3.摒棄“環路等待”條件

系統中的所有資源都有一個確定的唯一號碼，所有分配請求必須以序號上升的次序進行。例如：系統中有下列設備：輸入機(1)，印表機(2)，穿孔機(3)，磁帶機(4)，磁片(5)。有一進程要先後使用輸入機、磁片、印表機，則它申請設備時要按輸入機、印表機、磁片的順序申請。優點：同前兩法相比，其資源利用率和系統吞吐量有較明顯的改善。缺點：系統中各類資源的編號必須相對穩定，限制了新設備類型的增加；進程實際需要資源的順序不一定與資源的編號一致，因此仍會造成資源浪費。

在系統運行過程中，對進程發出的每一個系統能夠滿足的資源申請進行動態檢查，並根據檢查結果決定是否分配資源，若分配後系統可能發生死鎖，則不予分配，否則予以分配。把系統的狀態分為安全狀態和不安全狀態，只要能使系統始終都處於安全狀態，便可避免死鎖的發生。3.6.2避免死鎖1.安全狀態

如果系統能按某種順序（P1，P2，…,Pn）為每個進程分配其所需的資源，直至所有進程都能運行完成，稱系統處於安全狀態。若不存在這樣一個安全序列稱系統處於不安全狀態。其中，<P1，P2，…,Pn>稱為安全序列。

並非所有的不安全狀態都導致死鎖，但當系統進入不安全狀態後，便可能進而進入死鎖狀態；只要系統處於安全狀態，便可避免進入死鎖狀態

避免死鎖的本質在於：當進行資源分配時，如何避免進入不安全狀態。安全狀態舉例：

有三個進程p1、p2、p3，有12臺磁帶機。P1共要求10臺，P2共要求4臺，P3共要求9臺。在T0時刻，p1、p2、p3分別獲得5、2、2臺，尚有3臺空閒。進程最大需求已分配還需可用p110553p2422p3927

經分析，在T0時刻，系統是安全的。因為存在一個安全序列p2、p1、p3。見下圖。3.6.3利用銀行家演算法避免死鎖最有代表性的避免死鎖演算法，由Dijkstra提出。1.銀行家演算法中的數據結構可利用資源向量Available。它是一個含有m個元素的數組，其中每個元素代表一類可利用資源的數目。最大需求矩陣Max。n*m矩陣，表示n個進程的每一個對m類資源的最大需求。分配矩陣Allocation。n*m矩陣，表示每個進程分配的資源數。需求矩陣Need。n*m矩陣，表示每個進程還需要各類資源數。2.銀行家演算法描述當進程pi提出資源申請時，系統執行下列步驟：(1)

若Request[i]≤Need[i]，轉(2)；否則錯誤返回。(2)

若Request[i]≤Available，轉(3)；否則進程等待。(3)

假設系統分配了資源，則有：

Available:=Available-Request[i];Allocation[i]:=Allocation[i]+Request[i];Need[i]:=Need[i]-Request[i](4)

執行安全性演算法，若系統新狀態是安全的，則分配完成；若系統新狀態是不安全的，則恢復原狀態，進程等待。3.安全性演算法為進行安全性檢查，設置兩個向量：工作向量Work:表示系統可提供給進程繼續運行所需的各類資源數目，含有m個元素，在執行安全演算法開始時，Work:=Available;Finish:表示系統是否有足夠的資源分配給進程，使之運行完成。開始時先做Finish[i]:=false;當有足夠資源分配給進程時，再令Finish[i]:=true。安全性演算法步驟：(1)

Work:=Available;Finish:=false；(2)

尋找滿足下列條件的i：

a)Finish[i]=false；

b)Need[i]≤Work；

若找到，轉(3)；若找不到，則轉(4)。(3)

Work:=Work+Allocation[i]；

Finish[i]:=true；

轉(2)。(4)

若對所有i，Finish[i]=true，則系統處於安全狀態，否則處於不安全狀態。4.銀行家演算法舉例

設系統有五個進程和三類資源，每類資源分別有10、5、7。在T0時刻資源分配情況如圖：(1)

T0時刻的安全性檢查：T0時刻可以找到一個安全序列{p1,p3,p4,p0,p2}。系統是安全的。(2)

T0時刻P1請求資源，請求向量Request1(1,0,2)。執行銀行家演算法：①Request1(1,0,2)≤Need1(1,2,2)

②Request1(1,0,2)≤Available(3,3,2)

③系統先假定可為P1分配資源，並修改Available,Allocation1和Need1向量，由此形成的資源變化情況如圖一所示。④進行安全性檢查：如圖二所示。可以找到一個安全序列{p1,p3,p4,p0,p2}。故系統是安全的，可以將P1的請求分配給它。圖一：圖二：

(3)

P4請求資源，請求向量Request4(3,3,0)。執行銀行家演算法:①Request4(3,3,0)≤Need4(4,3,1);

②Request4(3,3,0)≤Available(2,3,0);

所以P4等待。P4的請求不能分配。(4)

P0請求資源,請求向量Request0(0,2,0)Request0(0,2,0)，執行銀行家演算法：①Request0(0,2,0)≤Need0(7,4,3);

②Request0(0,2,0)≤Available(2,3,0);

③系統暫時先假定可為P0分配資源，並修改圖一有關數據，如後圖所示。④進行安全性檢查：Available{2,1,0}已不能滿足任何進程需要，所以系統進入不安全狀態，P0的請求不能分配。3.7死鎖的檢測與解除3.7.1死鎖的檢測3.7.2死鎖的解除

死鎖檢測與解除是指系統設有專門的機構，當死鎖發生時，該機構能夠檢測到死鎖發生的位置和原因，並能通過外力破壞死鎖發生的必要條件，從而使得併發進程從死鎖狀態中恢復出來。

允許死鎖發生，操作系統不斷監視系統進展情況，判斷死鎖是否發生。一旦死鎖發生則採取專門的措施，解除死鎖並以最小的代價恢復操作系統運行。3.7.1死鎖的檢測1.資源分配圖

用來描述系統資源及資源的申請和分配情況的有向圖。定義為：二元組G=（V，E）

其中：

V：結點集，分為P(進程集合)，R(資源集合)兩部分。即P={p1,p2,…,pn}；R={r1,r2,…,rm}。

E：邊的集合，其元素為有序二元組(pi,rj)或(rj,pi)。資源請求邊：e={pi,rj}

進程

資源的一條有向邊表示進程pi申請rj類資源中的一個資源。資源分配邊：e={rj,pi}

資源

進程的一條有向邊表示rj類中的一個資源已被進程pi佔用。例：R1R2P2P3P4P1P1P2r1r2請求r2資源請求邊資源分配邊(1)