（計(jì)算機(jī)軟件與理論專業(yè)論文）具有時(shí)間約束的分布式軟件可靠性評(píng)估研究.pdf

華中科技大學(xué)碩士學(xué)位論文 摘要 對(duì)于分布式軟件可靠性研究 在最初階段 人們只是借鑒一般軟件可靠性評(píng)估的 基本理論和方法 隨著軟件可靠性評(píng)估技術(shù)的發(fā)展 形成了許多關(guān)于分布式軟件可靠 性評(píng)估的理論和方法 其中大部分是基于圖論 利用k 一端點(diǎn)網(wǎng)絡(luò)因式分解定理進(jìn)行評(píng) 估 這種評(píng)估方法雖然經(jīng)過理論分析和推導(dǎo) 具有一定的合理性 但是因其只考慮了 分布式軟件可靠性單項(xiàng)指標(biāo) 沒有綜合分析分布式軟件的其它性能對(duì)可靠性的影響 因此 在實(shí)際應(yīng)用方面具有一定的局限性 針對(duì)上述局限性 具有時(shí)間約束的分布式軟件可靠性評(píng)估研究 以分布式軟件 的可靠性模型為基礎(chǔ) 將精簡(jiǎn)和深度優(yōu)先兩種方法有機(jī)結(jié)合 引入時(shí)間約束因子 對(duì) 分布式軟件可靠性進(jìn)行理論分析 確定具有時(shí)間約束的分布式軟件可靠性評(píng)估的理論 方法 在此基礎(chǔ)上 推導(dǎo)出d e g r e e 1 精簡(jiǎn)算法 s e r i e s 精簡(jiǎn)算法 新的文件生成樹生 成算法 文件傳輸路徑生成算法以及響應(yīng)時(shí)間評(píng)估算法 在使用這一系列算法之前 首先對(duì)分布式系統(tǒng)進(jìn)行形式化描述 形成分布式系統(tǒng) 示意圖 為算法提供運(yùn)用環(huán)境 根據(jù)節(jié)點(diǎn)上可用的數(shù)據(jù)文件和節(jié)點(diǎn)的度數(shù) d e g r e e 一1 精簡(jiǎn)算法和s e r i e s 精簡(jiǎn)算法分別對(duì)分布式系統(tǒng)示意圖進(jìn)行度l 精簡(jiǎn)和度2 精簡(jiǎn) 降低 了評(píng)估階段的復(fù)雜度 在精簡(jiǎn)的分布式系統(tǒng)示意圖中 運(yùn)用新的文件生成樹生成算法 生成執(zhí)行程序的所有文件生成樹 以便確定數(shù)據(jù)文件的所有傳輸路徑 在每一個(gè)文件 生成樹中 運(yùn)用文件傳輸路徑生成算法 生成數(shù)據(jù)文件的所有傳輸路徑 為確定數(shù)據(jù) 文件的傳輸時(shí)間創(chuàng)造條件 在數(shù)據(jù)文件的傳輸路徑中 運(yùn)用響應(yīng)時(shí)間評(píng)估算法 對(duì)數(shù) 據(jù)文件的傳輸時(shí)間進(jìn)行評(píng)估 從而確定文件生成樹的狀態(tài) 根據(jù)文件生成樹的狀態(tài)和 狀態(tài)變遷情況 運(yùn)用m a r k o v 模型 對(duì)具有時(shí)間約束的分布式軟件的可靠性進(jìn)行評(píng)估 為了驗(yàn)證具有時(shí)間約束的分布式軟件可靠性評(píng)估算法的性能 通過理論分析和軟 件模擬兩種方式對(duì)可靠性進(jìn)行評(píng)估 其中軟件模擬通過可靠性評(píng)估模擬器實(shí)現(xiàn) 模擬 器自動(dòng)生成具有時(shí)間約束的分布式軟件并對(duì)其可靠性進(jìn)行評(píng)估 評(píng)估結(jié)果表明 上述 算法具有較好的合理性 可行性和準(zhǔn)確性 關(guān)鍵字 可靠性評(píng)估 時(shí)間約束 分布式軟件 文件生成樹 響應(yīng)時(shí)間 華中科技大學(xué)碩士學(xué)位論文 a b s t r a c t p e o p l eo f t e nu s et h eb a s i ct h e o r i e sa n dt h eb a s i cm e t l i o d so f t h es o f t w a r er e l i a b i l i t y a n a l y s i sa tt h ee a r l yt i m ew h e nt 1 1 c ys t u d yt h er e l i a b i l i t yo f d i s t r i b u t e ds o f t w a r e w i t ht h e d e v e l o p m e n to ft h et e c h n o l o g y o fs o w a r er e l i a b i l i t ye v a l u a t i o n s o m et h e o r i e sa n d m e t h o d sa b o u tt h ed i s t r i b u t e ds o f t w a r er e l i a b i l i t ye v a l u a t i o na r ef o u n d e d h o w e v e r m o s to f t h e ma r eb a s e do i lt h et h e o r yo fg r a p ha n de v a l u a t et h ed i s t r i b u t e ds o l a r er e l i a b i l i t yb y u s i n gk t e r m i n a lf a c t o r i n gt h e o r e m t h o u g ht h e s em e t h o d so f e v a l u a t i o na r ed e r i v e df r o m t h e o r e t i c a la n a l y z i n ga n dd e d u c i n g t h e ya r el i m i t e di np r a c t i c a la p p l y i n g b e c a u s et h e s e m e t h o d so n l ye v a l u a t et h er e l i a b i l i t yo fd i s t r i b u t e ds o f t w a r ea n dn o tr e f l e c tt h ee f f e c t so f t h eo t h e rp e r f o r m a n c eo fd i s t r i b u t e ds o f t w a r eo nt h e r e l i a b i l i t y a i m i n g t or e s o l v et h e s e p r o b l e m s t h i s t h e s i s a n a l y z e t h e r e l i a b i l i t y o f t i m e c o n s t r a i n e dd i s t r i b u t e ds o f t w a r ea n dd e d u c es o m ec o m p u t i n ge x p r e s s i o n s w h i c hi s b a s e do nt h ep r i n c i p l eo fd i s t r i b u t e dp r o g r a mr e l i a b i l i t y e v a l u a t i o n n a m e l yc o m b i n i n g r e d u c t i o nw i t hd e p t h f i r s ts e a r c hm a n n e r t h e nb a s e do nt h e s ec o m p u t i n ge x p r e s s i o n s w e d e d u c es o m ea l g o r i t h m s 1 1 1 e s ea l g o r i t h m si n c l u d ed e g r e e lr e d u c t i o na l g o r i t h m s e r i e s r e d u c t i o na l g o r i t h m n e wf i l es p a n n i n gt r e ea l g o r i t h m f i l et r a n s m i s s i o np a t ha l g o r i t h ma n d r e s p o n s e t i m eo f f i l et r a n s m i s s i o np a t ha l g o r i t h m b e f o r eu s i n gt h e s ea l g o r i t h m s t h ed i s t r i b u t e ds y s t e mi sf i r s t l yd e s c r i b e db ya p p l y i n g f o r m a l i z e dm e t h o d sa n dw ec a i lg e tt h es k e t c hm a po ft h ed i s t r i b u t e ds y s t e m t h e nt h e s e a l g o r i t h m sc a nb ea p p l i e di nt h es k e t c hm a p b a s e d o nt h ea v a i l a b l ed a t af i l e so nn o d ea n d t h ed e g r e eo fn o d e t h eg r a p ho ft h ed i s t r i b u t e ds y s t e mc a r lb er e d u c e db yu s i n gt h e d e g r e e lr e d u c t i o na l g o r i t h ma n dt h es e r i e sr e d u c t i o na l g o r i t h m t h u st h ec o m p l e xd e g r e e o fe v a l u a t i o nc a l lb er e d u c e d i nt h es k e t c hm a p h a v i n gb e e nr e d u c e d a l lt h ef i l es p a n n i n g t r e e sc a ns p a nb y u s i n gt h en e w f i l es p a n n i n gt r e ea l g o r i t h m s oa l lt h et r a n s m i s s i o np a t h s o fe a c hd a t af i l ec a nm a k es u r eb yt h ef i l et r a n s m i s s i o np a t ha l g o r i t h m t 1 l ct r a n s m i s s i o n t i m eo fe a c hd a t af i l ec a nb ec a l c u l a t e db yu s i n gt h er e s p o n s et i m eo ff i l et r a n s m i s s i o np a t h a l g o r i t h m b yu s i n gt h e s ea l g o r i t h m sa n dm a r k o vm o d e l t h er e l i a b i l i t yo f t i m e c o n s t r a i n e d d i s t r i b u t e ds o f t w a r ec a r tb ec a l c n l a t e do u t i no r d e rt ov a l i d a t et h ep e r f o r m a n c eo ft h er e l i a b i l i t ye v a l u a t i o n a l g o r i t h m s f o r t i m e c o n s t r a i n e dd i s t r i b u t e ds o f t w a r e w eu s et w od i f f e r e n tm e t h o d s i nt h ef i r s tm e t h o d s 1 1 華中科技大學(xué)碩士學(xué)位論文 t h er e l i a b i l i t yi se v a l u a t e db yu s i n gt h er e l i a b i l i t ye v a l u a t i o nm g o f i t h m i nt h es e c o n d e x a m p l e w e u s et h er e l i a b i l i t ye v a l u a t i o ns i m u l a t o rt oe v a l u a t et h er e l i a b i l i t y w ec a nd r a w s o m ec o n c l u s i o n s w h i c h i n c l u d i n g t h a tt h e a l g o r i t h m s a r e r a t i o n a l t h ep r o c e s s o f e v a l u a t i o ni sf e a s i b l ea n dt h er e s u l ti sv e r a c i o u s b ya n a l y z i n g t h e r e s u l to f t w om e t h o d s k e y w o r d s r e l i a b i l i t ye v a l u a t i o n t i m e c o n s t r a i n e d d i s l r i b u t e ds o t t w a r e f i l es p a n n i n gt r e e r e s p o n s et i m e i i l 獨(dú)創(chuàng)性聲明 本人聲明所呈交的學(xué)位論文是我個(gè)人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的 研究成果 盡我所知 除文中已經(jīng)標(biāo)明引用的內(nèi)容外 本論文不包含任何其他個(gè) 人或集體已經(jīng)發(fā)表或撰寫過的研究成果 對(duì)本文的研究做出貢獻(xiàn)的個(gè)人和集體 均已在文中以明確方式標(biāo)明 本人完全意識(shí)到本聲明的法律結(jié)果由本人承擔(dān) 學(xué)位論文作者簽名 彥嘻茲 日期 如岱年r 月6 日 學(xué)位論文版權(quán)使用授權(quán)書 本學(xué)位論文作者完全了解學(xué)校有關(guān)保留 使用學(xué)位論文的規(guī)定 即 學(xué)校有 權(quán)保留并向國(guó)家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版 允許論文被查閱和 借閱 本人授權(quán)華中科技大學(xué)可以將本學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù) 庫(kù)進(jìn)行檢索 可以采用影印 縮印或掃描等復(fù)制手段保存和匯編本學(xué)位論文 保密口 在 年解密后適用本授權(quán)書 本論文屬于 不保密剛 請(qǐng)?jiān)谝陨戏娇騼?nèi)打 4 學(xué)位論文作者簽名 孝運(yùn)烈 e 1 期 如牛年f 月g 日 指刪撇 屏紛 華中科技大學(xué)碩士學(xué)位論文 1 緒論 本章簡(jiǎn)要概述具有時(shí)間約束的分布式軟件可靠性評(píng)估的目的和意義以及國(guó)內(nèi)外 的軟件評(píng)估技術(shù) 分析分布式程序的評(píng)估方法 指出分布式程序評(píng)估時(shí)采用的評(píng)估指 標(biāo) 通過對(duì)不同評(píng)估技術(shù)和評(píng)估方法的研究 分別指出其優(yōu)點(diǎn)和缺點(diǎn) 在此基礎(chǔ)之上 介紹評(píng)估技術(shù)和評(píng)估方法的發(fā)展趨勢(shì) 分析具有時(shí)間約束的分布式軟件可靠性評(píng)估的 相關(guān)技術(shù) 關(guān)鍵內(nèi)容和優(yōu)缺點(diǎn) 最后 簡(jiǎn)要介紹研究方法 研究工作 預(yù)期結(jié)果和論 文組織結(jié)構(gòu) 1 1 課題研究的目的和意義 近年來 隨著科學(xué)技術(shù)的快速發(fā)展 微電子和計(jì)算機(jī)技術(shù)開始滲透到各個(gè)領(lǐng)域 人們對(duì)電子信息技術(shù)的應(yīng)用已經(jīng)處于一個(gè)迅猛發(fā)展的新時(shí)期 由于分布式實(shí)時(shí)系統(tǒng)結(jié) 構(gòu)一方面具有程序和數(shù)據(jù)文件的冗余性 另一方面又具有實(shí)時(shí)性 因此被廣泛用運(yùn)到 軍事 航空航天 航海和能量控制等領(lǐng)域 分布式實(shí)時(shí)軟件作為計(jì)算機(jī)系統(tǒng)的一部分 隨著應(yīng)用范圍的擴(kuò)大 其規(guī)模也不斷擴(kuò)大 功能不斷增多 復(fù)雜性不斷加深 在整個(gè) 計(jì)算機(jī)技術(shù)和信息處理中開始占有重要的地位 分布式實(shí)時(shí)軟件規(guī)模的增大和復(fù)雜程 度的提高 其發(fā)生差錯(cuò)率會(huì)越來越多 分布式實(shí)時(shí)軟件的失效可能造成災(zāi)難性的后果 迫使軟件工程界和可靠性工程界對(duì)分布式實(shí)時(shí)軟件的可靠性問題給予充分重視 整個(gè) 系統(tǒng)的主要問題已經(jīng)從硬件逐步轉(zhuǎn)向軟件 分布式程序系統(tǒng)的性能評(píng)估通常包含實(shí)時(shí)性 可靠性 穩(wěn)定性 易用性和準(zhǔn)確性 等 在評(píng)估時(shí) 首先評(píng)估分布式程序系統(tǒng)各個(gè)子系統(tǒng)的質(zhì)量 在保證軟件子系統(tǒng)質(zhì)量 的基礎(chǔ)上 選擇一定的度量指標(biāo) 對(duì)各子系統(tǒng)的實(shí)時(shí)性 可靠性 穩(wěn)定性 易用性和 準(zhǔn)確性進(jìn)行測(cè)量 評(píng)級(jí)和評(píng)估 對(duì)子系統(tǒng)的性能評(píng)估完畢后 再對(duì)整個(gè)系統(tǒng)的綜合性 能進(jìn)行評(píng)估 看是否能夠真正滿足實(shí)際的需要 分布式程序可靠性是衡量分布式程序質(zhì)量最重要的指標(biāo)和分布式程序開發(fā)的最 終目標(biāo) 分布式程序可靠性評(píng)估是以分布式程序可靠性模型為基礎(chǔ)對(duì)軟件的可靠性以 及與可靠性直接相關(guān)的度量 如故障強(qiáng)度 故障率 故障前平均時(shí)間等 進(jìn)行評(píng)估和 預(yù)測(cè) 對(duì)分布式程序可靠性的評(píng)估進(jìn)行研究將會(huì)在定量地度量軟件的可靠性 評(píng)估軟 件的性能 控制和管理軟件產(chǎn)品的研制 生產(chǎn)過程 提高分布式程序的生產(chǎn)率等方面 1 華中科技大學(xué)碩士學(xué)位論文 發(fā)揮重要的作用 然而 當(dāng)前分布式程序的評(píng)估模型側(cè)重于分布式程序的可靠性 很少反應(yīng)具有時(shí) 間約束的特征 具有時(shí)間約束的分布式軟件的可靠性評(píng)估是指在對(duì)分布式程序進(jìn)行評(píng) 估時(shí)必須對(duì)時(shí)間特征加以考慮 即可靠性是在一定時(shí)間約束條件下的可靠性 這項(xiàng)研 究在國(guó)際軟件測(cè)試領(lǐng)域中屬于較為前沿的工作 無任是對(duì)軍事軟件評(píng)估還是對(duì)其他領(lǐng) 域的軟件評(píng)估都具有一定的理論意義和實(shí)用價(jià)值 鑒于具有時(shí)間約束的分布式軟件的可靠性評(píng)估的理論意義和實(shí)用價(jià)值 本課題將 在研究時(shí)間約束因子對(duì)分布式軟件可靠性影響的基礎(chǔ)上 著重研究具有時(shí)間約束的分 布式軟件可靠性的評(píng)估相關(guān)理論和方法 在此基礎(chǔ)上 提出相關(guān)的評(píng)估算法和模型 建立一套完整的 適合具有時(shí)間約束的分布式軟件可靠性評(píng)估的理論和模型 使具有 時(shí)間約束的分布式軟件的可靠性評(píng)估技術(shù)能夠在軍事 國(guó)防 科研和生產(chǎn)等方面發(fā)揮 重要的作用 1 2 國(guó)內(nèi)外研究的現(xiàn)狀 分布式軟件可靠性和實(shí)時(shí)性作為分布式軟件的兩種最基本性能 在實(shí)際生產(chǎn)和運(yùn) 用中 更能引起人們注意 分布式軟件的可靠度表明的是一個(gè)分布式軟件系統(tǒng)按照用 戶需求和設(shè)計(jì)目標(biāo)執(zhí)行其功能的正確程度 通常包括三個(gè)要素 即規(guī)定的時(shí)間 規(guī)定 的環(huán)境條件和規(guī)定的功能 分布式軟件的實(shí)時(shí)性表明的是一個(gè)分布式軟件系統(tǒng)按照用 戶需求和設(shè)計(jì)目標(biāo)在規(guī)定的時(shí)間限度內(nèi)完成的能力 關(guān)于軟件可靠性的評(píng)估 從1 9 7 2 年出現(xiàn)第一個(gè)軟件可靠性的評(píng)估模型以來 人 們對(duì)軟件可靠性評(píng)估方法和模型的研究就沒有間斷過 人們總是不斷總結(jié)已有模型的 優(yōu)點(diǎn)和缺點(diǎn) 在已有的評(píng)估理論的基礎(chǔ)上 針對(duì)不同軟件的特點(diǎn)和性能 不斷的提出 新的模型和方法 分布式程序作為軟件領(lǐng)域中的一個(gè)重要組成部分 其可靠性的評(píng)估 理論和模型也是在這種研究中不斷的得到提高和升華 1 2 1 軟件可靠性評(píng)估研究現(xiàn)狀 自z j e l i n s 唧p b m o r a i l d a 第一次提出軟件可靠性分析模型 1 以來 軟件可靠性的 研究在國(guó)際上就開始變得活躍起來 見之于文獻(xiàn)的軟件可靠性統(tǒng)計(jì)分析的模型到現(xiàn)在 已經(jīng)超過百種 如h d m i l l s 提出的種子撤播法和加標(biāo)記法 2 讕來估計(jì)軟件中的缺陷數(shù) 這兩種方法實(shí)際上是利用捕獲一再捕獲抽樣技術(shù)估計(jì)程序中錯(cuò)誤數(shù) 在程序中預(yù)先有 華中科技大學(xué)碩士學(xué)位論文 意 播種 一些設(shè)定的錯(cuò)誤 種子 然后根據(jù)測(cè)試出的原始錯(cuò)誤數(shù)和發(fā)現(xiàn)的誘導(dǎo)錯(cuò) 誤的比例來估計(jì)程序中殘留的錯(cuò)誤數(shù) 其優(yōu)點(diǎn)是簡(jiǎn)便易行 缺點(diǎn)是誘導(dǎo)錯(cuò)誤的 種子 與實(shí)際的原始錯(cuò)誤之間的類比性估量困難 a l g o e l 和k o k u m o t o 提出一種非齊次的 泊松過程模型 n h p p 3 10 這種模型的最大優(yōu)點(diǎn)是假設(shè)軟件出現(xiàn)失效后 缺陷即被發(fā)現(xiàn) 而予以排除 缺點(diǎn)是在排除缺陷時(shí) 有可能引入新的欽陷 從二十世紀(jì)九十年代以來 y a m a d a 等人相繼提出的邏輯增長(zhǎng)曲線模型 4 l 和 c o m p e r t z 提出的增長(zhǎng)曲線模型是一種軟件可靠性增長(zhǎng)模型 它是用一個(gè)增長(zhǎng)函數(shù)來描 述軟件的改進(jìn)過程 預(yù)測(cè)軟件在檢錯(cuò)過程中的可靠性改進(jìn) t d o w m s 針對(duì)當(dāng)時(shí)大多數(shù) 軟件可靠性模型在測(cè)試階段將軟件處理成黑盒子閣的作法 提出對(duì)測(cè)試過程直接建模 w h i t t a k e r 等人采用馬爾可夫過程對(duì)軟件的測(cè)試 6 過程和測(cè)試用例作了研究 文獻(xiàn) 7 和 文獻(xiàn) 8 分別對(duì)軟件測(cè)試數(shù)據(jù)的自動(dòng)生成提出了 開 關(guān)搜索 o n o f fs e a r c h 算法和 約 束求解 c o n s t r a i n ts o l v i n g 技術(shù) 但是這些技術(shù)都是使用測(cè)試用例來發(fā)現(xiàn)失效或者 是通過模擬使用而在使用過程中發(fā)現(xiàn)失效 從1 9 9 6 年以來 宋曉秋等人相繼提出的j m 可靠性增長(zhǎng)模型 9 1 0 1 實(shí)際上是一種關(guān)于軟件失效率的分析模型 這種模型主要是用來 研究程序的失效率 j m 模型最大的弊端在于模型的假設(shè) 即 缺陷相應(yīng)的失效率相 等 這種假設(shè)在不太長(zhǎng)的時(shí)間內(nèi) 它是近似成立的 因此在不太長(zhǎng)的時(shí)間區(qū)間是可 用的 但在時(shí)間較長(zhǎng)的情況下 這種模型將不再適合 b a r b a r as a i zd eb u s t a m a n t e 等人第一次提出了一種多項(xiàng)式指數(shù)可靠性函數(shù)模型 m e r f t 1 1 這種模型本質(zhì)上是一種純理論的軟件可靠性評(píng)估模型 在實(shí)際評(píng)估過程 中很難執(zhí)行 為了使自己提出的模型實(shí)際可用 b a r b a r a s a i z d e b u s t a m a n t e 等人又提出 了一種近似指數(shù)可靠性函數(shù)模翌 e a r f t 1 1 這是一種純實(shí)際的軟件可靠性評(píng)估模型 但由于它缺少理論基礎(chǔ) 很難使別人信服 測(cè)試出來的數(shù)據(jù)不能被別人所接受 因此 從1 9 9 9 年以后 a m a l i os a i z d e b u s t a m a n t e 等人一起提出了一種新的軟件可靠性評(píng)估模 型 即m e r f e a r f 模型 n 1 2 l 這種模型將理論和實(shí)際相結(jié)合 對(duì)軟件的錯(cuò)誤率進(jìn)行 預(yù)測(cè) 其結(jié)果具有 定的說服力 但是 這種模型中假設(shè)出錯(cuò)過程和修復(fù)過程是相互 獨(dú)立的兩個(gè)過程 這種假設(shè)是否完全符合實(shí)際情況還很難確定 也許在某些情況是符 合的 而在另外的一些情況它卻不適合 在1 9 9 8 年至1 j 2 0 0 3 年間 由c s m i d t s 等人相繼提出了一些基于軟件體系結(jié)構(gòu)的可靠 性評(píng)估和預(yù)測(cè)方法 1 3 t 8 1 這些評(píng)估和預(yù)測(cè)方法由于軟件體系結(jié)構(gòu)的多樣性而顯得這種 方法沒有通用性 華中科技大學(xué)碩士學(xué)位論文 從上面所列舉的一些例子來看 這些軟件可靠性的評(píng)估模型還不能完全通用的統(tǒng) 計(jì)分析軟件的可靠性 其主要原因是這些模型對(duì)系統(tǒng)所做的假設(shè)固定不變 而軟件在 其丌發(fā)過程中受各種因素的影響 使得軟件的故障行為干差萬別 在進(jìn)行模型的參數(shù) 估計(jì)時(shí)又難以實(shí)時(shí)獲得充分的統(tǒng)計(jì)數(shù)據(jù) 無法在各種模型之間作識(shí)別 導(dǎo)致估計(jì)結(jié)果 與實(shí)際情況的不一致 即產(chǎn)生模型的不匹配的問題 1 2 2 分布式軟件可靠性評(píng)估研究現(xiàn)狀 在上述一般軟件可靠性評(píng)估技術(shù)不斷發(fā)展的同時(shí) 分布式軟件性能評(píng)估技術(shù)在此 基礎(chǔ)上也開始發(fā)展 目前 從國(guó)內(nèi)外關(guān)于分布式軟件性能評(píng)估的研究狀況來看 較有 成效的是關(guān)于分布式程序的可靠性評(píng)估 評(píng)估的指標(biāo)涉及分布式程序的可靠度 故障 率和 f 確性等方面 從a s a t y a n a r a y a n a 等人第一次提出網(wǎng)絡(luò)的可靠性和因式分解定理 1 9 以來 分布 式程序的可靠性評(píng)估就開始在原有的軟件可靠性評(píng)估理論的基礎(chǔ)上得到了發(fā)展 在此 基礎(chǔ)上 a s a t y a n a r a y a n a 等人對(duì)網(wǎng)絡(luò)的可靠性和因式分解定理進(jìn)行了發(fā)展并在此基礎(chǔ) 上建立了新的網(wǎng)絡(luò)可靠性評(píng)測(cè)模型 2 0 l v k p r a s a n n ak u a m a r s h a r i r i 和 c s r a g h a n v e n d r a 在此基礎(chǔ)上提出了一種分布式程序的可靠性評(píng)估模型和方法 2 這 種評(píng)估模型根據(jù)分布式程序執(zhí)行時(shí)所需的數(shù)據(jù)文件和數(shù)據(jù)文件在系統(tǒng)中的分布 產(chǎn)生 文件生成樹 f s t 和文件生成森林 f s f 再通過網(wǎng)絡(luò)的可靠性和因式分解定理對(duì)分布 式程序和分布式系統(tǒng)的可靠性進(jìn)行評(píng)估 根據(jù)這種評(píng)估方法 s h a r i r i 和 c s r a g h a n v e n d r a 又提出一種基于路徑和割集思想的符號(hào)化可靠性算法模型 s y r e l f 2 2 2 引 這種模型是對(duì)多個(gè)端點(diǎn)的網(wǎng)絡(luò)的可靠性進(jìn)行評(píng)估 它的建立使得分布式程序的 可靠性評(píng)估得到迅速發(fā)展 在這種模型之后 為了提高這種方法的評(píng)估效率和降低這 種評(píng)估算法的復(fù)雜度 d j c h e n 等相關(guān)人員相繼提出了一系列的評(píng)估算法和模型 2 4 j 如最小文件生成樹算法 m f s t 快速的可靠性評(píng)估算法 f r e a 一種基于快速的可 靠性評(píng)估算法 f s t s p r 符號(hào)化的可靠性算法 s m 改進(jìn)的因式分解算法 f m d j c h e n 等相關(guān)人員提出的這些算法 通常都是基于圖論和概率論 利用具有網(wǎng)絡(luò)可 靠性評(píng)估的因式分解定理 采用一系列的精簡(jiǎn)算法來簡(jiǎn)化模型 再利用文件生成樹 f s t 對(duì)分布式程序的可靠性進(jìn)行評(píng)估 陳國(guó)龍等人于2 0 0 0 年提出關(guān)于網(wǎng)絡(luò)系統(tǒng)的可 靠性評(píng)估方法首先將網(wǎng)絡(luò)系統(tǒng)化為等價(jià)的網(wǎng)絡(luò)圖 3 利用開關(guān)網(wǎng)絡(luò)的理論 定義系統(tǒng) 成功函數(shù) 給出網(wǎng)絡(luò)的輸入節(jié)點(diǎn)到輸出節(jié)點(diǎn)的所有最小路徑集的求解方法 華中科技大學(xué)碩士學(xué)位論文 上面這些分布式程序的可靠性評(píng)估算法實(shí)際上都是對(duì)分布式程序的可靠度進(jìn)行 評(píng)估 它們均是以可靠度作為分布式程序的可靠性指標(biāo) 對(duì)于分布式程序正確性測(cè)試 顧慶等相關(guān)人員于2 0 0 0 年提出了一種基于事件約束的分布式程序正確性測(cè)試 3 8 1 這種測(cè)試采用一種基于事件前后規(guī)約約束的約束規(guī)則 通過執(zhí)行測(cè)試用例所產(chǎn)生的事 件序列集對(duì)規(guī)約約束集的一致性和覆蓋程度來檢測(cè)被測(cè)程序的正確性 對(duì)于分布式程 序的故障率 雷航等相關(guān)人員于1 9 9 7 年提出了一種基于任務(wù)模塊的實(shí)時(shí)軟件可靠性 模型1 3 9 這種模型以任務(wù)模塊為基本測(cè)試單元 對(duì)系統(tǒng)的故障率進(jìn)行估測(cè) 這種模型 的優(yōu)點(diǎn)是任務(wù)的周期 任務(wù)切換方式 切換頻率以及任務(wù)故障率等基本參數(shù)易于分析 和測(cè)試 缺點(diǎn)是對(duì)于非實(shí)時(shí)系統(tǒng) 模塊之間的轉(zhuǎn)換方式和轉(zhuǎn)換頻率以及模塊間的接口 故障難確定 使得這一建模思想未得到進(jìn)一步的發(fā)展 1 3 現(xiàn)有可靠性評(píng)估的局限性與技術(shù)展望 雖然對(duì)分布式程序可靠性評(píng)估的研究取得了 定的成果 但是 面對(duì)分布式 程序應(yīng)用的越來越廣泛 構(gòu)造結(jié)構(gòu)的越來越復(fù)雜 現(xiàn)有的性能測(cè)試 評(píng)估方法遠(yuǎn)遠(yuǎn) 不能滿足實(shí)際需求 主要表現(xiàn)在 現(xiàn)有的性能測(cè)試和評(píng)估方法通常只是簡(jiǎn)單的針對(duì) 分布式程序性能的某一方面 沒有綜合考慮分布式程序不同性能之間的相互約束和 相互影響 如v k p r a s a n n a k u a m a r 和d j c h e n 等相關(guān)人員提出的f s t 算法 f s f 算法 m f s t 算法 f s t s p r 算法 f r e a 算法 s m 算法和f m 算法這些算法只是對(duì)分布式程序 的可靠性進(jìn)行評(píng)估 沒有綜合考慮實(shí)時(shí)性等其它性能對(duì)分布式程序可靠性的影響 如顧慶等相關(guān)人員只是對(duì)分布式程序的正確性進(jìn)行測(cè)試 沒有綜合考慮依賴性和 聚合性等其它性能對(duì)分布式程序正確性的影響 在實(shí)際運(yùn)用中 由于分布式程序的可靠性越來越重要 對(duì)實(shí)時(shí)性的要求也越來越 高 而實(shí)時(shí)性和可靠性又是反映分布式程序性能的兩個(gè)主要方面 因此 在對(duì)分布式 程序性能進(jìn)行測(cè)試和評(píng)估時(shí) 如何綜合考慮實(shí)時(shí)性和可靠性之間的相互約束和相互影 響將是 個(gè)迫切需要解決的問題 為了綜合考慮實(shí)時(shí)性和可靠性之間的相互約束和相互影響的關(guān)系 在對(duì)分布式程 序可靠性的進(jìn)行分析時(shí) 除了應(yīng)用標(biāo)準(zhǔn)的分布式程序可靠性模型的傳統(tǒng)方法外 還將 深入研究和開發(fā)分布式程序綜合性能的評(píng)估理論和評(píng)估模型 更好地為國(guó)民經(jīng)濟(jì) 社 會(huì)和國(guó)防服務(wù) 華中科技大學(xué)碩士學(xué)位論文 1 4 文章的研究?jī)?nèi)容和框架結(jié)構(gòu) 第一章是緒論 闡明了具有時(shí)間約束的分布式軟件可靠性評(píng)估研究的目的和意 義 分析了國(guó)內(nèi)外關(guān)于軟件可靠性和分布式軟件可靠性的一些評(píng)估方法 并分別指出 了這些評(píng)估方法的優(yōu)點(diǎn)和缺點(diǎn) 在此基礎(chǔ)上 對(duì)現(xiàn)有可靠性評(píng)估的局限性進(jìn)行了闡述 對(duì)可靠性評(píng)估技術(shù)進(jìn)行了展望 第二章是具有時(shí)間約束的分布式軟件可靠性評(píng)估的理論分析和推導(dǎo) 在根據(jù)分布 式軟件可靠性評(píng)估理論和方法 引入時(shí)間約束因子 對(duì)具有時(shí)間約束的分布式系統(tǒng)進(jìn) 行了形式化的描述 確定了具有時(shí)間約束的分布式軟件的可靠性評(píng)估指標(biāo) 理論分析 和推導(dǎo)出了具有時(shí)間約束的分布式軟件的可靠性評(píng)估的計(jì)算公式 第三章是具有時(shí)間約束的分布式軟件可靠性評(píng)估算法 基于可靠性評(píng)估的計(jì)算公 式 構(gòu)建了可靠性評(píng)估的一系列算法 并對(duì)可靠性評(píng)估的復(fù)雜性進(jìn)行了分析 第四章是評(píng)估實(shí)例 根據(jù)可靠性評(píng)估的一系列算法 描述了一個(gè)可靠性評(píng)估實(shí)例 的分析過程 計(jì)算過程和評(píng)估結(jié)果 第五章是具有時(shí)間約束的分布式軟件可靠性評(píng)估模擬器 主要描述了可靠性評(píng)估 模擬器的系統(tǒng)結(jié)構(gòu)和設(shè)計(jì)方法 第六章是基于模擬器的可靠性評(píng)估與結(jié)果分析 首先簡(jiǎn)要介紹了基于模擬器可靠 性評(píng)估的評(píng)估流程和實(shí)例生成 最后 對(duì)可靠性評(píng)估結(jié)果進(jìn)行了詳細(xì)的分析 第七章是結(jié)束語 主要是對(duì)文章的總結(jié)和對(duì)未來工作的展望 總之 本課題研究需要達(dá)到的要求是根據(jù)分布式計(jì)算機(jī)系統(tǒng)的體系結(jié)構(gòu)特點(diǎn) 結(jié) 合不同的應(yīng)用需要 在分布式程序基礎(chǔ)上 選擇適當(dāng)?shù)膮?shù)配置 建立具有時(shí)間約束 的分布式軟件可靠性評(píng)估模型和評(píng)估方法 確定性能測(cè)試指標(biāo) 在此基礎(chǔ)上 設(shè)計(jì)出 一種具有良好的穩(wěn)定性和可擴(kuò)展性 能夠提供靈活和友好的用戶界面 滿足不同用戶 需求的具有時(shí)間約束的分布式軟件可靠性評(píng)估系統(tǒng) 6 華中科技大學(xué)碩士學(xué)位論文 2 具有時(shí)間約束的分布式軟件可靠性評(píng)估理論 在對(duì)分布式程序的可靠性進(jìn)行評(píng)估時(shí) 依據(jù)d j c h e n 等相關(guān)人員提出的一系列 評(píng)估算法 首要步驟就是先對(duì)分布式系統(tǒng) d c s 進(jìn)行形式化的描述 接著再根據(jù)分布 式程序可靠性 d p r 評(píng)估的模型對(duì)分布式程序的可靠性進(jìn)行評(píng)估 由于具有時(shí)間約束 的分靠式系統(tǒng)和一般的分布式系統(tǒng)在結(jié)構(gòu)拓?fù)渖鲜窍嗤?唯一不同的是前者具有時(shí) 間約束而后者沒有 因此在對(duì)具有時(shí)間約束的分布式軟件的可靠性進(jìn)行評(píng)估時(shí) 基于 d j c h e n 等相關(guān)人員提出的分布式程序可靠性評(píng)估理論 增加時(shí)間約束因子 對(duì)具有 時(shí)間約束的分布式軟件可靠性進(jìn)行評(píng)估 2 1 分布式系統(tǒng)結(jié)構(gòu)與形式化的描述 一個(gè)分布式系統(tǒng) d c s 就是將一系列的計(jì)算機(jī) 通過通信網(wǎng)絡(luò)連接起來 在分布 式操作系統(tǒng)或者是分布式數(shù)據(jù)庫(kù)系統(tǒng)作用下 邏輯的成為一個(gè)整體 通信網(wǎng)絡(luò)在地 理上可以是分散的 也可以是局域網(wǎng) 雨分布式程序則是運(yùn)行在分布式操作系統(tǒng)之上 通過分布式操作系統(tǒng)能將任務(wù)分配到系統(tǒng)中的不同節(jié)點(diǎn)機(jī)上運(yùn)行 并返回?cái)?shù)據(jù) 程序 在節(jié)點(diǎn)機(jī)上執(zhí)行時(shí)可以訪問其它節(jié)點(diǎn)機(jī)上的數(shù)據(jù)文件 其它節(jié)點(diǎn)機(jī)上的數(shù)據(jù)文件通過 文件傳輸路徑可以傳輸?shù)匠绦蛩诘墓?jié)點(diǎn)機(jī) 如圖2 1 是 個(gè)簡(jiǎn)單的分布式系統(tǒng) 它 由六個(gè)節(jié)點(diǎn)機(jī) 七條傳輸鏈路 六個(gè)可執(zhí)行程序和七個(gè)可用的數(shù)據(jù)文件所組成 在對(duì) 分布式系統(tǒng)形式化描述時(shí) 通常用g 刈 e f p 表示這個(gè)分布式計(jì)算機(jī)系統(tǒng) 其中v 表示處理機(jī)的節(jié)點(diǎn)集合 e 表示處理機(jī)之間連接邊的集合 f 表示分布式計(jì)算機(jī)系統(tǒng) 中可用的數(shù)據(jù)文件集合 p 表示分布式計(jì)算機(jī)系統(tǒng)中的程序集合 如果用x i 表示一個(gè) 節(jié)點(diǎn)機(jī)i x j 表示節(jié)點(diǎn)機(jī)i 和節(jié)點(diǎn)機(jī)j 之間的鏈路 p i 表示分布式程序i f j 表示數(shù)據(jù) 文件j f n i 表示程序p i 執(zhí)行時(shí)所需的數(shù)據(jù)文件集 f a i 表示節(jié)點(diǎn)機(jī)x i 上可用的數(shù)據(jù)文 件集 p a i 表示節(jié)點(diǎn)機(jī)x i 上可執(zhí)行的程序集 則可以得到此分布式系統(tǒng)的形式化描述 g v e f p 其中v 2 x h x 2 x 6 e x 1 2 x t 3 x 2 3 x z a x 3 5 x 3 6 旭 5 p p i p 2 p 6 f f i f 2 f 6 f r f a i f i p a l p 1 f a 2 f 2 f 4 p a 2 p 2 p 3 f a a f 3 f 4 p a 3 2 p 3 f a 4 2 f f 4 f 5 p a 4 p 4 f a s 2 f 6 f t p a s p 5 f a 6 f 7 p a 6 p 5 p 6 華中科技大學(xué)碩士學(xué)位論文 圖2 1 一個(gè)分布式系統(tǒng)不意圖 由于具有時(shí)間約束的分布式計(jì)算機(jī)系統(tǒng)和分布式計(jì)算機(jī)系統(tǒng)具有相同的基本結(jié) 構(gòu) 并且在程序執(zhí)行 數(shù)據(jù)文件的訪問和數(shù)據(jù)文件在系統(tǒng)中的調(diào)度等方面具有相同之 處 不同之處只是前者具有時(shí)間約束的特性 因此對(duì)具有時(shí)間約束的分布式計(jì)算機(jī)系 統(tǒng)的描述可以表示為g v e f p t 其中v e f p 的含義與g v e f p 中v e f p 相同 t 表示文件傳輸?shù)募s束時(shí)間 為了便于對(duì)具有時(shí)間約束的分布式軟件可靠 性的分析和評(píng)估 將繼續(xù)引用上述符號(hào) 即 x i 表示一個(gè)節(jié)點(diǎn)機(jī)i x i f 表示節(jié)點(diǎn)機(jī)i 和節(jié)點(diǎn)機(jī)j 之間的鏈路 p j 表示分布式程序i f j 表示數(shù)據(jù)文件j f n i 表示程序p i 執(zhí)行時(shí)所需的數(shù)據(jù)文件集 f a 表示節(jié)點(diǎn)機(jī)x i 上可用的數(shù)據(jù)文件集 p a 表示節(jié)點(diǎn)機(jī)x 上可執(zhí)行的程序集 在引用上述符號(hào)的基礎(chǔ)上 考慮到時(shí)間約束的特性 引入 t 符號(hào) 表示文件傳輸?shù)?約束時(shí)間值 4 0 4 1 如圖2 1 如果在此分布式系統(tǒng)中引入時(shí)間約束因子t a t 則可以得到此圖的關(guān) 于具有時(shí)間約束的分布式系統(tǒng)的形式化描述 即為g f v e f p t 其中 v 2 x l x 2 x 6 e x l 2 x i 3 x 2 3 x 2 4 x 3 5 x 3 6 陽(yáng) 5 p p l p 2 p 6 i f 1 f 2 f 6 y 7 f a i f i p a l 2 p 1 f a 2 f 2 f 4 p a 2 2 p 2 p 3 f a 3 5 f 3 f 4 p a 3 p 3 f a 4 f 4 f s p a 4 p 4 f a 5 2 f 6 f 7 p a 5 p 5 f a 6 f 7 p a 6 p 5 p 6 t a t 華中科技大學(xué)碩士學(xué)位論文 2 2 可靠性評(píng)估指標(biāo)的確定 在確定具有時(shí)間約束的分布式軟件可靠性的評(píng)估指標(biāo)時(shí) 首先需要考慮的兩個(gè)方 面 即分布式程序可靠性評(píng)估和時(shí)間約束因子 為此將從這兩個(gè)方面探討具有時(shí)間約 束的分布式軟件可靠性的評(píng)估指標(biāo) 1 分布程序可靠性的評(píng)估方法和評(píng)估指標(biāo) 在文獻(xiàn) 2 4 中提到的關(guān)于一種分布式程序的可靠性評(píng)估方法 這種方法根據(jù)分布 式程序執(zhí)行所需的數(shù)據(jù)文件和數(shù)據(jù)文件在系統(tǒng)中節(jié)點(diǎn)機(jī)的位置 基于文件傳輸路徑 利用k 個(gè)端點(diǎn)的網(wǎng)絡(luò)因式分解對(duì)分布式程序的可靠性進(jìn)行評(píng)估 在這種評(píng)估方法中最 主要的算法就是最小文件生成樹 m f s t 算法 最小文件生成樹 m f s t 算法的基本思 想是 首先以分布式程序所在的節(jié)點(diǎn)作為根節(jié)點(diǎn) 根據(jù)分布式程序執(zhí)行時(shí)所需的數(shù)據(jù) 文件和數(shù)據(jù)文件在分布式系統(tǒng)中節(jié)點(diǎn)機(jī)的位置 通過廣度優(yōu)先的方式遍歷分布式系 統(tǒng)示意圖 產(chǎn)生所有的m f s t 然后 利用k 個(gè)端點(diǎn)的網(wǎng)絡(luò)因式分解對(duì)每個(gè)m f s t 的 月 可靠性進(jìn)行評(píng)估 最后 利用d p r p r ij m f s t j 其中 n 表示能夠運(yùn)行分布式程 禹 序的m f s t 的數(shù)量 計(jì)算出分布式程序的可靠性 在這種評(píng)估方法中 對(duì)分布式程序 進(jìn)行評(píng)估所采用的指標(biāo)是分布式程序的可靠度 在文獻(xiàn) 2 7 中進(jìn)一步提出了關(guān)于產(chǎn)生m f s t 的改進(jìn)算法 這種算法稱為快速的可 靠性評(píng)估方法 f i 也a 在f r e a 中主要是根據(jù)分布式程序所在的節(jié)點(diǎn)機(jī)和數(shù)據(jù)文件 在系統(tǒng)中節(jié)點(diǎn)機(jī)上的位置 首先采用d e g r e e 1 精簡(jiǎn) p a r a l l e l 精簡(jiǎn) s e r i e s 精簡(jiǎn)和 d e g r e e 2 精簡(jiǎn)等 然后通過廣度優(yōu)先遍歷分布式系統(tǒng)精簡(jiǎn)圖 產(chǎn)生所有的m f s t 然 后 利用k 個(gè)端點(diǎn)的網(wǎng)絡(luò)因式分解對(duì)每個(gè)m f s t 的可靠性進(jìn)行評(píng)估 最后 利用 n d p r p r l j m f s t 計(jì)算出分布式程序的可靠性 它所采用的評(píng)估指標(biāo)依然是分布式 蜀 程序的可靠度 在s m 算法中 首先將所有節(jié)點(diǎn)機(jī)看作理想節(jié)點(diǎn)機(jī) 通過廣度優(yōu)先 產(chǎn)生所有的 m f s t 然后在傳輸路徑中考慮節(jié)點(diǎn)機(jī)的非理想狀態(tài)對(duì)評(píng)估的影響 利用網(wǎng)絡(luò)端點(diǎn)的 可靠性評(píng)估方法 如s y r e l 對(duì)分布式程序的可靠性進(jìn)行評(píng)估 在這種評(píng)估方法中 對(duì)分布式程序進(jìn)行評(píng)估所采用的指標(biāo)也是分布式程序的可靠度 在f m 算法中 首先將可執(zhí)行分布式程序的節(jié)點(diǎn)機(jī)組成一個(gè)集合 然后 在這集 合中取出一系列的節(jié)點(diǎn) 考慮這些節(jié)點(diǎn)機(jī)之間的鏈路傳輸數(shù)據(jù)文件的可靠性 利用k 華中科技大學(xué)碩士學(xué)位論文 端點(diǎn)的網(wǎng)絡(luò)因式分解定理 對(duì)分布式程序的可靠性進(jìn)行評(píng)估 它所采用的評(píng)估指標(biāo)依 然是分布式程序的可靠度 2 分布程序?qū)崟r(shí)性的評(píng)估方法和評(píng)估指標(biāo) 在文獻(xiàn) 2 4 q a 提到的一種具有可靠性約束的分布式程序的實(shí)時(shí)性評(píng)估方法 這種 評(píng)估方法是建立在文件傳輸路徑的基礎(chǔ)上 借鑒分布式系統(tǒng)實(shí)時(shí)性評(píng)估的基本理論 在數(shù)據(jù)文件滿足一定的可靠性的前提下 對(duì)分布式程序的實(shí)時(shí)性進(jìn)行評(píng)估 在這種評(píng) 估方法中分別使用了數(shù)據(jù)文件生成算法 數(shù)據(jù)文件傳輸路徑的傳輸時(shí)間評(píng)估算法 數(shù) 據(jù)文件傳輸時(shí)間的排序算法 具有可靠性約束的分布式程序?qū)崟r(shí)性評(píng)估算法等算法 數(shù)據(jù)文件生成算法的基本思想是 首先將分布式計(jì)算機(jī)系統(tǒng)中的各個(gè)節(jié)點(diǎn)機(jī)均設(shè) 為將要檢測(cè)的節(jié)點(diǎn) 然后根據(jù)分布式程序在系統(tǒng)中的位置 確定分布式程序所在的節(jié) 點(diǎn)并以此節(jié)點(diǎn)為根節(jié)點(diǎn)進(jìn)行深度優(yōu)先搜索 根據(jù)分布式程序執(zhí)行時(shí)所需數(shù)據(jù)文件在節(jié) 點(diǎn)機(jī)上的位置 在數(shù)據(jù)文件的所有傳輸鏈路中判斷和確定數(shù)據(jù)文件的傳輸路徑 將此 路徑中各鏈路的通訊能力和數(shù)據(jù)文件的大小映射到文件p a t h l 中 數(shù)據(jù)文件傳輸路徑的傳輸時(shí)間評(píng)估算法的基本思想是 根據(jù)文件傳輸路徑中各鏈 路之間的傳輸能力和所傳輸文件的大小 分別計(jì)算出數(shù)據(jù)文件在各個(gè)鏈路上的傳輸時(shí) 間并將這些傳輸時(shí)間相加 得到數(shù)據(jù)文件在這路徑上的傳輸時(shí)間 將數(shù)據(jù)文件在這路 徑上的傳輸時(shí)間保存到文件t i m e p a t h l 中 數(shù)據(jù)文件傳輸時(shí)間的排序算法的基本思想是 將t i m e p a t h l 中每個(gè)數(shù)據(jù)文件的所 有傳輸路徑的傳輸時(shí)間分別按從小到大的順序排序 再將這種排序結(jié)果保存到文件 t i m e p a t h 2 中 具有可靠性約束的分布式程序?qū)崟r(shí)性評(píng)估算法的基本思想是 根據(jù)分布式程序執(zhí) 行時(shí)的可靠性約束條件 確定程序執(zhí)行時(shí)數(shù)據(jù)文件應(yīng)該具有的可靠性 根據(jù)數(shù)據(jù)文件 具有的可靠性約束條件 計(jì)算數(shù)據(jù)文件的實(shí)時(shí)時(shí)間 從而計(jì)算出具有可靠性約束下的 分布式程序的實(shí)時(shí)時(shí)間 從這種具有可靠性約束的分布式程序的實(shí)時(shí)性評(píng)估方法所用的評(píng)估思想可以看 出 它所采用的評(píng)估指標(biāo)實(shí)際上的分布式程序在滿足可靠性條件下程序的響應(yīng)時(shí)間 從上面關(guān)于分布式程序性能評(píng)估的兩個(gè)方面來看 對(duì)分布式程序可靠性的評(píng)估均 是采用程序的可靠度作為分布式程序可靠性的指標(biāo) 對(duì)分布式程序?qū)崟r(shí)性進(jìn)行評(píng)估考 慮的是文件的傳輸時(shí)間和程序的響應(yīng)時(shí)間 由于分布式程序和具有時(shí)間約束的分布式 軟件都同樣具有可靠性特性的問題 因此 在對(duì)具有時(shí)間約束的分布式軟件的可靠性 進(jìn)行評(píng)估是將繼續(xù)采用這一指標(biāo) 對(duì)其進(jìn)行評(píng)估 同時(shí) 考慮到具有時(shí)間約束的分布 1 0 華中科技大學(xué)碩士學(xué)位論文 式軟件具有時(shí)間約束因子 即當(dāng)分布式程序運(yùn)行超時(shí)的時(shí)候 分布式程序的執(zhí)行將為 錯(cuò)誤的狀態(tài) 因此 具有時(shí)間約束的分布式軟件在運(yùn)行時(shí)有狀態(tài)變遷的問題 故在對(duì) 具有時(shí)間約束的分布式軟件的可靠性進(jìn)行評(píng)估時(shí) 將引進(jìn)平均故障時(shí)間作為可靠性的 評(píng)估指標(biāo) 2 3 可靠性評(píng)估的相關(guān)概念和定義 由于具有時(shí)間約束的分布式軟件可靠性評(píng)估將采用程序的可靠度和平均故障時(shí) 間兩個(gè)評(píng)估指標(biāo) 因此 在對(duì)具有時(shí)間約束的分布式軟件可靠性評(píng)估理論進(jìn)行分析和 推導(dǎo)時(shí) 將會(huì)借鑒分布式程序可靠性評(píng)估的一些理論 在此基礎(chǔ)上 增加時(shí)間約束因 子 對(duì)其可靠性進(jìn)行評(píng)估 為了方便的對(duì)具有時(shí)間約束的分布式軟件的可靠性評(píng)估理 論進(jìn)行分析和推導(dǎo) 也為了使可靠性評(píng)估的算法和過程更容易理解 將引入相關(guān)概念 和定義 定義l 文件生成樹 f s t 是指在分布式系統(tǒng)示意圖中 由分布式程序所在的節(jié)點(diǎn) 和其它一些節(jié)點(diǎn)相連接而構(gòu)成的圖形 這種圖形包含了此分布式程序執(zhí)行時(shí)所需的所 有數(shù)據(jù)文件 以圖2 1 中的分布式系統(tǒng)為例來說明文件生成樹 在圖2 1 中 分布式程序p l 位于節(jié)點(diǎn)機(jī)x l 上 程序p l 執(zhí)行時(shí)所需數(shù)據(jù)文件f l f 2 f 3 f 4 而數(shù)據(jù)文件f l f 2 f 3 f 4 分別位于不同的節(jié)點(diǎn)機(jī)上 在圖2 2 中 它包含了分布式程序p l 所在的節(jié)點(diǎn)機(jī) x l 也包含了程序p 1 執(zhí)行時(shí)所需的所有數(shù)據(jù)文件 這些數(shù)據(jù)文件所在的節(jié)點(diǎn)機(jī)和程序 所在的節(jié)點(diǎn)機(jī)是相互連通的 因此 在圖2 1 中 對(duì)于分布式程序p l 來講 圖2 2 就 是一個(gè)文件生成樹 f a 2f 2 f 4 華中科技大學(xué)碩士學(xué)位論文 定義2 最小文件生成樹 m f s t 是指在一個(gè)文件生成樹中不再含有其它子文件 生成樹的圖形 以圖2 1 中的分布式系統(tǒng)為例來說明最小文件生成樹 在圖2 1 中 分布式程序 p i 位于節(jié)點(diǎn)機(jī)x 1 上 程序p 1 執(zhí)行時(shí)所需數(shù)據(jù)文件f 卜f 2 f 3 f 4 而數(shù)據(jù)文件f 1 f 2 f 3 f 4 分別位于不同的節(jié)點(diǎn)機(jī)上 在圖2 3 的兩個(gè)圖中 每個(gè)圖都包含了分布式 程序p 所在的節(jié)點(diǎn)機(jī)x 也包含了程序p l 執(zhí)行時(shí)所需的所有數(shù)據(jù)文件 這些數(shù)據(jù)文 件所在的節(jié)點(diǎn)機(jī)和程序所在的節(jié)點(diǎn)機(jī)是相互連通的 從定義1 可以知道 這兩個(gè)圖形 對(duì)于圖2 1 中程序p 1 來講都是文件生成樹 但是 這兩個(gè)文件生成樹的其它子圖 不 包含它自己本身的子圖 都不是文件生成樹 因此 在圖2 1 中 對(duì)于分布式程序p 1 來講 圖2 3 中的兩個(gè)圖形就是兩個(gè)最小文件生成樹 f n l ft f 2 f 3 f 畸 1 2 圖2 3圖2 1 中程序p 1 的兩個(gè)最小文件生成樹 定義3 具有時(shí)間約束的分布式軟件的可靠度是指軟件在分布式系統(tǒng)中運(yùn)行時(shí) 在規(guī)定的時(shí)間范圍內(nèi)能夠成功執(zhí)行的概率 定義4 冗余節(jié)點(diǎn)是指在原分布式系統(tǒng)中 如果一個(gè)節(jié)點(diǎn)的度數(shù)為2 且這個(gè)節(jié)點(diǎn) 不是任何m f s t 的葉節(jié)點(diǎn) 那么這個(gè)節(jié)點(diǎn)就稱為冗余節(jié)點(diǎn) 2 4 可靠性評(píng)估的理論分析和推導(dǎo) 在分布式系統(tǒng)中 程序在節(jié)點(diǎn)機(jī)中通常以一種冗余的方式存在 每個(gè)程序能夠在 一臺(tái)計(jì)算機(jī)或多臺(tái)計(jì)算機(jī)上運(yùn)行并能在執(zhí)行時(shí)訪問其它節(jié)點(diǎn)機(jī)上的數(shù)據(jù)文件 因此對(duì) 于任意一個(gè)分布式程序 其整個(gè)程序的運(yùn)行時(shí)間將包括兩部分 一部分是分布式程序 在節(jié)點(diǎn)機(jī)上真正執(zhí)行的時(shí)間 另一部分是分布式程序執(zhí)行時(shí) 數(shù)據(jù)文件在鏈路中的傳 1 2 華中科技大學(xué)碩士學(xué)位論文 輸所需的時(shí)間 由于分布式程序能夠在多個(gè)節(jié)點(diǎn)機(jī)上運(yùn)行 并且在當(dāng)今每個(gè)節(jié)點(diǎn)機(jī)的 c p u 的運(yùn)算能力都很強(qiáng) 分布式程序在節(jié)點(diǎn)機(jī)上真正執(zhí)行的時(shí)間與分布式程序執(zhí)行時(shí) 數(shù)據(jù)文件在鏈路中傳輸所花費(fèi)的時(shí)間比較起來 前者微不足道 因此 在計(jì)算分布式 程序的運(yùn)行時(shí)間時(shí)將主要計(jì)算數(shù)據(jù)文件在鏈路中的傳輸時(shí)間 綜上所述 在對(duì)具有時(shí)間約束的分布式軟件可靠性評(píng)估的理論進(jìn)行分析時(shí) 將不 再考慮分布式程序在節(jié)點(diǎn)機(jī)上真正執(zhí)行的時(shí)間對(duì)具有時(shí)間約束的分布式軟件可靠性 評(píng)估的影響 在文獻(xiàn) 2 4 1 c p 描述了一種關(guān)于分布式程序的可靠性評(píng)估方法 這種評(píng)估方法中最 主要的算法就是f s t 算法 它