趙 震, 張龍昌

云計(jì)算中多QoS調(diào)度機(jī)制研究

趙 震, 張龍昌

云計(jì)算的作為分布式系統(tǒng)中的一種新的服務(wù)配置模式，鼓勵(lì)研究人員在科學(xué)應(yīng)用時(shí)探討其利弊。云資源的動(dòng)態(tài)變化給資源管理帶來了很大的困難。在云計(jì)算環(huán)境中的調(diào)度工作中使用一個(gè)分割負(fù)載理論（DLT）設(shè)計(jì)有效的策略來最小化總的處理時(shí)間，處理器是負(fù)載均衡的，推導(dǎo)出一個(gè)封閉形式的解決方案將負(fù)載分段分配給每個(gè)處理器。以這種方式進(jìn)行工作調(diào)度使得云提供商可以獲得最大的服務(wù)效益并滿足客戶的服務(wù)質(zhì)量（QoS）需求。最后，通過嚴(yán)格的仿真研究量化該策略的性能。

云；網(wǎng)絡(luò)教育；服務(wù)質(zhì)量

0 引言

云計(jì)算是一種基于互聯(lián)網(wǎng)的計(jì)算方式，通過這種方式，共享的軟硬件資源和信息可以按需求提供給計(jì)算機(jī)和其他設(shè)備，主要是基于互聯(lián)網(wǎng)的相關(guān)服務(wù)的增加、使用和交付模式，通常涉及通過互聯(lián)網(wǎng)來提供動(dòng)態(tài)易擴(kuò)展且經(jīng)常是虛擬化的資源。云是網(wǎng)絡(luò)、互聯(lián)網(wǎng)的一種比喻說法。過去在圖中往往用云來表示電信網(wǎng)，后來也用來表示互聯(lián)網(wǎng)和底層基礎(chǔ)設(shè)施的抽象。狹義云計(jì)算指IT基礎(chǔ)設(shè)施的交付和使用模式，指通過網(wǎng)絡(luò)以按需、易擴(kuò)展的方式獲得所需資源；廣義云計(jì)算指服務(wù)的交付和使用模式，指通過網(wǎng)絡(luò)以按需、易擴(kuò)展的方式獲得所需服務(wù)。這種服務(wù)可以是IT和軟件、互聯(lián)網(wǎng)相關(guān)，也可是其他服務(wù)。它意味著計(jì)算也可作為一種商品通過互聯(lián)網(wǎng)進(jìn)行流通。

云計(jì)算是一個(gè)開放的平臺(tái)，它正在改變企業(yè)，機(jī)構(gòu)和個(gè)人如何理解，認(rèn)識(shí)和使用現(xiàn)有軟件系統(tǒng)。云計(jì)算中，沒有必要的組織來維護(hù)自己的服務(wù)器，也沒有自己的軟件。相反，一切都被移動(dòng)到云，按需提供，節(jié)約能源，物理空間和技術(shù)人員?；谠朴?jì)算的系統(tǒng)架構(gòu)在可擴(kuò)展性，可維護(hù)性和海量數(shù)據(jù)處理方面提供了很多優(yōu)勢(shì)。

云計(jì)算通過數(shù)據(jù)中心完成對(duì)資源的管理，并向用戶提供服務(wù)。服務(wù)提供商通過域代理進(jìn)行云服務(wù)注冊(cè)，用戶則通過云用戶中心注冊(cè)，并獲取服務(wù)信息。域代理針對(duì)用戶的服務(wù)需求，根據(jù)調(diào)度策略查找滿足用戶需求的服務(wù)，并完成調(diào)度。

云計(jì)算已經(jīng)得到了全世界許多研究人員的關(guān)注，但其中只有一小部分已經(jīng)解決了QoS性能問題[1]。QoS的性能指標(biāo)，如響應(yīng)時(shí)間，任務(wù)阻塞概率，立即進(jìn)行修復(fù)的概率，系統(tǒng)中有意義的任務(wù)數(shù)。許多研究人員對(duì)服務(wù)調(diào)度算法[2]進(jìn)行研究。

