實(shí)時(shí)分布系統(tǒng)容錯(cuò)調(diào)度算法的設(shè)計(jì)與實(shí)現(xiàn).pdf

1、實(shí)時(shí)分布系統(tǒng)的任務(wù)調(diào)度問(wèn)題是一個(gè)富有挑戰(zhàn)性的課題,也是當(dāng)前的一個(gè)研究熱點(diǎn).由于任務(wù)調(diào)度是一個(gè)典型的NP問(wèn)題,同時(shí)它又是直接影響分布式系統(tǒng)性能的關(guān)鍵因素.因此,研究實(shí)時(shí)分布計(jì)算機(jī)系統(tǒng)的任務(wù)調(diào)度策略具有重要的理論意義和實(shí)際意義.本文以"十五"預(yù)研項(xiàng)目為背景,在與單處理器調(diào)度算法相結(jié)合的基礎(chǔ)上,針對(duì)實(shí)際應(yīng)用中大量的實(shí)時(shí)周期任務(wù),以提高資源利用率為主要目標(biāo),對(duì)分布實(shí)時(shí)系統(tǒng)的調(diào)度理論與實(shí)現(xiàn)問(wèn)題進(jìn)行了深入的探索與研究.首先,給出與實(shí)時(shí)分布容錯(cuò)系統(tǒng)相

2、關(guān)系統(tǒng)(包括實(shí)時(shí)系統(tǒng)、容錯(cuò)系統(tǒng)、分布式系統(tǒng)和實(shí)時(shí)分布系統(tǒng))的模型和主要特點(diǎn),分析了這些系統(tǒng)所涉及的調(diào)度理論.進(jìn)一步指出,實(shí)時(shí)分布式系統(tǒng)由于自身具有冗余特性而使其實(shí)現(xiàn)容錯(cuò)可行.給出了任務(wù)可調(diào)度的證明和調(diào)度算法的評(píng)價(jià)指標(biāo).其次,根據(jù)分布系統(tǒng)容錯(cuò)調(diào)度原理,在單處理器實(shí)時(shí)調(diào)度采用EDF算法的基礎(chǔ)上,提出了采用不同容錯(cuò)技術(shù)的兩種實(shí)時(shí)分布系統(tǒng)容錯(cuò)調(diào)度算法:PPB-MFT-EDF算法和APB-MFT-EDF算法.前者采用了常用的容錯(cuò)技術(shù)—被動(dòng)備份容錯(cuò)

3、技術(shù),后者采用的則是主動(dòng)備份容錯(cuò)技術(shù).文中證明了兩種算法的可調(diào)度條件和一些重要性質(zhì).證明和模擬結(jié)果顯示:APB-MFT-EDF的性能優(yōu)于PPB-MFT-EDF算法,并對(duì)這一結(jié)果進(jìn)行了深入分析.第三,在以上算法的基礎(chǔ)上,進(jìn)一步提出了既可調(diào)度周期任務(wù)也可調(diào)度非周期任務(wù)的混合任務(wù)調(diào)度算法,它將所有非周期任務(wù)轉(zhuǎn)化為周期任務(wù)進(jìn)行調(diào)度,并有效地利用處理機(jī)無(wú)故障時(shí)的空閑資源.與其它同類算法相比,該算法簡(jiǎn)單實(shí)用,并可進(jìn)一步擴(kuò)大處理任務(wù)類型的范圍.針對(duì)單