計算網(wǎng)格服務(wù)分配的ＱｏＳ優(yōu)化研究

摘 要：為滿足用戶對QoS需求中執(zhí)行時間、服務(wù)費用的不同要求，提出一個計算資源服務(wù)分配的QoS優(yōu)化方法，有助于在眾多分配方案中作出滿足用戶特定需求的選擇。具體實例表明，這種方法具有較好的有效性和實際應(yīng)用價值。

關(guān)鍵詞：面向服務(wù)網(wǎng)格； 計算網(wǎng)格服務(wù)； 資源分配； 服務(wù)質(zhì)量優(yōu)化

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

文章編號：1001—3695(2007)03—0044—03

0 引言

隨著計算機科學(xué)技術(shù)的發(fā)展，網(wǎng)格已成為當(dāng)前國內(nèi)外研究的一個熱點和前沿領(lǐng)域[1]。實際的網(wǎng)格應(yīng)用都需要使用異構(gòu)的、類型多樣的資源，特別是要對這些資源共享使用。各個任務(wù)間更多的是協(xié)作[2]，使得資源的調(diào)度分配、任務(wù)執(zhí)行變得復(fù)雜。在網(wǎng)格計算環(huán)境中，大型計算任務(wù)往往被分解成若干個彼此聯(lián)系的子任務(wù)。這些子任務(wù)向資源管理系統(tǒng)提出資源請求。通常情況下，任務(wù)的數(shù)量多于資源數(shù)量。因此為了提高資源的使用效率同時保證任務(wù)在盡可能短的時間內(nèi)完成，資源調(diào)度器必須講究資源調(diào)度、分配的策略，提高相應(yīng)調(diào)度算法的有效性[3]。

隨著面向服務(wù)網(wǎng)格概念的提出，網(wǎng)格環(huán)境下所有資源都被看成網(wǎng)格服務(wù)（GS）[4]，包括計算資源。網(wǎng)格服務(wù)有統(tǒng)一的服務(wù)接口和獨立的功能描述；資源調(diào)度器也以服務(wù)的形式調(diào)度相應(yīng)的資源，除了有效完成資源調(diào)度任務(wù)外，還需要在調(diào)度過程中充分考慮用戶的特定應(yīng)用需求，為網(wǎng)格應(yīng)用提供非凡的服務(wù)質(zhì)量（Quality of Service，QoS）[5]。但在網(wǎng)格這樣的大規(guī)模環(huán)境中，保證服務(wù)質(zhì)量是一個挑戰(zhàn)，需要掌握和遵從全局范圍內(nèi)的服務(wù)等級協(xié)定SLA。全局SLA很大程度上又依賴本地SLA；本地SLA是服務(wù)提供者與用戶之間的需求約定[6]，其中包含了對服務(wù)質(zhì)量的約定，反映了用戶具體的QoS需求，包括應(yīng)用執(zhí)行時間、費用、服務(wù)可靠性、服務(wù)可用性、服務(wù)效率等。另一方面，網(wǎng)格環(huán)境下用戶的需求多樣性又是一個顯著特點，不同用戶對QoS需求具有不同的傾向性。資源調(diào)度必須反映這種傾向性，以保障用戶服務(wù)質(zhì)量。因此根據(jù)不同用戶的需求采用不同的資源服務(wù)分配方案具有重要的實際意義。

本文在此背景下，研究了計算資源服務(wù)的調(diào)度分配問題，把計算資源看成服務(wù)，關(guān)注用戶的QoS需求；重點研究了在計算資源的分配中如何反映用戶對服務(wù)執(zhí)行時間和服務(wù)費用的需求問題，提出了具體的分配策略和相應(yīng)的優(yōu)化方法。

1 相關(guān)研究和本文的主要工作

OGSA[4]定義了網(wǎng)格服務(wù)（Grid Service）的概念。網(wǎng)格服務(wù)是一種Web Service，該服務(wù)提供了一組接口。這些接口的定義明確并且遵守特定的慣例，解決服務(wù)發(fā)現(xiàn)、動態(tài)服務(wù)創(chuàng)建、生命周期管理、通知等問題。簡單地說，網(wǎng)格服務(wù)=接口/行為+服務(wù)數(shù)據(jù)。把資源、信息、數(shù)據(jù)等一切資源抽象為網(wǎng)格服務(wù)，十分有利于靈活的、一致的、動態(tài)的共享機制的實現(xiàn)。本文從計算資源服務(wù)角度研究計算資源調(diào)度分配問題。

