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

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

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

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

4、源不足進(jìn)程運(yùn)行推進(jìn)的順序不合適資源分配不當(dāng)l死鎖產(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)系HPM&S3. 3. 一般解決方案一般解決方案l預(yù)防摒棄“請(qǐng)求和保持”條件進(jìn)程一次性地申請(qǐng)?jiān)谡麄€(gè)運(yùn)行過程所需的全部資源，若系統(tǒng)沒有足夠資源，則全部不分配給進(jìn)程摒棄“不可剝奪”條件已經(jīng)保持某些資源的進(jìn)程，當(dāng)提出新的資源要求而不能立即得到滿足時(shí)，必須釋放它已經(jīng)保持的所有資源 HPM&S3.

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

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

7、&S3. 3. 一般解決方案一般解決方案l銀行家算法（避免）安全性檢查算法(1)設(shè)置兩個(gè)工作向量Work=AVAILABLE;FINISH (2)從進(jìn)程集合中找到一個(gè)滿足下述條件的進(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)你對(duì)某一件事情沒有一個(gè)很好的解決

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

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

10、一僵局。此時(shí),只能靠人工干預(yù)來重新啟動(dòng)網(wǎng)絡(luò),解除死鎖。HPM&S6. 6. 存儲(chǔ)轉(zhuǎn)發(fā)死鎖存儲(chǔ)轉(zhuǎn)發(fā)死鎖l直接存儲(chǔ)轉(zhuǎn)發(fā)死鎖兩個(gè)節(jié)點(diǎn)彼此的所有緩沖區(qū)都裝滿了等待輸出到對(duì)方的分組，造成兩節(jié)點(diǎn)既不能接收也不能發(fā)送分組的現(xiàn)象。l間接存儲(chǔ)轉(zhuǎn)發(fā)死鎖在一組節(jié)點(diǎn)之間，某節(jié)點(diǎn)的所有緩沖區(qū)都裝滿了等待輸出到下一節(jié)點(diǎn)的分組，這種情況依次傳遞構(gòu)成循環(huán)，造成多節(jié)點(diǎn)間的死鎖。HPM&S6. 6. 存儲(chǔ)轉(zhuǎn)發(fā)死鎖存儲(chǔ)轉(zhuǎn)發(fā)死鎖l防止方法每個(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ū)

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

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