【正文】 需求 ， 使每個(gè)進(jìn)程都可順利地完成 。 進(jìn)程 P1總共要求 10臺(tái)磁帶機(jī) ， P2和 P3分別要求 4臺(tái)和 9臺(tái) 。 第三章 處理機(jī)調(diào)度與死鎖 利用銀行家算法避免死鎖 1. 銀行家算法中的數(shù)據(jù)結(jié)構(gòu) (1) 可利用資源向量 Available。 這是一個(gè) n m的矩陣 ， 它定義了系統(tǒng)中 n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì) m類(lèi)資源的最大需求 。 如果Allocation［ i,j］ =K， 則表示進(jìn)程 i當(dāng)前已分得 Rj類(lèi)資源的數(shù)目為 K。 Need［ i,j］ =Max［ i,j］ Allocation［ i,j］ 第三章 處理機(jī)調(diào)度與死鎖 2. 銀行家算法 設(shè) Requesti是進(jìn)程 Pi的請(qǐng)求向量 ， 如果 Requesti［ j］ =K，表示進(jìn)程 Pi需要 K個(gè) Rj類(lèi)型的資源 。 Allocation［ i,j］ ∶ =Allocation［ i,j］ +Requesti［ j］ 。 第三章 處理機(jī)調(diào)度與死鎖 3. 安全性算法 (1) 設(shè)置兩個(gè)向量： ① 工作向量 Work: 它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類(lèi)資源數(shù)目 ， 它含有 m個(gè)元素 ，在執(zhí)行安全算法開(kāi)始時(shí) ， Work∶ =Available。 第三章 處理機(jī)調(diào)度與死鎖 (2) 從進(jìn)程集合中找到一個(gè)能滿(mǎn)足下述條件的進(jìn)程： ① Finish［ i］ =false。 go to step 2。 ④ 再利用安全性算法檢查此時(shí)系統(tǒng)是否安全。 ② Request0(0, 2, 0)≤Available(2, 3, 0)。 第三章 處理機(jī)調(diào)度與死鎖 2. 死鎖定理 圖 320 資源分配圖的簡(jiǎn)化 ( a ) ( b )P1( c )P1P2P1P2P2第三章 處理機(jī)調(diào)度與死鎖 3. 死鎖檢測(cè)中的數(shù)據(jù)結(jié)構(gòu) (1) 可利用資源向量 Available， 它表示了 m類(lèi)資源中每一類(lèi)資源的可用數(shù)目 。 第三章 處理機(jī)調(diào)度與死鎖 (4) 若不能把所有進(jìn)程都記入 L表中 ， 便表明系統(tǒng)狀態(tài) S的資源分配圖是不可完全簡(jiǎn)化的 。 Li∪ L。 為把系統(tǒng)從死鎖狀態(tài)中解脫出來(lá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)。 ?第三章 處理機(jī)調(diào)度與死鎖 死鎖的解除 (1) 剝奪資源。 Work ∶ =Available。 (3) 從進(jìn)程集合中找到一個(gè) Requesti≤Work的進(jìn)程 ， 做如下處理： ① 將其資源分配圖簡(jiǎn)化 ， 釋放出資源 ， 增加工作向量Work∶ =Work+Allocationi。 ??第三章 處理機(jī)調(diào)度與死鎖 圖 318 為 P0分配資源后的有關(guān)資源數(shù)據(jù) 第三章 處理機(jī)調(diào)度與死鎖 死鎖的檢測(cè)與解除 死鎖的檢測(cè) 1. 資源分配圖 (Resource Allocation Graph) 圖 319 每類(lèi)資源有多個(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資源 。 ② Request4(3, 3, 0) Available(2, 3, 0)， 讓 P4等待 。 第三章 處理機(jī)調(diào)度與死鎖 4. 銀行家算法之例 假定系統(tǒng)中有五個(gè)進(jìn)程 ｛ P0, P1, P2, P3, P4｝ 和三類(lèi)資源 ｛ A, B, C｝ ， 各種資源的數(shù)量分別為 7， 在 T0時(shí)刻的資源分配情況如圖 315 所示 。 (3) 當(dāng)進(jìn)程 Pi獲得資源后 ， 可順利執(zhí)行 ， 直至完成 ， 并釋放出分配給它的資源 ， Work［ j］ ∶ = Work［ i］ +Allocation［ i,j］ 。 開(kāi)始時(shí)先做 Finish［ i］ ∶ =false。 (4) 系統(tǒng)執(zhí)行安全性算法 ， 檢查此次資源分配后 ， 系統(tǒng)是否處于安全狀態(tài) 。 (2) 如果 Requesti［ j］ ≤Available［ j］ ， 便轉(zhuǎn)向步驟 (3)；否則 ， 表示尚無(wú)足夠資源 ， Pi須等待 。 這也是一個(gè) n m的矩陣 ， 用以表示每一個(gè)進(jìn)程尚需的各類(lèi)資源數(shù) 。 (3) 分配矩陣 Allocation。 如果Available［ j］ =K， 則表示系統(tǒng)中現(xiàn)有 Rj類(lèi)資源 K個(gè) 。 例如 ， 在 T0時(shí)刻以后 ， P3又請(qǐng)求 1臺(tái)磁帶機(jī) ， 若此時(shí)系統(tǒng)把剩余 3臺(tái)中的 1臺(tái)分配給 P3， 則系統(tǒng)便進(jìn)入不安全狀態(tài) 。 第三章 處理機(jī)調(diào)度與死鎖 2. 我們通過(guò)一個(gè)例子來(lái)說(shuō)明安全性 。 第三章 處理機(jī)調(diào)度與死鎖 預(yù)防死鎖的方法 預(yù)防死鎖 1. 摒棄“請(qǐng)求和保持”條件 2. 摒棄“不剝奪”條件 3. 摒棄“環(huán)路等待”條件 第三章 處理機(jī)調(diào)度與死鎖 系統(tǒng)安全狀態(tài) 1. 安全狀態(tài) 在避免死鎖的方法中 ， 允許進(jìn)程動(dòng)態(tài)地申請(qǐng)資源 ， 但系統(tǒng)在進(jìn)行資源分配之前 ， 應(yīng)先計(jì)算此次資源分配的安全性 。 第三章 處理機(jī)調(diào)度與死鎖 產(chǎn)生死鎖的必要條件 (1) 互斥條件 (2) 請(qǐng)求和保持條件 (3) 不剝奪條件 (4) 環(huán)路等待條件 第三章 處理機(jī)調(diào)度與死鎖 處理死鎖的基本方法 (1) 預(yù)防死鎖。 第三章 處理機(jī)調(diào)度與死鎖 1. 競(jìng)爭(zhēng)資源引起進(jìn)程死鎖 1) 2) 競(jìng)爭(zhēng)非剝奪性資源 3) 競(jìng)爭(zhēng)臨時(shí)性資源 第三章 處理機(jī)調(diào)度與死鎖 圖 312 I/O設(shè)備共享時(shí)的死鎖情況 R1R2P1P2第三章 處理機(jī)調(diào)度與死鎖 圖 313 進(jìn)程之間通信時(shí)的死鎖 S2P1S3P3S1P2第三章 處理機(jī)調(diào)度與死鎖 2. 進(jìn)程推進(jìn)順序不當(dāng)引起死鎖 1) 進(jìn)程推進(jìn)順序合法 圖 314 進(jìn)程推進(jìn)順序?qū)λ梨i的影響 P2R e l ( R1)P2R e l ( R2)P2R e q ( R1)P2R e q ( R2)P1R e q ( R1) P1R e q ( R2) P1R e l ( R1) P1R e l ( R2)①②③④D第三章 處理機(jī)調(diào)度與死鎖 2) 若并發(fā)進(jìn)程 P1和 P2按曲線(xiàn) ④ 所示的順序推進(jìn) ， 它們將進(jìn)入不安全區(qū) D內(nèi) 。 (2) 低效性。 在自調(diào)度方式中 ， 可采用在單處理機(jī)環(huán)境下所用的調(diào)度算法 ， 如先來(lái)先服務(wù) (FCFS)調(diào)度算法 、 最