ＤＮＡ計算在軟件抗衰技術中的應用研究

摘要:針對軟件系統中進程間控制#65380;調用及數據訪問的關系，分析了進程間的耦合程度，給出了判定進程間重啟相關度方法和系統重啟樹的構建規則，并結合DNA計算的原理和特性，給出了判定進程間重啟相關度DNA計算模型，并初步制定了重啟實施策略，為實現智能化細粒度軟件抗衰提供支持。

關鍵詞:軟件抗衰; 重啟相關度; 重啟樹; DNA計算

中圖分類號:TP302.7文獻標志碼:A

文章編號:1001－3695(2008)02－0436－04

軟件老化是指在軟件的長期不間斷運行過程中，由于系統內存占用和泄漏#65380;未釋放的文件鎖#65380;數據更新不及時#65380;存儲空間碎片以及舍入誤差的累積等原因而導致的軟件性能的衰退[1~3]。軟件老化最終導致軟件的失效。為對抗軟件老化，提出了軟件抗衰(software rejuvenation，SR)[2]策略。SR是當軟件性能衰退到一定程度時，終止程序的繼續運行，重啟系統以清理其內部狀態(如進行垃圾收集#65380;刷新操作系統內核表#65380;重新初始化內部數據結構等)，從而釋放操作系統資源，使軟件性能得到恢復[2，3]。

軟件抗衰是一種對軟件老化現象的積極反應，是在軟件故障發生前采取的重啟策略。許多已知和未知的軟件故障均可以通過軟件整體或部分的重啟排除。UC Berkeley和Stanford大學合作開展的面向恢復的計算(recovery oriented computing，ROC)的研究中提出的遞歸重啟(recursive restartability，RR)技術[4，5]和Candea提出的微重啟(microreboot)技術[6，7]，是預先建立一棵重啟樹(restart tree)，當執行重啟操作時，從重啟樹最底層的模塊開始重啟，性能不能恢復則上推一級，執行更大范圍的重啟。這兩種技術在軟件開發之初即遵循了模塊間松耦合的原則，使得一個模塊的重啟不會影響其他模塊的正常工作，其抗衰的粒度相對較大，限制程度也比較高，同時智能性和適用性相對較弱。要制定智能化細粒度的軟件抗衰策略，可以借鑒文獻[5，6]的思想，分析系統進程間的耦合關系，制定判定進程重啟相關性和重啟相關度的方法，最終確立系統的重啟樹，為系統的進程級細粒度軟件抗衰提供支持。

為了執行細粒度的SR，提高軟件抗衰技術的執行效率，進一步提高抗衰技術的智能化和自動化，本文分析了軟件系統中進程的耦合關系，定義了進程間的耦合程度，給出了進程重啟相關性和重啟相關度的判定方法，制定了系統重啟樹的構建方法;同時結合DNA計算的原理和特點，初步確定了軟件抗衰的DNA計算模型，實現準確高效地判定系統進程重啟相關度的目標，制定了系統的重啟實施策略，從而從根本上實現高效智能化細粒度進程級軟件抗衰技術。

1進程與進程耦合性

軟件包括計算機程序#65380;程序所使用的數據及有關的文檔資料。軟件分為系統軟件和為特定應用建立的應用軟件。系統軟件與計算機硬件交互，是處理不確定數據結構的程序，即操作系統。它們是底層通用的軟件，為特定應用建立的應用軟件往往是建立在它們之上的。不同的軟件系統皆由協同工作的軟件進程構成。進程就是一個正在執行的程序，包括程序計數器#65380;寄存器和變量的當前值。

盡管每個進程是一個獨立的實體，但進程間經常發生交互作用，這種進程連接的緊密程度稱為耦合性。進程間的連接越緊密，聯系越多，耦合程度越高。根據進程間交換數據的情況，通常將耦合性分為五類，即非直接耦合#65380;數據耦合#65380;控制耦合#65380;公共耦合和內容耦合。

如果進程間通過接口的參數表交換信息數據，稱為數據耦合。若上層進程調用下層進程完成指定功能，若調用關系是通過參數傳遞來實現的，稱為控制耦合。若進程間通過一個公共環境進行數據交換，稱為公共耦合。這個公共環境可以是全局變量#65380;全局數據結構#65380;通信緩沖區和數據(庫)文件等。若進程直接進入另一個進程中存取數據或使用服務，或存在雙向調用關系，稱為內容耦合。以上四種耦合的耦合程度依次增加。其中，內容耦合的適應性最差。如果進程間的聯系只是通過上層進程的控制和調用來實現，則視其為非直接耦合。本文中將采取直接交互方式而發生數據#65380;控制#65380;公共#65380;內容四種耦合關系的進程稱為直接耦合進程。

2進程重啟相關性及重啟相關度的判定

