劉軼彤

天津職業(yè)大學，中國·天津 300410

虛擬化；非合作博弈；效用最優(yōu)；資源分配策略

1 概述

動漫三維作品的后期渲染、視頻作品的合成加工、交互作品中虛擬現(xiàn)實效果的實時呈現(xiàn)，都需要具有大規(guī)模運算能力的設備對項目文件提供輸出保障。隨著學院對設備投入力度的增加，已建立具有高處理性能的集群系統(tǒng)。集群系統(tǒng)由多臺相同配置的計算機工作站組成，相互之間利用光纖交換機進行數(shù)據(jù)傳遞。為用戶項目文件的處理，提供高效、統(tǒng)一的處理器、內(nèi)存和存儲資源。在集群系統(tǒng)中通過資源管理軟件對項目文件進行資源分配。

隨著虛擬化技術的發(fā)展，將虛擬化軟件安裝在集群系統(tǒng)中，建立同時對多個用戶提供處理服務的虛擬化集群系統(tǒng)。對資源進行虛擬化，按照相應的類別形成統(tǒng)一的處理器資源集合、內(nèi)存集合及存儲集合，各類資源被劃分成相應資源池。在實際任務處理中，一般將系統(tǒng)資源等價于集群系統(tǒng)中處理項目文件所需的處理器資源，將內(nèi)存和存儲資源視為足夠充足。虛擬化集群系統(tǒng)主要解決如何充分、合理利用處理器資源的問題，需要對原來集群系統(tǒng)中任務分配策略進行調整，使任務分發(fā)軟件有效地分配和管理處理器資源，實現(xiàn)系統(tǒng)最大限度的資源利用。

論文考慮到實際的系統(tǒng)資源分配中存在的經(jīng)濟因素，引入博弈理論中非合作模型，結合任務文件對處理器資源使用的費用預算和完成任務最遲截止時間的條件約束，對虛擬化集群系統(tǒng)中資源分配策略進行分析，構建出單位時間內(nèi)使用相應處理器資源產(chǎn)生費用的函數(shù)關系，證明在分配策略下存在納什均衡解的條件。利用非合作博弈策略求得納什平衡，從而使資源分配得到最優(yōu)解。

2 虛擬化集群系統(tǒng)中資源分配經(jīng)濟模型的構建

在虛擬化集群系統(tǒng)中可以通過資源管理軟件實時地將集群處理器資源進行整合，按照實際的需要和支付，分配相應的資源，使集群系統(tǒng)的任務管理具有靈活、公平、高效的特點。在合理分配處理資源的同時，需要考慮經(jīng)濟上的因素，按照用戶的支付費用，在當前系統(tǒng)處理器資源池中得到相應比例的資源量。根據(jù)虛擬化集群系統(tǒng)的工作原理，資源池中資源不是指定一臺或幾臺上的物理資源，而是虛擬化集群系統(tǒng)的處理器資源可應用量，進行實時地分配給不同需求的項目文件[1]。設定提交項目文件的用戶數(shù)為N={1，2...i...n}，集群系統(tǒng)中物理工作站數(shù)M={1，2...j...m}，用戶提交的項目任務數(shù)為T={1，2...k...t}。Pkj是任務K 在機器J 上所占用的資源比例，按照單位時間處理器資源的使用價格Mk，乘以所需的處理器資源數(shù)量Ck和執(zhí)行時間Tkj，得到項目文件使用資源產(chǎn)生的費用，確保實際支付價格不能大于整個文件的初始預算。如資源單位時間使用價格、項目文件的處理預算，以及項目文件的最遲截止時間作為參數(shù)和約束條件，構成的模型如下：

3 虛擬化集群系統(tǒng)資源分配的非合作博弈

3.1 博弈理論的定義及模型

處理器資源作為虛擬化集群系統(tǒng)中最核心的部分，在處理多個用戶提交執(zhí)行任務文件的問題時，如何對資源池中資源的分配采用合理的策略，保證整個系統(tǒng)能夠實時有序地進行，提高系統(tǒng)的性能。虛擬化集群系統(tǒng)在設備的購買、軟件使用以及人員維護，都會產(chǎn)生經(jīng)濟上的費用，因此對于提交任務的用戶在使用系統(tǒng)資源時需要繳納一定的費用。系統(tǒng)中資源分配問題與社會經(jīng)濟活動有一定的相似性，可以引用經(jīng)濟學中博弈理論，解決對多個用戶申請?zhí)摂M化集群系統(tǒng)處理資源的分配策略，從而使整個資源池中的分配對每個用戶達到最優(yōu)[2]。