為了應(yīng)對計算網(wǎng)格環(huán)境下計算資源的管理和調(diào)度，文獻[7]提出了計算網(wǎng)格環(huán)境下一組相互獨立的計算任務(wù)的資源映射策略。該策略采用重復(fù)映射和定義效益函數(shù)的方法，能較好地完成資源的分配、滿足不同用戶的實際需要；在追求較小任務(wù)完成時間的同時兼顧任務(wù)的服務(wù)質(zhì)量需求。Buyya提出了一種基于應(yīng)用經(jīng)濟模型的優(yōu)化調(diào)度模型[8]，目的是在資源擁有者和使用者之間建立一種交易，以盡可能低的費用滿足資源使用者進行計算任務(wù)的最低要求。文獻[9]研究了網(wǎng)格服務(wù)合成中的QoS優(yōu)化模型，突出服務(wù)虛擬化、可擴展的QoS度量、基于多度量的合成服務(wù)全局QoS優(yōu)化等特點，為用戶QoS需求和全局服務(wù)質(zhì)量提供保障。文獻[10]基于企業(yè)網(wǎng)格環(huán)境討論了計算資源的分配如何影響全局SLA，并用一個實際企業(yè)應(yīng)用說明計算資源分配的方法及如何在遵從全局SLA的前提下確定具體的分配方案。但它只局限于具體應(yīng)用，沒有從普遍適用的理論高度給出分配方案的形式化描述。本文從服務(wù)的角度出發(fā)，圍繞網(wǎng)格計算任務(wù)執(zhí)行的資源分配問題，結(jié)合不同用戶對QoS需求的不同傾向性，描述了計算資源服務(wù)的分配方案，提出相應(yīng)QoS優(yōu)化方法，以滿足不同用戶的QoS需求，保障全局服務(wù)質(zhì)量[11]。

2 計算資源網(wǎng)格服務(wù)的分配及其QoS優(yōu)化

2.1 計算資源網(wǎng)格服務(wù)的分配方案

考查某個網(wǎng)格任務(wù)Task_x，假設(shè)完成Task_x需要總計NC（單位：百萬個）CPU周期，任務(wù)完成時間不能超過最多Tmax_s，整個網(wǎng)格任務(wù)所耗費用最多不超過Cmax（單位）。網(wǎng)格任務(wù)通常由并發(fā)執(zhí)行的多個計算網(wǎng)格服務(wù)來完成。設(shè)想可以調(diào)用的網(wǎng)格服務(wù)為GS_i（i=1，2，…，n），每個計算網(wǎng)格服務(wù)GS_i分別代表相應(yīng)的計算資源；另外，假定訪問網(wǎng)格服務(wù)資源GS_i的速率為V_i（單位：周期/s）、C_i（單位/s）為使用資源GS_i的費用。

式(1)說明，由單個網(wǎng)格服務(wù)GS_i來完成Taskx。這里的兩個約束條件T、C都不能超出全局SLA所規(guī)定的T_max或C_max，。顯然，在網(wǎng)格環(huán)境執(zhí)行任務(wù)，往往是多個并發(fā)服務(wù)來完成任務(wù)，而并非單個服務(wù)完成的。若所有可用的GS_i（i=1，2，…，n）都參與Taskx的執(zhí)行，同樣需要遵從全局SLA的規(guī)定，則有

式（2）描述了在網(wǎng)格多域、多節(jié)點環(huán)境下，調(diào)用計算網(wǎng)格服務(wù)GS_i完成Taskx的兩種特殊情況。為了保障用戶期望的QoS需求，以計算時間Tmax和使用服務(wù)費用C_max作為兩個約束條件。另一方面，針對這兩個約束條件，存在著不同的計算資源分配方案，即可以調(diào)用所有可用網(wǎng)格服務(wù)GS_i（i=1，2，…，n）中的一個或多個分配給既定任務(wù)。換言之，就是GS_i（i=1，2，…，n）中的任意服務(wù)組合都可以完成Task_x，只要每種組合遵從兩個約束條件即可。這里的每種服務(wù)組合就是一種資源分配方案。所以，針對Task_x更一般的資源分配方案可以描述為

顯然，在網(wǎng)格這樣龐大的動態(tài)環(huán)境下，n的數(shù)目將是非常大的，相應(yīng)分配方案的數(shù)目也很大，這將使分配方案的確定變得困難。實際上不可能分析每種方案的可行性，所以要改進。資源服務(wù)調(diào)度器應(yīng)該采用某種啟發(fā)式的方法，盡快接近目標優(yōu)化結(jié)果。關(guān)于這個內(nèi)容不是本文的重點。本文的重點是從T_max、C_max兩個QoS約束條件的角度考慮資源服務(wù)的分配，研究資源服務(wù)分配的QoS優(yōu)化方法，從而也幫助分配方案的確定。

2.2 QoS優(yōu)化方法

在式（3）描述的眾多資源服務(wù)分配方案中，如何選定其中一種是關(guān)鍵而實際的問題。對不同的應(yīng)用、不同的用戶QoS需求，可能適用不同的方案[11]。因此，不應(yīng)該試圖追求一種通用的方案適用于所有應(yīng)用，而要實事求是，具體情況具體對待。

