基于排隊論的軟件可靠性增長模型

摘要：軟件可靠性增長模型是軟件可靠性評估的重要手段。基于排隊論的軟件可靠性增長模型研究起步比較晚，但因排隊論在計算機系統性能評價等方面表現出的優異能力，使排隊論在計算機科學研究領域得到了廣泛的應用。對基于排隊論的軟件可靠性增長模型作了簡要介紹。在分析了有關模型的基礎上，指出了該領域研究中存在的一些問題，并對今后的研究方向提出了一些建議。

關鍵詞：軟件可靠性； 軟件可靠性增長模型； 無限服務臺排隊模型； 有限服務臺排隊模型

中圖分類號：TP3115 文獻標識碼：A文章編號：2095-2163（2013）02-0016-04

0引言

軟件可靠性增長模型是軟件可靠性評估的重要手段之一，是軟件可靠性評估和預測研究中產出成果最多、發展前景極為廣闊的一個研究領域[1-6]。該模型可以抽象成為隨機過程的一種表示，典型表現在描述軟件失效與運行剖面的關系的數學方程。通過軟件可靠性模型，可以完成一系列預測，即預測開發過程中的可靠性增長，預測或評估軟件在預定工作時間內的可靠度，預測軟件在任意時刻發生失效數的平均值、在規定的時間間隔內發生失效次數的平均值、以及預求軟件在任意時刻的失效率、軟件失效時間間隔的概率分布和軟件預期的交付時間，等等[1-6]。

基于排隊論的軟件可靠性增長模型的研究起步較晚，但卻因排隊論在計算機系統性能分析與評價等方面表現出的優異能力，特別是排隊論提供的一整套數學理論模型，對計算機系統性能可進行多個方面形式化表示，使得排隊論在計算機科學研究領域贏得了日漸升溫的熱議和相當高度的重視。本文對當前常見的、有代表性的基于排隊論的軟件可靠性增長模型進行了歸納總結，并對未來的發展進程也進行了展望。

1基于排隊論的軟件可靠性增長模型

排隊論是研究系統隨機聚散現象，探討隨機服務系統工作過程的數學理論和方法，又稱隨機服務系統理論，是運籌學的重要組成部分。排隊論是從現實排隊現象中抽象得到物理模型，以此建立數學模型而構設形成的一整套理論[7-9]。具體來說，該理論通過建立合適的數學模型和進行嚴整的數學分析去設計隨機服務系統，即對服務對象到來及服務期間的階段特性進行統計研究，得出這些數量指標（排隊長度、逗留時間、等待時間、忙碌期、服務強度等等）的統計規律，再以這些規律為基準對服務系統的結構進行改進或重新組織被服務對象，使得服務系統既能滿足服務對象的需求，又能使系統的經濟耗費最低或其他某些指標最優。排隊論所研究分析的是一個系統對一個群體提供某種服務時，該群體占用此服務系統時可能出現的各種狀態[7-9]。任何排隊服務系統都可以描述為如圖1所示[7-9]的具體流程。

由圖1可見，現將典型排隊服務系統中的主要名詞含義做以如下說明。這些名詞分別為：

（1）輸入。表示顧客以何種方式到達和加入排隊服務系統。

（2）排隊規則。表示當顧客形成等待服務的隊列時，排隊服務系統是如何從中選擇顧客以提供服務的。

（3）服務規則。通常假設各個顧客的服務時間相互獨立，且彼此呈相同分布。

（4）服務臺數目。指并列的能同時為顧客提供同一類型服務的設施數目，通常假設這些設施相互獨立。

（5）服務系統容量。一個服務系統，除了服務臺數量有所限制以外，排隊等待的容量也可能有限，即排隊等待服務的隊伍不能超過一定的長度。

迄今而止，研究人員開始討論使用排隊論的方法來解說軟件測試當中的故障修正過程可能出現的各種行為。根據軟件故障先檢測后修正，且從檢測到修正有一定延遲的特點，可將故障修正過程視為一個排隊服務系統，采用排隊論方法來分析軟件故障修正過程并建立故障修正過程模型。即已檢測到的軟件故障等待進一步修正的過程可以看成是進入服務系統等待服務的過程，如圖2所示。已檢測到的故障和修正人員分別對應于排隊服務系統中的到達顧客和服務人員，詳細情況分析如下：

