09第九章-網(wǎng)絡(luò)與分布式操作系統(tǒng)(2)(編輯修改稿)
2025-08-31 07:45 本頁面
【文章內(nèi)容簡(jiǎn)介】 ssed by Reference 死鎖處理 ? 死鎖預(yù)防 ? 全局資源排序 ? 基于 “ 優(yōu)先權(quán) /回退 ” 方式的時(shí)間戳 ? 死鎖避免 ? 分布銀行家算法 ? 死鎖檢測(cè) ? 對(duì)每個(gè)資源類型的實(shí)例 ? 集中方式 ? 分布方式 死鎖預(yù)防 ? 死鎖預(yù)防 ? 全局資源排序 + 請(qǐng)求排序 ? 給每個(gè)資源賦予一個(gè)唯一的整數(shù) . ? 如果一個(gè)進(jìn)程沒持有資源編號(hào)等于或大于 i 的資源，則可以申請(qǐng)編號(hào)為 i 的資源 . ? 優(yōu)點(diǎn)和缺點(diǎn) ? simple implementation ? little overhead ? difficulty in global resource ordering ? inconvenient for distributed processes to abide by the protocol 優(yōu)先級(jí)死鎖預(yù)防 ? 每個(gè)進(jìn)程 Pi被賦予一個(gè)唯一的優(yōu)先數(shù) ? 優(yōu)先數(shù)用來決定進(jìn)程 Pi 是否應(yīng)該等待進(jìn)程 Pj。 ? 如果 pri(Pi)pri(Pj ), Pi 等待 。 ? 否則 Pi 回退 . ? The scheme is deadlockfree. ? For every edge Pi ? Pj in the waitfor graph, Pi has a higher priority than Pj. Thus a cycle cannot exist. ? Possibility of starvationlow priority process may always be rolled back. ? Resolve: use timestamp instead of priority 等 死 (waitdie) ? 基于非剝奪策略。 ? 當(dāng)一個(gè)進(jìn)程 Pi要求另外一個(gè)進(jìn)程 Pj保持的資源時(shí)，Pi被允許等待，僅當(dāng)它具有比 Pj更小的郵戳?xí)r間，即 Pi是比 Pj更老，否則 Pi回退。 ? 例如，設(shè)進(jìn)程 P1, P2, P3分別具有郵戳?xí)r間 5, 10, 15。 ? 如果 P1要求 P2占用的資源 , 則 P1等待。 ? 如果 P3要求 P2占用的資源 , 則 P3回退。 ? 等待邊 ? (更老 )Pi?Pj(更年輕 ) 傷 等 (woundwait) ? 基于剝奪策略，是等－死的改版。 ? 當(dāng)進(jìn)程 Pi要求進(jìn)程 Pj當(dāng)前所保持的資源時(shí)，則 Pi獲準(zhǔn)等待的條件是它具有比 Pj更大的郵戳?xí)r間，即 Pi比 Pj更年輕，否則 Pj回退，即 Pj被 Pi所傷。 ? 例如 , 設(shè)進(jìn)程 P1, P2, P3分別具有郵戳?xí)r間 5, 10, 15。 ? 如果 P1要求 P2所占用的資源，則將剝奪 P2的資源給P1， P2回退； ? 如果 P3要求 P2占用的資源，則 P3等待。 ? 等待邊 ? (更年輕 ) Pi?Pj (更老 ) 死鎖避免 ? 銀行家算法 – 指定系統(tǒng)中某個(gè)進(jìn)程為銀行家 ， 由它保持執(zhí)行銀行家算法所必需的信息 。 – 銀行家負(fù)責(zé)系統(tǒng)中資源的分配。 ? 優(yōu)點(diǎn)和缺點(diǎn) – easy implementation – may incur too much overhead – possibility of bottleneck – if banker fails, the algorithm fails 死鎖檢測(cè) ? 每個(gè)站點(diǎn)保持一個(gè)局部等待圖。 ? 站點(diǎn)：所有進(jìn)程 (或者持有或者請(qǐng)求 )本地站點(diǎn)的資源。 站點(diǎn) A P1 P2 P3 P5 P2 P4 P3 站點(diǎn) B 死鎖檢測(cè) (Cont.) ? 全局等待圖是所有局部等待圖的合并。 P1 P2 P3 P5 P4 站點(diǎn) A 和站點(diǎn) B的全局等待圖 資源管理 集中方式 ? 中央資源管理者負(fù)責(zé)系統(tǒng)中所有資源的分配 . 系統(tǒng)資源表 資源類型 資源數(shù)量 物理位置 物理特性 分配狀態(tài) … … … … … 集中方式 (Cont.) ? 優(yōu)點(diǎn) ? 可以做出全局優(yōu)化的資源分配策略 。 ? 系統(tǒng)擴(kuò)充和裁減容易 ? 這只需要在系統(tǒng)資源分配表中增加一個(gè)新項(xiàng)目或刪除一個(gè)舊項(xiàng)目 ? 減少了資源管理算法的開銷 ? 除中央資源管理者外，其它站點(diǎn)不參與資源決策事務(wù) 。 集中方式 (Cont.) ? 缺點(diǎn) ? 可靠性低 ? 因?yàn)橐坏┵Y源管理者失效，則整個(gè)系統(tǒng)癱瘓。 ? 盡管引入多個(gè)資源管理者可以克服這一缺點(diǎn)，但保持多副本的一致性是困難的。 ? 中央資源管理者可能成為系統(tǒng)的瓶頸 ? 由于中央資源管理者的存在，使整個(gè)系統(tǒng)失去了自治性。 分布方式 ? 每個(gè)站點(diǎn)都有一個(gè)局部資源表 ， 用于記載屬于該站點(diǎn)的局部資源 ? 當(dāng)一個(gè)站點(diǎn)要申請(qǐng)局部資源時(shí) ， 它可由本地得到。 ? 當(dāng)一個(gè)站點(diǎn)要申請(qǐng)全局資源時(shí)，它向其它站點(diǎn)發(fā)送申請(qǐng)命令 ， 其它站點(diǎn)根據(jù)情況做出分配決策。 分布方式 (Cont.) ? 優(yōu)點(diǎn) ? 可靠性高 ? 因?yàn)槿魏我粋€(gè)站點(diǎn)、資源或服務(wù)的失效通常不會(huì)影響整個(gè)系統(tǒng) ? 每個(gè)站點(diǎn)具有較高的自治性 ? 它可以將其所擁有的資
外語相關(guān)推薦
鄂ICP備17016276號(hào)-1