童　釗，肖　正，李肯立

(1.湖南師范大學數(shù)學與計算機科學學院，湖南長沙 410082; 2.湖南大學信息科學與工程學院，湖南長沙 410082)

分布式系統(tǒng)中多用戶網(wǎng)絡應用的概率型調度算法研究

童釗1,2，肖正2，李肯立2

(1.湖南師范大學數(shù)學與計算機科學學院，湖南長沙 410082; 2.湖南大學信息科學與工程學院，湖南長沙 410082)

多用戶網(wǎng)絡應用是分布式計算中最主要的形式之一.為了充分挖掘分布式系統(tǒng)中的計算資源,任務調度是解決該問題的關鍵.然而,由于多用戶網(wǎng)絡應用中存在的不確定性,使得當前的調度方法在動態(tài)性、實時性、適應性等方面都存在諸多不足.考慮到用戶實時性需求,本文提出了概率型調度的思想.該思想將任務的分配看作概率事件,以用戶角度的最短響應時間為目標,給出了多用戶網(wǎng)絡應用的排隊模型,并進一步將調度定義為一個非線性規(guī)劃問題.分析表明上述方法在任務到達過程、服務率方面存在限制,進而提出了一個基于強化學習理論自適應調度算法.該算法首先利用Markov決策過程(MDP)描述該調度問題,然后對任務到達過程和服務率知識進行在線的學習.一旦獲得任務分配概率,遵從該概率可進行快速的任務調度.實驗表明上述兩個算法相比于Min-Min、Max-Min、Suffrage、ECT四種經(jīng)典調度算法具有更短的平均響應時間.除此性能外,通過實驗分析了該概率型調度方法的穩(wěn)定性.

分布式計算;多用戶;任務調度;排隊模型;概率型調度

1　引言

多用戶網(wǎng)絡應用是分布式計算中最主要的形式之一,大量應用對分布式系統(tǒng)的實時響應能力提出了更高的要求.其中,數(shù)據(jù)庫管理系統(tǒng)的查詢處理,尤其是Web數(shù)據(jù)庫,是一類較常見的多用戶網(wǎng)絡應用.在這些應用中,多個查詢請求的隨機到達,它們的處理必須分配到后臺分布式系統(tǒng)中某個處理單元上執(zhí)行.任務調度即決定在這種情況下,何時何資源處理這些查詢.任務調度是挖掘并行分布式系統(tǒng)巨大處理能力的關鍵[1].

Google搜索服務是多用戶網(wǎng)絡應用的一個實例,遍布全球的大量用戶向Google服務器發(fā)送關鍵字查詢請求.Google搜索引擎采用MapReduce技術將原始請求分割為幾類任務,然后將這些任務映射到服務器上處理.對于這樣的多用戶共享的分布式系統(tǒng)及其多用戶網(wǎng)絡應用包含三種不確定性:

(1)何時及任務將到達的數(shù)目未知.用戶何時將發(fā)起何種查詢請求無法預知.

(2)因為處理器和網(wǎng)絡的動態(tài)性,處理單元處理任務的完成時間不可預測.

(3)任務在被處理之前的等待時間不可預測.因為系統(tǒng)不是專用的,來自其他用戶的任務也將分配到這些處理資源上.

由于上述的不確定性,系統(tǒng)完整的信息不能提前預知.因此調度只能夠發(fā)生在運行時.只有充分利用計算資源,才能適應這些不確定性.另外,在多用戶網(wǎng)絡應用中,用戶通常在線等待響應.因此實時性是這類調度算法的一個重要制約因素.所以復雜的調度算法將不可行,短的響應時間(任務從用戶提交至完成的時間)是調度的目標.然而,上述狀態(tài)的不確定性和系統(tǒng)的異構性給該調度問題帶來了挑戰(zhàn).

任務調度是NP完全問題[2,3],即使是獨立非搶占式調度.研究發(fā)現(xiàn)目前的調度算法是在任務和處理單元之間建立一個確定的匹配,為分配的任務指定唯一的單元.確定型任務調度在每次調度時需要重新計算分配方案.為了壓縮調度時間,首次提出概率型調度,依據(jù)一定的概率分布來為任務指定處理單元.由于概率型分配不會立即引起性能的較大下滑,而且不需要實時更新.因此相比于確定型調度的重新計算,縮減了大量的調度時間.此外,確定型調度性能取決于狀態(tài)估計的準確度.如果狀態(tài)估計時發(fā)生偏離,調度的性能也將發(fā)生下降.而概率型調度能夠緩解這種性能的降級.第三,因為任務到達和服務時間是隨機的,因此性能指標的方差變得重要.方差越小,表明調度算法越穩(wěn)定.實驗表明概率型調度同時也能降低性能的方差.

出于上述原因,本文與以往工作不同在于基于概率調度的思想對能夠自適應固有的不確定性,快速生成響應時間較低的動態(tài)調度算法進行了探索.提出的概率型調度算法具有:任務執(zhí)行時間估計的不敏感和性能穩(wěn)定的兩個特性.

