分布式系統(tǒng)中實時任務的容錯調度及死鎖解除的研究.pdf

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

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

3、致死鎖，致使整個系統(tǒng)的效率大為降低。因此，研究如何解除分布式死鎖是很有意義的。本文第二個創(chuàng)新點是將遺傳算法思想引入解除分布式死鎖領域，設計了一種改進的廣義遺傳算法IGGA。先以模擬程序的運行結果說明工GGA效率高于現行的貪心算法然后通過分析工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