胡 靜

(山西農(nóng)業(yè)大學(xué) 軟件學(xué)院，山西 晉中 030801)

0 引 言

目前大數(shù)據(jù)計(jì)算平臺中已經(jīng)存在的調(diào)度器如默認(rèn)的FIFO調(diào)度器、公平調(diào)度器和計(jì)算能力調(diào)度器[1]等其它算法[2,3]調(diào)度作業(yè)時只考慮到了平臺資源利用率但沒有考慮作業(yè)截止時間和服務(wù)商收益問題。針對作業(yè)截止時間要求，部分研究學(xué)者[4-9]以作業(yè)截止期限為約束提出一種相應(yīng)的作業(yè)調(diào)度算法以提高作業(yè)的執(zhí)行效率與平臺資源利用率，但仍沒考慮服務(wù)商的收益問題。文獻(xiàn)[10-14]提出相關(guān)調(diào)度算法目的是使服務(wù)商的利潤最大化。文獻(xiàn)[15-17]均提出了新的調(diào)度方法，保證服務(wù)商的最大收益、服務(wù)的截止時間和平臺的資源利用率。在服務(wù)商指定時間內(nèi)完成每個作業(yè)可獲得的收益模式和現(xiàn)有作業(yè)調(diào)度器下，服務(wù)商沒有考慮到作業(yè)截止時間的準(zhǔn)確性和作業(yè)執(zhí)行的迫切需求，并且也沒有考慮作業(yè)調(diào)度結(jié)果對平臺資源利用率的影響。

基于上述問題，本文提出了一種服務(wù)商收益模式—獎懲共存收益模式(RP Model)。該收益模式考慮用戶對服務(wù)商的獎勵政策，即當(dāng)服務(wù)商在作業(yè)截止時間之前的一定時間范圍內(nèi)完成作業(yè)時對服務(wù)商給予相應(yīng)的獎勵值。此收益模式針對的是不確定作業(yè)截止時間是否準(zhǔn)確的用戶，并且該類用戶對于作業(yè)執(zhí)行完成有迫切需求。服務(wù)商為了滿足用戶較短的作業(yè)完成時間需求，盡量縮短每個作業(yè)的完成時間。當(dāng)作業(yè)實(shí)際完成時間比用戶提供的截止時間短時，服務(wù)商將該作業(yè)的實(shí)際完成時間作為較準(zhǔn)確的截止時間反饋給用戶，使得用戶以后提交相同的作業(yè)時就可以提供較準(zhǔn)確的截止時間，并且推進(jìn)了用戶處理作業(yè)群的整體行為。獎懲共存收益模式的提出實(shí)現(xiàn)了服務(wù)商與用戶的利益共贏。

本文以獎懲共存收益模式為目標(biāo)，提出了一種高效的MapReduce作業(yè)調(diào)度器——最大收益完成時間資源利用率調(diào)度器(MPCRS)，以盡量縮短每個作業(yè)的完成時間，提高平臺資源利用率，使服務(wù)商獲得最大收益。

1 MPCRS調(diào)度器設(shè)計(jì)

本文是在Hadoop2.x的Yarn資源管理系統(tǒng)的基礎(chǔ)上提出的MPCRS。Yarn作為統(tǒng)一資源管理系統(tǒng)，核心組件為全局資源管理器(resource manager，RM)，負(fù)責(zé)整個平臺的資源管理和分配。它主要由兩個組件構(gòu)成：作業(yè)調(diào)度器(Scheduler)和應(yīng)用程序管理器ApplicationsManager(ASM)。調(diào)度器能夠根據(jù)容量、隊(duì)列等限制條件，將平臺中的資源按照作業(yè)資源需求分配給各個將要運(yùn)行的作業(yè)。由于調(diào)度器是一個可插拔的組件，故本文將以滿足服務(wù)商最大收益、平臺最大資源利用以及作業(yè)最短完成時間為目標(biāo)設(shè)計(jì)一種MPCRS作業(yè)調(diào)度器。圖1展示了在Yarn平臺中MPCRS的作用以及構(gòu)成。

圖1 MPCRS的作用與構(gòu)成

