異構云環境下的密碼服務調度方法

孫德洋 婁嘉鵬 李建鵬 張寒冰 成文文

1(西安電子科技大學通信工程學院 陜西 西安 710071)2(北京電子科技學院網絡空間安全系 北京 100070)

0 引 言

云計算作為新興的計算模式，具有高可擴展性、高可靠性和按需服務等特點[1]，云基礎設施由共享的硬件和軟件商品資源池組成，這些資源按地理位置分布并提供按需服務[2-3]，可以為用戶提供可變的按需資源。從服務消費者角度來看，用戶希望獲得滿足其個性化需求的云服務，這些云服務將利用“云”中的領域知識和用戶端的狀態信息來提供服務，以極大提高用戶體驗。在云計算中，調度是重要的組成部分之一，其效率決定整個云計算環境的工作性能。面對云計算環境下的用戶業務類型多樣、需求個性化的問題，如何實現業務的高效調度，保證不同的業務請求得到快速、有效的解決起著至關重要的作用。

異構云環境下的任務調度問題，已被證明為NP-hard問題[4]，而多算法的密碼服務器屬于典型的異構系統，各密碼算法處理節點的處理能力存在差異，如果沒有有效的密碼服務調度機制，會導致作業包與處理節點之間的映射不合理，從而影響整個服務系統的工作性能。現有的很多文獻大多采用的是理想化的節點性能，通過采用一定的調度方法，從負載均衡、資源利用率和減少能耗等方面進行研究[5]，而調度系統性能的最優解往往與具體應用有關，需要針對具體實際問題建立模型[6]。本文從以上問題的角度出發，在充分考慮節點異構性的基礎上，提出一種基于任務截止時間的調度方法，通過兩級調度模型，完成作業包和密碼計算單元之間的映射，從而實現對不同密碼任務的調度。

1 相關研究

圍繞云環境下的任務調度問題，國內外學者展開一系列的研究工作，先后提出多種調度模型和算法[7]。文獻[8]提出了基于遺傳算法的兩階段任務調度方法，結合任務截止時間和資源利用率以確定優先級隊列，從而提升任務調度性能，但文中沒有考慮任務優先級等因素對調度的影響，無法滿足調度過程中的實時性需求。Zhou等綜合考慮了任務的截止時間和優先級等因素，提出一種基于仿真的動態調度方法，但該方法需反復查詢信息表并由模擬器模擬生成調度策略，實現較為復雜且系統開銷較大[9]。文獻[10]以總任務完成時間和任務平均完成時間作為參考量，提出一種雙適應度遺傳算法(DFGA)的任務調度算法，但該方案的節點處理能力較為理想化，無法適應不同節點處理能力不均衡的實際應用問題。文獻[11]提出一種基于滾動優化的實時任務調度系統，通過新增加虛擬機的方式來保證在任務的截止期內完成任務請求，此方案能在一定程度上保證任務執行的成功率，但是無法適應異構環境下不同節點處理能力不同的問題，并且無法處理虛擬云中的并行任務。文獻[12]提出通過用戶優先級感知負載平衡改進的Min-Min調度算法(PA-LBIMM)，但是該算法僅關注任務的運行時間、負載均衡和用戶優先級等因素，沒有考慮任務的完成時間約束，可能會導致計算資源中現有負載過多而產生的任務失效問題。

相比于傳統任務的調度系統而言，密碼服務的專業性、安全性、實時性要求更高，在實際的應用環境中，調度方案要均衡和優化影響系統性能的多種因素[13]。基于上述問題，本文針對異構云環境中不同密碼服務處理節點實現功能和性能不同的問題，綜合考慮用戶優先級、作業包等待時間、節點運算速率等級以及各節點當前任務隊列等影響因素，提出一種新的任務調度模型和算法，實現異構云環境下多種密碼任務的調度[14]。主要工作如下：

(1) 構建一種密碼任務調度模型，主要包括任務分析模塊、任務調度單元和異構環境下的算法計算模塊。

(2) 提出一種基于該調度模型的任務調度方案。通過對任務截止時間進行等級劃分，建立節點性能和任務截止時間之間的映射關系。

(3) 提出一種對應等級節點的任務調度算法。利用用戶優先級和任務等待時間定義任務優先級，實現請求任務與執行節點的最佳匹配。

2 系統模型

2.1 任務模型

假設現有n個相互獨立的作業包，則作業包的集合表示為T={T1,T2,…,Tn}，對于每個作業包Ti，具體可表示如下：

Ti={T_IDi,cmd,key_idi,Proi,d_timei,w_timei,e_timei,longi,datai,tar_vmi}