博弈論可以對多個相互獨立可自主選擇策略的用戶，在策略空間的選擇問題上，用戶相互牽連和制約，提供一個合適的分析框架。博弈的主體至少有3 個要素：參與者，策略空間、效用函數(shù)。博弈論的形式表達為：G={N,Si(N),Ui(?)}。以用戶對資源的出價集合表示為策略空間，Si為用戶i 的策略集合，每個用戶的效用以效用函數(shù)集合表示{Ui(.)}，Ui表示用戶i 的效用函數(shù)。博弈中參與者i 的效用表示為Ui(s)，對于Si最優(yōu)策略稱為Si*為用戶i 達到納什均衡的出價策略。以s 表示博弈中所有用戶的策略選擇，si是用戶i 的策略表示，s-i是除用戶i 以外用戶的策略選擇。博弈分為合作博弈和非合作博弈。虛擬化集群系統(tǒng)中每個用戶體較大項目任務文件具有并行處理的特性，在資源的利用和分配過程中，每個用戶沒有形成一種合作的模式，只是根據(jù)相互的出價的抉擇，在可支付的費用條件下，處理時間最小值作為資源分配結果的原則下，進行策略選擇問題，得到效用的最優(yōu)策略，即為建立一種非合作博弈模型。每個用戶進行策略的不斷優(yōu)化進行調整，以到達自身的最優(yōu)策略選擇，在這種策略下是每個用戶都達到一種最優(yōu)的狀態(tài)的均衡模型，形成非合作博弈模型中的最優(yōu)策略組合，任何其他的策略選擇都會小于均衡下的效用最大值，即為在資源分配中形成一種納什均衡，即為每個用戶最優(yōu)值的策略組合[3]。

3.2 非合作博弈模型中納什均衡的存在條件

論文引入博弈理論，首先要根據(jù)虛擬化集群系統(tǒng)的資源分配原則，對任務處理中使用的參數(shù)進行表示。用戶i 完成任務t 所獲得系統(tǒng)的CPU 的資源處理量、執(zhí)行任務的時間及用戶i 的使用系統(tǒng)實際支付費用：

在非合作博弈模型中納什均衡的存在條件為：（1）策略空間Si=(i=1，2，...，N)是歐式空間中一個非空的、緊的凸集。（2）效用函數(shù)Ui(s)是連續(xù)的且對Si是擬凹的。

用戶的出價策略空間Si為單個點集，顯然是歐氏空間上一個非空的緊致凸集，滿足條件（1）。效用模型形式化為費用約束下，解決任務處理的時間盡量最小化的優(yōu)化問題，對于在最優(yōu)化的問題應該轉化為。已知效用函數(shù)Ui(s) 在Si上滿足連續(xù)性。關于凹性，

在得到的二階導數(shù)結果公式中，任務大小qit，以及博弈用戶的出價sit和，以及占用系統(tǒng)資源的數(shù)量，三個參數(shù)均為正數(shù)，因此二階導數(shù)，已知效用函數(shù)Ui(s) 在策略Si上是凹函數(shù)。滿足效用最優(yōu)化模型存在非合作博弈納什均衡解的條件[4]。

3.3 效用策略選擇的最優(yōu)解

再利用系統(tǒng)資源總體預算的約束條件下利用拉格朗日方法去求解最值問題

通過對L(sit)關于λ進行一階導數(shù)運算，比將其值為0

可得：

si1為用戶i 對第一個任務使用集群資源的最優(yōu)出價，其他用戶同時也遵循這個出價的策略函數(shù)，用戶i 通過最優(yōu)出價策略達到效用最優(yōu)[5]。

4 實驗及結果分析

對虛擬化集群系統(tǒng)的任務管理軟件進行測試，通過軟件分析在應用非合作博弈理論的分配策略后，統(tǒng)計用戶的項目預算和任務文件的使用的資源價格以及執(zhí)行時間的相互關系。上述推導出理論應用在擁有48 臺服務器，每臺內(nèi)置8 核處理器組成的虛擬化集群系統(tǒng)。參數(shù)a表示系統(tǒng)處理器的處理能力，變化范圍為[96MIPS，384MIPS]，用戶的預算為b，變化范圍為[50，150]，設定同時參與提交任務數(shù)為n，變化范圍為[2，6]。

表1根據(jù)使用系統(tǒng)處理器的處理能力a 及提交任務數(shù)n，產(chǎn)生任務對資源出價的變化情況。隨著用戶數(shù)量的增加，通過對出價策略的考慮，影響任務執(zhí)行時間的變化情況。

表1 系統(tǒng)處理器分配能力和出價的變化情況

在表2中用戶的預算b 和提交任務數(shù)a 的變化時，任務文件的執(zhí)行時間受到影響。預算的增加會加快任務的執(zhí)行時間，隨著提交任務的增加，獲得的相對資源會減少，增加任務的執(zhí)行時間。

表2 在用戶的預算和執(zhí)行時間的變化情況

5 結語

論文通過對虛擬化集群系統(tǒng)結合非合作博弈理論，從而尋求效用最大化的處理資源的分配策略，該策略可以將用戶的預算和在博弈中用戶間的出價策略建立相互聯(lián)系。根據(jù)用戶自身的預算，進行對系統(tǒng)資源的合理分配需求。通過用戶項目文件的“預算-出價-時間”關系達到納什均衡，是分配策略達到效用最大化，證明了虛擬化集群系統(tǒng)中應用非合作博弈資源分配策略的可行性，具有一定的推廣和應用價值。