2023/2/4阜陽師范學院計算機與信息學院1第3章處理機調度與死鎖3.1處理機調度的基本概念3.2調度算法3.3實時調度3.4產生死鎖的原因和必要條件3.5預防死鎖的方法3.6死鎖的檢測與解除2023/2/4阜陽師范學院計算機與信息學院23.1處理機調度的基本概念3.1.1高級調度、中級調度、低級調度3.1.2調度隊列模型3.1.3選擇調度方式和調度算法的若干準則2023/2/4阜陽師范學院計算機與信息學院32023/2/4阜陽師范學院計算機與信息學院43.1.1高級、中級和低級調度經歷下述三級調度:高級調度（HighScheduling）中級調度（Intermediate-LevelScheduling）低級調度（LowLevelScheduling）2023/2/4阜陽師范學院計算機與信息學院51.高級調度

又稱為作業調度、宏觀調度或長程調度。用于決定把后備隊列中的哪些作業調入內存，為他們分配必要的資源，并創建進程。批處理系統：分時系統：實時系統：需要作業調度不需作業調度不需作業調度2023/2/4阜陽師范學院計算機與信息學院61.高級調度執行作業調度時，必須作出兩個決定：接納多少作業——每次接納多少作業進入內存，取決于多道程序度，即允許多少個作業同時在內存中運行。接納哪些作業——應接納哪些作業從外存調入內存，取決于所采用的調度算法。2023/2/4阜陽師范學院計算機與信息學院72.低級調度

通常也稱為進程調度、微觀調度或短程調度。進程調度是最基本的一種調度，在三種OS中都有。用于決定就緒隊列中哪個進程應先獲得處理機，并將處理機分配給選中的進程。為實現進程調度，應具有如下三個基本機制：排隊器分派器上下文切換2023/2/4阜陽師范學院計算機與信息學院82.低級調度進程調度可采用下述兩種調度方式：非搶占方式搶占方式搶占的原則有：（1）優先權原則（2）短作業（進程）優先原則（3）時間片原則2023/2/4阜陽師范學院計算機與信息學院93.中級調度

中級調度又稱為交換調度、中程調度或內存調度。它按一定的算法將外存中已具備運行條件的進程換入內存，而將內存中處于阻塞狀態的某些進程換出至外存。運行就緒阻塞掛起阻塞掛起就緒創建退出進程調度中級調度作業調度調度的層次2023/2/4阜陽師范學院計算機與信息學院113.1.2調度隊列模型僅有進程調度的調度隊列模型具有高級和低級調度的調度隊列模型同時具有三級調度的調度隊列模型2023/2/4阜陽師范學院計算機與信息學院121.僅有進程調度的調度隊列模型

在分時系統中就緒進程組織成FIFO隊列形式，按時間片輪轉方式運行。CPU就緒隊列阻塞隊列時間片完進程調度等待事件進程完成交互用戶事件出現2023/2/4阜陽師范學院計算機與信息學院132.具有高級和低級調度的調度隊列模型CPU就緒隊列時間片完進程調度等待事件1進程完成后備隊列等待事件2等待事件n事件1出現事件2出現事件n出現作業調度2023/2/4阜陽師范學院計算機與信息學院143.同時具有三級調度的調度隊列模型CPU就緒隊列時間片完進程調度進程完成后備隊列等待事件事件出現作業調度批量作業交互型作業中級調度就緒、掛起隊列事件出現阻塞、掛起隊列掛起阻塞隊列掛起中級調度2023/2/4阜陽師范學院計算機與信息學院153.1.3選擇調度方式和調度算法的若干準則面向用戶的準則周轉時間短平均周轉時間T平均帶權周轉時間（W=T(周轉)/Ts(CPU執行))響應時間快截止時間的保證優先權準則面向系統的準則系統吞吐量高處理機利用率好各類資源的平衡利用練習1設有4個作業同時到達，每個作業執行時間均為2h，它們在一臺處理器上按單道方式運行，則平均周轉時間為（）A.1hB.5hC.2.5hD.8hB2023/2/4阜陽師范學院計算機與信息學院173.2調度算法3.2.1FCFS與SJF/SPF調度算法3.2.2高優先權優先調度算法3.2.3基于時間片的輪轉調度算法2023/2/4阜陽師范學院計算機與信息學院183.2.1FCFS與SJF/SPF調度算法1.先來先服務調度算法(FCFS)

