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