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

1、HPM&S活動活動10 The Orange Game網(wǎng)絡(luò)中的路由和死鎖網(wǎng)絡(luò)中的路由和死鎖西安交通大學(xué)高效能建模與仿真研究小組2011年10本PPT的材料改編自項目Putting computers to work-AlgorithmsHPM&S 主要內(nèi)容主要內(nèi)容l橙子問題的描述l死鎖概念l一般解決方案l網(wǎng)絡(luò)路由l路由和死鎖l存儲轉(zhuǎn)發(fā)死鎖l重裝死鎖l結(jié)論及參考文獻(xiàn)HPM&S活動背景活動背景l(fā)曲水流觴是中國古代很多文人雅士熱衷的一種游戲。大家坐在河渠兩旁，在上流放置酒杯，酒杯順流而下，停在誰的面前，誰就取杯飲酒并作詩一首，被大家所熟知的著名典

2、故為：永和九年，晉代有名的大書法家、會稽內(nèi)史王羲之偕親朋謝安、孫綽等42人，在蘭亭修禊后，舉行飲酒賦詩的“曲水流觴”活動，引為千古佳話。l死鎖的根本原因是資源的競爭。在這個游戲里，酒杯和酒都可以看做資源。隨著游戲的進(jìn)行，酒杯會逐漸聚到下游，上游人有酒沒酒杯，下游人有酒杯沒酒，如果都不釋放資源就形成死鎖。HPM&S1. 1. 橙子問題的描述橙子問題的描述l游戲右圖是6小孩坐成一個圓圈，他們擁有11個橙子。將孩子和橙子做標(biāo)記，一個字母對應(yīng)一個孩子、兩個橙子。初始小孩不能持有他們對應(yīng)的橙子。l目標(biāo)孩子們通過傳遞橙子，使每個孩子最終持有他們相應(yīng)的橙子HPM&S1. 1. 橙子問題的描述

3、橙子問題的描述l橙子傳遞規(guī)則小孩一只手只能拿一個橙子橙子只能經(jīng)由空手傳遞給鄰居l問題小孩們很快就會發(fā)現(xiàn)，如果他們“貪婪”(一旦得到自己的橙子就不放手)，那么該組可能永遠(yuǎn)無法實現(xiàn)其目標(biāo)。在該游戲中，只有當(dāng)每個人都有自己的橙子，這個問題才被真正解決。HPM&S2. 2. 死鎖概念死鎖概念l死鎖多個進(jìn)程在執(zhí)行過程中，因爭奪資源而造成的一種互相等待的現(xiàn)象，若無外力作用，它們都將無法推進(jìn)下去HPM&S2. 2. 死鎖概念死鎖概念多個進(jìn)程在執(zhí)行過程中，因爭奪資源而造成的一種互相等待的現(xiàn)象，若無外力作用，它們都將無法推進(jìn)下去HPM&S2. 2. 死鎖概念死鎖概念l死鎖產(chǎn)生的原因系統(tǒng)資

4、源不足進(jìn)程運行推進(jìn)的順序不合適資源分配不當(dāng)l死鎖產(chǎn)生的四個必要條件資源互斥：一個資源每次只能被一個進(jìn)程使用請求與保持：一個進(jìn)程因請求資源而阻塞時，對已獲得的資源 保持不釋放不可剝奪（不可搶占）：進(jìn)程已獲得的資源，在未使用完之前，不能強行剝奪循環(huán)等待：若干進(jìn)程之間形成一種頭尾相接的循環(huán)等待資源關(guān)系HPM&S3. 3. 一般解決方案一般解決方案l預(yù)防摒棄“請求和保持”條件進(jìn)程一次性地申請在整個運行過程所需的全部資源，若系統(tǒng)沒有足夠資源，則全部不分配給進(jìn)程摒棄“不可剝奪”條件已經(jīng)保持某些資源的進(jìn)程，當(dāng)提出新的資源要求而不能立即得到滿足時，必須釋放它已經(jīng)保持的所有資源 HPM&S3.

