基于任務截止時間的多級密碼服務調度方案*

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

（中國電子科技集團公司第三十研究所，四川 成都 610041）

0 引言

密碼技術是云應用、云數據和云虛擬化設備的安全基礎之一。傳統密碼技術受限于擴展性差的密碼服務載體，無法滿足云環境下用戶對數據存儲、計算和傳輸的安全防護要求。云環境下的密碼服務是當前云安全解決方案的主流模式，而當前基于云計算的密碼服務具有請求多樣、算法多樣的任務多樣性。不同的服務應用根據自身的安全需求，可以選擇自身需要的不同強度的密碼服務。一種合理的調度方案是解決密碼資源安全、合理、快速分配的關鍵。

當前，云資源調度策略已經從簡單的單目標調度策略逐步演變為可預測的、多目標的、智能化的復雜調度策略。除需要考慮CPU、內存、存儲等資源外，云環境下的密碼服務需要考慮新引入的密碼計算資源。不僅要實現密碼服務平臺的負載均衡和密碼服務質量等目標，還要考慮密碼計算資源利用率和密碼設備的安全要求等對密碼服務云性能的影響。如何針對不同的密碼服務實現所請求的密碼服務的快速完成，并完成多個虛擬密碼機之間的合理調度，是實現資源利用率最優化的關鍵。

針對上述問題，本文提出基于任務截止時間的多級密碼服務調度技術，將任務截止時間轉化為任務緊迫度，以衡量任務的完成優先級。通過不同等級的調度，完成任務請求和虛擬密碼機之間的映射，從而滿足不同應用系統的差異化需求，整體提升云環境下的密碼服務性能。

1 任務調度相關研究

1.1 國內外相關研究

任務調度是指在特定時間將某些任務分配給特定的資源，是云計算中的一個重要問題。如何使用一種合理的調度機制，是提高性能和資源有效利用率的關鍵。目前，國內外學者研究了很多不同類型的調用機制，如云服務調度、啟發式調度、工作流調度、靜態調度和動態調度。在云計算中，資源的內部和外部需求都要維護，同時帶寬、存儲、資源開銷和響應時間等需求可能因每個任務的不同而不同。負載均衡、可伸縮性、可靠性、性能以及對計算節點的資源動態重新分配，是任務調度的主要問題。所以，在云計算中需要一個有效的任務調度算法。

根據最近的研究綜述，基于粒子群優化算法（Particle Swarm Optimization，PSO）的任務調度和基于遺傳算法（Genetic Algorithm，GA）的任務調度是研究熱點。

PSO算法適用于動態任務調度。文獻[1]提供了一個基于粒子群優化算法的啟發式調度方法，用于減少總執行開銷。該文獻對比了PSO和最佳資源選擇（Best Resource Selection，BRS）算法，結論是PSO有提升，節省了3倍的成本，同時增強了現有資源的工作分布，但是導致了更高的傳輸和存儲開銷。文獻[2]簡要提到了資源配置危機，通過設計一種PSO算法解決這一危機。該理論基于任務總執行時間、資源保留和每個任務的QoS，研究了多目標資源優化問題中的最優調度方法。然而，該成果只能夠用于簡單任務，沒有適用于任務調度問題的一般收斂理論。

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

1.2 密碼服務的任務調度目標

虛擬機調度策略在不同的目標之間往往是相互沖突的[7]。

（1）以提高資源利用率為目標的調度策略需要在減少活躍虛擬機的情況下，將云資源充分地分配到各個虛擬機，而這將導致在突發性負載條件下云服務質量的降低，影響用戶體驗。

（2）以服務質量為目標的調度策略往往會預留部分資源用于處理突發任務，保證服務質量，但是易造成資源閑置。

（3）以降低能耗為目標的調度策略通常通過減少活躍虛擬機來降低數據中心的能耗，以低成本完成高負載，但同樣會導致突發性負載條件下的宕機情況；

（4）以負載均衡為目標的調度策略需要開啟更多的虛擬機，將系統負載均衡地分配到各個云主機，既增加了能耗，又不能充分利用云資源。

關于虛擬機調度的研究，大部分方法都是在特定的研究情境中滿足主要目標，同時兼顧其他次要目標。本文主要針對云環境中的密碼服務，與傳統任務相比，密碼服務的任務與虛擬資源屬性之間、任務與用戶的身份之間，存在很強的依賴型。即使是使用相同的密碼服務，由于用戶需求不同，任務所使用的密碼算法可能不相同，導致不同的密碼算法對云計算中的資源調度和需求都不同。密碼服務對任務調度的時效性、安全性要求更高，各種密碼算法的復雜度也更高。針對上述問題，本文在傳統任務調度算法的基礎上提出了一種基于任務截止時間的多級密碼服務調度策略。

2 基于多級密碼服務的任務調度方案

2.1 任務調度模型

