分布式系統(tǒng)中實(shí)時(shí)任務(wù)的容錯(cuò)調(diào)度及死鎖解除的研究.pdf

1、摘要摘要對(duì)分布式實(shí)時(shí)系統(tǒng)的研究是當(dāng)今并行處理的研究熱點(diǎn)之一，如何合理有效地將并行任務(wù)分配到各個(gè)分布式處理機(jī)節(jié)點(diǎn)，將直接影響系統(tǒng)的執(zhí)行性能。本論文對(duì)分布式系統(tǒng)中實(shí)時(shí)任務(wù)的容錯(cuò)調(diào)度和死鎖解除兩個(gè)問題進(jìn)行了詳細(xì)研究，并為之建立了相關(guān)的數(shù)學(xué)模型及處理算法。(1)輪轉(zhuǎn)式容錯(cuò)調(diào)度算法:分布式以下分三部分討論統(tǒng)是一種多機(jī)多任務(wù)分布并行處理系統(tǒng)，它對(duì)實(shí)時(shí)性和可靠性都有很高的要求，特別是實(shí)時(shí)任務(wù)的處理必須在規(guī)定時(shí)限內(nèi)完成，否則會(huì)產(chǎn)生嚴(yán)重后果。本文第一個(gè)創(chuàng)

2、新點(diǎn)是引入輪轉(zhuǎn)調(diào)度思想，提出一種輪轉(zhuǎn)式容錯(cuò)調(diào)度算法RSRS設(shè)計(jì)的要點(diǎn)是:①采用主從備份技術(shù)實(shí)現(xiàn)容錯(cuò)，保證每一個(gè)實(shí)時(shí)任務(wù)都能及時(shí)完成②采用輪轉(zhuǎn)式調(diào)度提高任務(wù)調(diào)度的均衡性，使每一臺(tái)處理機(jī)工作量盡量飽和③通過預(yù)留資源的重疊使用和及時(shí)回收提高處理機(jī)利用率和任務(wù)接收率。RS算法調(diào)度時(shí)間短，資源浪費(fèi)少，模擬結(jié)果表明該算法是有效的。(2)死鎖解除:分布式實(shí)時(shí)系統(tǒng)的任務(wù)分配到各處理機(jī)節(jié)點(diǎn)之后，可能會(huì)由于共享資源、相互通訊、動(dòng)態(tài)使用存儲(chǔ)區(qū)和數(shù)據(jù)庫(kù)等原因?qū)?/p>

3、致死鎖，致使整個(gè)系統(tǒng)的效率大為降低。因此，研究如何解除分布式死鎖是很有意義的。本文第二個(gè)創(chuàng)新點(diǎn)是將遺傳算法思想引入解除分布式死鎖領(lǐng)域，設(shè)計(jì)了一種改進(jìn)的廣義遺傳算法IGGA。先以模擬程序的運(yùn)行結(jié)果說(shuō)明工GGA效率高于現(xiàn)行的貪心算法然后通過分析工GGA的收斂性從理論上摘要②Achievingquiteequilibriumoftasksdistributingbyrotationalschedulingtomaketheworkloadof

4、everyprocessorfurthestsaturated③Improvingtheprocessorutilizationandthetaskacceptedratiothroughoverlappingandreclaimingthereservedresourcebetimes.SimulationresultsshowthatRSiseficientwithshorterscheduletimeandlessresource

5、waste.(2)BreakingDeadlock:Indistributedsystemsthattherealtimetasksarescheduledtoeachprocessormayfallintodeadlockwhichwilldecreasetheefficiencyofthewholesystemgreatlybecauseofresourcesharingmutualcommunicationordynamicusi

6、ngofmemoryanddatabase.Soitisverymeaningfultostudyhowtoreleasethedistributeddeadlock.Thesecondcontributionofthispaperistopresentanimprovedgeneralizedgeneticalgorithm(IGGA)appliedtoreleasedeadlock.IGGAhasbeenprovedtobeprac

7、ticalinactualsystemsanditsefectivenessisbeterthanthatofgreedyalgorithms.Wegottheseconsequencesnotonlybysimulationresultsbutalsothroughitsconvergenceanalysis.Attheendofthediscussion.twoconcepts.i.e.selectivepressureandtak

8、eovertimeareintroducedtoanalyzethediferentinfluenceonIGGAbyusingdiferentchoicestrategies.(3)GAParallelComputation:FurthermoresomenewideaabouttheimpliedparallelismofGAwhichisstillbasedontheresearchofgeneticcontroversial吐t