本文所討論分配方案中的兩個約束因素，即最大執(zhí)行時間Tmax和最大能承受的費用Cmax，是大多數(shù)具體網(wǎng)格應(yīng)用中關(guān)心的重要QoS需求。網(wǎng)格資源分配機制對這兩個QoS需求的處理可能有不同的優(yōu)化方案。若用戶關(guān)注服務(wù)費用勝過其他所有因素，則資源服務(wù)調(diào)度器可考慮費用的優(yōu)化，使之最少，并使時間約束因素符合基本要求，這是第一種QoS需求優(yōu)化方案；若用戶更關(guān)心任務(wù)執(zhí)行的時間，則運用執(zhí)行時間的優(yōu)化，使之能達到最小值，并使費用約束因素符合基本要求，這是第二種QoS需求優(yōu)化方案。

對第一種QoS優(yōu)化方案，計算任務(wù)量的分配根據(jù)計算服務(wù)的費用反比例進行，即最小的費用分配最大的任務(wù)量。令x∈Z+Λx∈[1，n]作為參與執(zhí)行的資源服務(wù)數(shù)目，則

對第二種QoS優(yōu)化方案，由于費用不是最關(guān)心的約束因素，獲得最小的執(zhí)行時間。最優(yōu)化的方法就是按照資源訪問速率來分配計算周期，即

式(5)和(7)反映了用戶不同的QoS需求傾向。QoS優(yōu)化體現(xiàn)了這種需求，并把網(wǎng)格QoS控制中的資源分配優(yōu)化問題轉(zhuǎn)換為傳統(tǒng)數(shù)學(xué)規(guī)劃問題，可以采用數(shù)學(xué)規(guī)劃方法求解。

3 數(shù)例及分析

為了說明與驗證本文的資源服務(wù)分配方案和優(yōu)化思想，舉一個數(shù)值實例來進行驗證。實例觀察與參考了實際應(yīng)用的相關(guān)數(shù)值，因此更接近真實的網(wǎng)格服務(wù)執(zhí)行情況。對網(wǎng)格服務(wù)的費用，使用了模擬數(shù)據(jù)，并用單位量來表示。

假設(shè)NC=m×10⁷，m=1，2，…，9（百萬CPU周期），T_max=3000s，C_max=2 400（單位量）。由于排列組合會使問題的空間很大，為簡單起見，只考慮三個可用候選網(wǎng)格服務(wù)的情況。表1列出了這三個計算資源網(wǎng)格服務(wù)的資源訪問速率和所需費用值。表2和表3分別是QoS優(yōu)化后的第一種和第二種資源服務(wù)分配方案。

因此其計算任務(wù)的承擔(dān)量也按照費用高低比例確定。在列出的幾種服務(wù)分配方案中，為遵從全局SLA中T_max、C_max約束，只有一種服務(wù)分配方案是滿足要求的。表3的QoS優(yōu)化分配方案中，滿足全局SLA條件的有三種，用戶可以從中選擇最優(yōu)的，按照執(zhí)行時間最小的原則，就可以選擇(GS₁，GS₂，GS₃)最優(yōu)可行方案。

另外，計算任務(wù)應(yīng)該有某種結(jié)構(gòu)能反映任務(wù)間的協(xié)作性；處理時間還須包括數(shù)據(jù)傳輸?shù)耐ㄐ叛舆t和網(wǎng)格系統(tǒng)中間件處理的時間。總之，為保障用戶QoS需求，要充分考慮全局SLA，遵從全局SLA和各種QoS約束因素。實際的網(wǎng)格應(yīng)用當(dāng)然不止本文所討論的時間、費用兩個因素，不同的用戶會有不同的要求。全局的資源服務(wù)調(diào)度器應(yīng)分析各種具體應(yīng)用，使用啟發(fā)式調(diào)度算法，滿足各種應(yīng)用的資源調(diào)度需求。

4 結(jié)束語

網(wǎng)格環(huán)境下計算資源的廣域分布、異構(gòu)、動態(tài)、多管理域、存在不同的服務(wù)使用費用及任務(wù)執(zhí)行的協(xié)作性等特點，使計算資源的調(diào)度與分配變得復(fù)雜；同時，實際應(yīng)用中用戶的需求也存在多樣性；任務(wù)執(zhí)行的資源分配必須反映用戶不同的QoS需求。本文基于這些問題，提出了能滿足用戶對執(zhí)行時間、服務(wù)使用費用需求的計算資源服務(wù)分配的QoS優(yōu)化方法，并用具體實例進行說明和分析，具有重要的理論和實際應(yīng)用意義。

本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。