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

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

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

【文章目錄】：
摘要
Abstract
第1章 緒論
    1.1 研究背景
        1.1.1 分布式系統(tǒng)概述
        1.1.2 分布式互斥問(wèn)題
    1.2 分布式互斥算法分類
        1.2.1 按照互斥實(shí)現(xiàn)策略分類
        1.2.2 按照節(jié)點(diǎn)職能分類
        1.2.3 按照層次分類
    1.3 分布式互斥算法研究歷史與現(xiàn)狀
    1.4 論文組織結(jié)構(gòu)
第2章 主流分布式互斥算法介紹
    2.1 系統(tǒng)模型
    2.2 算法評(píng)價(jià)標(biāo)準(zhǔn)
        2.2.1 正確性評(píng)價(jià)
        2.2.2 算法性能評(píng)價(jià)
    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 旅行商問(wèn)題
        3.1.2 利用改進(jìn)的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章 改進(jìn)的Maekawa算法
    4.1 Maekawa仲裁集算法示例
    4.2 改進(jìn)算法
        4.2.1 改進(jìn)算法描述
        4.2.2 算法步驟
        4.2.3 消息與數(shù)據(jù)結(jié)構(gòu)
        4.2.4 偽代碼描述
    4.3 算法正確性證明與性能分析
        4.3.1 正確性證明
        4.3.2 算法性能分析
    4.4 算法容錯(cuò)性擴(kuò)展
    4.5 本章小結(jié)
第5章 仿真實(shí)驗(yàn)與結(jié)論
    5.1 基于令牌的互斥算法的仿真實(shí)驗(yàn)
        5.1.1 實(shí)驗(yàn)場(chǎng)景
        5.1.2 仿真實(shí)驗(yàn)結(jié)果
    5.2 改進(jìn)的Maekawa算法的仿真實(shí)驗(yàn)
        5.2.1 實(shí)驗(yàn)場(chǎng)景
        5.2.2 仿真實(shí)驗(yàn)結(jié)果
    5.3 本章小結(jié)
第6章 總結(jié)與展望
    6.1 主要內(nèi)容
    6.2 今后的工作
參考文獻(xiàn)
攻讀碩士學(xué)位期間主要的研究成果
致謝



本文編號(hào)：3792112