第三章處理機調(diào)度與死鎖本章內(nèi)容處理機調(diào)度常用調(diào)度算法介紹死鎖與預防死鎖的方法本章討論處理器資源的管理問題。處理器調(diào)度問題決定著整個系統(tǒng)的綜合性能。不同的CPU管理方法將為用戶提供不同性能的操作系統(tǒng)。3.1處理機調(diào)度的層次從處理器調(diào)度的對象、時間、層次等不同角度，可把處理器調(diào)度分成不同類型。按照調(diào)度涉及的層次不同，從用戶作業(yè)從進入系統(tǒng)成為后備作業(yè)開始，直到運行結束退出系統(tǒng)為止，可把處理器調(diào)度分成：高級調(diào)度中級調(diào)度低級調(diào)度3.1.1高級調(diào)度高級調(diào)度概念也稱為作業(yè)調(diào)度、長程調(diào)度或接納調(diào)度。按照系統(tǒng)預定的調(diào)度策略，決定把外存上處于后備隊列中的哪些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進程、分配必要的資源，然后再將創(chuàng)建的進程排在就緒隊列上，準備執(zhí)行。在批處理操作系統(tǒng)中，作業(yè)首先進入系統(tǒng)在輔存上的后備作業(yè)隊列等候調(diào)度，因此，作業(yè)調(diào)度是必須的。在純粹的分時或?qū)崟r操作系統(tǒng)中，通常不需要配備作業(yè)調(diào)度。作業(yè)相關概念作業(yè)：程序+數(shù)據(jù)+作業(yè)說明書作業(yè)步：相對獨立相互關聯(lián)的順序加工步驟作業(yè)流作業(yè)控制塊JCB：作業(yè)在系統(tǒng)中的標識，保存有系統(tǒng)對作業(yè)進行管理與調(diào)試所需要的全部信息作業(yè)標識用戶名稱、用戶帳戶作業(yè)類型、作業(yè)狀態(tài)資源需求調(diào)度信息進入時間、開始處理時間、需求時間……作業(yè)調(diào)度時要做的決定：（1）接納多少個作業(yè)（2）接納哪些作業(yè)（調(diào)度算法）作業(yè)調(diào)度的目標：（1）對所有作業(yè)盡量做到公平合理（2）高設備利用率（3）執(zhí)行盡可能多的作業(yè)（4）盡量短的響應時間3.1.2低級調(diào)度也稱為進程調(diào)度、短程調(diào)度。用于決定就緒隊列中的哪個進程獲得處理機。低級調(diào)度程序是操作系統(tǒng)最為核心的部分，低級調(diào)度策略的優(yōu)劣直接影響到整個系統(tǒng)的性能。最初的調(diào)度對象是傳統(tǒng)操作系統(tǒng)中的進程，隨著現(xiàn)代操作系統(tǒng)引入了多線程技術，進程演變成資源管理的單位，從而只作為中級調(diào)度的對象，內(nèi)核級線程則替代進程成為低級調(diào)度的對象。1.進程調(diào)度功能（1）記錄系統(tǒng)中所有進程的執(zhí)行情況（2）選擇占有處理機的進程(選擇算法)（3）進行進程上下文切換—個進程的上下文(context)包括進程的狀態(tài)、有關變量和數(shù)據(jù)結構的值、機器寄存器的值等相關程序、數(shù)據(jù)。當正在執(zhí)行的進程讓出處理機時，系統(tǒng)要做進程上下文切換，以使另一個進程得以執(zhí)行。2.進程調(diào)試中的三個基本機制排隊器：負責組織各進程隊列分派器：將選中的進程從就緒隊列中取出，分配處理機上下文切換機制兩對上下文切換：保存當前進程上下文，裝入分派程序上下文移出分派程序上下文，裝入新選進程現(xiàn)場信息3.進程調(diào)度方式1）非搶占方式進程一旦獲得處理機后便一起執(zhí)行下去，直至該進程完成或發(fā)生某事件被阻塞時，才把處理機分配給其他進程。決不允許某進程搶占已經(jīng)分配出去的處理機。當前進程無論在用戶態(tài)還是核心態(tài)都不可以被搶用CPU。不可搶先式OS：Windows98/95，在這些OS中，進程從運行態(tài)退出只能是自愿或阻塞，不能強迫運行態(tài)就緒態(tài)。引起進程調(diào)度的因素：（1）進程執(zhí)行完畢，或發(fā)生某事件不能再繼續(xù)執(zhí)行（2）I/O請求（3）進程通信或同步過程中執(zhí)行了原語操作優(yōu)點：實現(xiàn)實現(xiàn)簡單，系統(tǒng)開銷小，適用于批處理系統(tǒng)。缺點：不能滿足緊急任務的要求，不適用于實時系統(tǒng)。2）搶占方式當一個進程正在運行時，調(diào)度程序可以基于某種原則，剝奪已分配給它的處理機，將之分配給其它進程。剝奪原則有：（1）優(yōu)先權原則（2）短進程優(yōu)先原則（3）時間片原則。內(nèi)核完全不可搶先當前進程在用戶態(tài)時可隨時被搶用CPU，但處于核心態(tài)時完全不可以被搶用CPU。如：傳統(tǒng)的UNIX和Windows。這類操作系統(tǒng)通常在系統(tǒng)調(diào)用或中斷時屏蔽中斷，系統(tǒng)調(diào)用返回或中斷返回時開放中斷。內(nèi)核的部分可搶先當前進程在用戶態(tài)時隨時被搶用CPU，但處于核心態(tài)時則大部分時間不可以被搶用CPU，只在某些時刻點（可搶先點）可以被搶用CPU。如：UNIXSVR4。SVR4內(nèi)核定義了搶先點：內(nèi)核代碼中的這樣一些位置，內(nèi)核的數(shù)據(jù)結構處在一個穩(wěn)定的狀態(tài)，并且內(nèi)核馬上要開始長時間的、大量的計算。此時，內(nèi)核檢查是否有實時進程就緒需要運行，若有則搶先當前進程。完全可搶先或內(nèi)核完全可搶先無論當前進程處于用戶態(tài)還是核心態(tài)，都可以隨時可被搶用CPU。如：SUNSolaris（最成功的UNIX商業(yè)變種之一）。為做到完全可搶先，Solaris對SVR4的核心代碼做了全面修改，大部分的內(nèi)核全局數(shù)據(jù)結構都用正確的同步對象如互斥鎖或信號量來保護，并通過特殊內(nèi)核線程實現(xiàn)中斷來避免用提高優(yōu)先級的方法保護臨界區(qū)。Solaris內(nèi)核中只有極少的不可搶先代碼段。3.1.3中級調(diào)度中級調(diào)度實現(xiàn)進程在主存與外存間的對換。反映到進程狀態(tài)上就是掛起和解除掛起。中級調(diào)度將那些暫時不能運行的進程調(diào)出主存，此時這些進程處于掛起狀態(tài)。當被掛起的進程具備了運行條件，且主存又有空閑區(qū)域時，再由中級調(diào)度決定一部分這樣的進程重新調(diào)回主存工作。中級調(diào)度起到短期調(diào)整系統(tǒng)負荷的作用，調(diào)度的依據(jù)是存儲資源量和進程的當前狀態(tài)，目的是提高內(nèi)存利用率和系統(tǒng)吞吐量。3.2調(diào)度隊列模型和調(diào)度準則3.2.1調(diào)度隊列模型1．只有進程調(diào)度的調(diào)度隊列模型內(nèi)存中維護就緒進程隊列和阻塞進程隊列。系統(tǒng)可能以棧、樹、鏈表的方式組織隊列。2．具有高級與低級調(diào)度的調(diào)度隊列模型外存維護一個后備隊列，內(nèi)存維護就緒進程隊列和阻塞進程隊列。3．同時具有三級調(diào)度的調(diào)度隊列模型3.2.2選擇調(diào)度方式和調(diào)度算法的準則不同類型及目標的操作系統(tǒng)，其采用的調(diào)度方式與調(diào)度算法通常不同。1．面向用戶的準則2．面向系統(tǒng)的準則1．面向用戶的準則（1）周轉時間短周轉時間：作業(yè)提交計算機開始到完成返回用戶為止的時間間隔。（2）響應時間快響應時間：從提交一個請求到首次產(chǎn)生響應的時間間隔?；蛘哒f，用戶發(fā)送指令給計算機到計算機返回結果給用戶的時間間隔。1．面向用戶的準則（3）截止時間的保證評價實時系統(tǒng)的重要指標。截止時間：任務必須開始執(zhí)行的最遲時間，或必須完成的最遲時間。（4）優(yōu)先權準則：關鍵任務得到更好的性能指標（5）公平性：確保每個用戶每個進程獲得合理的CPU份額或其他資源份額。2．面向系統(tǒng)的準則（1）系統(tǒng)吞吐量高吞吐量：單位時間內(nèi)系統(tǒng)完成的作業(yè)數(shù)。（2）處理機利用率高：大中型系統(tǒng)的主要指標（3）各類資源的平衡利用3.3調(diào)度算法常用的作業(yè)調(diào)度算法有：FCFS（先來先服務）方法SJP（最短作業(yè)優(yōu)先）法HRN（最高響應比）法常用進程調(diào)度算法：RR（輪轉）法FCFS（先來先服務）法優(yōu)先級法多級反饋隊列算法3.2.1先來先服務算法最簡單的調(diào)度算法，基本思想是按進程（作業(yè)）到達的先后順序進行調(diào)度。作業(yè)調(diào)度：按照作業(yè)進入系統(tǒng)的先后次序來挑選作業(yè)，先進入系統(tǒng)的作業(yè)優(yōu)先被挑選。進程調(diào)度：按照進程進入就緒隊列的先后次序來分配處理器。先進入就緒隊列的進程優(yōu)先被挑選，運行進程一旦占有處理器將一直運行下去直到運行結束或阻塞，即采用非搶占調(diào)度方式。FCFS的特點：比較有利于長作業(yè)，而不利于短作業(yè)（進程）。有利于CPU繁忙型作業(yè)，而不利于I/O繁忙型作業(yè)。實現(xiàn)簡單平均周轉時間長3.2.1短作業(yè)（進程）優(yōu)先算法這是對FCFS算法的改進，其目標是減少平均周轉時間。SJF：從后備隊列中選擇估計運行時間最短的一個或幾個作業(yè)調(diào)入內(nèi)存。SPF：從就緒隊列中選擇一個估計運行時間最短的進程，將處理機分配給它。短進程優(yōu)先法調(diào)度方式短進程優(yōu)先算法既可以是非搶占式，也可以是搶占式。當一個進程正在執(zhí)行時，一個新進程進入就緒狀態(tài)，如果新進程需要的CPU時間比當前正在執(zhí)行的進程剩余下來還需的CPU時間短，掄占式短進程優(yōu)先算法強行趕走當前正在執(zhí)行進程，這種方式也叫最短剩余時間優(yōu)先算法(ShortestRemainingTimeFirst)。短作業(yè)優(yōu)先法的特性優(yōu)點：與FCFS相比，改善平均周轉時間和平均帶權周轉時間，縮短作業(yè)的平均等待時間。易于實現(xiàn)，系統(tǒng)吞吐量高。缺點：忽視了作業(yè)等待時間對長作業(yè)非常不利，長作業(yè)（進程）可能長時間得不到執(zhí)行；未能依據(jù)作業(yè)的緊迫程度來劃分執(zhí)行的優(yōu)先級；難以準確估計作業(yè)（進程）的執(zhí)行時間，從而影響調(diào)度性能。短作業(yè)優(yōu)先算法的變型：“最短剩余時間優(yōu)先”(ShortestRemainingTimeFirst)