如圖1所示，該平臺允許多用戶提交多個帶有SLA約束的作業(yè)。RM中主要包含MPCRS和ASM兩種組件，其中MPCRS是由RP Model、基于任務(wù)執(zhí)行時間的確定輪數(shù)算法(TRN)以及基于最大輪數(shù)的作業(yè)調(diào)度算法(MRNS)組成。RP Model將每個作業(yè)在不同時間段內(nèi)可獲得的相應(yīng)收益值作為TRN算法與MRNS算法的輸入值。為了盡量縮短每個作業(yè)的完成時間，TRN算法以RP Model下可獲得的收益值為標(biāo)準(zhǔn)，根據(jù)各個作業(yè)的Map和Reduce任務(wù)執(zhí)行時間，確定出作業(yè)在不同獎懲階段的Map和Reduce最大輪數(shù)組合以及最大標(biāo)準(zhǔn)時間。MRNS算法得到最大輪數(shù)組合方案和最大標(biāo)準(zhǔn)時間值后，結(jié)合平臺中現(xiàn)有資源數(shù)量，考慮平臺資源利用率，制定出對于當(dāng)前所有作業(yè)的調(diào)度策略(TS)。ASM將會根據(jù)TS策略啟動相應(yīng)作業(yè)的(application master，AM)，AM向RM申請所需的資源，RM為其任務(wù)分配在各個(node manager，NM)上的Container資源，使得該作業(yè)得以開始運(yùn)行。AM將作業(yè)分為Map和Reduce任務(wù)，由于MPCRS產(chǎn)生的TS策略是基于任務(wù)級別的，故為作業(yè)分配資源即為Map或Reduce任務(wù)分配資源。

2 MPCRS調(diào)度器實(shí)現(xiàn)

本文提出的MPCRS調(diào)度器是生成相應(yīng)的作業(yè)調(diào)度策略，而具體任務(wù)分配方法仍然遵循MapReduce的動態(tài)分配原則，因此不會對平臺中負(fù)載均衡等其它性能特性造成影響。在滿足平臺資源利用率最大的條件下，雖盡量縮短每個作業(yè)的完成時間，但不可避免會造成個別作業(yè)超出截止期限，無法按時完成。出現(xiàn)這種情況時需根據(jù)服務(wù)商收益最大化的目標(biāo)對作業(yè)的收益與賠付代價進(jìn)行衡量評估，經(jīng)過整體收益權(quán)衡后選擇放棄一些收益較少或賠付較少的作業(yè)。

2.1 獎懲共存收益模式-RP Model

在計(jì)算平臺中認(rèn)為每個節(jié)點(diǎn)的處理能力都大致相同，由于平臺中的資源是統(tǒng)一進(jìn)行管理和分配，故可動態(tài)分配的Container資源用R表示。用戶提交的作業(yè)j已知如下信息：j的截止時間j_deadline；在j_deadline之前j被完成，服務(wù)商可獲得的收益j_profit；如果j的實(shí)際完成時間j_completion的a倍比j_deadline短，用戶按照SLA中規(guī)定的獎勵比率α，支付除收益以外的獎勵值j_profit×α×a；j的實(shí)際完成時間j_completion超過j_deadline時，按照服務(wù)商與用戶簽訂的SLA賠付比率β進(jìn)行賠償，即當(dāng)j_deadlineb×j_deadline， 則需要賠付給用戶原收益的γ倍，即j_profit×γ；j具有的Map數(shù)量j_Nm和Reduce數(shù)量j_Nr；j中每一輪Map任務(wù)的執(zhí)行時間j_Tm和每一輪Reduce任務(wù)的執(zhí)行時間j_Tr。為了提高作業(yè)的執(zhí)行效率和平臺資源利用率，在平臺資源充足的條件下，要盡量使同一個作業(yè)的多個任務(wù)并行執(zhí)行，而每次并行執(zhí)行任務(wù)的時間稱為一輪任務(wù)的執(zhí)行時間。

根據(jù)以上關(guān)于作業(yè)的收益與賠付信息，結(jié)合平臺中可分配的資源數(shù)量，RP Model如下

(1)

(2)

式(1)表示完成所有作業(yè)后可獲得的收益和，其中每個作業(yè)的實(shí)際收益是由該作業(yè)在截止時間之前完成的收益j_profit與額外的獎勵或者懲罰f(j_profit) 組成。式(2)確保了將要運(yùn)行的任務(wù)每次并行請求資源時資源數(shù)不超過平臺中可動態(tài)分配的資源總和。獎懲共存函數(shù)f(j_profit) 表示如下

(3)