（1）顧客到達（故障檢測）。設隨機過程{Nd（t），t0}表示軟件測試中故障檢測的計數過程，對應于排隊系統的顧客到達過程。Nd（t）則表示從故障開始檢測、到t時刻為止，已檢測到的累計故障數，即到達的顧客數。如果軟件的失效過程滿足NHPP，那么顧客到達過程也為NHPP。第2期張楠，等：基于排隊論的軟件可靠性增長模型智能計算機與應用第3卷

（2）顧客離開（故障修正）。設隨機過程{Nc（t），t0}表示軟件測試中故障修正的計數過程，對應于排隊系統的顧客離開過程。Nc（t）則表示從故障開始修正、到t時刻為止，已修正的累計故障數，即離開的顧客數。對于任意t0，滿足Nc（t）Nd（t）。

（3）服務協議（故障修正策略）。描述已檢測到的故障采用何種原則進行修正。排隊系統中常見的服務協議有：先來先服務、后來先服務、優先服務、隨機服務。

（4）服務臺數（故障修正人員）。根據服務臺數目的限制可分為無限服務臺（無限修正人員數）和有限服務臺（有限修正人員數）。對于前者，假設已檢測到故障，就立即分配給服務臺進行修正，無需排隊等待。后者則是從軟件公司的實際情況出發，考慮資源的有限性和受控性，當所有服務臺繁忙時，會出現排隊等待現象。

2基于排隊論的軟件可靠增長模型研究現狀

近年來，學界各方已經開始探討如何使用排隊模型來對軟件測試行為展開研究。根據服務臺數量可能形成的限制，大致可分為兩類：無限服務臺排隊模型[10-13]和有限服務臺排隊模型[14-17]。

21基于無限服務臺排隊模型

無限服務臺排隊模型假設服務臺數量是無限的，即便顧客數目增加，也不會出現顧客排隊等待服務的現象，即表明已獲檢測的軟件故障無需等待排隊，就可直接進入故障修正服務系統。在這類模型中，頗具代表性的主要有如下幾種：

211Dohi 模型

Dohi 等[10]使用一個ISQ模型來描述軟件測試中的故障檢測行為。其突出成果是，提出了MX/G/∞排隊模型框架，并在文獻[11]中將有限故障和無限故障這兩類NHPP模型均統一到了MX/G/∞排隊模型中。該排隊模型假設到達的軟件測試案例服從參數為λ（>0）的泊松分布，每個測試案例i（i=1，2，…）對應一條Xi測試路徑。此時，還要假設隨機過程{N（t），t>0}服從參數為λ的NHPP，從0時刻開始進行測試，到任意t（>0）時刻，已檢測到的軟件故障數為N（t），那么：

P{N（t）=n}=∑∞j=0exp{-λt}（λt）jj！P{X1+…+Xn=n}（1）

其中， Xi表示非負整數的隨機變量。

為了簡化排隊模型，Dohi等[10]假定Xi=1的概率是1，即一個測試路徑最多只能檢測得到一個軟件故障。MX/G/∞排隊模型就隨之轉化為一個M/G/∞模型，到t時刻為止，已檢測到的軟件故障數可表示為：

P{N（t）=x}=λ∫t0H（x）dxx！exp-λ∫t0H（x）dx（2）

其中，H（x）表示故障檢測時間分布函數。

212Shibata模型

Shibata等[12]提出了使用一個無限服務臺排隊模型來描述軟件測試的故障修正行為。這個無限服務臺排隊模型假設，在任意時刻，軟件系統失效都是由軟件中存在的殘余故障所引起的，并且軟件故障修正時間不可以忽略，另外修正的故障數滯后于檢測到的故障數。

在其基礎上，還需假設，計數結果{Nd（t），t0}是一個遵循非齊次泊松分布的軟件故障失效過程，隨機變量Nd（t）表示，到t時刻為止，已檢測到的軟件故障數，則其均值函數為：

Hd（t；θ）=E[Nd（t；θ）]=∫t0λd（u，θ）du（3）

其中， λd（u，θ）表示軟件故障失效的密度函數。

假設軟件故障修正過程不可忽略，故障修正時間服從指數概率分布：

G（t；v）=1-exp（-vt）（4）

其中， v（>0）表示軟件故障修正率。

那么，到t時刻為止，已修正的軟件故障數的均值函數為：

Hc（t；θ，v）=∫t0λd（u，θ）G（t-u；v）du（5）

=∫t0λd（u，θ）[1-exp（-vt+vu）]du

213Kapur模型

