云測試平臺任務調度方法

任進

（北京工業大學 北京100124）

云測試平臺任務調度方法

任進

（北京工業大學 北京100124）

云計算是當前研究的熱門領域，現如今，越來越多的應用被架設在了云計算平臺中。而在軟件開發的流程中，軟件測試也是一個重要階段，所以，將軟件測試和云計算結合，對于提高軟件測試的效率具有非常重要的意義。目前，云測試平臺中的算法尚存在任務調度方式單一的問題。針對此問題，本文提出了一種任務調度模型，該模型采用遺傳算法和改進型的min-min算法，對任務進行調度。實驗表明，此算法在使用中具有非常好效果。

云計算；軟件測試；遺傳算法；改進型的min-min算法

現如今，云計算被越來越多的人熟知，但是對于云計算的定義并未達成一致，從廣義的角度講，云計算就是利用公共的計算機硬件資源，通過網絡的方式對其進行配置和使用的模式[1]。云計算作為一場IT革命，已經影響到社會生活的方方面面[2]。云計算方面的投資也作為新興的行業，得到了越來越多的關注，因而也涌現出了大量從事此服務的廠商。

1 云測試平臺的意義和重要性

1.1 云計算平臺的優勢

1）強大的擴展性

云計算平臺的顯著特點就是所有的計算資源都在云端，這意味著計算資源是可以隨時變化的。在需要增加的時候，可以通過增添云端設備的方式增加計算能力。使用起來非常的方便。

2）節約成本

在傳統的計算集群中，需要通過添加物理設備的方式增強計算能力，這大大的增加了硬件采購成本，但是使用云平臺可以都使用虛擬計算資源，大大節約了成本。

3）方便應用

通過云計算平臺的支持的應用，可以很方便的分享給其他人員，因為對于實際的操作者來講，云計算是一個虛擬的客戶端，無論身在何地，處在何時都能夠很方便的使用其他人的云應用。

1.2 云測試技術的優勢

云測試技術實際上是基于云計算的應用，所以它有云計算的優點，但是云計算平臺作為一種全新的測試平臺，又有著自己獨特的優勢。

1）提高設備使用率

在測試階段中，多設備和多終端的測試是重要內容之一，但是在使用的過程中，往往會遇到測試設備使用率低的問題：一臺測試設備往往在使用1次之后，就不會再次被使用了。但是云測試技術克服了這樣的問題，通過云分享功能，可以將此設備分享給其他測試人員，提高設備的利用率[3]。

2）提高效率

搭建測試環境在軟件的測試環節中往往是非常耗時的一項內容，在云測試平臺中有大量通用測試環境模板供測試人員選用，大大提高了測試工作的效率。

3）提高可靠性

測試設備故障也是在軟件測試階段遇到的棘手問題之一，遇到此問題往往會耗費很多寶貴時間。云測試平臺具有非常低的故障率，即使出現故障也可以很快跳轉到備用機中，這避免了設備故障給測試人員帶來的難題。

2 云測試平臺的研究現狀

云測試平臺推出之后，就受到了眾多學者和企業的關注，作為一種新的測試模式，云測試技術具有非常重要的市場價值和研究價值。

在學術界，云測試平臺是重要的研究方向之一，學者們紛紛的提出了對云測試的見解。有的學者就云測試技術和傳統的測試技術進行了比較，提出了兩者的聯系和區別[4]，有學者通過對云測試的研究，提出云測試應該遵循的一般步驟，為后來者提供了理論支持。還有的學者提出了測試即服務（Testing as a Service，TaaS）的測試理念，這一理念對于軟件測試具有強力的推動作用，并指導軟件測試不應該各自為戰，應將其作為一種服務提供給使用者[5]。

在工業界，云測試平臺被越來越多的企業重視，他們紛紛的推出了自己的云測試平臺。跨國公司IBM、惠普、微軟、VMware先后推出了自己的云測試平臺。國內的大型企業，中國銀行軟件中心還有中石化公司也推出了針對自己獨特的業務特點的云測試平臺。

3 云測試任務調度研究現狀