其中，α是在作業(yè)實(shí)際完成時間比規(guī)定的截止期限短a倍時可獲得的獎勵比率，β是作業(yè)實(shí)際完成時間比規(guī)定的截止期限長但沒有超過截止時間的b倍時作業(yè)的賠付比率，γ是作業(yè)實(shí)際完成時間超過規(guī)定截止時間b倍時所要賠付的收益倍數(shù)。在考慮到盡量使每個作業(yè)都在截止期限之前完成，故設(shè)置賠付率值要比獎勵率值大，即α≤β≤1； 而作為長時間超出截止期限的懲罰設(shè)置γ≥1。 由于不能簡單的根據(jù)作業(yè)實(shí)際完成時間和截止時間值就規(guī)定用戶付出獎勵或服務(wù)商付出賠付，而應(yīng)該是在兩者差值超過一定范圍后用戶才需要支付額外的獎勵值或服務(wù)商支付額外的賠付值，故設(shè)a,b>1。

2.2 基于任務(wù)執(zhí)行時間的確定輪數(shù)算法——TRN

TRN算法根據(jù)每個作業(yè)的Map和Reduce任務(wù)執(zhí)行時間，以RP Model中可獲得的收益值為標(biāo)準(zhǔn)，確定每個作業(yè)在不同獎懲階段的Map和Reduce最大輪數(shù)組合以及最大標(biāo)準(zhǔn)時間。在上節(jié)中介紹了用戶提交作業(yè)時已知的信息，其中包括作業(yè)j中每一輪Map任務(wù)的執(zhí)行時間j_Tm和每一輪Reduce任務(wù)的執(zhí)行時間j_Tr，并且j具有的Map數(shù)量j_Nm和Reduce數(shù)量j_Nr。

TRN算法的結(jié)果是要得到每個作業(yè)在不同獎懲階段時的任務(wù)最大輪數(shù)組合方案與最大標(biāo)準(zhǔn)時間。其中有關(guān)確定任務(wù)輪數(shù)的因素具體包括

(4)

(5)

(6)

在全部動態(tài)可分配資源只分配給一個作業(yè)的情況下，RN_m是作業(yè)j的Map任務(wù)的最少執(zhí)行輪數(shù)；RN_r則是Reduce任務(wù)的最少執(zhí)行輪數(shù)；式(6)表示作業(yè)j的最短執(zhí)行時間tleast是由任務(wù)的最少輪數(shù)與每輪任務(wù)的執(zhí)行時間組成。

算法1展示了如何在各獎懲階段獲得任務(wù)最大輪數(shù)組合方案以及最大標(biāo)準(zhǔn)時間。首先，算法根據(jù)作業(yè)的已知信息計(jì)算了每個作業(yè)的Map和Reduce任務(wù)的最少執(zhí)行輪數(shù)、最短執(zhí)行時間tleast以及在每個獎懲階段的最大標(biāo)準(zhǔn)時間tstandard(line(2)-line(5))； 其次，在每個最大標(biāo)準(zhǔn)時間時，比較了作業(yè)最短執(zhí)行時間與最大標(biāo)準(zhǔn)時間的大小，根據(jù)獎懲共存函數(shù)f(j_profit) 的模式要求，最大標(biāo)準(zhǔn)時間的最小值一定是大于等于最短執(zhí)行時間，故在每個獎懲階段都可以得到一種輪數(shù)組合方案A，最大限度地以空間換時間方案，即 (RN_m,RN_r,tstandard-tleast)(line(8))； 最后，根據(jù)剩余時間值的大小，找到能夠滿足執(zhí)行一輪Map和一輪Reduce任務(wù)時間的最大變量值k，i，從而得到方案集 (planjm_t∪planjr_t) ——最大限度的以時間換空間方案。由于作業(yè)完成時間超過截止時間后服務(wù)商就要對用戶進(jìn)行賠償，故要盡量保證每個作業(yè)的完成時間能夠達(dá)到最短，而任務(wù)的執(zhí)行輪數(shù)會直接影響到作業(yè)的完成時間。同一獎懲階段中，在輪數(shù)不超過任務(wù)數(shù)量的前提下，即 (RN_m+k)

算法1：TRN algorithm

Input：j_Tm: the processing time of the round map task

j_Tr: the processing time of the round reduce task

j_Nm: the number of map tasks for a job

j_Nr: the number of reduce tasks for a job