Kapur等[13]從軟件故障分類的角度出發，將故障分為復雜、嚴重、容易三類。研究三類軟件故障對軟件測試過程的影響，提出了使用無限服務臺排隊模型來描述軟件故障調試行為，而且將三類故障統一歸置到此無限服務臺排隊模型的框架，即M*/G/∞模型之中。

首先假設，軟件系統的故障分為復雜、嚴重、容易且軟件故障失效過程服從一個非齊次泊松規律，又由于軟件故障排除的實現是一計數過程，則到t時刻為止，已排除的軟件故障數的均值函數mc（t）可表示為：

m（t）=m1（t）+m2（t）+m3（t）（6）

其中，m1（t）表示復雜故障排除過程的均值函數；m2（t）表示嚴重故障排除過程的均值函數；m3（t）表示容易故障排除過程的均值函數。

在式（6）基礎上，進一步推知其中各分項m1（t）、m2（t）和m3（t）的計算公式分別如下。

復雜故障排除過程的均值函數表示為：

m1（t）=∫t0∫t-u0G1（t-u-v）dF1（u）dmf1（v）（7）

其中，G1（t）表示復雜故障排除時間服從的概率分布；F1（t）表示復雜故障隔離時間服從的概率分布；mf1（t）表示復雜故障觀測過程的均值函數。

嚴重故障排除過程的均值函數m2（t）表示為：

m2（t）=∫t0G2（t-u）dmf2（u）（8）

其中，G2（t）表示嚴重故障排除時間服從的概率分布；mf2（t）表示嚴重故障觀測過程的均值函數。

容易故障排除過程的均值函數m3（t）表示為：

m3（t）=∫t0（t-u）dmf3（u）（9）

其中，mf3（t）表示容易故障觀測過程的均值函數。

22基于有限服務臺系統的軟件可靠性增長模型

在無限服務臺模型，所做的已檢測到的故障能夠立即分配給服務臺的修正人員進行故障修正而無需排隊等待的假設并不符合現實情況。事實上，當前的軟件公司不可能擁有無限量的故障服務臺，由于軟件成本連同預算等原因，故障服務臺往往都是數量有限的、可控的。因而需要針對有限服務臺模式來建立軟件可靠性度量模型。這類模型中較為成熟的、成功的主要有以下幾種。

221Huang模型

Huang等[14-15]提出的模型需要做以下假設，假設軟件系統失效都是由軟件中存在的殘余故障所引起的，軟件故障檢測過程服從一個非齊次泊松分布，軟件故障修正過程不被忽略且修正的故障數滯后于檢測到的故障數，同時軟件故障修正服務臺的個數是有限的。在這種情況下，到t時刻為止，已修正的軟件故障數的均值函數mc（t）可表示為：

mc（t）=∫t0∑m-1h=0ρhe-ρh！λd（x）G（t-x）dx（10）

其中， m表示軟件故障修正服務臺數目； h表示軟件故障修正的個數； ρ表示一個正數； λd（x）表示軟件故障失效的密度函數； G（t-x）表示故障修正時間服從指數概率分布。

222Gokhale模型

Gokhale等[16]提出了n個獨立的M/M/1排隊模型，以其構建軟件系統缺陷維修過程。根據軟件系統缺陷的嚴重性級別，Gokhale等將軟件系統中缺陷分成m類。缺陷維修的策略可采用非搶占式優先權和搶占式優先權兩種。在非搶占式優先權中，具有高順序位的缺陷排在隊列前方；正在維修的缺陷不受排隊中等待個體的影響。當有高優先權缺陷到達時，正處于維修中的低優先權缺陷將繼續此過程，維修結束后，高級優先權缺陷的維修才能啟動，因此，嚴重級別為j的缺陷，其平均維修時間tnpj可以表示為：

tnpj=1μ+1μ ρj1-∑jk=1ρk（11）

其中，ρj表示一個新缺陷被劃分成嚴重級別為j的概率；μ表示缺陷維修時間分布的參數。

在搶占式優先權中，當高優先權的缺陷到達時，立即停止正在接受維護的低優先權的缺陷，即中斷正在進行的維修，轉為開始高優先權的缺陷維修，因此，嚴重級別為j的缺陷，其平均維修時間tpj可以表示為：

tpj=1μ 1Πjk=1（1-ρk）（12）

223Schneidewind模型

