異構云環(huán)境下的密碼服務調度方法

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

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

0 引 言

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

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

1 相關研究

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

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

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

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

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

2 系統(tǒng)模型

2.1 任務模型

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

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

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

作業(yè)包處理系統(tǒng)如圖1所示，該系統(tǒng)中的實時任務具有以下特性:

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

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

2.2 隊列模型

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

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

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

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

(1)

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

(2)

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

2.3 節(jié)點模型

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

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

對于任意VMi，有：

VMi={VM_IDi,VM_ratei,funci}

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

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

(3)

3 調度模型及算法

3.1 調度模型

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

圖2 調度模型

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

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

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

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

step4在每個等級隊列中，根據(jù)任務優(yōu)先級算法計算任務優(yōu)先級值，空閑節(jié)點根據(jù)該值的大小選擇相應的執(zhí)行任務；

step5將處理后的數(shù)據(jù)反饋輸出。

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

3.2 調度算法

3.2.1第一級調度

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

任務映射策略：當任務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第二級調度

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

完整的任務優(yōu)先級調度算法如下：

T_Proi=α×priorityi+β×waitTimei

(5)

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

算法2任務調度優(yōu)先級算法。

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

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

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

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

2. for(i=0; i

3. {

4. if(節(jié)點i空閑)

5. for(j=0; j

6. {

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

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

9. end if

10. }

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

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

13. 更新隊列k的屬性；

14. end if

15. end if

16. }

4 仿真及分析

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

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

表1 任務包的參數(shù)設置

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

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

5.6,5.5} (0≤i≤7)

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

表2 等級隊列的參數(shù)設置

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

仿真實驗1：系統(tǒng)負載分布。分別測試等級隊列和節(jié)點的負載分布情況。

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

圖3 隊列的負載分布

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

由圖4可知，在作業(yè)包數(shù)量固定的情況下，數(shù)據(jù)處理性能相似的節(jié)點作業(yè)包分布沒有較大差異?？傮w而言，節(jié)點負載量隨著節(jié)點處理性能的提高而增加。就節(jié)點7而言，在系統(tǒng)當前任務量下，負載量相對較少，為后續(xù)緊急作業(yè)包爆發(fā)的情況提供了保障，提高了系統(tǒng)在該情況下的調度成功率。

圖4 節(jié)點的負載分布

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

圖5 任務執(zhí)行效率測試

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

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

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

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

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

5 結 語

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