基于排隊理論的云計算資源分配模型的納什均衡優化方法研究

基金項目：江蘇省高等職業院校專業帶頭人高端研修資助項目；項目名稱：云背景下產學研協調育人平臺構建；項目編號：2021GRFX010。江蘇省高校哲學社會科學研究一般項目；項目名稱：云背景下產學研協調育人平臺構建；項目編號：2021SJA2012。

作者簡介：馮政軍（1977— ），男，江蘇高郵人，副教授，碩士；研究方向：計算機網絡技術，云計算。

摘要：為優化云計算系統在資源分配中的均衡性，不斷提升資源提供者的收益，文章提出以排隊理論為基礎的云計算資源模型。將云計算等待隊列的距離當作資源調度的基礎，進而融合了納什均衡理論對模型的資源調度策略展開合理性分析，并有針對性地提出合理優化的資源調度方法，并將其和分布式計算架構Hadoop當中的資源分配方式進行對比，進而得到實驗結果。實驗結果表明，和其他幾種算法相比，本次研究提出的改進資源分配算法不僅能夠滿足用戶對資源共享提出的需求，還能夠滿足資源提供者對提升系統響應時間提出的需要。

關鍵詞：云計算；資源分配；納什均衡；分析

中圖分類號：TP393 文獻標志碼：A

0 引言

在云計算系統當中，整體的資源利用效率有限，資源調度并不均衡，這些問題阻礙了云計算技術的持續發展，同樣也降低了資源提供者與使用者的自身利益。所以，當前需要從資源提供者以及使用者兩個角度出發來探討資源配置與共享的問題。資源提供者往往希望云計算系統內的資源能夠被合理地運用與配置。使用者更傾向于增強系統的功能性，在保障基本需求的前提下，更加迅速地完成用戶的實際操作。

1 資源分配的排隊模型

為了優先處理當前系統內的任務與資源分配問題，首先應當運用排隊理論構建排隊模型，設云計算為M/M/n+1的隨機服務系統，在這一系統當中，每一個計算資源都能被看作是一個工作臺，n是工作臺的數目，l則是需要等候的隊伍距離，使用者的需求抵達的時間間隔應當能夠符合泊松分布，工作臺的工作效率呈現出負指數分配。

在擬定的隊列當中，系統中每一種形態的轉移概率能夠體現為：

系統的響應時間包含服務時間與等待時間兩部分，等待時間可以被解釋為：在任務抵達后，如果檢測到工作臺中有任務在等待完成，則需要進入等候隊伍中等候開始工作。若某一個任務已經抵達，等候工作的任務為i，則這一時期的平穩概率qi能夠用下述式子來體現［1］：

若虛擬機當中的資源需求總量少于資源需求總量Cbasic，則可以調配這一虛擬機需求的資源；若高于資源需求量Cbasic，則給予服務器當中各個相互聯系的虛擬機一個上限；當某對虛擬機組合內，其中一個虛擬機的資源需求量高于基礎標準時，考慮消耗另一臺機器的多余資源或服務器中其他虛擬機的多余資源，一方面能夠保障資源調度的合理性符合基本要求，另一方面具有良好的公平性。

4 實驗仿真與結果分析

實驗環境的選擇：網絡傳輸率為1Gb/s，使用兩部服務器，每部服務器內都包含了4個虛擬機，4臺虛擬機相互之間有著不一樣的傳輸形式，一對一，一對多或是多對多。

在云計算系統內，每個向上提交的使用者需要完成的任務，都需要將應用或是計算任務作為重點，考量到任務中的串行以及并行等組合形式，實驗中的任務模擬MapReduce內任務的分布式計算工作手段，同時在8個節點的小型集群上搭建Hadoop集群，這幾個節點的屬性設置都需要結合本次實驗需求的CPU性能，隨機訪問的內存容量與帶寬。把本次研究中提出的納什均衡優化算法（MRA），借助Hadoop框架來運行，同時和Hadoop內核心的公平調度算法（Fair）、先入先出算法（FIFO）以及隨機調度算法（Random），分別從響應時間、CPU利用率以及內存利用效率3個角度出發進行對比［4］。公平調度算法下，每個任務能夠獲得同樣數量的資源，調度器隨著時間的變化平均配置任務量，這樣每個任務都能夠平均地獲取到資源，最終只需要消耗少量時間，進行的任務就可以訪問CPU，一些需要消耗更長時間來完成的任務則可以較晚完成，保障資源配置的合理性。在先入先出的調度算法下，對使用者提出的任務不進行特殊的順序安排，僅僅依據先來先工作的順序來進行。在隨機調度算法下，資源則是隨機被配置到各個任務內。3種算法在響應時間上的對比如圖1所示。