式中：T_IDi(i≥1)表示作業包的唯一標識，故不同作業包的標號不同，該字段主要用來將處理后的作業包按照T_IDi返回；cmd是命令字段，表示具體密碼任務的請求操作指令，可以為加密、解密、簽名、驗簽和Hash等請求，并規定對應的字段依次為1、2、3、…；key_idi為該密碼服務所需的密鑰標識；Proi表示用戶的等級；d_timei表示作業包截止時間，決定作業包與等級隊列之間的映射關系。所謂的截止時間，是指某項任務必須要在規定的時間內完成的時間[15]，即超過該時間任務失效；w_timei表示作業包等待時間，其值為從作業包加入到任務隊列至任務被執行這一時間段的總時間；e_timei為作業包的完成時間；longi為作業包的長度；datai為運算數據；tar_vmi表示經系統調度后作業包對應的目標執行節點，該參數由調度系統賦值。從而，作業包Ti可以由包含上述字段的的結構體定義，m個作業包可以由m維結構體數組task[m]定義。

作業包處理系統如圖1所示，該系統中的實時任務具有以下特性:

(1) 每一個作業包Ti都是非周期性的，其等待時間為w_timei，完成時間為e_timei，截止時間為d_timei，按上述可得到d_timei≥(w_timei+e_timei)。

(2) 作業包是不可搶占的，且相互獨立。

2.2 隊列模型

為了更好地滿足異構云環境下的用戶需求，保證用戶密碼服務任務的最佳處理節點匹配，根據節點的處理速率將其劃分為四個不同等級的隊列，分別為1級隊列、2級隊列、3級隊列和4級隊列。在用戶的任務調度過程中，各級隊列之間不設置固定的優先級差異，由系統第一級調度子系統綜合考慮不同任務的截止時間屬性、隊列長度屬性和時間屬性為任務尋找和匹配與其最佳的節點等級隊列。對于不同等級的隊列Qi，具體可表示為：

Qi={q_leni,q_timei,da_ratei,q_numi,l_numi,task[u]}

式中：q_leni表示隊列可容納的最多負載數，即隊列長度；q_timei字段為隊列的時間屬性，表示該隊列下節點所能處理任務的最小截止時間；da_ratei表示隊列下節點的平均數據處理速率；q_numi表示當前隊列下的節點個數；l_numi表示該隊列當前的負載量；task[u]表示已分配到該隊列中任務的標識集合，u滿足0≤u

在任意隊列中，假設所有節點單位任務的平均用時為t_Ti，則：

(1)

因此，在設置隊列長度與時間屬性時遵循以下約束關系：

(2)

正常情況下，對于作業包數量為l_numi的等級隊列，當滿足d_timei>q_timei且l_numi≤q_leni時，將當前作業包分配至該隊列，負載量l_numi+1，對應的密碼計算節點每執行一個作業包，負載量l_numi-1。當l_numi>q_leni時，即表示該等級隊列負載量已滿，當前作業包無法進入該隊列，將其調度到等級較高且滿足截止時間屬性q_timei的隊列中。

2.3 節點模型

在第二級調度中，通過任務優先級調度算法計算各任務的優先級，空閑節點根據所屬隊列中各任務的優先級大小選擇任務執行。其中，任務優先級調度算法綜合考慮任務對應的用戶優先級和等待時間屬性。

每個等級隊列對應的計算節點可用一個集合表示，即：VM={VM11,VM12,…,VM1n,…,VMn1,…,VMnn}。

對于任意VMi，有：

VMi={VM_IDi,VM_ratei,funci}

式中：VM_IDi表示對應節點的唯一標識，與任務模型的tar_vmi對應；VM_ratei表示節點下數據的處理速率，該值由節點本身確定；funci表示該節點下的功能，與任務模型的cmd對應。

對于具有n個節點的隊列Qi，隊列模型參數da_ratei和所屬節點的VM_ratei有以下對應的關系：

(3)

3 調度模型及算法

3.1 調度模型

調度模型包括以下四部分：作業分析模塊、任務請求隊列、任務映射模塊和等級隊列。如圖2所示。

圖2 調度模型

當有新的任務到達時，調度可以分為以下5個步驟：

step1不同地域的用戶終端提交任務請求，將作業包依次放入調度系統的任務接收隊列中；

step2調度器中的任務分析模塊根據不同的任務請求參數cmd，將任務接收隊列中的作業包依次放入對應的任務請求隊列中，例：加密隊列中的作業包均為加密算法任務請求，其他隊列同理；

