網(wǎng)絡(luò)中的路由和死鎖

活動(dòng)10TheOrangeGame

——網(wǎng)絡(luò)中的路由和死鎖西安交通大學(xué)高效能建模與仿真研究小組2011年10本PPT的材料改編自項(xiàng)目Puttingcomputerstowork-Algorithms

主要內(nèi)容橙子問(wèn)題的描述死鎖概念一般解決方案網(wǎng)絡(luò)路由路由和死鎖存儲(chǔ)轉(zhuǎn)發(fā)死鎖重裝死鎖結(jié)論及參考文獻(xiàn)活動(dòng)背景曲水流觴是中國(guó)古代很多文人雅士熱衷的一種游戲。大家坐在河渠兩旁，在上流放置酒杯，酒杯順流而下，停在誰(shuí)的面前，誰(shuí)就取杯飲酒并作詩(shī)一首，被大家所熟知的著名典故為：永和九年，晉代有名的大書(shū)法家、會(huì)稽內(nèi)史王羲之偕親朋謝安、孫綽等42人，在蘭亭修禊后，舉行飲酒賦詩(shī)的“曲水流觴”活動(dòng)，引為千古佳話(huà)。死鎖的根本原因是資源的競(jìng)爭(zhēng)。在這個(gè)游戲里，酒杯和酒都可以看做資源。隨著游戲的進(jìn)行，酒杯會(huì)逐漸聚到下游，上游人有酒沒(méi)酒杯，下游人有酒杯沒(méi)酒，如果都不釋放資源就形成死鎖。1.橙子問(wèn)題的描述游戲右圖是6小孩坐成一個(gè)圓圈，他們擁有11個(gè)橙子。將孩子和橙子做標(biāo)記，一個(gè)字母對(duì)應(yīng)一個(gè)孩子、兩個(gè)橙子。初始小孩不能持有他們對(duì)應(yīng)的橙子。目標(biāo)孩子們通過(guò)傳遞橙子，使每個(gè)孩子最終持有他們相應(yīng)的橙子1.橙子問(wèn)題的描述橙子傳遞規(guī)則小孩一只手只能拿一個(gè)橙子橙子只能經(jīng)由空手傳遞給鄰居問(wèn)題小孩們很快就會(huì)發(fā)現(xiàn)，如果他們“貪婪”(一旦得到自己的橙子就不放手)，那么該組可能永遠(yuǎn)無(wú)法實(shí)現(xiàn)其目標(biāo)。在該游戲中，只有當(dāng)每個(gè)人都有自己的橙子，這個(gè)問(wèn)題才被真正解決。2.死鎖概念死鎖多個(gè)進(jìn)程在執(zhí)行過(guò)程中，因爭(zhēng)奪資源而造成的一種互相等待的現(xiàn)象，若無(wú)外力作用，它們都將無(wú)法推進(jìn)下去2.死鎖概念多個(gè)進(jìn)程在執(zhí)行過(guò)程中，因爭(zhēng)奪資源而造成的一種互相等待的現(xiàn)象，若無(wú)外力作用，它們都將無(wú)法推進(jìn)下去2.死鎖概念死鎖產(chǎn)生的原因系統(tǒng)資源不足進(jìn)程運(yùn)行推進(jìn)的順序不合適資源分配不當(dāng)死鎖產(chǎn)生的四個(gè)必要條件資源互斥：一個(gè)資源每次只能被一個(gè)進(jìn)程使用請(qǐng)求與保持：一個(gè)進(jìn)程因請(qǐng)求資源而阻塞時(shí)，對(duì)已獲得的資源

保持不釋放不可剝奪（不可搶占）：進(jìn)程已獲得的資源，在未使用完之前，不能強(qiáng)行剝奪循環(huán)等待：若干進(jìn)程之間形成一種頭尾相接的循環(huán)等待資源關(guān)系3.一般解決方案預(yù)防摒棄“請(qǐng)求和保持”條件進(jìn)程一次性地申請(qǐng)?jiān)谡麄€(gè)運(yùn)行過(guò)程所需的全部資源，若系統(tǒng)沒(méi)有足夠資源，則全部不分配給進(jìn)程摒棄“不可剝奪”條件已經(jīng)保持某些資源的進(jìn)程，當(dāng)提出新的資源要求而不能立即得到滿(mǎn)足時(shí)，必須釋放它已經(jīng)保持的所有資源

