云環(huán)境下兩階段安全驅(qū)動(dòng)的容錯(cuò)調(diào)度算法

白晶晶，田生偉，禹 龍，于 炯，田國忠

（1.新疆大學(xué) 信息科學(xué)與程工學(xué)院，新疆 烏魯木齊830046；2.新疆大學(xué) 軟件學(xué)院，新疆 烏魯木齊830008；3.新疆大學(xué) 網(wǎng)絡(luò)中心，新疆 烏魯木齊830046；4.新疆工程學(xué)院 計(jì)算機(jī)工程系，新疆 烏魯木齊830000）

0 引 言

云計(jì)算具有動(dòng)態(tài)性、開放性和共享性等特點(diǎn)，這使云環(huán)境下的任務(wù)調(diào)度面臨新的安全挑戰(zhàn)［1］。在任務(wù)調(diào)度過程中，云供應(yīng)商除了滿足用戶基本的時(shí)間和費(fèi)用需求外，還應(yīng)保障用戶數(shù)據(jù)和隱私不被泄露、竊取和篡改［2］；此外，云資源往往表現(xiàn)出一定的失效性和波動(dòng)性［3］，因此可靠性成為任務(wù)調(diào)度的另一重要需求。針對安全可靠性調(diào)度，許多研究者提出了新的安全技術(shù)架構(gòu)和調(diào)度策略［2－4］。蔣從峰等通過改進(jìn)備份策略和調(diào)度算法，提高了任務(wù)調(diào)度成功率。但實(shí)際的云計(jì)算是處在異構(gòu)環(huán)境下，其任務(wù)之間具有依賴關(guān)系，這些算法僅適用于相互獨(dú)立的任務(wù)調(diào)度，存在一定的局限性［5，6］。

為了解決該問題，不少學(xué)者以具有依賴關(guān)系的任務(wù)為基礎(chǔ)，將安全驅(qū)動(dòng)模型與任務(wù)調(diào)度相結(jié)合，優(yōu)化了調(diào)度長度和安全滿意度，但忽略了用戶的可靠性需求，未能實(shí)現(xiàn)容錯(cuò)調(diào)度［7，8］；Qin Xiao等通過改進(jìn)通信模型或主／副本策略，實(shí)現(xiàn)了容錯(cuò)調(diào)度，并縮短了調(diào)度長度，但這些方法主要針對任務(wù)調(diào)度的可靠性，未對處理機(jī)進(jìn)行安全篩選，且同一時(shí)刻僅支持一個(gè)處理機(jī)失效，使容錯(cuò)存在一定的局限性［9－12］。

針對已有算法的局限性，本文以現(xiàn)有工作為基礎(chǔ)，提出了云環(huán)境下綜合考慮安全性和可靠性的調(diào)度算法。改進(jìn)了備份方式，并使用隊(duì)列策略擴(kuò)大了容錯(cuò)范圍，支持多處理機(jī)同時(shí)失效，使算法更具有應(yīng)用性。優(yōu)化了任務(wù)調(diào)度的安全性和可靠性。

1 容錯(cuò)調(diào)度模型

云環(huán)境下的異構(gòu)系統(tǒng)具有較高的復(fù)雜性，且任務(wù)調(diào)度是一個(gè)NP問題，為了集中討論所關(guān)心的中心問題，我們設(shè)定以下前提約束［13］：首先，系統(tǒng)中任意處理機(jī)均可能失效，失效可在任意時(shí)間點(diǎn)發(fā)生；其次，每個(gè)任務(wù)在執(zhí)行期間僅遇到一次處理機(jī)失效。

1.1 任務(wù)模型

云計(jì)算是異構(gòu)分布式系統(tǒng)的體現(xiàn)，任務(wù)之間具有依賴關(guān)系。一般選擇有向無環(huán)圖DAG （directed acyclic graph）對并行任務(wù)進(jìn)行描述。