step3任務映射模塊依據任務映射策略中隊列時間屬性、隊列長度屬性和任務截止時間之間的映射關系確定隊列等級，將作業包依次分配到對應的隊列中；

step4在每個等級隊列中，根據任務優先級算法計算任務優先級值，空閑節點根據該值的大小選擇相應的執行任務；

step5將處理后的數據反饋輸出。

為方便描述，本文流程圖和仿真等僅以加密請求為例，其他任務請求模式同加密請求。

3.2 調度算法

3.2.1第一級調度

當用戶提交的作業包進入任務接收隊列后，任務分析模塊根據作業包中的cmd字段將任務隊列中的作業包放入任務請求隊列中。以加密隊列為例，在此隊列中，對于任意作業包Ti，通過其字段中定義的d_timei值，根據映射策略關系將該作業包調度到對應的等級隊列中。

任務映射策略：當任務j截止時間、隊列k時間屬性以及長度滿足如下約束關系時，將任務分配至該等級隊列；否則，按照等級隊列屬性da_ratei遞增的順序依次查詢，若存在等級隊列符合上述約束關系，則將任務包調度至該隊列：

(sizeof(queue[k].task[ui])≤queue[k].q_len)

&& (task[j].d_time≥queue[k].q_time)

(4)

算法1任務與等級隊列的映射算法。

輸入：任務截止時間，等級隊列時間屬性和長度屬性；

輸出：依次遍歷各等級隊列，將任務分配到符合約束條件的等級隊列，更新該等級隊列屬性；否則丟棄該任務。