基于排隊論建立調度模型,將系統(tǒng)狀態(tài)的動態(tài)性質轉化為概率,這使得系統(tǒng)狀態(tài)具有一定的可預測性,從而使得靜態(tài)調度方法成為可能.進一步將多用戶網(wǎng)絡應用的調度問題定義為一個非線性規(guī)劃問題,并獲得一組最優(yōu)的分配概率.任務直接根據(jù)此概率分布進行分配,大大提高了調度的速度.但是由于排隊論中的一些假設前提與實際環(huán)境不符,上述方法的適用性較低,因此將機器學習方法引入調度中,提出了一種能適應系統(tǒng)狀態(tài)動態(tài)性的調度算法,相比于第一種方法,此方法沒有明顯增加調度的時間復雜度.首先,MDP被用來描述該調度問題,然后給出解決該MDP問題的基于強化學習的在線調度算法.實驗表明,本文提出的算法在平均響應時間上優(yōu)于Min-Min[4,5],Max-Min[4,5],XSuffrage[6],和ECT[6]四種經(jīng)典調度算法.最后,分析了響應時間的方差,證實了本文算法的穩(wěn)定性.通過對系統(tǒng)狀態(tài)估計的敏感性分析,本文所提出的算法也表現(xiàn)出較好的魯棒性.

2　相關工作

對于任務調度問題,近年來已經(jīng)有較多研究,但這個問題似乎遠沒有到達終點.這些算法主要分為兩類:一類是在編譯時確定何時何處來處理任務的靜態(tài)調度,另一類是在運行時進行決策的動態(tài)調度.如前所述,靜態(tài)調度發(fā)生在編譯時.有關任務和系統(tǒng)狀態(tài)的知識需要預先獲悉.但由于多用戶網(wǎng)絡應用中存在的不確定性,這些知識僅在運行時才能確定,因此,傳統(tǒng)的靜態(tài)調度無法適用本文研究的問題.

動態(tài)調度中,系統(tǒng)的狀態(tài)只有當任務運行時才能確定.隨著網(wǎng)絡計算的出現(xiàn),如云計算等,動態(tài)調度成為研究熱點.多用戶網(wǎng)絡應用的調度屬于動態(tài)調度的范疇.動態(tài)調度包括兩個階段:系統(tǒng)狀態(tài)估計和決策制訂.分布式系統(tǒng)的動態(tài)調度技術主要被分為:發(fā)送者發(fā)起,接收者發(fā)起,和對稱發(fā)起三類[7].在發(fā)送者發(fā)起算法中[8,9],過載的節(jié)點向負載較輕的節(jié)點轉移任務;在接收者發(fā)起算法中[10,11],負載較輕的節(jié)點向負載重的節(jié)點發(fā)出任務遷移請求;最后一類,發(fā)送者和接收者能夠對稱地發(fā)起負載遷移請求[12,13].實際上,這些技術都試圖在處理單元之間達到負載均衡.Makespan是并行分布式計算中一個主要性能指標,它反映的是系統(tǒng)的整體性能.而在多用戶網(wǎng)絡應用中,用戶期望他們的請求能夠被迅速處理.因此,本文關注如何進行任務分配以使用戶得到快速響應.

在上述調度算法中,節(jié)點既是處理單元也是任務調度器,分配任務給自己或其它節(jié)點,這種調度方式可能會增加調度開銷.集中式或者分布式調度則可以彌補這種性能損失.本文采用的是集中式調度方法,選取其中一個處理節(jié)點用于負責任務的調度.

在分布式系統(tǒng)中任務調度的一個難點是資源的動態(tài)性質[14].下列方法常被用于適應這種動態(tài)性,估計系統(tǒng)的狀態(tài).(1)利用第三方軟件組件的實時信息,如GIS(Grid Information Service)是網(wǎng)格中一種軟件組件[15],用來維護計算網(wǎng)格中用戶、軟件、服務和硬件的信息,一旦收到請求便返回相應的信息.(2)性能預測.一般而言,靜態(tài)算法在調度時依賴于性能評估.預測可以基于歷史記錄[16]或者負載建模[17,18].本文第一個算法即通過建立排隊模型進行預測.(3)再調度.基于當前最新的資源狀態(tài),再調度技術改變以前的調度決策[19,20].上述三種方法,各有優(yōu)缺:方法(1)需要額外的通信開銷;方法(2)很難保證一個簡單的算法能夠提供較高的預測精度;方法(3)需要改變系統(tǒng)基礎結構以支持任務遷移.

本文引入機器學習技術主動學習動態(tài)性質而不是僅僅像上述方法一樣獲取動態(tài)信息,該學習方法僅涉及少量的通信.在上述的動態(tài)調度算法中,每一個任務調度的時間復雜度至少與處理器的數(shù)量成正比,這可能導致任務的實時性需求無法滿足,而本文的概率型調度僅具有常量的時間復雜度,是一個快速調度算法.此外,以前的工作通常沒有考慮調度的穩(wěn)定性,而這一性質在動態(tài)環(huán)境下是十分重要的.另外,動態(tài)調度還取決于系統(tǒng)狀態(tài)估計.在這兩方面,本文的概率型調度算法表現(xiàn)出較高的穩(wěn)定性和對狀態(tài)估計的容錯能力,這是本文與以往工作的重要不同之處.

