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

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

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

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