定義1 用一個(gè)二元組G＝ （V，E）表示DAG，其中V＝ ｛v1，v2，…，vN｝表示任務(wù)的集合，N 表示任務(wù)總數(shù)；E＝ ｛eij｜eij＝＜vi，vj＞，vi，vj∈V｝為有向邊的集合，eij表示vi和vj間具有依賴關(guān)系，vj為vi的后繼，vj只有在vi完成后才能執(zhí)行；w（vi）表示vi的計(jì)算開銷，w（eij）表示vi和vj間的通信開銷，如果vi和vj在同一個(gè)處理機(jī)上，w（eij）的值為0。圖1 為任務(wù)DAG 的一個(gè)實(shí)例。

圖1 任務(wù)

定義2 異構(gòu)系統(tǒng)中包含一組處理機(jī)，這些處理機(jī)通過網(wǎng)絡(luò)連接在一起，網(wǎng)絡(luò)具有全連通性［7］。P＝ ｛p1，p2，…，pM｝表示處理機(jī)的集合，M 為處理機(jī)的總數(shù)；wij表示任意2個(gè)處理機(jī)pi和pj之間的通信開銷。圖2為處理機(jī)的一個(gè)實(shí)例。

圖2 處理機(jī)

1.2 安全模型

為了提高調(diào)度的安全性，模型中每個(gè)任務(wù)提供一個(gè)安全需求 （security demand，SD），每個(gè)處理機(jī)有一個(gè)信任等級 （trust level，TL）。處理機(jī)可以提供的安全服務(wù)共3種，分別為真實(shí)性、完整性和保密性［11］。

為了更具體地分析資源的安全水平，評估任務(wù)調(diào)度的風(fēng)險(xiǎn)性，我們對任務(wù)調(diào)度的風(fēng)險(xiǎn)率做出以下量化處理

2 調(diào)度算法

2.1 任務(wù)分配預(yù)備階段

2.1.1 任務(wù)調(diào)度優(yōu)先級

本文在經(jīng)典算法HEFT （heterogeneous earliest－finishtime）［7］的基礎(chǔ)上，考慮各種安全措施帶來的時(shí)間開銷，計(jì)算出任務(wù)的優(yōu)先級［7］。SRank＝ ｛SRank（vi）｜vi∈V｝，SRank（vi）表示任務(wù)vi的優(yōu)先級，根據(jù)優(yōu)先級大小對任務(wù)進(jìn)行排序，得到任務(wù)的調(diào)度序列，用SL （scheduling list）表示

在式 （3）和式 （4）中，vexit表示出口任務(wù)；w（eix）表示邊eix的通信開銷，w（vi）表示vi的計(jì)算開銷；succ（vi）是vi后繼的集合，SRank（vI，pj）表示vi在pj上的優(yōu)先級；uj表示pj的執(zhí)行速度，Cij表示vi在pj上的安全開銷。從出口任務(wù)開始，遞歸計(jì)算出每個(gè)任務(wù)的優(yōu)先級。

2.1.2 處理機(jī)篩選及備份預(yù)處理

在1.2小節(jié)可得出任務(wù)在處理機(jī)上的調(diào)度風(fēng)險(xiǎn)率Pr（vi，pj）（vI∈V，pj∈P），為了對處理機(jī)進(jìn)行定量篩選，我們設(shè)定了風(fēng)險(xiǎn)率閾值，用γ表示。選擇滿足條件Pr（vi，pj）＜γ的處理機(jī)作為vi的候選處理機(jī)。SP（vi）＝ ｛pj｜vi∈V，Pr（vi，pj）＜γ｝表示符合條件的處理機(jī)集合。若｜SP（vi）｜＝0，則用戶降低安全需求等級，使｜SP（vi）｜＞0；當(dāng)｜SP（vi）｜＞4時(shí)，選取Pr（vi，pj）值最大的4 個(gè)處理機(jī)，最終的候選處理機(jī)集合用SP’（vi）表示。

采用自適應(yīng)備份方式，確定任務(wù)備份數(shù)目，為正式調(diào)度做準(zhǔn)備。每個(gè)任務(wù)有一個(gè)主本和若干個(gè)副本，replica（vi）表示任務(wù)vi的副本數(shù)。如式 （5）所示，根據(jù)處理機(jī)的篩選結(jié)果確定replica（vi）的值，為了使備份數(shù)在一個(gè)合理的范圍內(nèi)，replica （vi）的上限為3［5］