5、3. 一般解決方案一般解決方案l預(yù)防摒棄“環(huán)路等待”條件資源按某種規(guī)則系統(tǒng)中的所有資源統(tǒng)一編號，申請時必須以上升的次序。系統(tǒng)要求申請進(jìn)程： 對它所必須使用的且屬于同一類的所有資源，必須一次申請完在申請不同類資源時，必須按各類設(shè)備的編號依次申請HPM&S3. 3. 一般解決方案一般解決方案l銀行家算法（避免）基本思想分配資源之前,判斷系統(tǒng)是否是安全的;若是,才分配。它是最具有代表性的避免死鎖的算法。數(shù)據(jù)結(jié)構(gòu)可利用資源向量Available 最大需求矩陣Max分配矩陣Allocation需求矩陣NeedHPM&S3. 3. 一般解決方案一般解決方案l銀行家算法（避免）算法描述設(shè)進(jìn)程

6、cusNeed提出請求REQUESTi，則銀行家算法按如下規(guī)則進(jìn)行判斷：(1)如果REQUESTcusNeedi=NEEDcusNeedi，則轉(zhuǎn)(2)；否則，出錯。(2)如果REQUESTcusNeedi=AVAILABLEcusNeedi。則轉(zhuǎn)(3)；否則，出錯。(3)系統(tǒng)試探分配資源，修改相關(guān)數(shù)據(jù)： AVAILABLEi-=REQUESTcusNeedi; ALLOCATIONcusNeedi+=REQUESTcusNeedi; NEEDcusNeedi-=REQUESTcusNeedi; (4)系統(tǒng)執(zhí)行安全性檢查，如安全，則分配成立；否則試探險性分配作廢，系統(tǒng)恢復(fù)原狀，進(jìn)程等待。 HPM

7、&S3. 3. 一般解決方案一般解決方案l銀行家算法（避免）安全性檢查算法(1)設(shè)置兩個工作向量Work=AVAILABLE;FINISH (2)從進(jì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)不安全。 HPM&S3. 3. 一般解決方案一般解決方案l鴕鳥算法概念當(dāng)你對某一件事情沒有一個很好的解決

8、方法時，那就忽略 它 ， 這 樣 的 算 法 稱 為 “ 鴕 鳥 算 法 “ （ O s t r i c h algorithm）。當(dāng)系統(tǒng)發(fā)生死鎖時不會對用戶造成多大影響，或系統(tǒng)很少發(fā)生死鎖的場合采用允許死鎖發(fā)生的鴕鳥算法，這樣一來可能開銷比不允許發(fā)生死鎖及檢測和解除死鎖的小。大多數(shù)操作系統(tǒng)，包括UNIX，MINUX和windows，處理死鎖問題的辦法僅僅是忽略它。其假設(shè)前提是大多數(shù)用戶寧可在極偶然的情況下發(fā)生死鎖也不愿接受性能的損失。所以鴕鳥算法，是平衡性能和復(fù)雜性而選擇的一種方法。 HPM&S3. 3. 一般解決方案一般解決方案l解除撤銷進(jìn)程撤銷陷于死鎖的全部進(jìn)程逐個撤銷陷于死鎖的

9、進(jìn)程，直到死鎖解除剝奪資源從陷于死鎖的進(jìn)程中逐個強迫放棄所占用的資源，直至死鎖消失； 從另外一些進(jìn)程那里強行剝奪足夠數(shù)量的資源分配給死鎖進(jìn)程，以解除死鎖狀態(tài)HPM&S4. 4. 網(wǎng)絡(luò)路由網(wǎng)絡(luò)路由l概念確定分組從發(fā)送發(fā)到接收方傳送過程中所經(jīng)歷的路徑或者路由器l常見路由算法靜態(tài)路由算法動態(tài)路由算法：鏈路狀態(tài)算法、距離向量路由算法HPM&S4. 4. 網(wǎng)絡(luò)路由網(wǎng)絡(luò)路由l鏈路狀態(tài)算法HPM&S5. 5. 路由和死鎖路由和死鎖死鎖是網(wǎng)絡(luò)中最容易發(fā)生的故障之一,即使在網(wǎng)絡(luò)負(fù)荷不很重時也會發(fā)生。死鎖發(fā)生時,一組節(jié)點由于沒有空閑緩沖區(qū)而無法接收和轉(zhuǎn)發(fā)分組,節(jié)點之間相互等待,并一直保持這