任務調度是關于任務處理的一個研究熱點，也是計算機中非常重要的研究內容。從之前的傳統的單任務調度，多任務調度，到如今的基于網格計算的任務調度，云計算的任務調度，眾多的學者一直都在豐富著任務調度的研究范圍。針對云計算下的任務調度，眾多的學者對其進行了各方面的研究。

在提高任務調度性能方面，眾多學者提出了很多有益的算法，其中包括min-min算法，max-min算法，蟻群算法，人工魚群算法，遺傳算法，模擬去火算法等等，這些算法各不相同，但是都能提高任務調度的性能，這些算法在某些特定的場景中，有著優良的調度性能。

服務質量 （QoS）約束同樣是當下的研究熱點。Chan等人提出以網絡帶寬作為約束條件，通過加權方式調度任務[8]；以用戶的多偏好作為約束，孫大為等人提出了基于免疫克隆的偏好多維QoS云計算調度優化算法[9]；以多工作流為前提，多QoS作為約束，Xu等人提出了工作流的多QoS調度策略[10]。

以經濟利益為目標的任務調度研究，已在云計算得到了廣泛的應用，更多的企業投入到了這個領域中。如何能夠獲得更大的經濟利益，成為云計算廠家需要面對的問題之一，對此，學者們進行了廣泛的研究。RaikumarBuyya等人以廠家的經濟利益作為目標函數，調整體系結構和資源分配策略，通過分配器調度資源，以提高經濟利益[11]；葛新等人提出以用戶的需求作為約束，對要求高的用戶分配計算能力強的資源，對于要求一般的用戶分配相對計算能力相對低的資源，以此達到提高經濟利益的目的[12]。

眾多的學者在任務調度方向進行了非常廣泛的研究，但針對云測試平臺的任務調度，目前仍有較多空白。云測試平臺中的任務相對于其他平臺有著自己的特點，其獨立性強，任務量大，時效性要求高。針對此需要有更有效的算法來完成云測試平臺的任務調度工作。

4 云測試平臺任務調度模型

4.1 任務調度模型

云測試平臺是基于云計算的一種新型的測試技術，是將云計算的豐富研究成果應用于軟件的測試環節中。在云測試平臺任務調度模型中，任務調度器根據任務調度算法在任務集合中調度任務，然后將任務推送給云測試平臺中的虛擬機。虛擬機通過任務執行器中的調度算法執行相應的任務，最后將任務全部執行完畢。上文描述的任務調度模型如下：

4.2 任務調度器

任務調度器的核心是使用遺傳算法進行任務的分配。遺傳算法自20世紀60年代初提出以來，已經被用在了很多領域。遺傳算法是將達爾文的進化思想和孟德爾的遺傳定律創造性的用于計算機領域中，創造出了一個全新的進化計算算法。

圖1 任務調度模型

1）染色體的映射方案

染色體中基因的長度既是需要分配的任務數量，基因在染色體中的位置代表任務的編號。每個基因中內含的數字代表將要分配給的計算設備編號，使用記號Vi表示。在初始狀態會生成一定數量的染色體。

表1 染色體映射方案

例如將10個子任務分配到5個資源上時，產生的一個染色體可能為{1，1，2，3，4，5，2，1，3，2}，此意味著任務在設備上執行。

2）適應度值函數的設計

適應度函數是在遺傳算法中非常重要的部分。遺傳算法通過適應度算法淘汰不良染色體，經過重復不斷的迭代，得到最優解，所以適應度函數的設計非常關鍵。在此定義的目標函數為

在此函數中E（i，j）代表將j任務分配于i設備之后，完成任務所需要的時間。F（x）表示在m個設備中最后一個任務的完成時間，也就是n個任務全部完成的時間。在遺傳算法中適應度函數的值決定染色體淘汰方向，由此可得適應度函數，就是目標函數的倒數，即將會淘汰適應度小的值。

3）染色體雜交

在遺傳算法中，通過染色體的雜交獲得更多新的染色體，此算法的雜交方案是將隨機提取原種群中的兩個染色體，選取其中的某個位置進行基因交換。

表2 S1染色體的基因序列

表3 S2染色體的基因序列

雜交步驟：

①隨機選取一個值i（1＜=i=10）。

②S1染色體中以i為中心的，長度為染色體總長度五分之一的基因序列中的開頭的位置為K，結尾的位置為M。