2.2 任務(wù)調(diào)度階段

2.2.1 隊(duì)列策略

在任務(wù)正式調(diào)度階段，由于已對處理機(jī)進(jìn)行了篩選，只需計(jì)算任務(wù)在候選處理機(jī)上的est和eft，從而減少計(jì)算開銷，降低了冗余度。EST（vi）＝ ｛est（vi，pj）｜pj∈SP’（vi），vi∈V｝，EFT（vi）＝ ｛eft（vi，pj）｜pj∈SP’（vi），vi∈V｝，其中est（vi，pj）和eft（vi，pj）分別表示任務(wù)vi在pj上的最早開始時(shí)間和最早完成時(shí)間，pj是vi的候選處理機(jī)。將EFT（vi）中的元素按其值的大小非降序排列，得到序列EFT（vi）asce和對應(yīng)的處理機(jī)序列SP’（vi）asce。

在上一階段已得到任務(wù)備份的數(shù)量，本階段將以此為基礎(chǔ)，對任務(wù)的主／副本進(jìn)行正式分配。參考田冠華等［3］的隊(duì)列理念，系統(tǒng)中每個(gè)處理機(jī)均維護(hù)2個(gè)局部隊(duì)列，和分別代表pj的主本隊(duì)列和副本隊(duì)列。若pj處于SP（vi）’asce的首位，則進(jìn)入；否則，進(jìn)入。每個(gè)任務(wù)的主／副本在相應(yīng)隊(duì)列中的位置與SL 中的位置保持一致。

2.2.2 調(diào)度原則

任務(wù)調(diào)度中，處理機(jī)上可能會出現(xiàn)空閑時(shí)間槽 （idle time slot，ITS），這里我們將時(shí)間長度不足的空閑時(shí)間段稱為任務(wù)的非完整空閑時(shí)間槽 （形成空閑時(shí)間槽所需的其他條件均滿足），用INITS （incomplete idle time slot）表示。

本文采用被動(dòng)副本方式，當(dāng)且僅當(dāng)主本執(zhí)行失敗時(shí)才啟動(dòng)副本的執(zhí)行［4］。每個(gè)任務(wù)的主本以經(jīng)典算法HEFT 的調(diào)度方式執(zhí)行，當(dāng)出現(xiàn)處理機(jī)失效導(dǎo)致任務(wù)主本調(diào)度失敗時(shí)，副本的執(zhí)行遵循以下調(diào)度原則 （the principles of backup－copy scheduling，PBS）：①優(yōu)先選擇ITS，當(dāng)存在多個(gè)ITS時(shí)，選擇使任務(wù)的eft最小的方案；②當(dāng)不存在ITS時(shí)，優(yōu)先選擇INITS，若存在多個(gè)INITS，選擇造成其他任務(wù)延遲時(shí)間最小的方案；③根據(jù)以上原則得出執(zhí)行方案后，均需與調(diào)度到處理機(jī)末尾的副本 （若存在這樣的副本）作對比，選擇eft最小的方案執(zhí)行；④同時(shí)有多個(gè)任務(wù)執(zhí)行失敗，且失敗任務(wù)的副本出現(xiàn)競爭時(shí)，競爭副本的執(zhí)行順序參照所在副本隊(duì)列的順序。

在蒸汽保護(hù)熱處理的情況下，毛白楊不一樣的熱處理時(shí)間得到了不一樣的粗糙度數(shù)據(jù)和圖片，結(jié)合圖7可知，在微觀形貌上，將未處理材與熱處理2 h、4 h比較，發(fā)現(xiàn)隨熱處理時(shí)間增加，樣品表面大而深的溝槽及表面木毛明顯減少，起伏狀況明顯減弱，同時(shí)附著物逐漸減少，其間的間隙、孔洞也逐漸變小，樣品表面趨于光滑平整。但1 h樣品因?yàn)槎虝r(shí)間的熱處理，導(dǎo)致其表面出現(xiàn)了較明顯的開裂，故其表面比未處理樣品還要粗糙。