任務調度模型如圖1所示。本文提供的任務分析和任務調度中的密碼處理分別由多個虛擬密碼機完成。這里的任務主要是指一次完整的密碼協議處理，如完成一次數據包的加密即為一個任務。

圖1 任務調度模型

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

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

（3）FTij=ETij+TSj，其中FTij表示第i個任務在第j個虛擬密碼機的完成時間，FTij表示第i個任務在第j個虛擬密碼機的執行時間，TSj表示虛擬密碼機的最早可用時間。

第i個密碼服務形式化描述如下：

式中：Tid表示任務的標識；Tlen表示任務的大小長度；Ttype標識密碼服務的類型，不同的密碼服務所需的資源不同；Tdl表示該任務的截止時間。

第j個虛擬密碼機形式化描述如下：

式中：Vid表示虛擬密碼機的標識；Vsp表示虛擬密碼機的處理速率；Vfc表示該虛擬密碼機能夠實現的密碼功能；Vexc表示任務執行時間，Vmin表示最小可執行任務時間，若當前節點有k個任務正在執行，則

虛擬密碼機的多元組屬性由任務調度模塊維護并更新。任務執行過程中對每個虛擬密碼機的當前狀態進行實時監控，以提高任務的調度效率和任務處理的實時性。

2.2 基于任務截止時間的任務調度方案

本文方案以任務截止時間為主目標，在此本文設置一個任務緊迫度，即：

它表示任務截止時間減去任務完成時間的值。這個值越小，表示任務越緊迫。當DTmin=0時，代表任務截止時間與完成時間相等；DTmin<0，則表示任務無法在截止時間內完成，則任務執行失敗。當兩個任務的緊迫度相同時，選擇任務標識值更小的優先執行。

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

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

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

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

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

同樣的，相應的任務等級對應4個等級的虛擬密碼機。等級越高，下標越小，功能及性能越好。這是一個向下單向兼容的虛擬機分類。當高等級虛擬機空閑時，也可以將低等級的任務分配至高等級虛擬機，但是高等級的任務不能夠分配至低等級的虛擬密碼機執行，以盡可能達到資源利用率高且負載均衡的目的。

（1）Vfc=1表示該虛擬機具有全部密碼服務的功能，且計算能力最強，可執行全部等級的任務，優先執行高等級任務；

（2）Vfc=2表示該虛擬機具有大部分密碼服務的功能，且計算能力較強，可執行除Ttype=1的其余等級任務；

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

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

3 任務調度流程

3.1 任務流程

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

任務調度具體流程如下。

（1）服務器將任務發送到任務分析模塊，由任務分析模塊根據任務的屬性、請求等，將具有任務標識等多元屬性的包頭添加至任務包；

（2）任務分析模塊將具有多元屬性域的包頭的任務包發送到任務調度模塊；

（3）任務調度模塊通過分析包頭中的相關屬性字段，將任務映射至相應虛擬密碼機進行密碼服務，完成一次任務調度。

在以任務截止時間為首要目標的同時，通過合理設置，利用Min-Min調度算法思想，在高等級虛擬密碼機空閑或即將空閑時，將低等級的任務合理分配至高等級虛擬機。在高等級虛擬密碼機占用率過高時，正常分配相應等級的任務至相應虛擬密碼機，從而達到負載均衡的目的。

本文通過對任務截止時間為首要目標進行等級劃分，建立虛擬密碼機性能和任務截止時間之間的映射關系，將任務分別放入不同虛擬密碼機對應的等級隊列。映射的主要依據是任務處理截止時間要求和等級隊列的最小任務等待時間。截止時間為每個任務包處理完成的時間需求。最小任務等待時間可表示對應虛擬密碼機的處理速率或負載情況，隨著系統運行動態變化。最終各等級隊列中的任務將被分發至相應等級的虛擬密碼機，由虛擬密碼機負責執行相應密碼服務。完整的密碼服務多級調度流程如圖2所示。

圖2 密碼服務多級調度流程

3.2 不同策略的執行時間對比測試

本文為了測試方案的效率，與傳統的遺傳算法（GA策略）和粒子群算法（PSO策略）進行對比。測試對比任務參數設置如表1所示。

表1 測試參數

在使用相同數量虛擬密碼機和任務屬性的情況下，計算3種方案在不同任務數量情況下的任務執行時間，結果如圖3所示。

圖3 策略效率對比

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

4 結語

本文通過分析現有的任務調度方案和密碼服務需求，提出了一種基于任務截止時間的多級密碼服務調度技術。以任務截止時間為第一優化目標，提出任務緊迫度的等級劃分，并以本文所提出的任務緊迫度作為衡量任務調度的標準，使得不同等級的虛擬密碼機完成不同等級的任務。通過和傳統的任務調度算法進行效率對比可以看出，本文方案在使得完成密碼服務的時間盡量短的情況下，兼顧虛擬密碼機性能的負載均衡，以滿足不同應用系統的差異化需求，整體提升云環境下的密碼服務能力。