【導(dǎo)讀】在每次執(zhí)行作業(yè)調(diào)度時，都須做出以下兩個決定。操作，如P操作、Block原語、Wakeup原語等。的批處理系統(tǒng)環(huán)境。但它難以滿足緊急任務(wù)的要求——立即。執(zhí)行，因而可能造成難以預(yù)料的后果。顯然，在要求比較嚴。格的實時系統(tǒng)中，不宜采用這種調(diào)度方式。短作業(yè)(進程)優(yōu)先原則。中級調(diào)度又稱中程調(diào)度。為此，應(yīng)使那些暫時不能運行的進程不再占用寶貴。狀態(tài)稱為就緒駐外存狀態(tài)或掛起狀態(tài)。外存上的哪些又具備運行條件的就緒進程，重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊列上等待進程調(diào)度。圖3-2示出了具有高、低兩級調(diào)度的調(diào)度隊列模型。該模型與上一模型的主要區(qū)別在于如下兩個方面。截止時間的保證。件而被阻塞放棄處理機時，再重新調(diào)度。至16，其帶權(quán)周轉(zhuǎn)時間由2增至。理機重新分配給另一優(yōu)先權(quán)最高的進程。中，以及對性能要求較高的批處理和分時系統(tǒng)中。運行期間保持不變。一般地，優(yōu)先權(quán)是利用某一范圍內(nèi)的。又把該整數(shù)稱為優(yōu)先數(shù)。

　　