f(j_profit): the reward or the punishment of a job

N: the number of jobs

R: dynamically allocate the number of resources

Output：Planj_t: the maximum round numbers plans

tstandard: the maximum standard time for a job

(1)forj=0;j

(2)RN_m←the minimum round numbers of map tasks

(3)RN_r←the minimum round numbers of reduce tasks

(4)tleast←the minimum processing time of a jobj

(5)tstandard∈T←the maximum standard time of every PR stage

(6)whiletstandarddo

(7)iftstandard≥tleastthen

(8) getting the round numbers plan A (RN_m,RN_r), the remaining time (tstandard-tleast)

(9)k,i≥1andk,iareintegersandk,iarethemaximumvaluesthatmeettherequirements

(10)if(tstandard-tleast)≥j_Tmkthen

(11) getting plan B (RN_m+k,RN_r), the remaining time (tstandard-tleast-j_Tm×k)

(12)if(tstandard-tleast-j_Tm×k)≥j_Tr×ithen

(13) getting plan C (RN_m+k,RN_r+i), the remaining time (tstandard-tleast-j_Tm×k-j_Tr×i)

(14)elsethen

(15)planjm_t={A,B}

(16)endif

(17) planjm_t={A, B, C}

(18)endif

(19)if(tstandard-tleast)≥j_Tr×ithen

(20) getting plan D (RN_m,RN_r+i), the remaining time (tstandard-tleast-j_Tr×i)

(21)if(tstandard-tleast-j_Tr×i)≥j_Tr×kthen

(22) getting plan E (RN_m+k,RN_r+i), the remaining time (tstandard-tleast-j_Tr×i-j_Tm×k)

(23)elsethen

(24) planjr_t={A, D}

(25)endif

(26) planjr_t={A, D, E}

(27)endif

(28)Planj_t={A}∪planjm_t∪planjr_t

(29)endif

(30)endwhile

(31)endfor

2.3 基于最大輪數(shù)的作業(yè)調(diào)度算法—MRNS

在TRN算法確定出Map、Reduce任務(wù)最大輪數(shù)組合方案和最大標(biāo)準(zhǔn)時間后，MRNS算法結(jié)合平臺中現(xiàn)有資源數(shù)量，考慮平臺資源利用率，制定出對于當(dāng)前所有作業(yè)的調(diào)度策略，以實(shí)現(xiàn)收益最大化的目標(biāo)。MRNS算法如下所示：

算法2：MRNS algorithm

Input：Planj_t: the maximum round numbers plans

tstandard: the maximum standard time for a job

N: the number of jobs

δ: the threshold of the resource utilization

Output： TS: the optimal scheduling strategy based on tasks

F: the maximum profit

(1)forj=0;j

(2) whenj_tstandard=j_deadline/a, calculate f(j_profit)

(3)F=F+j_profit

(4)endfor

(5)F=F+max(f(j_profit))

(6)jobjof the maximum reward is added to scheduling queue

(7)whenj_tstandard=j_deadline/a,Planj_tof the jobjis selected

(8)whilePlanj_tdo

(9) recording the completion timej_completion

(10) calculating the remaining resourcesrwhen the jobjbegins to be scheduled till the end

(11)if(R-r)/R≥δthen

(12)idlingtheremainingresourcesandwaitingforthepreviousjobcompletion

(13)fori=0;i

(14)ifj_completion≥i_deadlinethen

(15) the jobiis added to the end of scheduling queue

(16)elseifi_deadline-j_completion≥i_1tstandard+j_completionthen

(17) the jobigets the reward f(i_profit)

(18)elseifi_2tstandard+j_completion≤i_deadline-j_completionthen

(19) the jobigets the reward 0

(20)elseifi_3tstandard+j_completion≤i_deadline-j_completionthen

(21) the jobigets the punishment f(i_profit)elsethen

(22) the jobigets the maximum punishment f(i_profit)

(23)endfor

(24) according to f(i_profit) for each job, sortingN-1 jobs

(25)if?f(i_profit)≥0then

(26) the jobithat has the maximum reward is added to the scheduling queue

(27)elseif?f(i_profit)<0then

(28) according to sorting results, find the jobimee-ting f(i_profit)>(-i_profit×γ) & the minimum f(i_profit)

(29) the jobiis added to the scheduling queueelsethen

