基于任務(wù)截止時(shí)間的多級(jí)密碼服務(wù)調(diào)度方案*

王 瑛，張 芳，裴 升，李海波，周 波，劉坤禹

（中國(guó)電子科技集團(tuán)公司第三十研究所，四川 成都 610041）

0 引言

密碼技術(shù)是云應(yīng)用、云數(shù)據(jù)和云虛擬化設(shè)備的安全基礎(chǔ)之一。傳統(tǒng)密碼技術(shù)受限于擴(kuò)展性差的密碼服務(wù)載體，無(wú)法滿足云環(huán)境下用戶對(duì)數(shù)據(jù)存儲(chǔ)、計(jì)算和傳輸?shù)陌踩雷o(hù)要求。云環(huán)境下的密碼服務(wù)是當(dāng)前云安全解決方案的主流模式，而當(dāng)前基于云計(jì)算的密碼服務(wù)具有請(qǐng)求多樣、算法多樣的任務(wù)多樣性。不同的服務(wù)應(yīng)用根據(jù)自身的安全需求，可以選擇自身需要的不同強(qiáng)度的密碼服務(wù)。一種合理的調(diào)度方案是解決密碼資源安全、合理、快速分配的關(guān)鍵。

當(dāng)前，云資源調(diào)度策略已經(jīng)從簡(jiǎn)單的單目標(biāo)調(diào)度策略逐步演變?yōu)榭深A(yù)測(cè)的、多目標(biāo)的、智能化的復(fù)雜調(diào)度策略。除需要考慮CPU、內(nèi)存、存儲(chǔ)等資源外，云環(huán)境下的密碼服務(wù)需要考慮新引入的密碼計(jì)算資源。不僅要實(shí)現(xiàn)密碼服務(wù)平臺(tái)的負(fù)載均衡和密碼服務(wù)質(zhì)量等目標(biāo)，還要考慮密碼計(jì)算資源利用率和密碼設(shè)備的安全要求等對(duì)密碼服務(wù)云性能的影響。如何針對(duì)不同的密碼服務(wù)實(shí)現(xiàn)所請(qǐng)求的密碼服務(wù)的快速完成，并完成多個(gè)虛擬密碼機(jī)之間的合理調(diào)度，是實(shí)現(xiàn)資源利用率最優(yōu)化的關(guān)鍵。

針對(duì)上述問(wèn)題，本文提出基于任務(wù)截止時(shí)間的多級(jí)密碼服務(wù)調(diào)度技術(shù)，將任務(wù)截止時(shí)間轉(zhuǎn)化為任務(wù)緊迫度，以衡量任務(wù)的完成優(yōu)先級(jí)。通過(guò)不同等級(jí)的調(diào)度，完成任務(wù)請(qǐng)求和虛擬密碼機(jī)之間的映射，從而滿足不同應(yīng)用系統(tǒng)的差異化需求，整體提升云環(huán)境下的密碼服務(wù)性能。

1 任務(wù)調(diào)度相關(guān)研究

1.1 國(guó)內(nèi)外相關(guān)研究

任務(wù)調(diào)度是指在特定時(shí)間將某些任務(wù)分配給特定的資源，是云計(jì)算中的一個(gè)重要問(wèn)題。如何使用一種合理的調(diào)度機(jī)制，是提高性能和資源有效利用率的關(guān)鍵。目前，國(guó)內(nèi)外學(xué)者研究了很多不同類型的調(diào)用機(jī)制，如云服務(wù)調(diào)度、啟發(fā)式調(diào)度、工作流調(diào)度、靜態(tài)調(diào)度和動(dòng)態(tài)調(diào)度。在云計(jì)算中，資源的內(nèi)部和外部需求都要維護(hù)，同時(shí)帶寬、存儲(chǔ)、資源開(kāi)銷和響應(yīng)時(shí)間等需求可能因每個(gè)任務(wù)的不同而不同。負(fù)載均衡、可伸縮性、可靠性、性能以及對(duì)計(jì)算節(jié)點(diǎn)的資源動(dòng)態(tài)重新分配，是任務(wù)調(diào)度的主要問(wèn)題。所以，在云計(jì)算中需要一個(gè)有效的任務(wù)調(diào)度算法。

根據(jù)最近的研究綜述，基于粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）的任務(wù)調(diào)度和基于遺傳算法（Genetic Algorithm，GA）的任務(wù)調(diào)度是研究熱點(diǎn)。