允許比當前進程剩余時間更短的進程搶占當前進程“最高響應比優(yōu)先”

(HighestResponseRatioNext)

響應比R=(等待時間+要求執(zhí)行時間)/要求執(zhí)行時間是FCFS和SJF的折衷3.3.2最高優(yōu)先權優(yōu)先算法（FPF）作業(yè)調(diào)度：從后備隊列中選擇若干個優(yōu)先權最高的作業(yè)進入內(nèi)存。進程調(diào)度：每一個進程給出一個優(yōu)先數(shù)，處理器調(diào)度每次選擇就緒進程隊列中優(yōu)先數(shù)最大者，讓它占用處理器運行。1．優(yōu)先權調(diào)度算法的類型（1）非搶占式優(yōu)先權算法系統(tǒng)一旦將處理機分配給優(yōu)先權最高的進程后，該進程便一直執(zhí)行下去直到完成。主要用于批處理系統(tǒng)，也用于某些實時要求不嚴的實時系統(tǒng)中。（2）搶占式優(yōu)先權調(diào)度算法系統(tǒng)按最高優(yōu)先權分配處理機。只要出現(xiàn)另一個優(yōu)先權更高的進程，則進程調(diào)度程序停止當前進程的執(zhí)行，重新將處理機分配給新到的優(yōu)先權最高的進程。常用于嚴格的實時系統(tǒng)中，或?qū)π阅芤筝^高的批處理和分時系統(tǒng)中。2．優(yōu)先權的類型（1）靜態(tài)優(yōu)先權靜態(tài)優(yōu)先權是在創(chuàng)建進程時確定的，在整個運行期間不再改變。確定優(yōu)先權的依據(jù)有：進程類型。如系統(tǒng)進程優(yōu)先權高于用戶進程。進程對資源的需求。如估計運行時間、內(nèi)存需求等。用戶要求。由用戶或操作員根據(jù)作業(yè)的緊急程序指定一個優(yōu)先級。靜態(tài)優(yōu)先權法簡單易行，系統(tǒng)開銷小，但不夠精確。2．優(yōu)先權的類型（2）動態(tài)優(yōu)先權創(chuàng)建進程時所賦予的優(yōu)先權，在進程周期內(nèi)可以動態(tài)變化。如隨等待時間的增加而改變。優(yōu)先權確定依據(jù)：根據(jù)進程占用有CPU時間的長短來決定。根據(jù)就緒進程等待CPU的時間長短來決定。3.高響應比優(yōu)先算法最高響應比優(yōu)先法（HRN）是對FCFS方式和SJF方式的一種綜合平衡。HRN調(diào)度策略同時考慮每個作業(yè)的等待時間長短和估計需要的執(zhí)行時間長短，從中選出響應比最高的作業(yè)投入執(zhí)行。響應比=（等待時間+要求服務時間）/要求服務時間特點：（1）在等待時間相同時，此算法是優(yōu)待短作業(yè)的，實現(xiàn)的是SJF。（2）在要求服務時間相同時，優(yōu)先權決定于等待時間，實現(xiàn)的是FCFS。（3）長作業(yè)在等待足夠長時，也可獲得處理機。這種算法是介于FCFS和SJF之間的一種折中算法。但是由于每次調(diào)度前要計算響應比，系統(tǒng)開銷也要相應增加。3.3.3基于時間片的輪轉調(diào)度算法1.時間片輪轉法系統(tǒng)將所有就緒進程按FIFS規(guī)則排隊，每個進程輪流運行一個相同的時間片。每次調(diào)度時將CPU分派給隊首進程，讓其執(zhí)行一個時間片。在一個時間片結束時，發(fā)生時鐘中斷，調(diào)度程序據(jù)此暫停當前進程的執(zhí)行，將其送到就緒隊列的末尾，再將處理機分配給就緒隊列的隊首進程。這樣可保證就緒隊列中的所有進程在一定時間內(nèi)均能獲得一時間片的處理機，即系統(tǒng)在能在給定時間內(nèi)響應所有用戶的請求。好處：使系統(tǒng)及時響應。缺點：輪轉法調(diào)度是一種剝奪式調(diào)度，系統(tǒng)耗費在進程切換上的開銷比較大，時間片長度變化的影響:過長－>退化為FCFS算法，進程在一個時間片內(nèi)都執(zhí)行完，響應時間長。過短－>用戶的一次請求需要多個時間片才能處理完，切換次數(shù)增加，系統(tǒng)開銷大。時間片長度的確定：（1）系統(tǒng)效率（2）對響應時間的要求：