3　排隊模型

在描述排隊模型之前,首先分析一下響應時間和Makespan之間的關系.

3.1響應時間與Makespan

響應時間指系統(tǒng)中某個任務從提交到完成所經(jīng)歷的時間[21],而Makespan指從第一個任務到達至最后一個任務完成之間的時間間隔,用于表示完成所有到達任務的總時間.這兩個定義有不同的含義.Makespan用于測量一個系統(tǒng)并行化應用的并行化程度.而響應時間是為每一個用戶服務的瞬時速率.一般而言,較大的響應時間導致較長的Makespan,但有時在特定的環(huán)境下,不得不適當延長Makespan,減少任務的等待時間,使得響應時間降低.下面的示例說明即使在同樣的Makespan下,不同的調度方案可以得到不同的響應時間.

3.2形式化描述

根據(jù)分布式系統(tǒng)中多用戶網(wǎng)絡應用的信息流,基于排隊論建立了一個簡單的模型,如圖2所示.

根據(jù)任務的大小進行分類,調度器負責將來自用戶的任務分配給系統(tǒng)中的各處理單元.到達的任務首先被壓入調度器的到達隊列,然后調度器處理隊列中所有的任務,每一次從到達隊列提取一個任務,分配給某處理單元并將其放入處理單元的本地隊列中.處理單元以先進先出(FIFO)的方式處理本地隊列中的任務.這些處理單元是異構的.在多用戶網(wǎng)絡應用環(huán)境中,用戶期盼得到快速響應.因此,調度問題即為:將任務映射到能夠給用戶較快響應的處理單元.

分布式系統(tǒng)能夠處理m類任務,用戶提交的任務類型集合為{t1,t2,…,tm}.假設任務到達過程為泊松(Poisson)流,λ是任務到達率.定理1證明了本地隊列的到達過程也是一個泊松流,兩個連續(xù)到達任務的時間間隔服從指數(shù)分布,排隊論中M/G/1模型被應用于本地隊列.類型為ti的任務在處理單元PUj上的服務率用μij表示.圖2中Prij表示類型為ti的任務調度到PUj上概率.為了簡化,PUj的服務率視為μij的均值,如下:

(1)

PUj上的任務到達率λj定義如下(見定理1):

(2)

其中,λij是PUj上類型為ti的任務到達率,ρij是PUj的本地隊列中任務類型為ti的概率.ρi是到達隊列中任務類型為ti的概率.

證畢.

定理1PUj的本地隊列上任務到達過程為泊松流,且到達率為λj.

證畢.

本地隊列是一個典型的排隊系統(tǒng).基于排隊論中的結論[22],可以得到以下信息,如表1所示.

表1　排隊模型中使用的符號

(1)平均隊列長度Ls:隊列中任務總數(shù),包括正在被服務的任務.

(2)平均等待長度Lq:隊列中等待服務的任務數(shù)目.

(3)平均等待時間Tq:任務接受服務之前的等待時間.Tq由兩部分組成:到達隊列和本地隊列中的平均等待時間.

(3)

(4)平均逗留時間Ts:任務在系統(tǒng)中耗費的總時間,包括服務時間.Ts由兩部分組成:到達隊列和本地隊列中的平均逗留時間.

(4)

在這個調度模型中,如果調度器能夠迅速的進行任務調度,即μ≥λ,則Tq和Ts中的第一項可以忽略.第4節(jié)中提出的概率調度算法是這一類算法,能在常量時間內完成調度,從而使條件μ≥λ得到滿足.使用排隊論,不確定性通過概率參數(shù)被消除,基于這些概率分布,可以獲得最佳的調度方案.在下一節(jié)中,將詳細描述這一算法.

4　概率型調度算法

在上述模型下,本文提出了兩個概率型調度算法,達到最小化任務的響應時間的目的.首先,將該調度問題定義為一個非線性規(guī)劃問題;但由于受到一些與實際的前提不相符的條件約束,接下來使用MDP對調度問題進行定義,并提出了相應的基于學習的調度算法.

4.1基于非線性規(guī)劃的算法

對于多用戶網(wǎng)絡應用,用戶期望得到快速響應.因為分配是一個隨機事件,所以采用期望響應時間作為目標函數(shù).在上節(jié)調度模型下,類型為ti的任務平均響應時間定義如下:

(5)

因為采用概率型調度機制,調度器能快速的完成任務的分配,到達隊列中的逗留時間相比于本地隊列的等待時間可以忽略不計.因此,式(5)中的近似是合理的.

MinRTavg

s.t.0≤Prij≤1

(6)

對于式(6)中的非線性規(guī)劃問題,有許多求解方法.本文中采用MATLAB工具箱中的“fmincon”求解.

