網(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é)論及參考文獻HPM&S活動背景活動背景l(fā)曲水流觴是中國古代很多文人雅士熱衷的一種游戲。大家坐在河渠兩旁，在上流放置酒杯，酒杯順流而下，停在誰的面前，誰就取杯飲酒并作詩一首，被大家所熟知的著名典

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

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

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

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

6、cusNeed提出請求REQUESTi，則銀行家算法按如下規(guī)則進行判斷：(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ù)原狀，進程等待。 HPM

7、&S3. 3. 一般解決方案一般解決方案l銀行家算法（避免）安全性檢查算法(1)設(shè)置兩個工作向量Work=AVAILABLE;FINISH (2)從進程集合中找到一個滿足下述條件的進程， FINISH=false; NEED=Work; 如找到，執(zhí)行(3)；否則，執(zhí)行(4) (3)設(shè)進程獲得資源，可順利執(zhí)行，直至完成，從而釋放資源。 Work+=ALLOCATION; Finish=true; GOTO (2) (4)如所有的進程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解除撤銷進程撤銷陷于死鎖的全部進程逐個撤銷陷于死鎖的

9、進程，直到死鎖解除剝奪資源從陷于死鎖的進程中逐個強迫放棄所占用的資源，直至死鎖消失； 從另外一些進程那里強行剝奪足夠數(shù)量的資源分配給死鎖進程，以解除死鎖狀態(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ā)生時,一組節(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ā)生嚴重的問題:該目的節(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é)作解決問題，個人勝利不代表團需要相互協(xié)作解決問題，個人勝利不代表團隊成功隊成功HPM&S9. 9. 參考文獻參考文獻