Schneidewind[17]提出了一個基于排隊系統的軟件故障修正模型。在軟件故障修正排隊模型中，假設軟件系統失效都是由軟件中存在的故障所引起，并且一個故障只引發一個軟件失效，同時服務時間和等待時間都服從指數分布。根據假設條件，得出以下公式：

λ=D（T1）+X12ΔT12（13）

其中，λ表示故障達到率；ΔT12表示故障修正的等待時間；X12表示在T12時刻觀測到的故障檢測個數；D（T1）表示在時刻預測的故障檢測個數。

其后，故障修正率μ的計算公式為：

μ=D（T1）+X12+D（ΔT3）ΔT23（14）

其中，μ表示故障修正率；ΔT23表示故障修正的服務時間；D（ΔT3）表示在T3時刻預測的故障檢測個數。

3結束語

文本給出了基于排隊論的軟件可靠性增長模型簡介。根據服務臺數量的限制，確定了兩類模型：基于無限服務臺的軟件可靠性增長模型和基于有限服務臺的軟件可靠性增長模型。盡管研究者在基于排隊論的軟件可靠性增長模型研究方面已經取得了較為顯著的研究成果，但仍存在如下關鍵問題有待解決和完善：

（1）現有的基于排隊論的軟件可靠性建模過程沒有考慮軟件測試的資源問題。

（2）因為資源有限問題，現有的基于有限服務臺的軟件可靠性增長模型并未考慮排錯延遲等待這一問題的解決之道。

參考文獻：

[1]MUSA J D， IANNINO A， OKUMOTO K. Software reliability， measurement， prediction and application[M]. New York： McGram-Hill， 1987： 3.

[2]趙曉華. 計算機軟件可靠性與質量管理[M]. 北京： 中國經濟出版社， 1994： 7.

[3]LYU M R. Handbook of Software Reliability Engineering[M]. New York： McGram-Hill， 1996： 8.

[4]徐仁佐， 謝旻， 鄭人杰. 軟件可靠性模型及應用[M]. 北京： 清華大學出版社，1994：2.

[5]黃錫滋. 軟件可靠性、安全性與質量保證[M]. 北京： 電子工業出版社， 2002： 6.

[6]徐仁佐. 軟件可靠性工程[M]. 北京： 清華大學出版社， 2007：5.

[7]TRIVEDI K S. Probability and Statistics with Reliability Queuing and Computer Science Applications[M]. New York： John Wiley and Sons， 2002： 7.

[8]林闖. 計算機網絡和計算機系統的性能評價[M]. 北京： 清華大學出版社， 2001： 4.

[9]陸傳賚. 排隊論[M]. 北京： 北京郵電大學出版社， 2009： 2.

[10]DOHI T， MATSUOKA T， OSAKI S. An infinite server queuing model for assessment of the software reliability[J]. Electronics and Communications in Japan， 2002， 85（3）： 43-51.

[11]DOHI T， OSAKI S， TRIVEDI K S. An infinite server queuing approach for describing software reliability growth unified modeling and estimation framework[C]//Proceedings of the 11th Asia-Pacific Software Engineering Conference， Busan， Korea， 2004： 110-119.

[12]SHIBATA K， RINSAKA K， DOHI T， et al. Quantifying software maintainability based on a fault-detection/correction model[C]//Proceedings of the 13th IEEE International Symposium on Pacific Rim Dependable Computing， Melbourne， Australia， 2007： 35-42.

[13]KAPUR P K， ANADA S， INOUE S， et al. A unified approach for developing software reliability growth model using infinite server queuing model[J]. International Journal of Reliability， Quality and Safety Engineering， 2010， 17（5）： 401-424.

[14]HUANG W C， HUANG C Y， SUE C C. Software reliability prediction and assessment using both finite and infinite Server queuing approaches[C]//Proceedings of the 12th IEEE International Symposium on Pacific Rim Dependable Computing， California， USA， 2006： 194-201.

[15]HUANG C Y， HUANG W C. Software reliability analysis and measurement using finite and infinite Server queuing models[J]. IEEE Transactions on Reliability. 2008， 57（1）： 192-203.

[16]GOKHALE S S， MULLEN R E. Queuing models for field defect resolution process[C]// Proceedings of the 17th IEEE International Symposium on Software Reliability Engineering， North Carolina， USA， 2006： 353-362.

[17]SCHNEIDEWIND N F. An integrated failure detection and fault correction model[C]// Proceedings of the International Conference on Software Maintenance， Montréal， Canada， 2002： 238-241.