(30) ?f(i+n_profit)<0,f=|-i+1_profit×γ|+|-i+2_profit×γ|+…+|-i+n_profit×γ|

(31)iff(i_profit)≥fthen

(32) the jobiis added to the scheduling queueelsethen

(33) find the jobi+nmeeting f(i+n_pro-fit)=-i+n_profit×γthat is the minimum

(34) the jobi+nis added to the scheduling queue

(35)elsethen

(36) when the scheduled jobjhas the remaining resources, recording the start timetrfor the remaining resources

(37)fori=0;i

(38)iftr≤i_1tstandardthen

(39) the remaining resourcesrmeetsPlani_tthat on thei_1tstandard

(40) Comparingtr+i_1tstandardwithi_tstandard

(41) the jobiget the maximum |f(i_profit)| besides the maximum punishment

(42)ifi_1tstandard≤tr≤i_2tstandardthen

(43) the remaining resourcesrmeetsPlani_tthat on thei_2tstandard

(44) Comparingtr+i_2tstandardwithi_tstandard

(45) the jobiget the maximum |f(i_profit)| besides the maximum punishment

(46)endfor

(47) the jobiis scheduled that has the maximum |f(i_profit)|

(48)F=F+f(i_profit)

(49)endwhile

(50)F=F+f(i_profit)

算法2中首先根據(jù)所有作業(yè)在j_tstandard=j_deadline/a時的最大獎勵值f(j_profit)，確定被調(diào)度的作業(yè)并且選擇最大輪數(shù)組合方案集(line(1)-line(7))；其次，在前一作業(yè)的所有輪數(shù)組合方案集中，選擇具有局部最大收益的輪數(shù)組合方案進(jìn)行調(diào)度(line(8)-line(49))；最后將所有作業(yè)加入到調(diào)度隊(duì)列后，根據(jù)每個作業(yè)相應(yīng)的任務(wù)輪數(shù)組合方案，計(jì)算全局的最大收益值(line(50))。其中，在選擇具有局部最大收益的輪數(shù)組合方案時，優(yōu)先考慮平臺的資源利用率。當(dāng)資源利用率大于給定閾值時，則空閑資源，直到前一作業(yè)執(zhí)行完成后，在剩余作業(yè)中選擇局部收益最大的作業(yè)進(jìn)行串行調(diào)度(line(11)-line(34))。在選擇局部收益最大的作業(yè)時，通過每個作業(yè)的截止時間與前一作業(yè)的完成時間差所在范圍，比較每個作業(yè)在該時間范圍內(nèi)可獲得的獎勵或懲罰值，選擇出使得局部收益最大的作業(yè)和相應(yīng)的任務(wù)輪數(shù)組合方案。當(dāng)資源利用率小于給定閾值時(line(35)-line(48))，將要調(diào)度的作業(yè)與前一作業(yè)并行執(zhí)行，充分利用平臺資源，使得資源利用率達(dá)到最大。在選擇合適的作業(yè)加入到調(diào)度隊(duì)列之前，記錄前一作業(yè)有空余資源時的開始時間點(diǎn)tr，tr與每個作業(yè)的最大標(biāo)準(zhǔn)時間tstandard進(jìn)行比較，當(dāng)剩余資源能夠滿足最大標(biāo)準(zhǔn)時間范圍內(nèi)的任務(wù)最大輪數(shù)要求時，則選擇 |f(j_profit)| 值最大的作業(yè)加入到調(diào)度隊(duì)列，對于懲罰值已經(jīng)達(dá)到最大的作業(yè)則放在調(diào)度隊(duì)列最后進(jìn)行調(diào)度。由于每個被選中的作業(yè)都有多種最大輪數(shù)組合方案，故在每選擇出一種調(diào)度組合方案后則計(jì)算相應(yīng)的局部收益值，最終選擇全局收益值最大的調(diào)度隊(duì)列與調(diào)度策略進(jìn)行調(diào)度。調(diào)度策略中包含了已選擇的作業(yè)任務(wù)輪數(shù)與開始時間點(diǎn)，在調(diào)度前就預(yù)先指定了對于每個作業(yè)中任務(wù)的資源分配數(shù)與分配時間點(diǎn)。

3 實(shí)驗(yàn)評估

3.1 實(shí)驗(yàn)環(huán)境與設(shè)置