按進程申請CPU（就緒）的次序processRuntimeP127P23P35P1P2P302730352023/2/4阜陽師范學院計算機與信息學院19

FCFS實例下表列出了A、B、C、D四個作業分別到達系統的時間、要求服務的時間、開始執行的時間及各自的完成時間，計算出各自的周轉時間和帶權周轉時間。FCFS（FirstComeFirstServe)2023/2/4阜陽師范學院計算機與信息學院20作業名到達時間服務時間開始執行時間完成時間周轉時間帶權周轉時間A01B1100C21D3100FCFS（FirstComeFirstServe)0111110110011011021001001022021991.992023/2/4阜陽師范學院計算機與信息學院21FCFS的特點:

FCFS調度算法有利于CPU繁忙型的作業，而不利于I/O繁忙型的作業（進程）比較有利于長作業，而不利于短作業FCFS（FirstComeFirstServe)2023/2/4阜陽師范學院計算機與信息學院222.短作業（進程）優先調度算法帶權周轉時間周轉時間完成時間SJF帶權周轉時間周轉時間完成時間FCFS42534服務時間43210到達時間平均EDCBA作業名

作業情況調度算法4417621210214115.518143.592.8441982.6718163.2631.51392.2582.12023/2/4阜陽師范學院計算機與信息學院232.短作業（進程）優先調度算法SJF調度算法的優缺點：優點：有效降低作業的平均等待時間，提高系統吞吐量缺點：(1)對長作業不利(2)不能保證緊迫性作業（進程）的及時處理(3)不一定能真正做到短作業優先2023/2/4阜陽師范學院計算機與信息學院243.2.2高優先權優先調度算法1.優先權調度算法的類型為照顧緊迫性作業，使之在進入系統后便獲得優先處理，引入了最高優先權優先（HPF）調度算法。它分為兩種：非搶占式優先權算法搶占式優先權調度算法2023/2/4阜陽師范學院計算機與信息學院253.2.2高優先權優先調度算法2.優先權的類型靜態優先權：在創建進程時確定的，在進程的整個運行期間保持不變,又稱優先數。動態優先權：在創建進程時所賦予的優先權可以隨進程的推進或隨其等待時間的增加而改變。2023/2/4阜陽師范學院計算機與信息學院263.高響應比優先調度算法(HRRN)

為每個作業引入動態優先權，并使作業的優先級隨著等待時間的增加而以速率a提高，則可解決問題。見下式：

優先權=(等待時間+要求服務時間)/要求服務時間＝響應時間/要求服務時間3.2.2高優先權優先調度算法練習2一個作業8：00到達系統，估計運行時間為1h。若10:00開始執行該作業，其響應比是（）A.2B.1C.3D.0.5C例題1設有4個作業J1、J2、J3、J4，它們的到達時間和計算時間如表所示。若這4個作業在一臺處理器上按單道方式運行，采用高響應比優先調度算法，試寫出各作業的執行順序、各作業的周轉時間及平均周轉時間作業到達時間計算時間J18：00120minJ28：3040minJ39：0025minJ49：3030min解析：優先權（響應比）=(等待時間+要求服務時間)/要求服務時間＝響應時間/要求服務時間作業提交時間開始時間執行時間結束時間周轉時間J18：008：00120min10：00120minJ28：3010：2540min11：05155minJ39：0010：0025min10：2585minJ49：3011：0530min11：35125min例題2在一個批處理系統中，有兩個作業進程。有一個作業序列，其到達時間及估計運行時間如表所示。系統作業采用最高響應比優先調度算法，進程的調度采用短進程優先的搶占式調度算法作業到達時間估計運行時間J110：0035minJ210：1030minJ310：1545minJ410：2020minJ510：3030min例題2（1）列出各作業的執行時間（即列出每個作業運行的時間片段，如作業i的運行時間序列為10：00-10：40）（2）計算這批作業的平均周轉時間。2023/2/4阜陽師范學院計算機與信息工程學院32J110:00J4:20m10:10J2到達J210:35J1完成J4進內存分析：J3J4J510:55J4完成J3進內存J1:10mJ1:25m11:25J2完成J5進內存J2:30mJ5:30m11:55J5完成12:40J3完成J3:45m例題3有一個具有兩道作業的批處理系統，作業調度采用短作業優先調度算法，進程調度采用搶占式優先級調度算法，作業的運行情況如表所示，其中作業的優先數即為進程的優先數，優先數越小，優先級越高。2023/2/4阜陽師范學院計算機與信息學院33作業到達時間運行時間優先數J18：0040min5J28：2030min3J38：3050min4J48：5020min6（1）列出所有作業進入內存的時間及結束的時間（2）計算平均周轉時間2023/2/4阜陽師范學院計算機與信息工程學院34J18:00J1:20m8:20J2到達J28:30分析：J3J48:50J2完成J4進入J1:20mJ2:10m9:10J1完成J3進內存J3:50mJ4:20m10:00J3完成10:20J4完成J2:20m2023/2/4阜陽師范學院計算機與信息學院353.2.3基于時間片的輪轉調度算法(RR)

