基于銀行家算法的分布式互斥請求集生成算法研究.pdf

1、分布式互斥系統(tǒng)的效率極大程度上取決于生成請求集的效率，目前的請求集生成算法已經(jīng)將請求集長度降到最低，但是時間復(fù)雜度過高；如果想要獲得快捷的生成效果，又需增加請求集長度。所以設(shè)計出一種集最優(yōu)長度和較優(yōu)時間復(fù)雜度為一體的請求集生成算法成為目前亟待解決的問題。
　　本文詳細分析分布式互斥算法的研究背景和發(fā)展歷程。在此基礎(chǔ)上，重點探討分布式互斥系統(tǒng)的特征、請求集序列對于系統(tǒng)的重大意義。同時也對比介紹原有請求集生成算法的優(yōu)缺點，針對其時間復(fù)

2、雜度和空間復(fù)雜度不可兼得的狀況提出一種新型的請求集生成方案。
　　本文的重點內(nèi)容和創(chuàng)新點有以下幾個方面：
　　1、建立分布式互斥請求集生成算法的數(shù)學(xué)模型，通過比對現(xiàn)有的請求集算法的特點，確定了一個優(yōu)秀的請求集該具有的標(biāo)準(zhǔn)，明確了研究方向。
　　2、分析銀行家算法和請求集生成算法的理念的相似之處。將銀行家算法為避免死鎖，獲取安全進程序列的遞歸思想，借鑒到請求集生成算法中。增設(shè)一個請求集剩余長度的變量，以該變量及節(jié)點狀態(tài)數(shù)

3、組作為邊界條件，可以確定申請進入請求集節(jié)點的合法性。該算法能獲得最優(yōu)請求集長度，其時間復(fù)雜度遠遠小于同樣具有最優(yōu)請求集長度的LUK算法。
　　3、提出一種動態(tài)確定請求集初始化節(jié)點數(shù)與初始化位置的局部遞歸的請求集生成算法。它通過增加初始化節(jié)點數(shù)量，可以減少在計算請求集時需要尋找的節(jié)點數(shù)量的方式，以達到降低生成請求集的時間復(fù)雜度的目的，理論上能將算法的時間復(fù)雜度降低到N N N6/??2/N3/。本文還采用局部遞歸的方式來保證在降低請