上述的排隊模型和基于非線性規(guī)劃的算法給出了一個求解動態(tài)任務調度的方法,但同時該方法預置了一些假設:任務到達過程認為是泊松過程,即兩個連續(xù)任務的到達時間間隔服從指數(shù)分布.然而,這一假設在實際環(huán)境中可能并不成立.因此,在本小節(jié)中,針對不同的任務到達過程對算法性能進行了分析.

首先,通過上述模型和算法得到一組調度概率,然后在四種不同任務到達過程下分析基于以上調度概率的任務平均響應時間.對于四種不同的任務到達過程,假設其任務到達時間間隔分布服從指數(shù)分布、常數(shù)、均勻和卡方分布,其期望均是任務到達率的倒數(shù)1/λ.其中常數(shù)分布指連續(xù)任務到達時間間隔是常量1/λ.假設本實驗模擬的分布式系統(tǒng)具有3個處理單元,其服務率分別是50,35,40.任務的響應時間包括等待時間和執(zhí)行時間.實驗中分析了每100個任務的平均響應時間,結果如圖3所示.指數(shù)分布的平均響應時間最低,因為指數(shù)分布的模型和算法的假設前提相吻合,而卡方分布的平均響應時間最長.由此可見,當實際與假設條件發(fā)生偏離時,基于非線性規(guī)劃的調度算法的性能會下降,并且隨著到達率的增加,性能下降更快.

任務到達過程存在不確定性,在網(wǎng)絡分布式計算系統(tǒng)中,任務的執(zhí)行時間通常不確定.接下來,將分析當狀態(tài)估計不正確時,算法的魯棒性.實驗中仍然假設包含3個處理單元的分布式系統(tǒng),其真正的服務率分別是50,35,40.對到達率是60和80進行了兩組實驗,當處理單元的狀態(tài),這里即服務率,估計發(fā)生錯誤時,響應時間變化如圖4所示.X坐標軸的四個點分別代表服務率估計正確,低估5個單位,高估5個單位和高估10個單位.從圖中可以看出,無論何種估計錯誤發(fā)生,平均響應時間都發(fā)生增長.且在實驗中,低估相比于同幅度的高估產生更差的結果.

在本小節(jié)分析了當任務到達過程、處理單元狀態(tài)估計發(fā)生錯誤時,提出的基于非線性規(guī)劃算法的魯棒性,實驗結果表明該方法對調度的參數(shù)較為敏感.針對該問題,下一小節(jié)給出了一個基于學習的調度算法,它能自適應這些不確定性,且不需要提前預測,在第5節(jié)將對這兩個算法的有效性進行分析.

4.2基于強化學習的算法

從上述分析可知,基于非線性規(guī)劃的算法具有魯棒性方面的不足.此外,在排隊模型式(1)中,對所有任務,使用平均服務率,這樣的簡化抽象實質上將所有任務認為是同樣大小,這種與實際不相符的假設會給性能帶來一定影響.為了消除以上問題,本小節(jié)提出了一個在線學習算法,該算法能學習任務到達模式以及適應不同任務大小的服務率.

4.2.1調度問題MDP定義

如前所述,對于多用戶網(wǎng)絡應用調度問題,任務隨機到達調度器.必須等所有任務到達或者預知任務到達過程,否則無法找到最優(yōu)的分配方案.即,當前任務的分配取決于后續(xù)到達任務的分配.當前任務最短響應時間的分配可能會延長后續(xù)任務的響應時間,從而分布式系統(tǒng)的平均響應時間增大.基于以上觀點,多用戶網(wǎng)絡應用的調度成為一個動態(tài)規(guī)劃問題,一個分配方案的好壞必須要待所有任務全部分配完才能知曉.

前面的分配對后繼的分配具有一定的影響.而當前任務的分配決策僅和當前的任務類型有關,只需知道任務類型,便可知該任務可在哪些單元上處理.實質上,每一個分配可看作是一個決策制訂階段.因此,一個完整的調度方案包含多個這樣的階段.在這樣的描述下,調度成為一個Markov決策過程(MDP)[23].下文將用四元組將調度問題定義為一個MDP問題.

(1)S是狀態(tài)集,相當于任務類型集,S={t1,t2,…,tm};

(2)B是分配行為集,其由任務類型和處理單元對組成,B={|ti∈S;1≤j≤n};

(3)Γ是狀態(tài)轉換函數(shù):S×B→PD(S),其中PD(S)是當前狀態(tài)為s時,選擇行為b后轉移到新狀態(tài)的概率分布;

(4)R是報酬函數(shù):S×B→R,其中r∈R表示在狀態(tài)s選擇行為b時的立即回報.回到本問題,R是響應時間的函數(shù).

將調度作為一個動態(tài)規(guī)劃問題,其目標函數(shù)是折扣累積回報,定義如下:

(7)