PSO算法適用于動(dòng)態(tài)任務(wù)調(diào)度。文獻(xiàn)[1]提供了一個(gè)基于粒子群優(yōu)化算法的啟發(fā)式調(diào)度方法，用于減少總執(zhí)行開(kāi)銷。該文獻(xiàn)對(duì)比了PSO和最佳資源選擇（Best Resource Selection，BRS）算法，結(jié)論是PSO有提升，節(jié)省了3倍的成本，同時(shí)增強(qiáng)了現(xiàn)有資源的工作分布，但是導(dǎo)致了更高的傳輸和存儲(chǔ)開(kāi)銷。文獻(xiàn)[2]簡(jiǎn)要提到了資源配置危機(jī)，通過(guò)設(shè)計(jì)一種PSO算法解決這一危機(jī)。該理論基于任務(wù)總執(zhí)行時(shí)間、資源保留和每個(gè)任務(wù)的QoS，研究了多目標(biāo)資源優(yōu)化問(wèn)題中的最優(yōu)調(diào)度方法。然而，該成果只能夠用于簡(jiǎn)單任務(wù)，沒(méi)有適用于任務(wù)調(diào)度問(wèn)題的一般收斂理論。

文獻(xiàn)[3]采用最小-最?。∕in-Min）和最大-最小（Max-Min）方法，結(jié)合標(biāo)準(zhǔn)遺傳算法，提出了一種增強(qiáng)遺傳算法。Min-Min算法是一種最小執(zhí)行時(shí)間算法，將任務(wù)盡量分配至運(yùn)算能力最強(qiáng)的資源節(jié)點(diǎn)上，減少任務(wù)執(zhí)行時(shí)間，但會(huì)導(dǎo)致負(fù)載不均衡，使得能力較強(qiáng)的節(jié)點(diǎn)產(chǎn)生極高的占用率，而其他節(jié)點(diǎn)出現(xiàn)較小的利用率。Max-Min算法是將可執(zhí)行任務(wù)時(shí)間最早的節(jié)點(diǎn)分配給需要最大資源的任務(wù)，然后更新節(jié)點(diǎn)的可用時(shí)間和剩余任務(wù)集，直到全部任務(wù)調(diào)用完畢。文獻(xiàn)[4]闡述了如何使用遺傳算法進(jìn)行任務(wù)調(diào)度。文獻(xiàn)[5]解釋了云服務(wù)工作流調(diào)度和使用分層云服務(wù)工作流的優(yōu)化方案，包括云工作流任務(wù)并行以及分割、語(yǔ)法和語(yǔ)義的云工作流任務(wù)匹配算法以及基于多個(gè)QoS約束的云工作流調(diào)度和優(yōu)化，并對(duì)該算法的性能進(jìn)行了實(shí)驗(yàn)分析。文獻(xiàn)[6]解釋了一種用于云環(huán)境中使用優(yōu)先隊(duì)列進(jìn)行任務(wù)調(diào)度的改進(jìn)遺傳算法。當(dāng)前的文獻(xiàn)大多是基于一般的云服務(wù)任務(wù)調(diào)度，但是針對(duì)密碼服務(wù)的任務(wù)調(diào)度沒(méi)有很好的解決方案。針對(duì)該問(wèn)題，本文提出了一種基于任務(wù)截止時(shí)間的多級(jí)密碼服務(wù)調(diào)度方案。

1.2 密碼服務(wù)的任務(wù)調(diào)度目標(biāo)

虛擬機(jī)調(diào)度策略在不同的目標(biāo)之間往往是相互沖突的[7]。

（1）以提高資源利用率為目標(biāo)的調(diào)度策略需要在減少活躍虛擬機(jī)的情況下，將云資源充分地分配到各個(gè)虛擬機(jī)，而這將導(dǎo)致在突發(fā)性負(fù)載條件下云服務(wù)質(zhì)量的降低，影響用戶體驗(yàn)。

（2）以服務(wù)質(zhì)量為目標(biāo)的調(diào)度策略往往會(huì)預(yù)留部分資源用于處理突發(fā)任務(wù)，保證服務(wù)質(zhì)量，但是易造成資源閑置。

（3）以降低能耗為目標(biāo)的調(diào)度策略通常通過(guò)減少活躍虛擬機(jī)來(lái)降低數(shù)據(jù)中心的能耗，以低成本完成高負(fù)載，但同樣會(huì)導(dǎo)致突發(fā)性負(fù)載條件下的宕機(jī)情況；