【正文】 ， 便轉(zhuǎn)向步驟 2；否則認為出錯 ， 因為它所需要的資源數(shù)已超過它所宣布的最大值 。 (2) 如果 Requesti［ j］ ≤Available［ j］ ， 便轉(zhuǎn)向步驟 (3)；否則 ， 表示尚無足夠資源 ， Pi須等待 。 第三章 處理機調(diào)度與死鎖 (3) 系統(tǒng)試探著把資源分配給進程 Pi， 并修改下面數(shù)據(jù)結(jié) 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， 以完成本次分配；否則 ， 將本次的試探分配作廢 ， 恢復(fù)原來的資源分配狀態(tài) ， 讓進程 Pi等待 。 第三章 處理機調(diào)度與死鎖 3. 安全性算法 (1) 設(shè)置兩個向量： ① 工作向量 Work: 它表示系統(tǒng)可提供給進程繼續(xù)運行所需的各類資源數(shù)目 ， 它含有 m個元素 ，在執(zhí)行安全算法開始時 ， Work∶ =Available。 ② Finish: 它表示系統(tǒng)是否有足夠的資源分配給進程 ， 使之運行完成 。 開始時先做 Finish［ i］ ∶ =false。 當有足夠資源分配給進程時 ， 再令 Finish［ i］ ∶ =true。 第三章 處理機調(diào)度與死鎖 (2) 從進程集合中找到一個能滿足下述條件的進程： ① Finish［ i］ =false。 ② Need［ i,j］ ≤Work［ j］ ； 若找到 ， 執(zhí)行步驟 (3)， 否則 ， 執(zhí)行步驟 (4)。 (3) 當進程 Pi獲得資源后 ， 可順利執(zhí)行 ， 直至完成 ， 并釋放出分配給它的資源 ， Work［ j］ ∶ = Work［ i］ +Allocation［ i,j］ 。 Finish［ i］ ∶ = true。 go to step 2。 (4) 如果所有進程的 Finish［ i］ =true都滿足 ， 則表示系統(tǒng)處于安全狀態(tài)；否則 ， 系統(tǒng)處于不安全狀態(tài) 。 第三章 處理機調(diào)度與死鎖 4. 銀行家算法之例 假定系統(tǒng)中有五個進程 ｛ P0, P1, P2, P3, P4｝ 和三類資源 ｛ A, B, C｝ ， 各種資源的數(shù)量分別為 7， 在 T0時刻的資源分配情況如圖 315 所示 。 圖 315 T0時刻的資源分配表 第三章 處理機調(diào)度與死鎖 (1) T0時刻的安全性： 圖 316 T0時刻的安全序列 第三章 處理機調(diào)度與死鎖 (2) P1請求資源： P1發(fā)出請求向量 Request1(1， 0， 2)，系統(tǒng)按銀行家算法進行檢查： ① Request1(1, 0, 2)≤Need1(1, 2, 2) ② Request1(1, 0, 2)≤Available1(3, 3, 2) ③ 系統(tǒng)先假定可為 P1分配資源 ， 并修改 Available, Allocation1和 Need1向量 ， 由此形成的資源變化情況如圖 315 中的圓括號所示 。 ④ 再利用安全性算法檢查此時系統(tǒng)是否安全。 第三章 處理機調(diào)度與死鎖 圖 317 P1申請資源時的安全性檢查 第三章 處理機調(diào)度與死鎖 (3) P4請求資源： P4發(fā)出請求向量 Request4(3， 3， 0)， 系 ① Request4(3, 3, 0)≤Need4(4, 3, 1)。 ② Request4(3, 3, 0) Available(2, 3, 0)， 讓 P4等待 。 (4) P0請求資源： P0發(fā)出請求向量 Requst0(0， 2， 0)， 系統(tǒng)按 ① Request0(0, 2, 0)≤Need 0(7, 4, 3)。 ② Request0(0, 2, 0)≤Available(2, 3, 0)。 ③ 系統(tǒng)暫時先假定可為 P0分配資源，并修改有關(guān)數(shù)據(jù)，如圖 318 所示。 ??第三章 處理機調(diào)度與死鎖 圖 318 為 P0分配資源后的有關(guān)資源數(shù)據(jù) 第三章 處理機調(diào)度與死鎖 死鎖的檢測與解除 死鎖的檢測 1. 資源分配圖 (Resource Allocation Graph) 圖 319 每類資源有多個時的情況 P1P2r1r2第三章 處理機調(diào)度與死鎖 (2) 凡屬于 E中的一個邊 e∈ E， 都連接著 P中的一個結(jié)點和 R中的一個結(jié)點 ， e={pi, rj}是資源請求邊 ， 由進程 pi指向資源 rj， 它表示進程 pi請求一個單位的 rj資源 。 e={rj, pi}是資源分配邊 ， 由資源 rj指向進程 pi, 它表示把一個單位的資源 rj分配給進程 pi。 第三章 處理機調(diào)度與死鎖 2. 死鎖定理 圖 320 資源分配圖的簡化 ( a ) ( b )P1( c )P1P2P1P2P2第三章 處理機調(diào)度與死鎖 3. 死鎖檢測中的數(shù)據(jù)結(jié)構(gòu) (1) 可利用資源向量 Available， 它表示了 m類資源中每一類資源的可用數(shù)目 。 (2) 把不占用資源的進程 (向量 Allocation∶ =0)記入 L表中 ， 即 Li∪ L。 (3) 從進程集合中找到一個 Requesti≤Work的進程 ， 做如下處理： ① 將其資源分配圖簡化 ， 釋放出資源 ， 增加工作向量Work∶ =Work+Allocationi。 ② 將它記入 L表中 。 第三章 處理機調(diào)度與死鎖 (4) 若不能把所有進程都記入 L表中 ， 便表明系統(tǒng)狀態(tài) S的資源分配圖是不可完全簡化的 。 因此 ， 該系統(tǒng)狀態(tài)將發(fā)生死鎖 。 Work ∶ =Available。 L ∶ = {Li|Allocationi=0∩Requesti=0} for all Li L do begin for all Requesti≤Work do begin Work ∶ =Work+Allocationi。 Li∪ L。 end end deadlock∶ = (L={p1, p2, …, p n})。 ?第三章 處理機調(diào)度與死鎖 死鎖的解除 (1) 剝奪資源。 (2) 撤消進程。 為把系統(tǒng)從死鎖狀態(tài)中解脫出來 ， 所花費的代價可表示為： R(S)min=min{Cui}+min{Cuj}+min{Cuk}+… 第三章 處理機調(diào)度與死鎖 圖 321 付出代價最小的死鎖解除方法 U1V12V13V1kW132W134W13kP2P3……P2P4… Pk…PkU2V21V22V2kW231W234W23k…P1P4… Pk…UkVk1Vk2VkkWk21Wk22Wk2k……Pk… …SP1(cu1) P1(cuk)P1(cud