為了更清楚地說明以上調(diào)度原則，下面從一般情況到特殊情況對副本調(diào)度原則進(jìn)行實(shí)例性解釋說明。

情況3：如圖3 （c）所示，在tfail時(shí)刻p1和p2同時(shí)失效，和執(zhí)行失敗。vi有一個(gè)副本，vj有2 個(gè)副本。（2）∈。在p3上，和間存在INITS，此時(shí)和（1）間存在競爭。由于在中，的優(yōu)先級較高，故選擇的執(zhí)行方案為：從t0時(shí)刻在p3上依次執(zhí)行和，造成延遲時(shí)間△tjl，。此外，若（2）在p4末尾執(zhí)行，。由于t1＜t2，故選擇的最終方案為：在p3上依次執(zhí)行和（1）。

圖3 副本調(diào)度原則情況舉例

2.3 算法流程

下面給出算法的基本流程：

（1）～ （2）步是計(jì)算任務(wù)調(diào)度優(yōu)先級，并根據(jù)優(yōu)先級對任務(wù)進(jìn)行排序； （4）～ （10）步是計(jì)算調(diào)度風(fēng)險(xiǎn)率，對處理機(jī)進(jìn)行篩選；（11）步是根據(jù)篩選結(jié)果最終確定候選處理機(jī)，計(jì)算出備份數(shù)目； （12）～ （16）步是任務(wù)正式備份，主／副本進(jìn)入相應(yīng)的隊(duì)列； （17）～ （25）步是根據(jù)調(diào)度原則對任務(wù)進(jìn)行正式調(diào)度，同時(shí)實(shí)現(xiàn)容錯(cuò)。

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

為了驗(yàn)證算法TSDFT （two－stage security－driven and fault tolerant scheduling algorithm）的有效性，我們設(shè)計(jì)了一組實(shí)驗(yàn)，從風(fēng)險(xiǎn)率、可調(diào)度性和可靠性3個(gè)方面對算法進(jìn)行評估。使用matlab作為仿真實(shí)驗(yàn)環(huán)境，由于云環(huán)境下系統(tǒng)具有異構(gòu)性，實(shí)驗(yàn)中所有DAG 和資源圖隨機(jī)生成，使用不同參數(shù)得到不同的DAG 和資源圖。任務(wù)總數(shù)N ∈｛20，40，60，80，100｝，處理機(jī)總數(shù)M ∈ ｛8，16，32，64｝；任務(wù)的計(jì)算開銷在 ［5，50］內(nèi)均勻分布。

3.1 實(shí)驗(yàn)1：風(fēng)險(xiǎn)率測試與分析

本次實(shí)驗(yàn)在通信／計(jì)算比率 （communication to computational ratio，CCR）不同的情況下，對比TSDFT、HEFT和SDS （security－driven list scheduling algorithm）［7］3 種算法的任務(wù)調(diào)度風(fēng)險(xiǎn)率。CCR ∈ ｛0.1，0.4，0.8，1.0，2.0｝，風(fēng)險(xiǎn)率閾值γ取0.3。隨機(jī)生成100 個(gè)DAG，每個(gè)CCR值下，實(shí)驗(yàn)進(jìn)行100次，結(jié)果取平均值。實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 風(fēng)險(xiǎn)率對比結(jié)果

算法eFRD （efficient fault－tolerant reliability cost driven algorithm）［12］和FMCED （fault－tolerant maximum communication efficiency－driven algorithm）［13］實(shí)現(xiàn)了容錯(cuò)調(diào)度，但未考慮對資源的安全篩選，且備份方式固定。為了驗(yàn)證本文在改進(jìn)以上2種算法后的有效性，我們進(jìn)行了實(shí)驗(yàn)2和實(shí)驗(yàn)3。實(shí)驗(yàn)中，處理機(jī)失效率服從泊松分布，設(shè)定其范圍在MINR 和MAXR 之間，MINR 取1.0×10－6／h，MAXR∈［3.5×10－6／h，7.5×10－6／h］［13］。