在基于Hadoop框架的計(jì)算平臺中對本文提出的調(diào)度器進(jìn)行驗(yàn)證，使用的是Hadoop 2.7.1版本。平臺中的所有節(jié)點(diǎn)都是同構(gòu)節(jié)點(diǎn)，其中包含1個主節(jié)點(diǎn)和20個從節(jié)點(diǎn)。每個節(jié)點(diǎn)的配置信息為CPU 8 cores，16 GB RAM，1 TB hard disk, Red Hat Enterprise Linux6.2 System。資源管理和調(diào)度使用Yarn資源框架，設(shè)置Container大小為1 core和2G RAM，這樣每個節(jié)點(diǎn)上有8個Container，整個平臺中共有160個Container。在實(shí)驗(yàn)中設(shè)置塊大小為默認(rèn)的64 M。

3.2 實(shí)驗(yàn)數(shù)據(jù)集與實(shí)驗(yàn)指標(biāo)

為評估算法性能，使用PUMA benchmark suits中的MapReduce標(biāo)準(zhǔn)應(yīng)用程序，每類程序的數(shù)量、輸入數(shù)據(jù)規(guī)模、截止時間以及數(shù)據(jù)來源見表1。

表1 數(shù)據(jù)集

WordCount是CPU密集型程序，TeraSort是I/O密集型程序，Inverted-Index既是CPU密集型也是I/O密集型，3種程序均為典型的MapReduce程序。

在評估MPCRS的效率時，將MPCRS分別與FIFO、Fair、EDF調(diào)度算法在作業(yè)完成時間、服務(wù)商收益及平臺資源利用率等方面進(jìn)行比較。通過以下性能指標(biāo)評價算法的性能。

(1)作業(yè)完成時間：j_completion。

(2)最大收益：Profit。

(3)平臺資源利用率：Utilization。

根據(jù)作業(yè)的開始時間和執(zhí)行時間可以得出作業(yè)的完成時間，j_start是作業(yè)的開始執(zhí)行時間，j_execute是作業(yè)j的全部任務(wù)執(zhí)行完畢所經(jīng)歷的時間，默認(rèn)全部的作業(yè)都同時到達(dá)，作業(yè)的完成時間j_completion表示為

j_completion=j_start+j_execute

(7)

j_profit為在SLA協(xié)議中規(guī)定的截止時間之前完成作業(yè)j可獲得的收益，根據(jù)服務(wù)商可獲得的最大收益，用RP Model中獎懲共存收益函數(shù)f(j_profit)衡量

(8)

式(3)中所提到的α，β，γ分別為獎勵比率、懲罰比率以及最大懲罰倍數(shù)，設(shè)置α=0.3，β=0.5，γ=2，a，b分別為時間限定倍數(shù)，設(shè)置a=b=1.5。

定義平臺資源利用率Utilization時，使用作業(yè)完成后所占資源與時間的乘積和平臺中整體資源與時間的乘積比值表示

(9)

其中，Rtotal是平臺中全部資源數(shù)量，Ttotal是全部作業(yè)執(zhí)行完畢后的總時間，Rtaski是作業(yè)j中第i輪任務(wù)執(zhí)行所占用的資源數(shù)量，Ttaski是第i輪任務(wù)所需執(zhí)行時間。

3.3 實(shí)驗(yàn)結(jié)果與分析

3.3.1 作業(yè)執(zhí)行的高效性

如圖2所示，為4個調(diào)度器在全部作業(yè)的平均完成時間指標(biāo)上的對比結(jié)果。從圖中可以看出，F(xiàn)IFO調(diào)度器的作業(yè)平均完成時間達(dá)到了24.3 min，依次降低是EDF調(diào)度器22.3 min、Fair調(diào)度器20.8 min以及MPCRS 18 min。FIFO調(diào)度器的作業(yè)平均完成時間最長是由于當(dāng)一個作業(yè)正在執(zhí)行時會占用集群中的全部資源，不能使其它作業(yè)開始執(zhí)行，故這樣就會延長大部分作業(yè)的完成時間，導(dǎo)致全部作業(yè)的平均完成時間延長。MPCRS與FIFO、EDF以及Fair相比，作業(yè)的平均完成時間有所減短。

圖2 作業(yè)平均完成時間