③將K之前的基因序和M之后的基因序全部復制到新染色體S′中。

④在S2中從頭到尾搜索，在S′中插入S2中獨有的基因，即S′中沒有S2中有的基因，如果插入之后S’中基因序仍然沒有補齊，則在空位填充S′中出現最少的基因。

由此產生了全新的染色體S1′。

按照雜交步驟演示如下：

A隨機選擇的數字為4。

B經過2-3步得到如下S1′：

表4 S1′染色體的基因序列

C經過4步得到的結果如下：

表5 S1′染色體的基因序列

S1′染色體的基因序列：

表6 S1′染色體的基因序列

4）變異操作

對S1，S2，S′求其適應度函數值，求適應度最小的染色體執行基因變異。變異的方案為隨機選中染色體的一個基因，將其變為染色體中設備號出現最少的。變異后的S1′記為S′′，將此基因加入原始種群中。

經過變異之后的染色體S′′：

表7 S′′染色體的基因序列

5）再生成操作

重新利用適應度算法求在種群中所有染色體的適應度值，淘汰低適應度染色體，在此過程中需要保持種群數量的穩定。當算法遇到終止條件的任何一種時，算法即停止。算法的終止條件：

①算法迭代100次，染色體無變化。

②算法迭代次數超過15 00次。

③經過迭代，染色體收斂為同一染色體

在達到終止條件后，輸出適應度值最高的染色體。

4.3 任務執行器

任務調度器將任務推送到云平臺計算資源之后，VM任務執行器將通過一種改進的min-min算法執行對應的任務。

4.3.1 基本的min-min算法

min-min算法在任務調度方面有著實現簡單，響應速度快等特點。

min-min算法的基本步驟如下：

1）將所有的任務填入任務執行表中

2）比較每個任務的執行時間，將執行時間最短的任務先執行。

3）任務執行完畢后，將此任務從任務執行表中刪除

4）重復進行2-3步，直到任務表為空為止。

4.3.2 云計算環境下改進min-min算法

雖然min-min的優點非常的明顯，但是它也存在著不足，比如長任務會處于長時間等待狀態，為了解決此問題，提出了一種帶權值的改進型的minmin調度算法。

基本步驟如下：

1）將所有任務記入任務列表中，并且記錄他們的預計執行時間，記為ExceptTime（i）

2）通過公式計算每個任務的權值

Q（i）=TimeExcept（i）/WaitTime（i）

其中TimeExcept（i）代表第i個任務的預計執行時間，WaitTime（i）代表此任務的等待時間。將其更新到權值表中。

3）通過基本min-min算法調度在第2步得到的帶權值的任務。將權值最小的任務執行。

4）將執行完畢的任務從任務表和權值表中刪除。

5）更新權值表和任務列表，

6）重復2-5步，直到任務表為空。

到此算法結束。

5 實驗與結果分析

5.1 實驗環境與數據

為了獲得更好的實驗結果，硬件環境采用一臺8核i7處理器，采用16 G內存，在其上虛擬出8臺主機，其中一臺主機擁有一個核心，2 G內存和30 G硬盤空間。軟件的回歸測試和驗收測試是在軟件測試中非常關鍵的測試階段，本文將針對這兩個階段進行測試。被測軟件分別是校郵箱服務平臺和校OA服務平臺。測試主要任務也分為WEB測試和后臺API測試。其中WEB前端全部使用Selenium編寫，后臺API的測試用例全部使用Java語言編寫。

測試用例分布如下：

表8 測試用例分布

5.2 實驗結果與分析

實驗中采用兩種調度方式，一種是傳統任務調度方式，即先來先服務進行調度，另一種即是本文提出的任務調度方案，分別對其結果進行了統計和分析。

實驗結果如表9、10所示：

表9 郵件服務平臺測試花費時間統計結果/min

表10 OA服務平臺測試花費時間統計結果/min