T(響應時間)=N(進程數(shù)目)*q(時間片)（3）就緒進程的數(shù)目：數(shù)目越多，時間片越小（4）CPU的處理能力：應當使用戶輸入通常在一個時間片內(nèi)能處理完，否則使響應時間，平均周轉時間和平均帶權周轉時間延長。2.多級反饋隊列調(diào)度算法

多級反饋隊列算法是時間片輪轉算法和優(yōu)先級算法的綜合和發(fā)展。1）實現(xiàn)（1）系統(tǒng)中設置多個就緒隊列，分別賦予不同的優(yōu)先級，并逐級降低。（2）為不同隊列所規(guī)定的時間片長度不同，優(yōu)先權越高的隊列分配的時間片越小。如逐級加倍。（3）新進程進入內(nèi)存后，先投入隊列1的末尾，按FCFS算法排隊調(diào)度；若按隊列1的一個時間片未能執(zhí)行完，則降低投入到隊列2的末尾。如果在隊列2的時間片內(nèi)未能完成，則降低投入到隊列3……；如此下去，降低到最后的隊列，則按“時間片輪轉”算法調(diào)度直到完成。（4）僅當較高優(yōu)先級的隊列為空，才調(diào)度較低優(yōu)先級的隊列中的進程執(zhí)行。如果進程執(zhí)行時有新進程進入較高優(yōu)先級的隊列，則搶先執(zhí)行新進程，并把被搶先的進程投入原隊列的末尾。（5）阻塞進程被喚醒時，進入原來的就緒隊列中。2）性能（1）終端型作業(yè)用戶提供高的響應時間。（2）短批處理作業(yè)用戶在第一個或前2個時間片中即可完成，平均周轉時間短。（3）長批處理作業(yè)用戶不會饑餓。3）優(yōu)點為提高系統(tǒng)吞吐量和縮短平均周轉時間而照顧短進程。為獲得較好的I/O設備利用率和縮短響應時間而照顧I/O型進程。不必估計進程的執(zhí)行時間，動態(tài)調(diào)節(jié)。3.4實時調(diào)度實時系統(tǒng)中存在若干個實時進程或?qū)崟r任務，反應或控制某些外部事件。實時系統(tǒng)要響應的事件（要處理的實時任務）可以進一步劃分為周期性事件和非周期性事件，都聯(lián)系著一個截止響應時間。3.4.1實現(xiàn)實時調(diào)度的基本條件提供必要的信息就緒時間、截止時間、處理時間、資源要求、優(yōu)先級系統(tǒng)處理能力強多采用搶占式調(diào)度機制具有快速切換機制設置快速的硬件中斷機構適當?shù)臋C制使進行切換開銷小3.4.2實時調(diào)度算法分類1．非搶占式調(diào)度算法（1）非搶占式輪轉調(diào)度算法通過對所有周期性任務的分析預測（到達時間、運行時間、結束時間、任務間的優(yōu)先關系），事先確定一個固定的調(diào)度方案。這種方法的特點是有效但不靈活。（2）非搶占式優(yōu)先級調(diào)度算法2．搶占式調(diào)度算法（1）基于時鐘中斷的搶占式優(yōu)先權調(diào)度算法。（2）立即搶占的優(yōu)先權調(diào)度算法3.4.3常用的實時調(diào)度算法實時調(diào)度算法可以分為動態(tài)實時調(diào)度算法和靜態(tài)實時調(diào)度算法兩類。動態(tài)實時調(diào)度算法在運行時作出調(diào)度決定，靜態(tài)實時調(diào)度算法在系統(tǒng)啟動之前完成所有的調(diào)度決策。常用的實時算法都是基于優(yōu)先權的算法。1．最早截止時間優(yōu)先即EDF算法

