劉軼彤

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

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

1 概述

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

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

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

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

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

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

3.1 博弈理論的定義及模型

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

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

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

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

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

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

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

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

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

通過對L(sit)關(guān)于λ進(jìn)行一階導(dǎo)數(shù)運算，比將其值為0

可得：

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

4 實驗及結(jié)果分析

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

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

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

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

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

5 結(jié)語

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