云計(jì)算是一種新的技術(shù)趨勢(shì)，用戶可以租用軟件，硬件，基礎(chǔ)設(shè)施和計(jì)算資源。用戶可以提交他們的工作交給云計(jì)算處理或把數(shù)據(jù)存儲(chǔ)在云中。不同的用戶具有不同的QoS需求。云調(diào)度器必須能的這樣一種方式工作，以這種方式進(jìn)行工作調(diào)度使得云提供商可以獲得最大的服務(wù)效益并滿足客戶的服務(wù)質(zhì)量（QoS）需求。在應(yīng)用分割負(fù)載理論的云中，任意被分割的負(fù)載是沒有任何先后關(guān)系的，它們被分布到各種處理器，使整個(gè)負(fù)載可以在可能的最短時(shí)間內(nèi)被處理。使用DLT的一個(gè)重要的原因是它的靈活性，易處理，數(shù)據(jù)并行計(jì)算，計(jì)算難度[3]。

此外，為了實(shí)現(xiàn)云平臺(tái)的全部潛力，建立公共和私有云的耦合框架是必要的。作為由于越來越多的功能所帶來的資源的缺乏和混合云計(jì)算的復(fù)雜性是不可避免的，一個(gè)感知的資源配置的算法對(duì)于滿足最終用戶的QoS需求是至關(guān)重要的[4]。

在傳統(tǒng)的網(wǎng)絡(luò)計(jì)算系統(tǒng)，如網(wǎng)格環(huán)境中，CPU的個(gè)數(shù)是固定的。云計(jì)算是一種提供“彈性服務(wù)”環(huán)境，（按需求自動(dòng)擴(kuò)展資源），這促使我們使用云計(jì)算系統(tǒng)來滿足對(duì)資源需求[5]的變化。我們的工作可以概括如下：當(dāng)所有參與的處理器同時(shí)停止時(shí)，我們推導(dǎo)出一個(gè)封閉形式的解決方案將負(fù)載分段分配給每個(gè)處理器。我們也考慮基于成本的多QoS在云計(jì)算環(huán)境[6]下的調(diào)度。

本文的其余部分安排如下：第2節(jié)給出了相關(guān)研究背景；在3節(jié)給出云調(diào)度環(huán)境和數(shù)學(xué)公式；我們?cè)?節(jié)給出了新DLT模型來解決這個(gè)問題；第5節(jié)中給出了實(shí)驗(yàn)結(jié)果；最后是結(jié)論與未來的工作。

1 研究背景

云計(jì)算系統(tǒng)是根據(jù)需求提供服務(wù)，它們被設(shè)計(jì)為可擴(kuò)展的，靈活的網(wǎng)絡(luò)計(jì)算機(jī)服務(wù)器。在我們的模型中，我們建模一個(gè)由組織/機(jī)構(gòu)維護(hù)的私有云系統(tǒng)，其主要給其成員或最終用戶提供軟件服務(wù)。

在云計(jì)算中，用戶沒有自己的任何基礎(chǔ)設(shè)施部分。用戶只需使用云計(jì)算模型提供的服務(wù)并為使用的服務(wù)付費(fèi)。云計(jì)算模模型可以提供任何可能形式的服務(wù)，如進(jìn)行高性能計(jì)算應(yīng)用的計(jì)算資源，Web服務(wù)，社交網(wǎng)絡(luò)和電信服務(wù)[7]。DLT已被證明是在云計(jì)算環(huán)境中處理大規(guī)模網(wǎng)絡(luò)系統(tǒng)上的計(jì)算負(fù)載的一個(gè)有價(jià)值的工具[6]。雖然DLT使用線性建模，最近的研究也表明DLT范式也被運(yùn)用于要求非線性處理計(jì)算[8]。

最近，DLT范式的研究為設(shè)計(jì)有效的策略來最小化在云計(jì)算環(huán)境中所進(jìn)行的大規(guī)模的多項(xiàng)式乘積計(jì)算所需的總的處理時(shí)間。資源分配器分布所有負(fù)載的云計(jì)算，被認(rèn)為是一組虛擬CPU實(shí)例（VCI），這些VCI給資源分配器回傳處理結(jié)果。進(jìn)一步的，一個(gè)程序員的編程模式是在動(dòng)態(tài)、異構(gòu)的云環(huán)境中應(yīng)用DLT范式開發(fā)出高性能的應(yīng)用程序。該模式使用基于性能的方法將任務(wù)分發(fā)到工作節(jié)點(diǎn)來減少調(diào)度開銷。