一個進程重啟時，可能導致其他進程的故障或錯誤，稱為進程間的重啟相關性。進程間重啟相關性取決于它們的耦合程度。對應于進程間的幾種耦合性，將重啟相關性分為四類，即相互獨立#65380;功能相關#65380;狀態相關和功能雙向相關。定義如下:

定義1若進程A調用進程B，則A與B功能相關，記為A→B。

性質1功能相關的傳遞性:若A→B，B→C，則A→C。

定理1若進程A與B功能相關，則A重啟，B同時重啟，但B重啟時，A不一定重啟。

定義2若A→B，且B→A，則A與B功能雙向相關，記為AB。

性質2功能雙向相關具有交換性和傳遞性。若AB，則BA;若AB，BC，則AC。

定理2若進程A與B功能雙向相關，則其中一個進程重啟;另一進程同時重啟，即A與B總是同時重啟。

定義3若A與B有數據或狀態共享，則A與B狀態相關，記為A∧B。

性質3狀態相關具有交換性和傳遞性。若A∧B，則B∧A;若A∧B，B∧C，則A∧C。

定理3若進程A與B狀態相關，則其中一個進程需重啟;另一進程同時重啟，即A與B總是同時重啟。

定義4若進程A與B既非功能相關也非狀態相關，則A與B相互獨立，記為AB。

性質4相互獨立的交換性:若AB，則BA。

在數據耦合和非直接耦合的情況下，相應的進程認為相互獨立。相對獨立不存在傳遞性。當兩進程非直接相連時，判定它們的重啟相關性需要考慮其間經過的所有進程之間的重啟相關性。

定義5一個進程A重啟與另一進程B重啟的相關程度稱為重啟相關度D[A·B]，取值為{0，1，-1，2，3，4}。具體地，D[AB]=0，D[A→B]=1，D[A∧B]=2，D[AB]=3。另外定義D[A·A]為進程A自身重啟相關度，且D[A·A]=4。特別地，若A→B，則記B與A的重啟相關度為D[B·A]=-1。

可推知D[A·B]=0/1/2/3A相對B獨立/A與B功能相關/A與B狀態相關/A與B功能雙向相關。

約定1當兩個進程之間存在多種重啟相關性時，取重啟相關度最高的相關性。當兩個進程之間存在多種耦合時，取最高的耦合。

定義6若進程A與B功能相關，認為從A可達B，但從B不可達A;若進程A與B狀態相關或功能雙向相關，認為A與B相互可達;若進程A與B相互獨立，認為A與B相互不可達;反之亦然。

定義7若進程A與K非直接連接，但A經若干進程可達K，則認為從A到K間有一條可達路徑R[A~K]，經歷的進程以“-”連接。

約定2若從進程A到K存在可達路徑R[A~K]=A-K1-K2-…-Kn-K，則A與K的重啟相關度為D[A·K]=min{D[A·Kn]，D[Kn·K]}。

推論1若進程A與K間存在可達路徑R[A~K]，但不存在可達路徑R[K~A]，則A與K功能相關。

推論2若進程A與K間既不存在可達路徑R[A~K]，也不存在可達路徑R[K~A]，則A與K相互獨立。

推論3若進程A與K間既存在可達路徑R[A~K]，又存在可達路徑R[K~A]，則A與K或狀態相關或功能雙向相關。

對于定理1~3及推論1~3在文獻[7]中給出了詳細證明。

3生成重啟樹

重啟任一進程時，必須同時重啟其與之重啟相關性超過一定限度的所有進程，視為一個重啟群。因此進程執行重啟操作前，必先計算其重啟相關度和可達集。否則會出現數據丟失，數據不一致，甚至軟件失效等運行錯誤。

3.1進程可達集的生成

定義8若從進程A到K存在可達路徑R[A~K]，則K為進程A的可達進程。A的所有可達進程構成A的可達進程集，簡稱可達集，用S[A]表示。

定理4進程A與其任意可達進程K的重啟相關度D[A·K]>0。

若K為進程A的可達進程，則存在可達路徑R[A~K]，由推論1#65380;3得進程A與K間至少為功能相關，據定義5，D[A·K]>0。

由此要確定各進程的可達集，需以下步驟:

a)確認初始進程和終結進程。因為可達路徑是單向的。

b)查找從初始進程到終結進程的所有可達路徑。

c)按每一條可達路徑求初始進程和終結進程間的重啟相關度。

d)確定初始進程和終結進程的最終重啟相關度及重啟相關性。

e)將與初始進程的重啟相關度大于零的終止進程放入初始進程可達集中。

3.2重啟樹的構建

重啟樹是由重啟進程的可達集構成的一種倒置的樹狀結構。但它并不是眾多重啟進程可達集的隨意組合，需要根據軟件的實際運行情況進行分析。具體步驟如下:

a)監控需要分析軟件的運行情況，在不同的運行環境和實際情況下，分析導致軟件性能衰退的是何種系統資源。可能在不同情況下，導致性能衰退的系統資源不同，也可能是幾種系統資源同時導致性能衰退，但影響的程度不同。對其中任一種系統資源，執行步驟b)~e)。

b)對損耗該類系統資源的應用進程排序。注意損耗并不是指資源的占用量，而是指占用后不使用也不釋放的資源量。

e)按前述方法分析所排進程序列中任一進程對其他進程的重啟相關度和可達集。

d)將損耗該類系統資源最多的進程的可達集作為第一級重啟群。在重啟樹中表示為第一層的葉子。

e)按步驟b)所排次序，判斷下一進程可達集是否屬于以前所有進程的可達集的并集的子集，是則忽略該進程，分析其后續進程，否則將其作為下一級重啟群。在重啟樹中表示為下一層的葉子。依此類推，可得重啟樹的一個枝。

f)若軟件的性能衰退是同時由幾種系統資源的損耗導致的，則對其他系統資源重復步驟b)~e)，得到重啟樹的其他枝。

g)合并重啟樹的各枝，將各枝最底層葉子的并集作為該層重啟群，若該并集為所有進程的全集U，則視其為重啟樹的根，否則將全集U作為重啟樹的根。以此來恢復其他意外或不可測因素導致的失效。

4DNA計算在軟件重啟中的應用

在計算機中，利用有機分子的信息處理能力來代替數字開關部件，這就是DNA計算的基本思想。分析軟件抗衰中進程重啟相關性和重啟相關度的判定方法，結合DNA計算的原理，可確定其在判定進程重啟相關度以構建系統重啟樹中的可用性。

4.1簡明進程交互圖的確定

確定直接耦合進程的耦合程度是判定任意進程間的重啟相關度前提，故進程間的交互圖的提取和確定成為首要工作。軟件系統中UML組件圖具有統一的標準并且概念明確#65380;圖形結構清晰，可將其作為構建進程交互圖的原始圖形，并對其重要交互信息加以提取，最終構建出所要求的簡明的直接耦合進程交互圖。

4.2DNA計算判定進程重啟相關度

設定所得直接耦合進程交互圖中每條邊表示為E(s，d，e)。其中:s為起始進程;d為終止進程;e為有向邊的權值。為了方便利用推論1#65380;2#65380;3來判定任意進程間的重啟相關度，將所得直接耦合進程交互圖作如下轉換:

此時假定通過對系統進行長時間監測或經驗數據的分析知，物理內存的損耗與CPU的占用是導致系統性能衰退的主要因素，將系統各進程對物理內存的損耗程度排序為c，e，g， f，則對應的重啟樹的一枝如圖2所示;將系統各進程對CPU的損耗程度排序為d，b，h，a，可得重啟樹的另一枝如圖3所示;由此最終獲得的系統重啟樹如圖4所示。

5重啟的實施

實際的重啟應該以一種順序方式執行，因此需根據實際情況建立有序重啟鏈。該重啟鏈可能是重啟樹的一個分枝，也可能是多個分枝的順序鏈接或交叉鏈接。具體如下:

情況1若軟件衰退主要由某一因素引起，且其他因素影響相對小得多，則將重啟樹的一個分枝作為重啟鏈，重啟樹的根為鏈尾。

情況2若軟件衰退比較有規律，且運行過程中導致系統性能衰退的諸因素的主次不會發生變化，則按其決定各分枝重啟的先后順序，影響越大越早重啟。按該順序將重啟樹的枝首尾相接形成重啟鏈。若后面分枝中的葉子表示的重啟可達集是重啟鏈中前面葉子的子集，則忽略該葉子。重啟樹的根作為鏈尾。

情況3若軟件衰退無固定規律可循，其影響因素在運行過程的不同階段和不同環境下也不確定，重啟部分進程后軟件的衰退規律難以估計，則需通過實時監測值確定按哪一枝執行重啟。用這種方法得到的重啟鏈隨實際情況不同而變化，且各級恢復的次數不定，當監測值達到預定閾值時即執行相關模塊重啟。同樣地，重啟樹的根作為鏈尾。

如對于圖4中的重啟樹，若物理內存的損耗是軟件衰退的主要因素，與其比較，CPU的損耗小得多，則根據情況一，可以得到重啟鏈S[c]#S[e]#S[f]#U;若物理內存的損耗是軟件衰退的主要因素，CPU的損耗是次要因素但必須考慮，則可以按情況二確定重啟鏈:S[d]#S[b]#S[a]#U。舉例說明情況三，軟件開始運行時，導致系統性能衰退的主要因素為物理內存的損耗，則S[c]為重啟鏈的頭，一段時間后，檢測到CPU的損耗成為主要因素，則應按另一枝執行重啟，因此有S[c]#S[d]。注意即使S[d]S[c]，也不忽略該重啟群。因為對CPU的損耗不一定是由于重啟S[c]無法釋放足夠的CPU，可能是由于當時運行環境造成的。若確實重啟S[d]沒有釋放足夠CPU，再重啟該分枝中下一個葉子。依此類推，根據運行過程中的實際監測值，可以決定重啟群并獲得一重啟鏈。