(EarliestDeadlineFirst)根據(jù)任務的開始截止時間來確定任務的優(yōu)先級。截止時間越早，優(yōu)先級越高。實時任務的就緒隊列按優(yōu)先級排序，調(diào)度程序總是選擇隊首進程占有處理機。EDF算法用于非搶占調(diào)度方式2．最低松弛度優(yōu)先(LLF)算法根據(jù)任務的緊急（或松馳）程序來確定任務的優(yōu)先級。任務緊急程序高，為該任務所賦予的優(yōu)先級愈高。該算法主要用于搶占式調(diào)度方式。松弛度=必須完成時間-其本身的運行時間-當前時間假如在一個實時系統(tǒng)中，有兩個周期性實時任務A和B，任務A要求每20ms執(zhí)行一次，執(zhí)行時間為10ms；任務B只要求每50ms執(zhí)行一次，執(zhí)行時間為25ms。A和B任務每次必須完成的時間利用LLF算法進行調(diào)度的情況3.5產(chǎn)生死鎖的原因和必要條件死鎖實例設系統(tǒng)有一臺打印機(R1)一臺掃描儀(R2)，被并發(fā)的A、B兩進程共享。用信號量S1、S2表示R1、R2是否可用，S1、S2初值為1。A、B并發(fā)時就可能產(chǎn)生死鎖。死鎖概念死鎖：多個進程因競爭共享資源而造成的一種僵局，若無外力作用，這些進程都將永遠不能再向前推進。一組并發(fā)進程彼此互相等待對方所擁有的資源，且這些并發(fā)進程在得到對方的資源之前不會釋放自己所擁有的資源。從而造成大家都想得到資源而又都得不到資源，各并發(fā)進程不能繼續(xù)向前推進的狀態(tài)。這一組進程就稱為死鎖進程。3.5.1產(chǎn)生死鎖的原因產(chǎn)生死鎖的因素不僅與系統(tǒng)擁有的資源數(shù)量有關，而且與資源分配策略，進程對資源的使用要求以及并發(fā)進程的速率有關。1.競爭系統(tǒng)資源2.進程的推進順序不當