其中γ是折扣因子.式(7)中,期望回報的計算只有當所有任務完成一系列的分配行為后才能獲得,當前行為的效用取決于未來的行為.因此,折扣累積回報ψ依賴于狀態(tài)轉移函數(shù)Γ,即任務到達過程.然而,提前獲取有關到達任務的知識是不現(xiàn)實的.假設任務到達是一個泊松過程也將帶來一定的負面影響,如4.1.1節(jié)所分析.下一小節(jié)將使用一種模型無關的強化學習方法——Q學習,用來解決以上問題.

4.2.2自適應算法

調度器在進行分配決策時,需要考慮兩個因素:一是各處理單元的負載情況,它決定了任務的執(zhí)行開銷,即行為的立即回報;二是任務到達過程的預測.因為任務隨機出現(xiàn),盡管當前立即回報很高,但長遠來看,系統(tǒng)的平均回報率并不一定如此.通過獲得到達過程信息使得系統(tǒng)長期回報最大化,Q學習正是一種能夠在線學習到達過程,并逐漸適應這兩個參數(shù)的方法.

根據(jù)Q學習算法,如果類型為ti的任務到達調度器,行為bij=∈B的期望回報為:

Q(ti,bij)=(1-α)Q(ti,bij)+α[R(ti,bij)+γV(tk)]

(8)

其中α(0<α≤1)是學習速率,V(tk)是下一個轉移狀態(tài)tk的期望回報.V(tk)按照式maxjQ(tk,bkj)進行更新.立即回報R(ti,bij)是任務ti到達至其在PUj上完成所花費時間的倒數(shù).根據(jù)強化學習理論,學習過程試圖最大化ψ.此外,Q學習是一種試錯型方法,在算法1中使用輪盤賭的方法根據(jù)概率Prij進行行為選擇,Prij可以在執(zhí)行完一個任務時按照下式進行更新:

(9)

Prij將收斂到一個穩(wěn)定值.

上述算法是一個在線學習算法,當任務被分配并執(zhí)行完后進行分配概率的學習.

5　實驗與結果分析

本節(jié)將對提出的兩個調度算法進行實驗驗證.實驗中,任務到達服從隨機分布,其服務時間假設服從指數(shù)分布.基于學習的算法的有關參數(shù)設置如下:

(1)探索率Pe=0.2:任務分配以0.2的概率進行隨機分配,否則將按照分配概率進行分配.探索機制用于避免局部最優(yōu).該值越大,則收斂越慢;

(2)折扣因子γ=0.9:累積折扣回報表達式的系數(shù);

(3)學習速率α= 0.3:該參數(shù)同樣對收斂速度也有影響.它也可以設置為一個單調遞減的函數(shù).

另外,在服務率的設置上有所不同.在排隊模型中,將所有任務的平均服務率作為處理單元的服務率,而通常任務具有不同的大小,所以在某處理單元上任務完成所耗費的時間有一個較大變化范圍,因此用單一值定義服務率的抽象能力有限.在基于學習的算法中,為每一個處理單元上各任務均定義相應的服務率,在收斂性實驗中的服務率矩陣如表2所示,為了便于比較,各處理單元的平均服務率保持和4.1.1節(jié)中的一致,其它參數(shù)保持不變.

表2　服務率矩陣

本節(jié)所有的實驗都是基于PC進行的模擬仿真,在將來工作中考慮將這些實驗移植到真實集群系統(tǒng)上進行.

圖5給出了收斂性實驗的結果,每一種顏色所占的比例代表了將類型為t1的任務分配到三個處理單元的概率.隨著學習的進行,三個分配概率值震蕩減小,趨于穩(wěn)定.此外,在前幾百個迭代周期內,任務以較大概率分配給PU1.造成這一現(xiàn)象的原因是:在初始時,處理單元空閑,而PU1具有最大的處理能力,隨著任務不斷到達,PU1上發(fā)生阻塞,這時任務開始向具有次大處理能力的PU2轉移.

本文下一步工將對基于Q學習算法的魯棒性進行分析.實驗設置參照4.1.1節(jié),對四種不同隨機分布及四種不同到達率下的平均響應時間進行了記錄.圖6給出了這組實驗的結果,其中藍色代表基于Q學習的算法,而紅色代表基于規(guī)劃的算法.從圖6可以得出兩個結論:第一,與圖4中的結果比較,基于規(guī)劃算法的平均響應時間更長,其原因可能是因為本實驗中對不同任務類型的服務率進行了區(qū)分,而基于規(guī)劃的算法將所有任務視為同樣大小.同樣的原因,對于指數(shù)分布的任務到達間隔,基于學習的算法也表現(xiàn)出優(yōu)于基于規(guī)劃算法的性能.這一原因從表3可以得到更好的理解,表3給出了兩個算法在到達率λ=80的分配概率,在實驗中各種任務類型出現(xiàn)的概率依次為0.4,0.2,0.1,0.1.對于基于規(guī)劃的算法,當不同類型的任務以相同概率出現(xiàn),則其分配概率也相同;而由于基于學習的算法考慮了各處理單元上任務大小的影響,分配概率相互之間存在差異.第二,對于不同的任務到達分布,基于學習算法的平均響應時間相對平穩(wěn),相比而言,基于規(guī)劃算法的性能在非指數(shù)分布下降,這與4.1.1節(jié)的實驗結果一致.由此可見,基于學習的調度算法對任務到達過程具有更強的適應能力.