此外，該調(diào)度策略應(yīng)為滿足不同的QoS要求的多工作流而開發(fā)。在[8]，一個(gè)多QoS約束的多工作流調(diào)度策略（mqmw）解決了這個(gè)問題。該策略可以調(diào)度在任何時(shí)候開始的多個(gè)任務(wù)流并滿足QoS需求。在這里，任務(wù)被認(rèn)為是不可分割的。

據(jù)我們所知，基于代價(jià)的多QoS調(diào)度的DLT模型考慮尚未應(yīng)用在云計(jì)算中。本文將提出一個(gè)這樣的DLT模型來解決這個(gè)問題。

2 調(diào)度環(huán)境和優(yōu)化準(zhǔn)則

2.1 調(diào)度模型環(huán)境

該模型的調(diào)度環(huán)境主要包括5部分：

1、一組用戶（云用戶）：很多云最終用戶想要從云獲得服務(wù)。他們正在尋找不同的服務(wù)（如計(jì)算服務(wù)，網(wǎng)絡(luò)服務(wù)，基礎(chǔ)設(shè)施服務(wù)）這些服務(wù)具有不同級(jí)別的QoS（可能有不同的成本和期限，可能有不同的優(yōu)先權(quán)）。

2、預(yù)處理機(jī)和任務(wù)分類：本單元處理用戶的任務(wù)和執(zhí)行一些預(yù)處理并分類。

3、數(shù)據(jù)中心/執(zhí)行器：這是一個(gè)負(fù)責(zé)為用戶提供服務(wù)主要部件。數(shù)據(jù)中心主要是由若干個(gè)存儲(chǔ)資源（存儲(chǔ)單元和存儲(chǔ)服務(wù)器）組成，虛擬機(jī)和計(jì)算資源（主要是處理單元）的集合。本文只研究計(jì)算資源。每個(gè)處理單元從相應(yīng)的調(diào)度隊(duì)列獲得任務(wù)。

4、數(shù)據(jù)中心經(jīng)理：從不同的處理單元收集最近的處理單元屬性向量。該處理單元屬性向量包括每秒百萬條指令（MIPS）表明每秒有多少指令被執(zhí)行及指令的執(zhí)行代價(jià)。

5、作業(yè)調(diào)度：它有兩個(gè)輸入，一個(gè)來自預(yù)處理單元另一個(gè)來自數(shù)據(jù)中心經(jīng)理，它獲取相關(guān)的用戶QoS需要信息并確定哪些處理單元能夠滿足這樣的QoS。因此，作業(yè)調(diào)度的主要任務(wù)是獲得從作業(yè)到處理單元的一個(gè)最佳的映射。

2.2 優(yōu)化準(zhǔn)則

在所有的到目前為止有關(guān)可分負(fù)載調(diào)度的相關(guān)文獻(xiàn)，最優(yōu)性準(zhǔn)則常用作最佳的解決方案。它指出，為了獲得最佳的處理時(shí)間，所有的場(chǎng)所參與計(jì)算的節(jié)點(diǎn)必須同時(shí)停止是必要的。否則，負(fù)荷被重新分配以提高處理時(shí)間。

3 DLT代價(jià)模型

本節(jié)提出的可分負(fù)載DLT模型調(diào)度的云計(jì)算環(huán)境。對(duì)負(fù)荷分配封閉式解決方案被提出來。在這里，我們將一步步討論封閉形式的解決方案，通過它可以計(jì)算分配到各處理節(jié)點(diǎn)的負(fù)載的最優(yōu)分片來為每個(gè)處理器實(shí)現(xiàn)最低的代價(jià)和最優(yōu)的數(shù)據(jù)分配。調(diào)度圖如圖1所示：

圖 1可分任務(wù)調(diào)度

讓我們考慮以下因素：N是系統(tǒng)總的任務(wù)個(gè)數(shù)，M是系統(tǒng)中總的處理器個(gè)數(shù)，ωi處理器單元每條指令的代價(jià)，βj表明任務(wù)j的延遲代價(jià)。Ψj是任務(wù)j的延遲成本估計(jì)，ICj表示每任務(wù)預(yù)期指令個(gè)數(shù)，MIPSj每秒機(jī)器j能執(zhí)行的指令數(shù)。