如圖3所示，為每個作業(yè)在不同調(diào)度器的調(diào)度下執(zhí)行完畢后的完成時間對比結(jié)果。首先可以看出3個類型的作業(yè)隨著數(shù)據(jù)量的增大，作業(yè)完成時間在不斷變長；其次在數(shù)據(jù)量相同時，不同類型的作業(yè)完成時間差距很小，說明資源的統(tǒng)一分配對不同類型的作業(yè)性能不會造成影響；最后通過比較在4種調(diào)度器調(diào)度下的作業(yè)不同執(zhí)行性能可以看出，使用MPCRS時的作業(yè)完成時間明顯短于使用其它3種調(diào)度器時的時間，但Job9使用MPCRS時完成時間高于使用EDF和Fair的時間，這是由于在選擇Job9最大輪數(shù)執(zhí)行方案時，在最大標(biāo)準(zhǔn)時間范圍內(nèi)，所選的任務(wù)輪數(shù)最多，這樣會使得作業(yè)的整體完成時間較輪數(shù)較少時有所延長，而且TRN算法和MRNS算法在計(jì)算時具有一定的時間消耗，故在作業(yè)執(zhí)行過程中完成時間有一定延長是不可避免的。這個完成時間的延長范圍在可允許的范圍內(nèi)，是可以容忍的。

圖3 每個作業(yè)完成時間

3.3.2 收益最大化

根據(jù)上節(jié)作業(yè)執(zhí)行的高效性實(shí)驗(yàn)中可以得出每個作業(yè)的執(zhí)行性能，但本文設(shè)計(jì)MPCRS的最終目標(biāo)是使服務(wù)商獲取最大收益，故依據(jù)式(1)和式(3)，得到如圖4所示的使用不同調(diào)度器時的最大化收益。其中Ideal為總收益的理想值

圖4 服務(wù)商收益

(10)

從圖4中可以看出使用不同的調(diào)度器時，服務(wù)商可以獲得的最大收益差值較大。其中使用FIFO獲得的總收益與理想值Ideal差值最大，使用MPCRS可獲得的總收益與理想值Ideal差值最小。由于大部分作業(yè)的獎勵值仍為0和有部分延遲作業(yè)的存在，故使用MPCRS時服務(wù)商可獲得的總收益值與理想值仍有一定差距。

3.3.3 平臺資源利用率的高效性

圖5為在各個統(tǒng)計(jì)階段時，使用4個調(diào)度器時的平臺資源利用率。從圖中可以看出，使用FIFO時的平臺資源利用率最低，這是由于當(dāng)一個作業(yè)執(zhí)行時，浪費(fèi)了其它空閑資源。使用EDF時同樣不能充分利用平臺資源，使得大量空閑資源浪費(fèi)。使用Fair調(diào)度器時的資源利用率較高，但仍然沒有使用MPCRS時的資源利用率高。MPCRS中的MRNS算法考慮了平臺資源利用率的影響，故在各個統(tǒng)計(jì)階段中大部分的資源利用率都在90%以上，但在第5階段和第8階段資源利用率較低，這是在統(tǒng)計(jì)階段時作業(yè)執(zhí)行情況的影響。

圖5 平臺資源利用率

4 結(jié)束語

結(jié)合服務(wù)商與用戶之間的利益關(guān)系，本文提出一種RP Model作為服務(wù)商收益最大化的評價標(biāo)準(zhǔn)，并以該評價標(biāo)準(zhǔn)為目標(biāo)提出了MPCRS，其中具體包括TRN算法和MRNS算法。TRN算法以RP Model中的收益值為標(biāo)準(zhǔn)，根據(jù)各個作業(yè)的Map和Reduce任務(wù)執(zhí)行時間，確定出作業(yè)在不同獎懲階段的Map和Reduce的最大輪數(shù)組合以及最大標(biāo)準(zhǔn)時間；MRNS算法以TRN算法得出的結(jié)果為輸入，在滿足平臺資源利用率的前提下，選擇出具有局部最大收益的作業(yè)和該作業(yè)的任務(wù)最大輪數(shù)方案，從而制定出TS策略。實(shí)驗(yàn)結(jié)果表明，本文設(shè)計(jì)的作業(yè)調(diào)度器MPCRS所生成的TS策略能夠最大程度的縮短每個作業(yè)的完成時間，提高平臺資源利用率，并且在服務(wù)商獲得最大收益的同時，用戶能夠得到較為準(zhǔn)確的截止時間，真正意義上實(shí)現(xiàn)了服務(wù)商和用戶的利益共贏。