隨著網(wǎng)絡(luò)技術(shù)的不斷發(fā)展,分布式系統(tǒng)得到了廣泛的研究與應(yīng)用。互斥問題是分布式系統(tǒng)設(shè)計時的關(guān)鍵問題,它保證并發(fā)進程正確的訪問臨界資源。由于分布式系統(tǒng)中網(wǎng)絡(luò)帶寬有限,且臨界資源的數(shù)目是固定的,因此研究設(shè)計網(wǎng)絡(luò)負載輕、臨界資源利用率高的分布式互斥算法具有重要的意義。 分布式互斥算法根據(jù)實現(xiàn)互斥的策略可以分為基于令牌的算法和基于許可的算法,本文分別介紹了這兩類中的典型算法,并分析比較了它們的優(yōu)缺點。令牌算法實現(xiàn)簡單,比較適用于環(huán)形網(wǎng)絡(luò)和無線網(wǎng)絡(luò)。但是該算法需要發(fā)送消息較多,且同步延遲較大,臨界資源利用率不高。對此本文提出一種新的基于令牌的互斥算法,新的算法中通過采用基于令牌請求的策略,減少了消息數(shù),并且令牌不再按照邏輯環(huán)的順序循環(huán)傳遞,而是根據(jù)節(jié)點請求順序傳遞,降低了同步延遲。在基于許可的算法中,本文詳細介紹了Maekawa算法。Maekawa算法首次提出了仲裁集的概念,互斥的范圍從以往算法的全局互斥縮小為局部互斥,顯著的降低了發(fā)送消息的數(shù)量。但是Maekawa算法實現(xiàn)較為復(fù)雜,且同步延遲較多。針對Maekawa算法的缺點,本文對其進行了改進。改進后的算法將Maekawa仲裁集與令牌策略進行結(jié)合...

【文章頁數(shù)】：66 頁

【學(xué)位級別】：碩士

【文章目錄】：
摘要
Abstract
第1章 緒論
    1.1 研究背景
        1.1.1 分布式系統(tǒng)概述
        1.1.2 分布式互斥問題
    1.2 分布式互斥算法分類
        1.2.1 按照互斥實現(xiàn)策略分類
        1.2.2 按照節(jié)點職能分類
        1.2.3 按照層次分類
    1.3 分布式互斥算法研究歷史與現(xiàn)狀
    1.4 論文組織結(jié)構(gòu)
第2章 主流分布式互斥算法介紹
    2.1 系統(tǒng)模型
    2.2 算法評價標準
        2.2.1 正確性評價
        2.2.2 算法性能評價
    2.3 分布式互斥算法介紹
        2.3.1 基于令牌傳遞的分布式互斥算法
        2.3.2 Lamport算法
        2.3.3 Richard&Agrawal算法
        2.3.4 Maekawa算法
    2.4 幾種分布式互斥算法的比較
    2.5 本章小結(jié)
第3章 一種新的基于令牌的分布式互斥算法
    3.1 構(gòu)造邏輯環(huán)
        3.1.1 旅行商問題
        3.1.2 利用改進的TSP求解算法構(gòu)建邏輯環(huán)
    3.2 算法描述
        3.2.1 算法步驟
        3.2.2 消息與數(shù)據(jù)結(jié)構(gòu)
        3.2.3 偽代碼描述
    3.3 算法正確性證明與性能分析
        3.3.1 正確性證明
        3.3.2 算法性能分析
    3.4 本章小結(jié)
第4章 改進的Maekawa算法
    4.1 Maekawa仲裁集算法示例
    4.2 改進算法
        4.2.1 改進算法描述
        4.2.2 算法步驟
        4.2.3 消息與數(shù)據(jù)結(jié)構(gòu)
        4.2.4 偽代碼描述
    4.3 算法正確性證明與性能分析
        4.3.1 正確性證明
        4.3.2 算法性能分析
    4.4 算法容錯性擴展
    4.5 本章小結(jié)
第5章 仿真實驗與結(jié)論
    5.1 基于令牌的互斥算法的仿真實驗
        5.1.1 實驗場景
        5.1.2 仿真實驗結(jié)果
    5.2 改進的Maekawa算法的仿真實驗
        5.2.1 實驗場景
        5.2.2 仿真實驗結(jié)果
    5.3 本章小結(jié)
第6章 總結(jié)與展望
    6.1 主要內(nèi)容
    6.2 今后的工作
參考文獻
攻讀碩士學(xué)位期間主要的研究成果
致謝



本文編號：3792112