在分時系統中，為保證能及時響應用戶的請求，必須采用基于時間片的輪轉式進程調度算法。在早期，分時系統中采用的是簡單的時間片輪轉法，進入90年代后，廣泛采用多級反饋隊列調度算法。2023/2/4阜陽師范學院計算機與信息學院36將系統中所有的就緒進程按照FCFS原則，排成一個隊列。每次調度時將CPU分派給隊首進程，讓其執行一個時間片。在一個時間片結束時，將其送到就緒隊列的末尾，并通過上下文切換執行當前的隊首進程。一、時間片輪轉算法1.基本原理2023/2/4阜陽師范學院計算機與信息學院372.時間片長度的確定時間片長度變化的影響過長－>退化為FCFS算法。過短－>用戶的一次請求需要多個時間片才能處理完，上下文切換次數增加。對響應時間的要求：T(響應時間)=N(進程數目)*q(時間片)一、時間片輪轉算法2023/2/4阜陽師范學院計算機與信息學院382023/2/4阜陽師范學院計算機與信息學院39二、多級反饋隊列調度算法

實施過程如下：（1）應設置多個隊列并為各個隊列賦予不同的優先級。第一個最高，依次降低。該算法賦予各個隊列中進程執行時間片的大小也不相同，優先權越高，時間片越短。1.調度算法2023/2/4阜陽師范學院計算機與信息學院40多級反饋隊列調度算法