6結束語

要執行智能化細粒度進程級軟件抗衰策略，進一步增強軟件抗衰的適用性和靈活性，更大程度地節省抗衰成本，并從根本上實現軟件抗衰的智能化和自動化，以此提高軟件的可靠性，必須具備三個前提條件:一是軟件系統進程運行協作情況可監控;二是能夠確定合理的計算系統任意進程間重啟相關度和生成系統重啟樹的方法;三是構建DNA計算數學模型快速高效地判定進程重啟相關度，以實現系統恢復;一般情況下，軟件系統都滿足第一個條件。

第二個條件是實現第三個條件的前提，本文根據軟件系統中進程間的控制調用及數據訪問關系，分析了進程間的耦合程度，給出了判定進程重啟相關度和構建系統重啟樹的方法，并在此基礎上結合DNA計算的原理及快速高效的特點，給出了在重啟技術中DNA計算的數學模型，制定了系統初步的重啟實施策略，從根本上解決了計算系統運行時由于進程易變#65380;量多而導致的進程間重啟度難以快速判定的問題。

第三個條件是實現智能化細粒度進程級軟件抗衰的關鍵。本文分析了DNA計算的特點和原理，初步構造出了基于DNA計算的軟件抗衰進程重啟數學模型，并給出了模型的功能作用和工作原理，從而利用此模型快速高效地判定出系統中任意進程重啟相關度，進而構建出系統的重啟樹，制定出初步的系統重啟實施策略，最終為執行細粒度的進程級軟件抗衰策略奠定了堅實的基礎，從根本上實現了軟件抗衰的智能化和自動化。并在很大程度上提高了抗衰技術的實施效率，更大程度地節約了抗衰成本，從而增強了抗衰技術的適用性和靈活性，提高了軟件可靠性。

參考文獻:

[1]GARG S， MOORSEL A V， VAIDYANATHAN K. A methodology for detection and estimation of software aging[C]//Proc of the 9th International Symposium on Software Reliability Engineering. Washington D C: IEEE Computer Society， 1998:283.

[2]HUANG Y， KINTALA C， KOLETTIS N. Software rejuvenation: analysis， module and applications[C]//Proc of FTCS－25. Pasadena， CA: IEEE Computer Society， 1995.

[3]CASTELLI V， HARPER R E， HERDELBERGER P. Proactive ma－nagement of software aging[J]. IBM JRD， 2001，45(2):311－332.

[4]CANDEA G， FOX A. Recursive restartability: turning the reboot sledgehammer into a scalpel[C]//Proc of the 8th Workshop on Hot Topics in Operating Systems.[S.l.]: IEEE， 2001.

[5]CANDEA G， KAWAMOTO S， FUJIKI Y. Microreboot: a technique for cheap recovery[C]//Proc of the 6th Symposium on Operating Systems Design and Implementation. Berkeley， CA: USENIX Association， 2004.

[6]CANDEA G， CUTLER J， FOX A. Improving availability with recursive microreboots: a soft－state system case study[J]. Performance Evaluation Journal， 2004，56(1－3):213－248.

[7]王湛，游靜，趙顏利，等.基于訪問關系的進程重啟相關性判定[J].計算機科學，2006，33(9):274－277.

[8]HONG Y， CHEN D， LI L. Closed loop design for software rejuvenation[C]//Workshop on Self－Healing， Adaptive and Self－Managed Systems(SHAMAN). New York: ACM， 2002.

[9]XIEA W， HONGB Y， TRIVEDI K. Analysis of a two－level software rejuvenation policy[J]. Reliability Engineering and System Safety， 2005，87(1):13－22.

[10]PATTERSON D， BROWN A， BROADWELL P. Recovery oriented computing(ROC): motivation， definition， techniques， and case studies， UCB/CSD－02－1175[R].[S.l.]:UC Berkeley Computer Science， 2002.

[11]YOU Jing， XU Jian， ZHAO Xue－long， et al. Modeling and cost ana－lysis of nested software rejuvenation policy[J]. LNCS， 2005，3612:1280－1289.

[12]YOU Jing， XU Jian， ZHAO Xue－long， et al. Modeling and availability analysis of nested software rejuvenation policy[J]. IEEE SMC， 2005，1(10－12):34－38.

[13]KARI L.DNA computing: tomorrow’s reality[M].River Edge:World Scientific Publishing， 2001:811－829.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”