3.一般解決方案預(yù)防摒棄“環(huán)路等待”條件資源按某種規(guī)則系統(tǒng)中的所有資源統(tǒng)一編號(hào)，申請(qǐng)時(shí)必須以上升的次序。系統(tǒng)要求申請(qǐng)進(jìn)程：對(duì)它所必須使用的且屬于同一類(lèi)的所有資源，必須一次申請(qǐng)完在申請(qǐng)不同類(lèi)資源時(shí)，必須按各類(lèi)設(shè)備的編號(hào)依次申請(qǐng)3.一般解決方案銀行家算法（避免）基本思想分配資源之前,判斷系統(tǒng)是否是安全的;若是,才分配。它是最具有代表性的避免死鎖的算法。數(shù)據(jù)結(jié)構(gòu)可利用資源向量Available最大需求矩陣Max分配矩陣Allocation需求矩陣Need3.一般解決方案銀行家算法（避免）算法描述設(shè)進(jìn)程cusNeed提出請(qǐng)求REQUEST[i]，則銀行家算法按如下規(guī)則進(jìn)行判斷：(1)如果REQUEST[cusNeed][i]<=NEED[cusNeed][i]，則轉(zhuǎn)(2)；否則，出錯(cuò)。(2)如果REQUEST[cusNeed][i]<=AVAILABLE[cusNeed][i]。則轉(zhuǎn)(3)；否則，出錯(cuò)。(3)系統(tǒng)試探分配資源，修改相關(guān)數(shù)據(jù)：

AVAILABLE[i]-=REQUEST[cusNeed][i];

ALLOCATION[cusNeed][i]+=REQUEST[cusNeed][i];

NEED[cusNeed][i]-=REQUEST[cusNeed][i];(4)系統(tǒng)執(zhí)行安全性檢查，如安全，則分配成立；否則試探險(xiǎn)性分配作廢，系統(tǒng)恢復(fù)原狀，進(jìn)程等待。3.一般解決方案銀行家算法（避免）安全性檢查算法

(1)設(shè)置兩個(gè)工作向量Work=AVAILABLE;FINISH

(2)從進(jìn)程集合中找到一個(gè)滿(mǎn)足下述條件的進(jìn)程，

FINISH==false;

NEED<=Work;

如找到，執(zhí)行(3)；否則，執(zhí)行(4)

(3)設(shè)進(jìn)程獲得資源，可順利執(zhí)行，直至完成，從而釋放資源。

Work+=ALLOCATION;Finish=true;

GOTO(2)

(4)如所有的進(jìn)程Finish=true，則表示安全；否則系統(tǒng)不安全。3.一般解決方案鴕鳥(niǎo)算法概念當(dāng)你對(duì)某一件事情沒(méi)有一個(gè)很好的解決方法時(shí)，那就忽略它，這樣的算法稱(chēng)為“鴕鳥(niǎo)算法“（Ostrichalgorithm）。當(dāng)系統(tǒng)發(fā)生死鎖時(shí)不會(huì)對(duì)用戶(hù)造成多大影響，或系統(tǒng)很少發(fā)生死鎖的場(chǎng)合采用允許死鎖發(fā)生的鴕鳥(niǎo)算法，這樣一來(lái)可能開(kāi)銷(xiāo)比不允許發(fā)生死鎖及檢測(cè)和解除死鎖的小。大多數(shù)操作系統(tǒng)，包括UNIX，MINUX和windows，處理死鎖問(wèn)題的辦法僅僅是忽略它。其假設(shè)前提是大多數(shù)用戶(hù)寧可在極偶然的情況下發(fā)生死鎖也不愿接受性能的損失。所以鴕鳥(niǎo)算法，是平衡性能和復(fù)雜性而選擇的一種方法。3.一般解決方案解除撤銷(xiāo)進(jìn)程