1）可剝奪資源和非剝奪資源可剝奪資源：分配給某進程后又可以被其他進程或系統(tǒng)剝奪的資源。如處理機、內(nèi)存。非剝奪資源：一旦分配給某進程后不能強行收回，只能由進程自行釋放的資源。永久性資源：可以被多個進程多次使用的資源（可再用資源）。臨時性資源：由一個進程產(chǎn)生，被另一進程使用一段時間后便無用的資源。如消息，中斷信號，同步信號等（可消耗性資源）。2）競爭資源引起死鎖（1）競爭非剝奪資源（2）競爭臨時性資源3．進程推進順序不當P1P2Request(R1);Request(R2);Request(R2);Request(R1);Releast(R1);Releast(R2);Releast(R2);Releast(R1);3.5.2產(chǎn)生死鎖的必要條件1．互斥條件：資源獨占，排他性使用。2．請求和保持條件：當進程因請求資源而阻塞時，不釋放已占有的資源。3．不剝奪條件：進程已獲得的資源不能被剝奪，只能在使用完時由自己釋放。4．環(huán)路等待條件：在發(fā)生死鎖時，必然存在一個進程--資源的環(huán)形循環(huán)鏈，鏈中每一個進程已獲得的資源被下一個進程所請求，同時它又請求上一進程所擁有的資源。3.5.3處理死鎖的基本方法預防死鎖：設置限制條件，破壞產(chǎn)生死鎖的四個必要條件中的一個或幾個條件。避免死鎖：在每次的資源動態(tài)分配過程中，對系統(tǒng)能夠滿足的資源申請進行安全性檢查，根據(jù)結果決定是否進行此次分配。檢測死鎖：允許系統(tǒng)發(fā)生死鎖，但設置檢測機構，及時檢測出死鎖的發(fā)生。解除死鎖：外力推動解除死鎖。具體方法有：撤消或掛起死鎖進程、剝奪資源等。3.6預防死鎖的方法3.6.1預防死鎖死鎖的預防：通過設置限制條件，破壞產(chǎn)生死鎖的四個必要條件中的一個或幾個條件，使系統(tǒng)在任何時刻都不滿足死鎖的必要條件，從而預防死鎖的發(fā)生。1．資源一次性分配進程必須在運行前一次性地申請運行期間所需的全部資源，這樣進程在整個運行期間不會再提出資源請求，從而摒棄了請求和保持條件。優(yōu)點：簡單，易于實現(xiàn)，安全。缺點：（1）資源浪費嚴重。降低進程并發(fā)度。（2）進程延遲運行。（3）不適用資源需要未知的進程。2．可剝奪資源允許進程逐個申請資源，當進程新的資源請求未滿足時，必須釋放已占有的資源，待以后需要時再重新申請。此策略表明進程已占有的資源可被暫時釋放，即被剝奪了，從而摒棄“不剝奪”條件。缺點：（1）復雜，實現(xiàn)困難且代價大。（2）延長了進程的周轉時間，增加系統(tǒng)開銷。3．資源有序申請系統(tǒng)給每類資源賦予一個序號，每一個進程嚴格按照序號遞增的順序請求資源，釋放則相反。此方法不可能形成資源占有與請求的環(huán)路，從而破壞環(huán)路等待條件。優(yōu)點：相對而言，系統(tǒng)利用率高，系統(tǒng)吞吐量大。缺點：（1）限制設備擴充。系統(tǒng)事先確定資源序號，限制了新類型設備的增加。（2）限制了進程對資源的請求，編程困難。（3）資源浪費。當進程使用順序與資源序號不相符時，也會造成資源浪費。3.6.3避免死鎖避免死鎖的方法就是讓系統(tǒng)處于安全狀態(tài)中。在避免死鎖的策略中，允許進程動態(tài)地申請資源。死鎖避免：系統(tǒng)對進程運行過程中發(fā)出的每一個系統(tǒng)能夠滿足的資源申請進行安全檢查，根據(jù)檢查結果決定是否分配資源。若此次分配會導致系統(tǒng)進入不安全狀態(tài)，則不予分配；否則予以分配。1．安全狀態(tài)安全狀態(tài)指系統(tǒng)能按某種進程順序來為每個進程分配其所需資源，直至每個進程的最大需求，使每個進程都可順序完成。若系統(tǒng)不存在這樣一個序列，則稱系統(tǒng)處于不安全狀態(tài)，不安全狀態(tài)一般會導致死鎖。2．安全狀態(tài)實例P953．由安全狀態(tài)向不安全狀態(tài)的轉換