10、一僵局。此時,只能靠人工干預(yù)來重新啟動網(wǎng)絡(luò),解除死鎖。HPM&S6. 6. 存儲轉(zhuǎn)發(fā)死鎖存儲轉(zhuǎn)發(fā)死鎖l直接存儲轉(zhuǎn)發(fā)死鎖兩個節(jié)點彼此的所有緩沖區(qū)都裝滿了等待輸出到對方的分組，造成兩節(jié)點既不能接收也不能發(fā)送分組的現(xiàn)象。l間接存儲轉(zhuǎn)發(fā)死鎖在一組節(jié)點之間，某節(jié)點的所有緩沖區(qū)都裝滿了等待輸出到下一節(jié)點的分組，這種情況依次傳遞構(gòu)成循環(huán)，造成多節(jié)點間的死鎖。HPM&S6. 6. 存儲轉(zhuǎn)發(fā)死鎖存儲轉(zhuǎn)發(fā)死鎖l防止方法每個節(jié)點設(shè)置M+1個緩沖區(qū),并以0到M編號。 M為通信子網(wǎng)的直徑,即從任一源節(jié)點到任一目的節(jié)點間的最大鏈路段數(shù)。每個分組都是按照編號遞增規(guī)則分配緩沖區(qū)。節(jié)點之間不會相互等待空閑緩沖區(qū)

11、而發(fā)生死鎖現(xiàn)象。使每個分組上都攜帶一個全局性的惟一的時間戳,每個節(jié)點要為每條輸入鏈路保留一個特殊的接收緩沖區(qū),而其它緩沖區(qū)均可用于存放中轉(zhuǎn)分組。 HPM&S7. 7. 重裝死鎖重裝死鎖假設(shè)發(fā)給一個端系統(tǒng)的報文很長,被源節(jié)點拆成若干個分組發(fā)送,目的節(jié)點要將分組重新裝配成報文遞交給目的端系統(tǒng)若目的節(jié)點用于重裝報文的緩沖區(qū)空間有限,而且它無法知道正在接收的報文究竟被拆成多少個分組此時,就可能發(fā)生嚴(yán)重的問題:該目的節(jié)點用完了它的緩沖空間,但它又不能將尚未拼裝完整的報文遞送給目的端系統(tǒng),而鄰節(jié)點仍在不斷地向它傳送分組,但它卻無法接收。 HPM&S7. 7. 重裝死鎖重裝死鎖HPM&

12、;S7. 7. 重裝死鎖重裝死鎖l避免方法允許目的節(jié)點將不完整的報文遞交給目的端系統(tǒng)一個不能完整重裝的報文能被檢測出來,并要求發(fā)送該報文的源端系統(tǒng)重新傳送為每個節(jié)點配備一個后備緩沖空間,用以暫存不完整的報文HPM&S8. 8. 結(jié)論結(jié)論l主要結(jié)論當(dāng)對資源的需求有依賴關(guān)系時，有可能出現(xiàn)當(dāng)對資源的需求有依賴關(guān)系時，有可能出現(xiàn)“死鎖死鎖”的情況的情況一個在任何人繼續(xù)下去之前，死鎖都一直存在任何人繼續(xù)下去之前，死鎖都一直存在，因此，有些人總是必須返回的在，因此，有些人總是必須返回的 需要相互協(xié)作解決問題，個人勝利不代表團(tuán)需要相互協(xié)作解決問題，個人勝利不代表團(tuán)隊成功隊成功HPM&S9. 9. 參考文獻(xiàn)參考文獻(xiàn)