通過對實驗數據的分析，可以看到，文中提出的云平臺下的任務調度算法大大的提高了任務調度效率，其中在回歸測試階段云平臺任務調度比傳統任務調度在花費時間方面減少了52%、48%，在驗收階段減少了22%、36%；當測試用例全部是WEB前端時，花費時間減少了48%、50%，而測試用例全部是API后臺時，花費時間減少了56%、52.5%。從實驗數據分析可以看到，測試用例越多，本算法的優勢越明顯，符合預期。由于文中提出的算法在初始階段需要花費大量的時間，所以任務少時本算法優勢不明顯。通過觀察可以發現在 API后臺測試的效果優于WEB前端測試，經過分析發現，WEB前端測試依賴瀏覽器等第三方軟件，由此帶來了不必要的時間耗費，而API后臺測試，則完全獨立，不會有此問題。

6 結 論

文中基于遺傳算法和改進min-min算法提出一種云測試平臺的任務調度模型，從前文的分析中，可以清晰的看到此任務模型可以提高云平臺的任務調度效率。但是在研究的過程中也發現一些問題，即算法的啟動時間相對較長等問題，今后將繼續關注對此問題，并對其進行解決。

[1]Saurabh KumarGarg，SteveVersteeg，Rajkumar Buyya，et al.A framework for ranking of cloud computing services[J].Future generations computer systems，2013，29（4）:1012-1023.

[2]Murugesan，San.Cloud Computing:The new normal [J].Computer，2013，46（1）:77-79.

[3]白虹橋.基于云計算的軟件測試技術探索與研究[J].信息技術與信息化，2015（3）：65-66.

[4]雷萬保.云計算環境下的軟件測試研究[J].信息化研究，2013（1）:1-3.

[5]Lian Y，Wei-Tek T，Xiangji C，et al.Testing as a serviceovercloud:FifthIEEEInternationalSymposiumonServiceOrientedSystemEngineering（SOSE），Nanjing，2010[C].2010.

[6]林奇.基于云計算的測試管理予臺[J].科技傳播, 2013（17）:227-228.

[7]黃璐.基于遺傳算法的云計算任務調度算法研究[D].廈門：廈門大學，2014.

[8]Chauhan S S'Joshi R C.A heuristic for QoS based independent task scheduling in gridenvironment[C]// Industrial and Information Systems(ICIIS),2010 International Conferenceon.IEEE,2010:102-106.

[9]孫大為,常桂然,李鳳云，等.一種基于免疫克隆的偏好多維QoS云資源調度優化算法[J].電子學報，2011（8）：1824-1831.

[10]Xu M，Cui L，Wang H,et al.A multiple QoS constrained scheduling strategy of multipleworkflows for cloud computing[C]//Parallel and Distributed Processing with Applications,2009 IEEE International Symposium on.IEEE,2009:629-634.

[11]Buyya R,Yeo C S，Venugopal S,et al.Cloud computing and emerging IT platforms:Vision,hype, and reality for delivering computing as the 5th utility[J].Future Generation computersystems，2009，25（6）:599-616.

[12]葛新，陳華平，杜冰，等.基于云計算集群擴展中的調度策略研究 [J].計算機應用研究，2011，28（3）:995-997.

[13]李喬，柯棟梁，王小林.云測試研究現狀綜述[J].計算機應用研究，2012，29（12）：4403.

[14]Masayuki Hirayama,Osamu Mizuno,TohruKikuno.Analysis of software test item Generation-Comparison between High Skilled and Low Skilled Engineers[J].計算機科學技術學報：英文版，2005，20（2）:250-257.

[15]李建鋒,彭艦.云計算環境下基于改進遺傳算法的任務調度算法[J].計算機應用，2011（1）：184-186.

The module of task schedule in cloud testing platform

REN Jin
（Beijing University of Technology，Beijing 100124，China）

The study of Cloud Computing is one of the most popular study aspects.More and more appliances are deployed in Cloud.It is of great significance for the increase of Software Test efficiency that we deploy the applicationsof Software Testing， which are very momentous during software development，in Cloud.But the method of Task Schedule is very simple in Testing cloud.In order to solve the problem，we explored one module that use genetic algorithm and improved min-min algorithm to arrange tasks.Experimental results show that the module truly improves the efficiency of Software Test.

cloud computing；software testing；genetic algorithm；improve min-min

TN0

：A

：1674－6236（2017）03-0056-05

2016-01-18稿件編號：201601139

任 進（1988—），男，山西呂梁人，碩士。研究方向：云計算，軟件測試。