2023/2/4阜陽師范學院計算機與信息學院41二、多級反饋隊列調度算法(2)當一個新進程進入內存后，首先將它放入第一隊列的末尾，按FCFS原則排隊等待調度。如它在一個時間片結束時尚未完成，調度程序便將該進程轉入第二隊列的末尾。(3）僅當第1～（i-1）隊列空閑時，才會調度第i隊列中的進程運行。2023/2/4阜陽師范學院計算機與信息學院422.多級反饋隊列調度算法的性能終端型作業用戶短作業優先短批處理作業用戶周轉時間較短長批處理作業用戶二、多級反饋隊列調度算法2023/2/4阜陽師范學院計算機與信息學院43補充作業1、假如有四道作業，它們的進入時間和運行時間由下表給出，在單道程序環境下，分別填寫先來先服務、短作業優先和RR（2）算法的完成時間、周轉時間、帶權周轉時間、平均周轉時間和帶權平均周轉時間。2023/2/4阜陽師范學院計算機與信息學院44作業號進入時間運行時間FCFSSJFRR（3）完成時間周轉時間帶權周轉時間完成時間周轉時間帶權周轉時間完成時間周轉時間帶權周轉時間1042110326432平均2、有一個內存只能裝入兩道作業的批處理系統，作業調度采用短作業優先的調度算法，進程調度采用以優先數為基礎的搶占式調度算法。下表中所列的優先數是指進程調度的優先數，且優先數越小優先級越高。作業名到達時間估計運行時間優先數A10:0040分5B10:2030分3C10:3050分4D10:5020分6問：列出所有作業進入內存的時刻以及結束的時刻計算作業的平均周轉時間3、假設一個系統中有5個進程，它們的到達時間和服務時間如表所示，忽略I/O以及其他開銷時間，若分別按先來先服務（FCFS），非搶占及搶占的短進程優先（SPF）、高響應比優先（HRRN）、時間片輪轉（RR=1）、多級反饋隊列調度算法（FB，第i級隊列的時間片=2i-1)以及立即搶占的多級反饋隊列調度算法進行CPU調度，請給出各進程的完成時間、周轉時間、帶權周轉時間、平均周轉時間和平均帶權周轉時間。進程到達時間服務時間A03B26C44D65E822023/2/4阜陽師范學院計算機與信息學院49第3章處理機調度與死鎖3.3實時調度3.4產生死鎖的原因和必要條件3.5預防死鎖的方法3.6死鎖的檢測與解除2023/2/4阜陽師范學院計算機與信息學院503.3實時調度實時調度：合理安排就緒實時任務的執行次序，滿足每個實時任務時間約束條件的調度實時任務：具有明確時間約束的計算任務2023/2/4阜陽師范學院計算機與信息學院513.3實時調度3.3.1實現實時調度的基本條件3.3.2實時調度算法的分類3.3.3常用的幾種實時調度算法2023/2/4阜陽師范學院計算機與信息學院523.3.1實現實時調度的基本條件提供必要的信息系統處理能力強采用搶占式調度機制具有快速切換機制2023/2/4阜陽師范學院計算機與信息學院531.提供必要的信息就緒時間開始截止時間和完成截止時間處理時間資源要求優先級2023/2/4阜陽師范學院計算機與信息學院542.系統處理能力強

假如系統中有M個周期性的硬實時任務，處理時間為Ci，周期時間表示為Pi

則單機系統中必須滿足條件

∑（Ci/

Pi）≤1

多處理機系統∑（Ci/

Pi）≤N2023/2/4阜陽師范學院計算機與信息學院553.采用搶占式調度機制

硬實時任務：廣泛采用搶占機制小的實時系統：可采用非搶占調度機制（簡化調度程序和對任務調度時所花費的系統開銷）3.采用搶占式調度機制2023/2/4阜陽師范學院計算機與信息學院562023/2/4阜陽師范學院計算機與信息學院574.具有快速切換機制

(1)對外部中斷的快速響應能力(2)快速的任務分派能力2023/2/4阜陽師范學院計算機與信息學院583.3.2實時調度算法的分類可以按照不同方式對實時調度算法加以分類：根據實時任務性質的不同可分為硬實時調度算法和軟實時調度算法；按調度方式的不同可分為非搶占調度算法和搶占調度算法；2023/2/4阜陽師范學院計算機與信息學院593.3.3常用的幾種實時調度算法

最早截止時間優先EDF（EarliestDeadlineFirst）算法最低松弛度優先LLF（LeastLaxityFirst）算法2023/2/4阜陽師范學院計算機與信息學院60EDF算法用于非搶占調度圖示

1342t按開始截止時間早晚的排序任務執行任務到達134212341.最早截止時間優先EDF算法

截止時間越早，其優先級越高2023/2/4阜陽師范學院計算機與信息學院612.最低松弛度優先LLF算法松弛度=完成截止時間—運行時間—當前時間任務的緊急程度愈高，松弛度愈低，優先級愈高。要求系統有一個按松弛度排序的實時任務就緒隊列該算法主要用于可搶占調度方式中2023/2/4阜陽師范學院計算機與信息學院62LLF算法例tA1A2A3A4A5A6B1B2020406080100120

假如在一個實時系統中，有兩個周期型實時任務A、B，任務A要求每20ms執行一次，執行時間為10ms；任務B要求每50ms執行一次，執行時間為25ms；由此可得知AB任務每次必須完成的時間分別為A1、A2、A3…和B1、B2、B3…如下圖：2023/2/4阜陽師范學院計算機與信息學院63LLF算法例圖示tt1