撤銷(xiāo)陷于死鎖的全部進(jìn)程逐個(gè)撤銷(xiāo)陷于死鎖的進(jìn)程，直到死鎖解除剝奪資源從陷于死鎖的進(jìn)程中逐個(gè)強(qiáng)迫放棄所占用的資源，直至死鎖消失；從另外一些進(jìn)程那里強(qiáng)行剝奪足夠數(shù)量的資源分配給死鎖進(jìn)程，以解除死鎖狀態(tài)4.網(wǎng)絡(luò)路由概念確定分組從發(fā)送發(fā)到接收方傳送過(guò)程中所經(jīng)歷的路徑或者路由器常見(jiàn)路由算法靜態(tài)路由算法動(dòng)態(tài)路由算法：鏈路狀態(tài)算法、距離向量路由算法4.網(wǎng)絡(luò)路由鏈路狀態(tài)算法5.路由和死鎖死鎖是網(wǎng)絡(luò)中最容易發(fā)生的故障之一,即使在網(wǎng)絡(luò)負(fù)荷不很重時(shí)也會(huì)發(fā)生。死鎖發(fā)生時(shí),一組節(jié)點(diǎn)由于沒(méi)有空閑緩沖區(qū)而無(wú)法接收和轉(zhuǎn)發(fā)分組,節(jié)點(diǎn)之間相互等待,并一直保持這一僵局。此時(shí),只能靠人工干預(yù)來(lái)重新啟動(dòng)網(wǎng)絡(luò),解除死鎖。6.存儲(chǔ)轉(zhuǎn)發(fā)死鎖直接存儲(chǔ)轉(zhuǎn)發(fā)死鎖兩個(gè)節(jié)點(diǎn)彼此的所有緩沖區(qū)都裝滿(mǎn)了等待輸出到對(duì)方的分組，造成兩節(jié)點(diǎn)既不能接收也不能發(fā)送分組的現(xiàn)象。間接存儲(chǔ)轉(zhuǎn)發(fā)死鎖在一組節(jié)點(diǎn)之間，某節(jié)點(diǎn)的所有緩沖區(qū)都裝滿(mǎn)了等待輸出到下一節(jié)點(diǎn)的分組，這種情況依次傳遞構(gòu)成循環(huán)，造成多節(jié)點(diǎn)間的死鎖。6.存儲(chǔ)轉(zhuǎn)發(fā)死鎖防止方法每個(gè)節(jié)點(diǎn)設(shè)置M+1個(gè)緩沖區(qū),并以0到M編號(hào)。M為通信子網(wǎng)的直徑,即從任一源節(jié)點(diǎn)到任一目的節(jié)點(diǎn)間的最大鏈路段數(shù)。每個(gè)分組都是按照編號(hào)遞增規(guī)則分配緩沖區(qū)。節(jié)點(diǎn)之間不會(huì)相互等待空閑緩沖區(qū)而發(fā)生死鎖現(xiàn)象。使每個(gè)分組上都攜帶一個(gè)全局性的惟一的"時(shí)間戳",每個(gè)節(jié)點(diǎn)要為每條輸入鏈路保留一個(gè)特殊的接收緩沖區(qū),而其它緩沖區(qū)均可用于存放中轉(zhuǎn)分組。7.重裝死鎖假設(shè)發(fā)給一個(gè)端系統(tǒng)的報(bào)文很長(zhǎng),被源節(jié)點(diǎn)拆成若干個(gè)分組發(fā)送,目的節(jié)點(diǎn)要將分組重新裝配成報(bào)文遞交給目的端系統(tǒng)若目的節(jié)點(diǎn)用于重裝報(bào)文的緩沖區(qū)空間有限,而且它無(wú)法知道正在接收的報(bào)文究竟被拆成多少個(gè)分組此時(shí),就可能發(fā)生嚴(yán)重的問(wèn)題:該目的節(jié)點(diǎn)用完了它的緩沖空間,但它又不能將尚未拼裝完整的報(bào)文遞送給目的端系統(tǒng),而鄰節(jié)點(diǎn)仍在不斷地向它傳送分組,但它卻無(wú)法接收。7.重裝死鎖7.重裝死鎖避免方法允許目的節(jié)點(diǎn)將不完整的報(bào)文遞交給目的端系統(tǒng)一個(gè)不能完整重裝的報(bào)文能被檢測(cè)出來(lái),并要求發(fā)送該報(bào)文的源端系統(tǒng)重新傳送為每個(gè)節(jié)點(diǎn)配備一個(gè)后備緩沖空間,用以暫存不完整的報(bào)文8.結(jié)論主要結(jié)論當(dāng)對(duì)資源的需求有依賴(lài)關(guān)系時(shí)，有可能出現(xiàn)“死鎖”的情況一個(gè)在任何人繼續(xù)下去之前，死鎖都一直存在，因此，有些人總是必須返回的需要相互協(xié)作解決問(wèn)題，個(gè)人勝利不代表團(tuán)隊(duì)成功9.參考文獻(xiàn)湯子瀛，