處理器i執(zhí)行代價(jià)為公式（1）：

任務(wù)i的延遲時(shí)間為公式（2）：

4 總結(jié)在本文中，我們提出在云計(jì)算機(jī)環(huán)境中的DLT范式處理作業(yè)調(diào)度問題。在云計(jì)算環(huán)境中使用DLT范式進(jìn)行分配策略可以最小化總代價(jià)。為此，我們?cè)O(shè)計(jì)并分析了一個(gè)封閉形式的解決方案關(guān)于任務(wù)調(diào)度的問題。作為這項(xiàng)工作的一個(gè)直接擴(kuò)展我們將嘗試通過考慮通信開銷影響和動(dòng)態(tài)負(fù)載的情況。我們也將考慮更多的實(shí)時(shí)任務(wù)分配來一步優(yōu)化這一模型。通過這樣的改進(jìn)，該模型可以集成在現(xiàn)有的云基礎(chǔ)設(shè)施中，以提高他們的性能。

[1] Khazaei H, Misic J, Misic V: Performance analysis of cloud computing centers using M/G/m/m+r. queuing systems［J］. IEEE Trans Parallel Distributed Syst 2012, 23:5.

[2] 張龍昌， 鄒華， 楊放春．一種基于多QoS注冊(cè)中心和模型異構(gòu)的WEB服務(wù)選擇算法［J］．電子與信息學(xué)報(bào) ,2011,1:168-173．

[3] A. Shokripour, M. Othman, Categorizing DLT researches and its applications, European Journal of Scientific Research 37 (3) (2009)496 – 515.

[4] B. Javadi, J. Abawajyb, R. Buyya, Failure-aware resource provisioning for hybrid Cloud infrastructure, Journal of Parallel and Distributing Computing, 72(2012), 1318 - 1331.

[5] G.N. Iyer, V. Bharadwaj, S.G Krishnamoorthy. On Handling Large-Scale Polynomial Multiplications in Compute Cloud Environments using Divisible Load Paradigm, IEEE Transactions on Aerospace and Electronic Systems, 48 (1) (2012), 820 – 831.

[6] Xu, M., Cui, L., Wang , H., Bi, Y.. A Multiple QoS Constrained Scheduling Strategy of Multiple Workflows for Cloud Computing. IEEE International Symposium on Parallel and Distributed Processing with Applications, (2009), pp. 629 – 634.

[7] M. Mezmaza, N. Melabb, Y. Kessaci b, Y.C. Lee, E. G. Talbi, A.Y. Zomayac, D. Tuyttens, A parallel bi-objective hybrid metaheuristic for energy-aware scheduling for cloud computing systems, Journal of Parallel and Distributing Computing, 71(2011), 1497 –1508.

[8] J. T. Hung, and T. G. Robertazzi. Scheduling nonlinear computational loads. IEEE Transactions on Aerospaceand Electronic Systems, 44(3) (2008), 1169 – 1182.

Research on Cloud Model with QoS Applied to Webucation

Zhao Zhen, Zhang Longchang
（College of Information Science and Technology,BoHai University,Jinzhou121013,China）

The advent of cloud computing as a new model of service in distributed systems, encourages researchers to investigate its benefits and drawbacks in scientific applications. The dynamic of cloud resource makes resource allocation more difficult. In this research, we attempt to investigate the use of a Divisible Load Theory (DLT) to design efficient strategies to minimize the overall processing time for scheduling jobs in compute cloud environments. We consider homogeneous processors in our analysis and we derive a closed-form solution for the load fractions to be assigned to each processor. Our analysis also attempts to schedule the jobs such a way that cloud provider can gain maximum benefit for his service and Quality of Service (QoS) requirement user’s job.Finally, we quantify the performance of the strategies via rigorous simulation studies.

Cloud; Webucation;Quality of Service

TP393

A

1007-757X(2014)01-0008-02

2013.12.05）

趙 震（1977-），男，渤海大學(xué)信息科學(xué)與技術(shù)學(xué)院，博士研究生，講師。研究方向：數(shù)據(jù)庫與云計(jì)算，錦州，121013張龍昌（1978-），男，渤海大學(xué)信息科學(xué)與技術(shù)學(xué)院，博士，副教授。研究方向：云計(jì)算與食品安全信息化，錦州，121013