t2

t3

t4

t5

t6

t7

t8

01020304050607080A1(10)A2(10)A3(10)A4(10)B1(20)B1(5)B2(15)B2(10)

4、對下面的5個非周期性實時任務，按最早開始截止時間優先調度算法，判斷是該用搶占方式還是非搶占方式，并給出調度順序。補充作業進程到達時間執行時間開始截止時間A1020110B202020C402050D502090E6020705、若有3個周期性任務，任務A要求每20ms執行一次，執行時間為10ms；任務B要求每50ms執行一次，執行時間為10ms；任務C要求每50ms執行一次，執行時間15ms應如何按最低松弛度優先算法對它們進行調度？2023/2/4阜陽師范學院計算機與信息學院673.5產生死鎖的原因和必要條件3.5.1產生死鎖的原因3.5.2產生死鎖的必要條件3.5.3處理死鎖的基本方法2023/2/4阜陽師范學院計算機與信息學院68關于死鎖

死鎖是指多個進程在運行過程中因爭奪資源而造成的一種僵局，當進程處于這種狀態時，若無外力作用，它們都將無法再向前推進。2023/2/4阜陽師范學院計算機與信息學院693.5.1產生死鎖的原因產生死鎖的原因可歸結為如下兩點：競爭資源

進程間推進順序非法可搶占和非搶占性資源可重用性（永久性）資源和可消耗性（臨時性）資源2023/2/4阜陽師范學院計算機與信息學院70P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)①②③④D進程推進順序不當引起死鎖2023/2/4阜陽師范學院計算機與信息學院713.5.2產生死鎖的必要條件

雖然進程在運行過程中可能發生死鎖，但死鎖的發生也必須具備一定的條件。可以看出，必須具備以下四個條件:1.互斥條件：進程所競爭的資源必須被互斥使用。2.請求和保持條件：指進程已經保持了至少一個資源，但又提出了新的資源請求，而該資源又被其他進程占有，此時請求進程阻塞，但又對自己已獲得的其他資源保持不放。2023/2/4阜陽師范學院計算機與信息學院723.5.2產生死鎖的必要條件

3.不剝奪條件：指進程已獲得的資源，只能在使用完時由自己釋放。

4.環路等待條件：指在發生死鎖時，必然存在一個“進程——資源”的環形鏈，環路中的每一條邊是進程在請求另一進程已經占有的資源。

2023/2/4阜陽師范學院計算機與信息學院733.5.3處理死鎖的基本方法一、預防死鎖——消除產生死鎖的必要條件二、避免死鎖——分配資源時防止進入不安全狀態三、檢測死鎖——不預防死鎖，出現死鎖就解除四、解除死鎖——與檢測死鎖配合使用2023/2/4阜陽師范學院計算機與信息學院743.6預防與避免死鎖的方法3.6.1預防死鎖3.6.2系統安全狀態3.6.3利用銀行家算法避免死鎖2023/2/4阜陽師范學院計算機與信息學院753.6.1預防死鎖1.摒棄“請求和保持”條件靜態資源分配法一次性地申請其在整個過程運行過程中所需要的全部資源優點：算法簡單、易于實現且很安全缺點：資源浪費嚴重，進程延遲運行2023/2/4阜陽師范學院計算機與信息學院762.摒棄“不剝奪”條件資源暫時釋放策略:申請新的資源得不到滿足則暫時釋放已有的所有資源。從而摒棄了“不剝奪”條件。該方法實現起來比較復雜且付出很大代價。可能會造成前功盡棄，反復申請和釋放情況。3.6.1預防死鎖2023/2/4阜陽師范學院計算機與信息學院773.摒棄“環路等待”條件有序資源分配法：

與前兩種策略比較，資源利用率和系統吞吐量都有較明顯的改善。但也存在嚴重問題：為資源編號限制新設備的增加；進程使用設備順序與申請順序相反；限制用戶編程自由。r1r2rk......申請次序rm2023/2/4阜陽師范學院計算機與信息學院78檢測可滿足請求

分配