3.2 實(shí)驗(yàn)2：可調(diào)度性測試與分析

成功執(zhí)行的任務(wù)占所有提交的任務(wù)的百分比稱為可調(diào)度性，它反映了算法尋找可行方案的能力［13］。實(shí)驗(yàn)2在不同的任務(wù)數(shù)目下，對比算法eFRD、FMCED 和TSDFT 的可調(diào)度性。實(shí)驗(yàn)結(jié)果如圖5所示。

圖5 可調(diào)性對度比結(jié)果

從圖5中可以看出，當(dāng)任務(wù)數(shù)目在40以內(nèi)時(shí)，3種算法的性能比較接近；隨著任務(wù)數(shù)目的增加，TSDFT 可調(diào)度性優(yōu)于eFRD 和FMCED。主要原因是，隨著提交的任務(wù)數(shù)的增加，調(diào)度規(guī)模不斷擴(kuò)大，在調(diào)度過程中失效任務(wù)數(shù)目也相應(yīng)增加，致使可調(diào)度性出現(xiàn)一定的波動(dòng)；而算法TSDFT 的容錯(cuò)調(diào)度建立在資源安全篩選的基礎(chǔ)上，當(dāng)任務(wù)執(zhí)行失敗時(shí)，其副本所在處理機(jī)安全等級較高，調(diào)度成功率增加，從而減小了失敗任務(wù)在提交任務(wù)中的比例。

3.3 實(shí)驗(yàn)3：可靠性測試與分析

可靠性反映了算法的容錯(cuò)能力［13］，本次實(shí)驗(yàn)在處理機(jī)失效率不同的情況下，對比任務(wù)調(diào)度的可靠性。實(shí)驗(yàn)結(jié)果如圖6所示。

圖6 可靠性對比結(jié)果

從圖6中可以看出，隨著處理機(jī)失效率的增加，3種算法的可靠性均有小幅波動(dòng)，整體呈下降趨勢。處理機(jī)失效率相同的情況下，TSDFT 的可靠性較高，并且隨著處理機(jī)失效率增大，這種優(yōu)勢更加明顯。主要原因是，當(dāng)處理機(jī)失效率增大時(shí)，單位時(shí)間內(nèi)失效處理機(jī)次數(shù)增多，執(zhí)行失敗的任務(wù)數(shù)量也隨之增加。在失效率較高時(shí)，可能出現(xiàn)一個(gè)以上處理機(jī)同時(shí)失效的情況。算法TSDFT 對處理機(jī)進(jìn)行安全篩選，且使用隊(duì)列策略解決了多處理機(jī)同時(shí)失效的問題，容錯(cuò)能力更強(qiáng)，提高了調(diào)度的可靠性。

4 結(jié)束語

通過分析云計(jì)算環(huán)境下任務(wù)調(diào)度的安全和可靠性需求，提出了一種兩階段安全驅(qū)動(dòng)的容錯(cuò)調(diào)度算法。該算法同時(shí)實(shí)現(xiàn)了資源安全篩選和任務(wù)的容錯(cuò)調(diào)度，改進(jìn)了備份方式并擴(kuò)大了容錯(cuò)范圍。實(shí)驗(yàn)結(jié)果表明算法降低了任務(wù)調(diào)度的風(fēng)險(xiǎn)率，提高了任務(wù)調(diào)度的安全性和可靠性，使算法適合于云計(jì)算環(huán)境下異構(gòu)系統(tǒng)中具有依賴關(guān)系任務(wù)的調(diào)度。下一步的研究工作主要是進(jìn)一步完善容錯(cuò)調(diào)度模型，考慮任務(wù)2次執(zhí)行失敗的情況，進(jìn)一步擴(kuò)大容錯(cuò)范圍。

［1］FENG Dengguo，ZHANG Min，ZHANG Yan，et al.Study on cloud computing security ［J］.Journal of Computing Applications，2011，22 （1）：71－83（in Chinese）.［馮登國，張敏，張妍，等.云計(jì)算安全研究［J］.軟件學(xué)報(bào)，2011，22 （1）：71－83.］