（4）以負(fù)載均衡為目標(biāo)的調(diào)度策略需要開(kāi)啟更多的虛擬機(jī)，將系統(tǒng)負(fù)載均衡地分配到各個(gè)云主機(jī)，既增加了能耗，又不能充分利用云資源。

關(guān)于虛擬機(jī)調(diào)度的研究，大部分方法都是在特定的研究情境中滿足主要目標(biāo)，同時(shí)兼顧其他次要目標(biāo)。本文主要針對(duì)云環(huán)境中的密碼服務(wù)，與傳統(tǒng)任務(wù)相比，密碼服務(wù)的任務(wù)與虛擬資源屬性之間、任務(wù)與用戶的身份之間，存在很強(qiáng)的依賴型。即使是使用相同的密碼服務(wù)，由于用戶需求不同，任務(wù)所使用的密碼算法可能不相同，導(dǎo)致不同的密碼算法對(duì)云計(jì)算中的資源調(diào)度和需求都不同。密碼服務(wù)對(duì)任務(wù)調(diào)度的時(shí)效性、安全性要求更高，各種密碼算法的復(fù)雜度也更高。針對(duì)上述問(wèn)題，本文在傳統(tǒng)任務(wù)調(diào)度算法的基礎(chǔ)上提出了一種基于任務(wù)截止時(shí)間的多級(jí)密碼服務(wù)調(diào)度策略。

2 基于多級(jí)密碼服務(wù)的任務(wù)調(diào)度方案

2.1 任務(wù)調(diào)度模型

任務(wù)調(diào)度模型如圖1所示。本文提供的任務(wù)分析和任務(wù)調(diào)度中的密碼處理分別由多個(gè)虛擬密碼機(jī)完成。這里的任務(wù)主要是指一次完整的密碼協(xié)議處理，如完成一次數(shù)據(jù)包的加密即為一個(gè)任務(wù)。

圖1 任務(wù)調(diào)度模型

（1）任務(wù)集合T={T1,T2,…,Tn}，表示參與任務(wù)調(diào)度的任務(wù)集合，其中下標(biāo)為i=(1,2,…,n)，表示第i個(gè)任務(wù)。

（2）虛擬密碼機(jī)集合V={V1,V2,…,Vm}，其中下標(biāo)為j=(1,2,…,m)，表示不同等級(jí)的虛擬密碼機(jī)。根據(jù)密碼的性能不同，可將其劃分為不同等級(jí)的虛擬密碼機(jī)群。

（3）FTij=ETij+TSj，其中FTij表示第i個(gè)任務(wù)在第j個(gè)虛擬密碼機(jī)的完成時(shí)間，F(xiàn)Tij表示第i個(gè)任務(wù)在第j個(gè)虛擬密碼機(jī)的執(zhí)行時(shí)間，TSj表示虛擬密碼機(jī)的最早可用時(shí)間。

第i個(gè)密碼服務(wù)形式化描述如下：

式中：Tid表示任務(wù)的標(biāo)識(shí)；Tlen表示任務(wù)的大小長(zhǎng)度；Ttype標(biāo)識(shí)密碼服務(wù)的類型，不同的密碼服務(wù)所需的資源不同；Tdl表示該任務(wù)的截止時(shí)間。

第j個(gè)虛擬密碼機(jī)形式化描述如下：

式中：Vid表示虛擬密碼機(jī)的標(biāo)識(shí)；Vsp表示虛擬密碼機(jī)的處理速率；Vfc表示該虛擬密碼機(jī)能夠?qū)崿F(xiàn)的密碼功能；Vexc表示任務(wù)執(zhí)行時(shí)間，Vmin表示最小可執(zhí)行任務(wù)時(shí)間，若當(dāng)前節(jié)點(diǎn)有k個(gè)任務(wù)正在執(zhí)行，則

虛擬密碼機(jī)的多元組屬性由任務(wù)調(diào)度模塊維護(hù)并更新。任務(wù)執(zhí)行過(guò)程中對(duì)每個(gè)虛擬密碼機(jī)的當(dāng)前狀態(tài)進(jìn)行實(shí)時(shí)監(jiān)控，以提高任務(wù)的調(diào)度效率和任務(wù)處理的實(shí)時(shí)性。

2.2 基于任務(wù)截止時(shí)間的任務(wù)調(diào)度方案

本文方案以任務(wù)截止時(shí)間為主目標(biāo)，在此本文設(shè)置一個(gè)任務(wù)緊迫度，即：