不分配安全不安全系統處于安全狀態：存在安全進程序列<p1,p2,…,pn>;安全不安全死鎖1.安全狀態3.6.2系統安全狀態避免死鎖的實質就是系統在進行資源分配時，如何使系統不進入不安全狀態。2023/2/4阜陽師范學院計算機與信息學院792.安全狀態之例

假定系統中有三個進程A、B和C，共有12臺磁帶機。進程A總共要求10臺，B和C分別要求4臺和9臺。假設在T0時刻,進程A、B和C已分別獲得5臺、2臺和2臺，尚有3臺未分配，如下表所示：進程最大需求已分配還需可用ABC10495225273進程最大需求已分配還需可用B42235A105510C92712

經分析發現，在T0時刻系統是安全的，因為此時存在一個安全序列<B,A,C>，即只要系統按此進程序列分配資源，就能使每個進程都順利完成。2023/2/4阜陽師范學院計算機與信息學院803.由安全狀態向不安全狀態的轉換如果在T0時刻后，C又請求到一臺磁帶機，若此時系統把剩余3臺中的1臺分配給C，則系統便進入不安全狀態。因為，此時再也無法找到一個安全序列，結果導致死鎖。進程最大需求已分配還需可用A10553B422C927

所以，引入安全狀態的目的在于進行資源分配時，要使系統不發生死鎖，只要保證當前的系統狀態是安全的，即每次資源分配之后系統都處于安全狀態。2C936練習1某計算機系統中有8臺打印機，由K個進程競爭使用，每個進程最多需要3臺打印機。該系統可能會發生死鎖的K的最小值是（），不會發生死鎖的最大值是（）。A.2B.3C.4D.5解析：R類資源共m個，n個進程互斥使用，每個進程對R類資源最大需求量為w設：M=n*（w-1）+1則m<M的可能會發生死鎖，m>=M絕對不會死鎖練習1某計算機系統中有8臺打印機，由K個進程競爭使用，每個進程最多需要3臺打印機。該系統可能會發生死鎖的K的最小值是（），不會發生死鎖的最大值是（）。A.2B.3C.4D.5CB2023/2/4阜陽師范學院計算機與信息學院843.6.3利用銀行家算法避免死鎖最有代表性的避免死鎖的算法，是Dijkstra的銀行家算法。這是由于該算法能用于銀行系統現金貸款的發放而得名的。銀行家算法中的數據結構（1）可利用資源向量Available。這是一個含有m個元素的數組，其中的每一個元素代表一類可利用的資源數目，其動態初始值是系統中所配置的該類全部可用資源的數目，其數值隨該類資源的分配與回收而動態的改變。如果Available[j]=K,則表示系統中現有Rj類資源K個。（2）最大需求矩陣Max。這是一個n*m的矩陣，它定義了系統中n個進程中的每一個進程對m類資源的最大需求。如果Max[i,j]=K,則表示進程i需要Rj類資源的最大數目為K。（3）分配矩陣Allocation。這也是一個n*m的矩陣，它定義了系統中每一類資源當前已分配給每一進程的資源數。如果Allocation[i,j]=K,則表示進程i當前已分得Rj類資源的數目為K。（4）需求矩陣Need。這也是一個n*m的矩陣，用以表示每一個進程尚需的各類資源數。如果Need[i,j]=K,則表示進程i還需要Rj類資源K個，方能完成其任務。上述三個矩陣間存在的關系：Need[i,j]=Max[i,j]-Allocation[i,j]2023/2/4阜陽師范學院計算機與信息學院853.6.3利用銀行家算法避免死鎖安全性算法系統所執行的安全性算法可描述如下：（1）設置兩個向量：工作向量work：表示系統可提供給進程繼續運行所需的各類資源數目，它含有m個元素，在執行安全算法開始時，work:=Available;Finish:

它表示系統是否有足夠的資源分配進程，使之運行完成。開始時先做Finish[i]:=false;當有足夠資源分配給進程時，再令Finish[i]:=true。2023/2/4阜陽師范學院計算機與信息學院86安全性檢測算法FWork:=Available;Finish:=false;有滿足條件的j:Finish[i]=falseNeed[j]WorkFinish[i]=true;Work:=Work+Allocation[j]Ti,Finish[i]=trueTF安全不安全賦初值進程是否完成資源是否夠用進程獲得資源后，順利完成并釋放資源進程是否都完成2023/2/4阜陽師范學院計算機與信息學院87（2）從進程集合中找到一個能滿足下述條件的進程：

Finish[i]=false;Need[i,j]<=work[j];若找到，執行步驟3，否則執行步驟4。（3）當進程Pi獲得資源后，可順利執行，直至完成，并釋放出分配給它的資源，故應執行：

work[j]:=work[i]+Allocation[i,j];Finish[i]:=true;gotostep2;（4）如果所有進程的Finish[i]=true都滿足，則表示系統處于安全狀態；否則，系統處于不安全狀態。安全性算法2023/2/4阜陽師范學院計算機與信息學院884.銀行家算法之例

假定系統中有五個進程{P0,P1,P2,P3,P4}和三類資源{A,B,C}，各種資源的數量分別為10、5、7，在T0時刻的資源分配情況如圖所示。431002433P4011211222P3600302902P2122200322P1332743010753P0AvailableABCNeedABCAllocationABCMaxABC

資源情況進程2023/2/4阜陽師范學院計算機與信息學院894.銀行家算法之例T0時刻的安全性：利用安全性算法對T0時刻的資源分配情況進行分析可知，在T0時刻存在著一個安全序列{P1,P3,P4,P2,P0}，故系統是安全的。FalseFalseFalseFalseFalseTrue10570107431047P0True1047302600745P2True745002431743P4True743211011532P3True532200122332P1FinishWork+AllocationABCAllocationABCNeedABCWorkABC

資源情況進程2023/2/4阜陽師范學院計算機與信息學院903.6.3利用銀行家算法避免死鎖銀行家算法設Requesti是進程Pi的請求向量，如果Requesti

[j]=K，表示進程Pi需要K個Rj類型的資源。當Pi發出資源請求后，系統按下述步驟進行檢查：2023/2/4阜陽師范學院計算機與信息學院91Pi請求資源Requesti[j]Need[j]請求超量，錯返Requesti[j]Available[j]不滿足，等待Available[j]:=Available[j]-Requesti[j]Allocation[i,j]:=Allocation[i,j]+Requesti[j]Need[i,j]:=Need[i,j]-Requesti[j]安全確認，pi繼續Available[j]:=Available[j]+Requesti[j]Allocation[i,j]:=Allocation[i,j]-Requesti[j]Need[i,j]:=Need[i,j]+Requesti[j]pi等待FTFTTF請求的資源是否超出實際需求是否有足夠的資源暫時分配資源恢復原來的資源分配狀態2023/2/4阜陽師范學院計算機與信息學院92（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）系統執行安全性算法，檢查此次資源分配后系統是否出于安全狀態以決定是否完成本次分配。銀行家算法2023/2/4阜陽師范學院計算機與信息學院934.銀行家算法之例P1請求資源：P1發出請求向量Request1(1，0，2),系統按銀行家算法進行檢查：（1）Request1(1，0，2)<=Need1(1，2，2)（2）Request1(1，0，2)<=Available1(3，3，2)（3）系統先假定可為P1分配資源，并修改Available、Allocation1和Need1向量。（4）再利用安全性算法檢查此時系統是否安全。如下表：2023/2/4阜陽師范學院計算機與信息學院94FalseFalseFalseFalseFalse4.銀行家算法之例

由所進行的安全性檢查得知，可以找到一個安全序列{P1,P3,P4,P0,P2},因此，系統是安全的，可以立即將P1所申請的資源分配給它。True1057302600755P2True755010743745P0True745002431743P4True743211011532P3True532302020230P1FinishWork+AllocationABCAllocationABCNeedABCWorkABC

資源情況進程2023/2/4阜陽師范學院計算機與信息學院954.銀行家算法之例P4請求資源：P4發出請求向量Request4(3，3，0),系統按銀行家算法進行檢查：（1）Request4(3，3，0)<=Need4(4