［2］Dimitrios Z，Dimitrios L.Addressing cloud computing security issues［J］.Future Generation Computer Systems，2012，28（3）：583－592.

［3］TIAN Guanhua，MENG Dan，ZHAN Jianfeng.Reliable resource provision policy for cloud computing［J］.Chinese Journal of Computers，2010，33 （10）：1859－1872 （in Chinese）. ［田冠華，孟丹，詹劍鋒.云計(jì)算環(huán)境下基于失效規(guī)則的資源動(dòng)態(tài)提供策略［J］.計(jì)算機(jī)學(xué)報(bào)，2010，33 （10）：1859－1872.］

［4］ZHANG Shuiping，LI Jizhen，ZHANG Fengqin，et al.Research and implementation of data center security system based on cloud computing ［J］.Computer Engineering and Design，2011，32 （12）：3965－3968 （in Chinese）. ［張水平，李紀(jì)真，張風(fēng)琴，等.基于云計(jì)算的數(shù)據(jù)中心安全體系研究與實(shí)現(xiàn)［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2011，32 （12）：3965－3968.］

［5］JIANG Congfeng，WANG Cheng，LIU Xiaohu.Fault tolerant grid job scheduling based on dynamic replication ［J］.Application Research of Computers，2008，25 （3）：738－743 （in Chinese）.［蔣從峰，王乘，劉小虎.基于動(dòng)態(tài)備份的容錯(cuò)網(wǎng)格任務(wù)調(diào)度 ［J］.計(jì)算機(jī)應(yīng)用研究，2008，25 （3）：738－743.］

［6］LUO Wei，YANG Fumin，PANG Liping，et al.A real time fault－tolerant scheduling algorithm of periodic tasks in heterogeneous distributed systems［J］.Chinese Journal of Computers，2007，30 （10）：1741－1749 （in Chinese）.［羅威，陽富民，龐麗萍，等.異構(gòu)分布式系統(tǒng)中實(shí)時(shí)周期任務(wù)的容錯(cuò)調(diào)度算法［J］.計(jì)算機(jī)學(xué)報(bào)，2007，30 （10）：1741－1749.］

［7］TANG XY，LI K，ZENG Z，et al.A novel security－driven scheduling algorithm for precedence－constrained tasks in heterogeneous distributed systems ［J］.IEEE Transaction on Computers，2011，60 （7）：1017－1029.

［8］ZHU Hai，WANF Yuping.Integration of security grid dependent tasks scheduling double－objective optimization model and algorithm ［J］.Journal of Software，2011，22 （11）：2729－2748 （in Chinese）.［朱海，王宇平.融合安全的網(wǎng)格依賴任務(wù)調(diào)度雙目標(biāo)優(yōu)化模型及算法 ［J］.軟件學(xué)報(bào)，2011，22（11）：2729－2748.］

［9］ZHENG Q，Veeravalli B.On the design of communicationaware fault－tolerant scheduling algorithms for precedence constrained tasks in grid computing systems with dedicated communication devices［J］.Journal of Parallel and Distributed Computing，2009，69 （3）：282－294.

［10］Benoit A，Hakem M，Robet Y.Contention awareness and fault－tolerant scheduling for precedence constrained tasks in heteroge－neous systems ［J］.Parallel Computing，2009，35（2）：83－108.

［11］QIN X，JIANG H.A novel fault－tolerant scheduling algorithm for precedence constrained tasks in real time heterogeneous system［J］.Parallel Computing，2006，32 （5－6）：331－356.

［12］TANG XY，Li K，Li RF，et al.Reliability－aware scheduling strategy for heterogeneous distributed computing systems［J］.Journal of Parallel and Distributed Computing，2010，70 （9）：941－952.

［13］LING Y，LUO ZS，GE YJ.Fault－tolerant scheduling algorithm for precedence constrained tasks in grid computing systems with communication efficiency ［C］／／Proceeding of the 3rd International Conference on Information Sciences and Interaction Sciences.Chengdu，China：IEEE，2010：205－210.