對于m個待調度任務和等級隊列k(0

1. for(j=0;j

2. {

3. for(k=0;k<4;k++)

4. {

5. if((4)式成立)

6. Queue[k].task[ui]=j;

7. ui++;

8. end if

9. }

10. }

3.2.2第二級調度

不同用戶優先級不同，且每個作業包經算法1調度后在等級隊列中的等待時間也不相同。為了使較高等級用戶的作業包具有較高的執行優先級，同時避免其他用戶的任務在隊列中等待時間過長，本文提出一種基于用戶優先級和等待時間的加權任務優先級調度算法。通過該算法確定任務優先級T_Pro的大小，處理節點根據該值從其所述的等級隊列中選擇相應的任務執行。

完整的任務優先級調度算法如下：

T_Proi=α×priorityi+β×waitTimei

(5)

式中：α、β分別為加權系數，α，β∈[0,1]且α+β=1。

算法2任務調度優先級算法。

輸入：各等級隊列的任務集合，以及對應執行節點屬性；

輸出：若等級隊列中的任務已被執行節點成功調度，則返回調度成功標識，且更新該任務所在等級隊列屬性。

對于共有n個執行節點、m個待分配任務的等級隊列k:

1. 初始化局部變量temp=big=m，以及優先級數組F[m+1]={0}；

2. for(i=0; i

3. {

4. if(節點i空閑)

5. for(j=0; j

6. {

7. if(任務j未被節點調度)

8. 式(5)計算獲得最大優先級任務的標識:big；

9. end if

10. }

11. if(F[big]!=0)

12. 將big標識的任務分配至節點i；

13. 更新隊列k的屬性；

14. end if

15. end if

16. }

4 仿真及分析

通過在Windows環境下的C語言編程仿真，本節對調度系統任務的負載分布、完成時間以及加權系數對不同等級用戶作業包等待時間的影響進行了仿真測試分析，并在完成時間的測試中，與隨機法進行對比分析。由于其他密碼服務任務請求的總體過程相同，在以下仿真中僅以加密算法為例進行。

在本次仿真中，作業包的參數設置如表1所示，其中，Proi表示用戶的優先級，d_timei表示任務截止時間，w_timei表示任務等待時間，longi為作業包的長度。

表1 任務包的參數設置

共設置4個等級隊列、8個處理節點，分別從0開始編號，每個等級隊列分別對應兩個處理節點：節點0和節點1所屬隊列編號為0，節點2和節點3所屬隊列編號為1，節點4和節點5所屬隊列編號為2，節點6和節點7所屬隊列編號為3。對于待處理數據量大小相同的單位作業包，各節點預計完成時間分別為(單位時間)：

Vm[i].(VM_ratei)={9.9,9.7,8.6,8.3,6.7,6.5,

5.6,5.5} (0≤i≤7)

等級隊列的參數設置如表2所示，其中，q_timei表示隊列的時間屬性，q_leni表示隊列長度，da_ratei表示隊列下節點的平均數據處理速率。

表2 等級隊列的參數設置

由于任務優先級算法中的加權系數α、β只影響等級隊列中各作業包的執行順序，不影響系統的負載分布和任務執行效率，故在仿真實驗1和實驗2中可任意設置該加權值，本文中取α=0.6、β=0.4。

仿真實驗1：系統負載分布。分別測試等級隊列和節點的負載分布情況。

等級隊列的負載分布。按上述方式設置處理節點數量、處理節點性能參數以及隊列參數，隨機生成不同數量的作業包，各隊列的負載分布隨作業包數量變化情況如圖3所示。

圖3 隊列的負載分布

由圖3可知，在相同作業包數量的情況下，較高處理節點對應的等級隊列(隊列2和隊列3)作業包負載量較大，體現了異構云環境下“能者多勞”的分配策略。隨著作業包數量的增多，各等級隊列中的負載分布逐漸增加，且均保持良好的負載分布。

由圖4可知，在作業包數量固定的情況下，數據處理性能相似的節點作業包分布沒有較大差異。總體而言，節點負載量隨著節點處理性能的提高而增加。就節點7而言，在系統當前任務量下，負載量相對較少，為后續緊急作業包爆發的情況提供了保障，提高了系統在該情況下的調度成功率。

圖4 節點的負載分布

仿真實驗2：執行效率測試。為了測試本文算法的執行效率，設置相同的處理節點屬性以及等級隊列屬性，隨機生成不同數量的作業包，分別測試在使用本文算法、隨機法和遺傳算法時各節點最大完成時間隨作業包數量的變化情況，如圖5所示。

圖5 任務執行效率測試

由圖5可知，在相同的實驗環境與參數設置下，本文算法的執行效率明顯優于隨機法和遺傳算法。這是因為本文提出的算法考慮了作業包的自身屬性、等級隊列的負載情況以及處理節點的異構性，調度過程中以任務包的截止時間為參考進行節點的匹配，考慮作業包的優先級和等待時間因素選擇執行任務，并且每次調度完成后及時反饋和更新各調度節點信息。同時，對滿載的等級隊列，通過將作業包動態調度到高等級隊列，保證了任務的處理效率。而本文采用的隨機法中節點是按照編號順序從等級隊列中隨機選擇任務來調度執行，會出現已空閑的高性能節點需等待低性能運算節點運行完成后才能進行后續任務調度的情況，無法充分發揮高性能節點的處理優勢，從而導致整體任務運行時間較長。遺傳算法在進行大量的個體計算時，計算時間較長，算法的收斂速度較慢，與隨機法相似，在為任務搜索和匹配最佳執行節點時也未充分考慮節點運算速率異構等問題，故會影響整個調度系統的完成時間。因此，本文算法在最大完成時間上相較于隨機法減少了約14.48%～19.52%，相較于遺傳算法減少了約4.44%～17.54%，并且隨著作業包數量的增多，執行效率的提升更明顯。

仿真實驗3：加權系數α對不同等級用戶任務在等級隊列中平均等待時間的影響。設置作業包總數為8 000，保持各處理節點、等級隊列的性能屬性固定不變，依次改變任務優先級算法中加權系數α值，分別測試不同等級用戶對應作業包在等級隊列中的平均等待時間，如圖6所示。

圖6 α對平均等待時間的影響

由于隨著系數的增加，在任務優先級調度算法中用戶優先級占據的比重逐漸加大，等待時間占據的比重減少，故優先級越高的用戶作業包會優先得到處理。從而，在圖6中，隨著加權系數α的增大，3、4級用戶對應的單位作業包平均等待時間逐漸降低，1、2級用戶單位作業包的平均等待時間逐漸增加。由此可知，α和β的取值會對作業包在等級隊列中的等待時間有一定的影響。

通過測試結果可知，當作業包數量逐漸增加，本文的框架和算法有更好的優勢。

5 結 語

本文提出基于任務截止時間的二級任務調度模型，設計一個基于作業包屬性的調度算法。首先根據作業包的命令標識cmd把任務調度到相應的任務請求隊列。然后根據任務的截止時間d_timei選擇合適的等級隊列，在選擇等級隊列時可根據其參數q_leni對作業包進行動態調整，避免因某一個等級隊列負載量過大導致其他作業包無法進行及時處理而失效的情況。在對應的等級隊列中，通過任務調度優先級算法計算得到任務的優先級，空閑處理節點根據優先級值的大小選擇相應的任務執行。仿真結果表明，該框架能有效保證節點的負載分布和良好的執行效率，與隨機法和遺傳算法相比，其執行效率分別提高了17%和11%左右。