表3　本文兩個算法的分配概率示例

Prijt1t2t3t4t5PU1Learning0.35870.35410.34030.33270.3484Programming0.49340.41340.37330.37330.4134PU2Learning0.32150.32530.32440.33460.3281Programming0.20520.26930.30130.30130.2693PU3Learning0.31980.32070.33530.33270.3235Programming0.30140.31740.32540.32510.3174

下面的實驗將本文提出的算法與其它經(jīng)典調度算法進行了比較.動態(tài)調度有兩種模式:一種稱為批模式,在該模式下,當一批任務到達后才啟動調度機制,Min-Min,Max-Min,和Suffrage是這種模式三個經(jīng)典算法.對于Min-Min算法,一批任務的最早完成時間(ECT)均被計算,然后總是挑選具有最小ECT的映射作為當前的一次調度,直至所有任務調度完.而對于Max-Min算法,則每次挑選具有最大ECT的映射.Suffrage算法則是挑選具有最大損失值的映射.一般,損失值可定義為任務最大和次大ECT之間的差值.批的大小可以以任務的數(shù)量或者時間周期作為劃分標準.顯然,批模式下只有當達到批的規(guī)模,任務才開始進行調度,先到達的任務不得不等待,這將造成響應時間的增加.此外,由于需要計算所有任務處理單元對的ECT,這類算法的時間復雜度漸近于批大小與處理單元數(shù)目之積.基于上述的原因使得批模式算法不能滿足實時性的需求,因此在線模式被提出.這類算法立刻對到達的任務根據(jù)最小執(zhí)行時間(MET)或者ECT進行分配,MET或者ECT越小,則越可能分配給該處理單元.所有這些啟發(fā)式算法試圖減少響應時間,但忽略了負載均衡問題,從而可能使得平均響應時間增加.本文提出的兩個概率型調度算法屬于在線模式,這組實驗將對本文算法,以及Min-Min,Max-Min,Suffrage和一個基于ECT的簡單在線算法的性能展開分析.

本文中,平均響應時間被用來作為評估調度算法的主要指標,然而,在動態(tài)環(huán)境中,隨機性導致了平均響應時間振蕩不穩(wěn)定的現(xiàn)象.在任何任務到達過程下人們總是希望調度算法總是能夠產生一個較好的調度方案.如果將平均響應時間看作是一個隨機變量,期望平均響應時間的方差能夠盡量小.因此,在動態(tài)調度中,方差也是一個重要的評價指標.出于這樣的考慮,在進行性能分析時,不僅考慮平均響應時間,也對其方差變化進行了分析.

本文提出的基于規(guī)劃的算法有兩個約束:任務到達時間間隔呈指數(shù)分布,不區(qū)分各任務類型的規(guī)模大小.圖7、8檢驗了這兩個約束條件滿足和不滿足兩個條件下算法的性能.圖7是假設任務到達服從指數(shù)分布且任務大小相同,本文兩個算法與其它四個經(jīng)典算法性能比較結果.假設中任務大小相同意味著對于所有的任務三個處理單元的服務率分別是50,35,40.因為滿足了基于規(guī)劃算法的假設,所以其產生了最優(yōu)的分配方案,任務響應時間最快.而基于學習的算法找到的是一個次優(yōu)解,因此圖7中基于學習的算法性能低于基于規(guī)劃的算法.圖中,本文算法和ECT算法的平均響應時間隨著任務到達率增加而增加,而三個批模式算法趨勢相反,其原因是批模式算法只有當一批任務全部到達才進行調度.當?shù)竭_任務比較稀疏時,這一現(xiàn)象更嚴重,因為更多的時間用來等待后續(xù)任務的到達.這一現(xiàn)象在圖8中同樣存在.圖8是當任務到達為一般分布且大小不一致時的比較結果,使用不同的任務到達率(見表2)來表示任務大小的不同.圖8中,正如所預料的,當上述條件不滿足時,基于規(guī)劃的算法得到的不是最優(yōu)解,因此性能下滑,但基于學習的算法仍然表現(xiàn)穩(wěn)定.與圖7相比,各算法的響應時間有所增加,這是因為一些較大任務的服務率縮小(見本節(jié)開始部分的表2).無論是圖7還是圖8,本文算法相比于四種經(jīng)典算法都表現(xiàn)出較好的性能.另外,不同于前人工作中的性能比較,對平均響應時間的方差同樣進行了分析.任務到達是隨機的,因此平均響應時間是一個隨機變量.從圖中可以看出基于學習的算法方差較小,性能優(yōu)于其它算法.當與前提假設發(fā)生偏離時,基于規(guī)劃算法的方差出現(xiàn)放大.在實驗中,還發(fā)現(xiàn)Min-Min,Max-Min和Suffrage算法具有非常相似的性能,這可能是由于這三個算法需要到達任務呈現(xiàn)某種形式才能體現(xiàn)出各自的優(yōu)勢,例如,如果規(guī)模較大的任務不常見時,這時Max-Min算法性能可能會有所提升.