對于不同算法工作時對虛擬機能力造成的影響，在實驗的過程中將會用4種不同的算法分別運用在工作流體系中，同時對比CPU利用效率以及內存利用效率兩個方面的數據，最終結果如圖2—3所示。

在仿真測試中選取工作執行60s后的情況進行分析，可觀察到，在10s、23s、44s幾個時間點中，使用MRA調度算法時，系統內的內存與CPU利用效率都出現了顯著降低，說明依據調度方式，在這一階段內，任務正在等候系統進行的資源配置，然而由于這一階 段的資源利用率顯著下降，后續調度加速任務進程。因此在上述幾個階段后，CPU的利用效率出現了顯著提升，在本次選擇的60s調度階段內，因為任務分配的時間較為合理，沒有由于任務數目的提升和納什均衡理論運行中產生的損耗，對系統CPU的正常運作造成阻礙，也沒有提升系統運作的難度。在相同的階段，運用其余幾種算法時，內存利用效率均處于不斷提升的狀態，CPU利用效率出現了顯著改變，同時變化程度較為顯著。因此可以看出，運用MRA算法可以有效提升系統性能。

最終從實驗中能夠看出，虛擬機的基礎資源需求是資源合理分配與優化的最重要部分，借助MRA的資源配置方法，能夠有效提升系統資源利用效率，便于對資源分配進行合理調整，符合使用者提出的需要。

5 結語

為了同時滿足使用者與資源提供者提出的需要，本次研究運用納什均衡理論嘗試處理云計算系統中的資源配置問題，同時對于任務中的等候隊列運用排隊理論來展開理性分析，將需要改善處理的問題轉為分布式優化算法，符合資源提供者在提升系統響應時間、提高資源利用水平等方面提出的需求，同時可以保障使用者對資源需求的合理性提出的需要。通過和Hadoop算法進行的對比與實驗，說明本次探討的計算資源優化配置手段能夠保障資源共享所具有的合理性與公平性。未來，研究中心將主要放置在如何在解決合理配置問題的基礎上，探討能源消耗的降低，實現資源分配中的優化，減少資源浪費。

參考文獻

［1］李桂君，寇晨歡，胡軍，等.云服務資源調度機制的協同與優化研究［J］.系統科學與數學，2020（8）：1365-1383.

［2］周克楠.基于納什均衡的需求響應多用戶策略研究［J］.電子測試，2020（4）：43-45.

［3］王巖，汪晉寬，宋欣.云計算資源納什均衡優化分配方法改進［J］.計算機工程，2017（12）：17-24.

［4］孟川杰，張福泉，羅一帆.博弈模型下云資源分配納什均衡算法［J］.機床與液壓，2018（6）：184-192.

（編輯 傅金睿）

Abstract： In order to effectively improve the balance of cloud computing system in the process of resource allocation， continuously improve the revenue of resource providers， and form a cloud computing resource model based on queuing theory. Considering the distance of the waiting queue and taking it as the basis of resource scheduling， we integrate the Nash equilibrium theory to carry out a rational analysis of resource scheduling strategies， propose a reasonably optimized resource scheduling method， and compare it with the resource allocation method in the distributed computing architecture Hadoop. The experimental results show that， compared with other algorithms， the improved resource allocation algorithm proposed in this study can not only meet the needs of users for resource sharing， but also meet the needs of resource providers for improving system response time.

Key words： cloud computing; resource allocation; Nash equilibrium; analysis