如果不按照安全序列分配資源，則系統(tǒng)可能會由安全狀態(tài)進入不安全狀態(tài)。3.6.3銀行家算法避免死鎖單種資源的銀行家算法描述：假定一個銀行家擁有資金，數(shù)量為∑，被N個客戶共享。銀行家對客戶提出下列約束條件：每個客戶必須預先說明自己所要求的最大資金量每個客戶每次提出部分資金量申請和獲得分配如果銀行滿足了客戶對資金的最大需求量，那么，客戶在資金運作后，應在有限時間內(nèi)全部歸還銀行。銀行則保證：若一個客戶所要求的最大資金量不超過∑，則銀行一定接納該客戶，并處理他的資金需求；銀行在收到一個客戶的資金申請時，可能因資金不足而讓客戶等待，但保證在有限時間內(nèi)讓客戶獲得資金。三種資源分配狀態(tài)：(a)安全(b)安全(c)不安全

銀行家算法就是對每一個請求進行檢查，檢查這次資源申請是否會導致不安全狀態(tài)。若是，則不滿足該請求；否則便滿足。1．銀行家算法中的數(shù)據(jù)結構（1）可利用資源向量Available[m]。每一個元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動態(tài)地改變。如果Available［j］=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個。（2）最大需求矩陣Max[n][m]。定義了系統(tǒng)中n個進程中的每一個進程對m類資源的最大需求。如果Max[i][j]=K，則表示進程i需要Rj類資源的最大數(shù)目為K。1．銀行家算法中的數(shù)據(jù)結構（3）分配矩陣Allocation[n][m]定義了系統(tǒng)中每一類資源當前已分配給每一進程的資源數(shù)。如果Allocation[i][j]=K，則表示進程i當前已分得Rj類資源的數(shù)目為K。（4）需求矩陣Need[n][m]用以表示每一個進程尚需的各類資源數(shù)。如果Need[i][j]=K，則表示進程i還需要Rj類資源K個，方能完成任務。Need[i][j]=Max[i][j]-Allocation[i][j]

2．銀行家算法設Requesti是進程Pi的資源請求向量，如果Requesti[j]=K，表示進程Pi需要K個Rj類型的資源。當Pi發(fā)出資源請求后，系統(tǒng)按下述步驟檢查：（1）如果Requesti[j]≤Need[i][j]，便轉向步驟2；否則認為出錯，因為它所需要的資源數(shù)已超過它所宣布的最大值。（2）如果Requesti[j]≤Available[j]，便轉向步驟(3)；否則，表示尚無足夠資源，Pi須等待。（3）系統(tǒng)試著把資源分配給進程Pi，并修改下面數(shù)據(jù)結構中的數(shù)值：Available[j]=Available[j]-Requesti[j];Allocation[i][j]=Allocation[i][j]+Requesti[j];Need[i][j]=Need[i][j]-Requesti[j];（4）系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復原來的資源分配狀態(tài)，讓進