前文提到概率型調度能夠有效緩解狀態(tài)估計不準確的問題,圖9驗證了此結論.該實驗的參數(shù)設置與圖8的實驗一致,第一列代表狀態(tài)估計正確時的平均響應時間,從左至右各列依次代表任務完成時間出現(xiàn)低估或者高估時的結果.低估和高估的效果通過調整服務率來達到,比如,↓5表示每一任務類型的估計服務率下降5個單位.從圖9可以看出本文提出的算法振蕩幅度較小,因此本文的概率型調度算法對狀態(tài)估計準確度的敏感性較低,從而對狀態(tài)估計的約束相對寬松.

6　總結

本文研究了分布式計算中多用戶網(wǎng)絡應用的任務調度問題,通過對其動態(tài)性和不確定性的深入分析,提出了兩個概率型調度算法:一是在排隊模型下的基于非線性規(guī)劃算法;一是基于強化學習的算法.實現(xiàn)了一種快速有效的調度方法.第一個算法在滿足前提條件下能夠得到最優(yōu)的分配概率,第二個算法則具有更強的適應性,能適用各種動態(tài)環(huán)境.

[1]Jiang Y C,Jiang J C.Contextual resource negotiation-based task allocation and load balancing in complex software systems[J].IEEE Trans Parallel and Distributed Systems,2009,20(5):641-653.

[2]Gary M R,Johnson D S.Computers and Intractability:A Guide to the Theory of NP-Completeness[M],New York,NY,USA:W H Freeman and Co, 1979.

[3]Ullman J D.NP-complete scheduling problems[J].J Computer and Systems Sciences,1975,10:384-393.

[4]Gkoutioudi K Z,Karatza H D.Multi-criteria job scheduling in grid using an accelerated genetic algorithm[J].J Grid Computing,2012,10(2):311-323.

[5]Omara F A,Arafa M M.Genetic algorithms for task scheduling problem[J].J Parallel and Distributed Computing,2010,70(1):13-22.

[6]Hu X S,Dick R P.Temperature-aware scheduling and assignment for hard real-time applications on MPSoCs[J].IEEE Trans Very Large Scale Integration Systems,2011,19(10):1884-1897.

[7]Chakrabarti P P,Kumar R.Online scheduling of dynamic task graphs with communication and contention for multiprocessors[J].IEEE Trans on Parallel and Distributed Systems,2012,23(1):138-153.

[8]Wen Y,Xu H,Yang J D.A heuristic-based hybrid genetic-variable neighborhood search algorithm for task scheduling in heterogeneous multiprocessor system[J].Information Sciences,2011,181(3):567-581.

[9]Sinnen O,To A,Kaur M.Contention-aware scheduling with task duplication[J].J Parallel and Distributed Computing,2011,71(1):77-86.

[10]Benoit A,Robert Y.Complexity results for throughput and latency optimization of replicated and data-parallel workflows[J].Algorithmica,2010,57(4):689-724.

[11]艾麗華,羅四維.數(shù)據(jù)網(wǎng)格虛擬機動態(tài)存儲層析的研究[J].電子學報,2010,38(11):2680-2685.

AI Li-hua,LUO Si-wei.Research on dynamic storage hierarchy of data grid virtual machine[J].Acta Electronica Sinica,2010,38(11):2680-2685.(in Chinese)

[12]Subrate R,Zomaya A Y,Landfeldt B.Game-theoretic approach for load balancing in computational grids[J].IEEE Trans on Parallel and Distributed Systems,2008,19(1):66-76.

[13]Jiang Y C,Huang Z C.The rich get richer:preferential attachment in the task allocation of cooperative networked multiagent systems with resource caching[J].IEEE Trans on Systems,Man,and Cybernetics-Part A:Systems and Humans,2012,24(5):1040-1052.

[14]Aktaruzzaman M.Literature Review and Survey:Resource Discovery in Computational Grids[R].Technical Report,School of Computer Science,University of Windsor,Windsor,Ontario,Canada,2003.

[15]張偉哲,田志宏,張宏莉,等.虛擬計算環(huán)境中的多機群協(xié)同調度算法[J].軟件學報,2007,18(8):2027-2037.

Zhang Weizhe,Tian Zhihong,Zhang Hongli,et al.Multi-cluster co-allocation scheduling algorithms in virtual computing environment[J].Journal of Software,2007,18(8):2027-2037.(in Chinese)

[16]肖鵬,胡志剛.截止時間約束下獨立網(wǎng)格任務的協(xié)同調度模型[J].電子學報,2011,39(8):1852-1857.

Xiao Peng,Hu Zhigang.Co-scheduling model for independent tasks with deadline constraint in computational grid[J].Acta Electronica Sinica,2011,39(8):1852-1857.(in Chinese)