它表示任務(wù)截止時(shí)間減去任務(wù)完成時(shí)間的值。這個(gè)值越小，表示任務(wù)越緊迫。當(dāng)DTmin=0時(shí)，代表任務(wù)截止時(shí)間與完成時(shí)間相等；DTmin<0，則表示任務(wù)無(wú)法在截止時(shí)間內(nèi)完成，則任務(wù)執(zhí)行失敗。當(dāng)兩個(gè)任務(wù)的緊迫度相同時(shí)，選擇任務(wù)標(biāo)識(shí)值更小的優(yōu)先執(zhí)行。

根據(jù)不同的密碼服務(wù)需要的資源和任務(wù)緊迫度，將任務(wù)分為4類不同的密碼服務(wù)類型。

（1）Ttype=1表示該服務(wù)需要最多的密碼計(jì)算資源，任務(wù)緊迫度最高的任務(wù)（DTmin<1），如非對(duì)稱加解密服務(wù)等；

（2）Ttype=2表示該服務(wù)需要較多的密碼計(jì)算資源，任務(wù)緊迫度第二的任務(wù)（1

（3）Ttype=3表示該服務(wù)需要較少的密碼計(jì)算資源，任務(wù)緊迫度第三的任務(wù)（10

（4）Ttype=4表示該服務(wù)需要的計(jì)算資源不用太多，任務(wù)緊迫度最低的任務(wù)(20

同樣的，相應(yīng)的任務(wù)等級(jí)對(duì)應(yīng)4個(gè)等級(jí)的虛擬密碼機(jī)。等級(jí)越高，下標(biāo)越小，功能及性能越好。這是一個(gè)向下單向兼容的虛擬機(jī)分類。當(dāng)高等級(jí)虛擬機(jī)空閑時(shí)，也可以將低等級(jí)的任務(wù)分配至高等級(jí)虛擬機(jī)，但是高等級(jí)的任務(wù)不能夠分配至低等級(jí)的虛擬密碼機(jī)執(zhí)行，以盡可能達(dá)到資源利用率高且負(fù)載均衡的目的。

（1）Vfc=1表示該虛擬機(jī)具有全部密碼服務(wù)的功能，且計(jì)算能力最強(qiáng)，可執(zhí)行全部等級(jí)的任務(wù)，優(yōu)先執(zhí)行高等級(jí)任務(wù)；

（2）Vfc=2表示該虛擬機(jī)具有大部分密碼服務(wù)的功能，且計(jì)算能力較強(qiáng)，可執(zhí)行除Ttype=1的其余等級(jí)任務(wù)；

（3）Vfc=3表示該虛擬機(jī)具有較少密碼服務(wù)的功能，且計(jì)算能力較弱，可執(zhí)行3、4等級(jí)的任務(wù)；

（4）Vfc=4表示該虛擬機(jī)只具有固定的密碼服務(wù)的功能，且計(jì)算能力最弱，只能夠執(zhí)行等級(jí)為4的任務(wù)。

3 任務(wù)調(diào)度流程

3.1 任務(wù)流程

應(yīng)用系統(tǒng)發(fā)起的密碼服務(wù)請(qǐng)求首先匯聚到任務(wù)接收隊(duì)列，任務(wù)分析模塊對(duì)任務(wù)接收隊(duì)列中的任務(wù)包進(jìn)行分類，并按照不同類型的密碼服務(wù)將任務(wù)包放入不同的任務(wù)請(qǐng)求隊(duì)列。這里將任務(wù)分類到不同隊(duì)列的主要作用有兩個(gè)：對(duì)應(yīng)用未設(shè)置任務(wù)截止時(shí)間的，可以根據(jù)不同業(yè)務(wù)類型設(shè)置截止時(shí)間；可以方便使用多線程，同時(shí)對(duì)多個(gè)任務(wù)進(jìn)行映射處理，提升處理速率，同時(shí)避免一種類型的任務(wù)阻塞其他任務(wù)；用戶可以設(shè)置相應(yīng)的參數(shù)，如將任務(wù)緊迫度設(shè)置為高，可以將任務(wù)提前送入空隊(duì)列進(jìn)行作業(yè)。

任務(wù)調(diào)度具體流程如下。

（1）服務(wù)器將任務(wù)發(fā)送到任務(wù)分析模塊，由任務(wù)分析模塊根據(jù)任務(wù)的屬性、請(qǐng)求等，將具有任務(wù)標(biāo)識(shí)等多元屬性的包頭添加至任務(wù)包；

（2）任務(wù)分析模塊將具有多元屬性域的包頭的任務(wù)包發(fā)送到任務(wù)調(diào)度模塊；

（3）任務(wù)調(diào)度模塊通過(guò)分析包頭中的相關(guān)屬性字段，將任務(wù)映射至相應(yīng)虛擬密碼機(jī)進(jìn)行密碼服務(wù)，完成一次任務(wù)調(diào)度。

在以任務(wù)截止時(shí)間為首要目標(biāo)的同時(shí)，通過(guò)合理設(shè)置，利用Min-Min調(diào)度算法思想，在高等級(jí)虛擬密碼機(jī)空閑或即將空閑時(shí)，將低等級(jí)的任務(wù)合理分配至高等級(jí)虛擬機(jī)。在高等級(jí)虛擬密碼機(jī)占用率過(guò)高時(shí)，正常分配相應(yīng)等級(jí)的任務(wù)至相應(yīng)虛擬密碼機(jī)，從而達(dá)到負(fù)載均衡的目的。

本文通過(guò)對(duì)任務(wù)截止時(shí)間為首要目標(biāo)進(jìn)行等級(jí)劃分，建立虛擬密碼機(jī)性能和任務(wù)截止時(shí)間之間的映射關(guān)系，將任務(wù)分別放入不同虛擬密碼機(jī)對(duì)應(yīng)的等級(jí)隊(duì)列。映射的主要依據(jù)是任務(wù)處理截止時(shí)間要求和等級(jí)隊(duì)列的最小任務(wù)等待時(shí)間。截止時(shí)間為每個(gè)任務(wù)包處理完成的時(shí)間需求。最小任務(wù)等待時(shí)間可表示對(duì)應(yīng)虛擬密碼機(jī)的處理速率或負(fù)載情況，隨著系統(tǒng)運(yùn)行動(dòng)態(tài)變化。最終各等級(jí)隊(duì)列中的任務(wù)將被分發(fā)至相應(yīng)等級(jí)的虛擬密碼機(jī)，由虛擬密碼機(jī)負(fù)責(zé)執(zhí)行相應(yīng)密碼服務(wù)。完整的密碼服務(wù)多級(jí)調(diào)度流程如圖2所示。

圖2 密碼服務(wù)多級(jí)調(diào)度流程

3.2 不同策略的執(zhí)行時(shí)間對(duì)比測(cè)試

本文為了測(cè)試方案的效率，與傳統(tǒng)的遺傳算法（GA策略）和粒子群算法（PSO策略）進(jìn)行對(duì)比。測(cè)試對(duì)比任務(wù)參數(shù)設(shè)置如表1所示。

表1 測(cè)試參數(shù)

在使用相同數(shù)量虛擬密碼機(jī)和任務(wù)屬性的情況下，計(jì)算3種方案在不同任務(wù)數(shù)量情況下的任務(wù)執(zhí)行時(shí)間，結(jié)果如圖3所示。

圖3 策略效率對(duì)比

從圖3可以看出，本文策略比傳統(tǒng)的遺傳算法和粒子群算法在相同任務(wù)量的執(zhí)行時(shí)間上有進(jìn)一步的提升。本文方案將任務(wù)截止時(shí)間作為首要考慮參數(shù)，且設(shè)計(jì)多級(jí)調(diào)度，將最緊要的任務(wù)調(diào)度到性能最好的虛擬密碼機(jī)執(zhí)行，是合理有效的。

4 結(jié)語(yǔ)

本文通過(guò)分析現(xiàn)有的任務(wù)調(diào)度方案和密碼服務(wù)需求，提出了一種基于任務(wù)截止時(shí)間的多級(jí)密碼服務(wù)調(diào)度技術(shù)。以任務(wù)截止時(shí)間為第一優(yōu)化目標(biāo)，提出任務(wù)緊迫度的等級(jí)劃分，并以本文所提出的任務(wù)緊迫度作為衡量任務(wù)調(diào)度的標(biāo)準(zhǔn)，使得不同等級(jí)的虛擬密碼機(jī)完成不同等級(jí)的任務(wù)。通過(guò)和傳統(tǒng)的任務(wù)調(diào)度算法進(jìn)行效率對(duì)比可以看出，本文方案在使得完成密碼服務(wù)的時(shí)間盡量短的情況下，兼顧虛擬密碼機(jī)性能的負(fù)載均衡，以滿足不同應(yīng)用系統(tǒng)的差異化需求，整體提升云環(huán)境下的密碼服務(wù)能力。