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

劉軼彤

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

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

1 概述

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

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

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

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

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

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

3.1 博弈理論的定義及模型

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

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

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

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

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

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

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

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

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

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

可得：

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

4 實(shí)驗(yàn)及結(jié)果分析

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

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

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

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

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

5 結(jié)語(yǔ)

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