[17]He L,Jarvis S A,Spooner D P,Bacigalupo D,Tan G,Nudd G R.Scheduling DAG-based applications in multicluster environments with background workload using task duplication[J].International Journal of Computer Mathematics,2010,87(11):2387-2397.

[18]Sakellariou R,Zhao H.A low-cost rescheduling policy for efficient mapping of workflows on grid systems[J].J Scientific Programming,2004,12(4):253-262.

[19]張理論,葉紅,吳建平,等.基于最大負載偏移率的并行負載平衡性能分析[J].計算機研究與發(fā)展,2010,47(6):1125-1131.

Zhang Lilun,Ye Hong,Wu Jianping.Parallel load-balancing performance analysis based on maximal ratio of load offset[J].Journal of Computer Research and Development,2010,47(6):1125-1131.(in Chinese)

[20]Qin X,Xie T.An availability-aware task scheduling strategy for heterogeneous systems[J].IEEE Trans on Computers,2008,7(57):188-199.

[21]Donald Gross,John F Shortle,James M Thompson,Carl M Harris.Fundamentals of Queueing Theory[M].Hoboken,NJ:John Wiley & Sons,2008.

[22]Kaelbling L P,Littman M L,Moore A W.Reinforcement learning:a survey[J].Journal of Artificial Intelligence Research,1996,4:237-285.

[23]吳小東,韓建軍,王夭江.一種基于VFD多核系統(tǒng)的硬實時任務節(jié)能調度算法[J].計算機研究與發(fā)展,2012,49(5):1018-1027.

Wu Xiaodong,Han Jianjun,Wang Tianjiang.Energy-aware scheduling of hard real-time tasks in VFD-based multi-core systems[J].Journal of Computer Research and Development,2012,49(5):1018-1027.(in Chinese)

童釗男，1985年2月生，湖南岳陽人.2007年獲得北京理工大學計算機科學專業(yè)學士學位，2014年獲得湖南大學工學博士學位，現(xiàn)為湖南師范大學數(shù)學與計算機科學學院講師.主要研究方向為并行與分布式計算、資源管理、任務調度、并行算法設計.

E-mail：tongzhao@hunnu.edu.cn

肖正男，1981年4月生，湖南懷化人.2003年本科畢業(yè)于湖南大學通信工程專業(yè)，2009年獲得復旦大學計算機應用技術專業(yè)博士學位，現(xiàn)為湖南大學信息科學與工程學院助理教授.主要研究方向為并行與分布式計算，分布式人工智能，協(xié)同計算.

E-mail：zxiao@hnu.edu.cn

李肯立男，1971年10月生，湖南婁底人.2000年獲得中南大學數(shù)學專業(yè)碩士學位，2003年獲得華中科技大學計算機科學博士學位，現(xiàn)為湖南大學信息科學與工程學院教授.2004年至2005年在伊利諾伊大學厄巴納-香檳分校任訪問學者.2013年獲得教育部科技進步二等獎.CCF高級會員.主要研究方向為并行計算，網(wǎng)格計算，云計算，DNA計算.E-mail：lkl510@263.net

A Queueing Model and Probabilistic Scheduling for Multi-user Network Applications

TONG Zhao1,2,XIAO Zheng2,LI Ken-li2

(1.College of Mathematics and Computer Science,Hunan Normal University,Changsha,Hunan 410082,China；2.College of Information Science and Engineering,Hunan University,Changsha,Hunan 410082，China)

Multi-user network application is one of the most popular forms of distributed computing.To fully exploit computing resources in distributed systems,task scheduling is critical.However,in scheduling of multi-user network application because lots of uncertainties exist such as task arrival,task completion time,etc.,the state of the art scheduling approaches fail in dynamic,real time,or adaptability.On account of the real time property,we put forward the concept of probabilistic scheduling to compress scheduling time,which regards task allocation as a probabilistic event.Unexpectedly,compared with traditional scheduling approaches which are always determinate,probabilistic scheduling has other advantages like insensitivity to task execution time estimation and steady performance.Based on the idea of probabilistic scheduling and considering the shortest response time from the perspective of users,a queueing model is given for multi-user network application,and scheduling is defined as a non-linear programming problem.But due to its limitation on task arrival process and service rate,a self-adaptive algorithm is proposed by use of reinforcement learning theory.The scheduling problem is described by Markov Decision Process (MDP),and then task arrival process and service rate can be learned on line.Once the allocation probability is acquired,scheduling is quite fast by following such probability distribution.The two algorithms are validated and they outperform such four classic algorithms as Min-Min,Max-Min,Suffrage,and ECT at the average response time.Except for the mean of response time,their variance is also examined to confirm the stability generated by probabilistic scheduling.

distributed computing;multi-user;task scheduling;queueing model;probabilistic scheduling

2013-02-27;

2013-07-26；責任編輯：郭游

國家自然科學基金重點項目(No.61133005);國家自然科學基金青年項目(No.61402157);湖南省自然科學基金(No.13JJ4038);湖南師范大學青年基金(No.11404)

TP391

A

0372-2112 (2016)07-1679-10

??學報URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.07.023