基于關(guān)聯(lián)數(shù)據(jù)本地化的多密碼作業(yè)流調(diào)度算法 *

關(guān)川江，李建鵬，史國(guó)振，毛 明

(1.西安電子科技大學(xué)通信工程學(xué)院，陜西 西安 710071； 2.北京電子科技學(xué)院電子與通信工程系,北京 100070)

1 引言

密碼服務(wù)是一種由安全協(xié)議、密碼算法、密碼基礎(chǔ)設(shè)施、密碼芯片等密碼相關(guān)設(shè)備和系統(tǒng)提供的服務(wù)，包括加密、解密、數(shù)字簽名、認(rèn)證等安全服務(wù)和密碼資源管理服務(wù)等[1]。云環(huán)境中密碼服務(wù)的應(yīng)用不僅可以促進(jìn)安全可靠云計(jì)算體系的建設(shè)，也可以有效簡(jiǎn)化密碼模塊的設(shè)計(jì)與實(shí)施，使得密碼技術(shù)的使用更集中、規(guī)范和易于管理[2]。采用集中式部署方法將密碼機(jī)集群資源池化，實(shí)現(xiàn)對(duì)“密碼資源集中管理、虛擬化共享、內(nèi)網(wǎng)調(diào)度、外網(wǎng)專用”，是當(dāng)前密碼服務(wù)云的主流實(shí)現(xiàn)方法[3]。

工作流調(diào)度是在云資源上執(zhí)行高度相互依賴任務(wù)的過程，其主要目的是實(shí)現(xiàn)用戶任務(wù)與云中計(jì)算資源的最優(yōu)匹配，以最大化資源吞吐量[4]，是一個(gè)著名的NP-Complete類問題[5]。云計(jì)算中的資源調(diào)度工作主要包括發(fā)現(xiàn)資源和過濾資源、選擇目標(biāo)資源、將資源分配給目標(biāo)任務(wù)等步驟[6]。異構(gòu)系統(tǒng)基于列表的任務(wù)啟發(fā)式調(diào)度算法中，RR(Round-Robin)[7]通過建立處理資源循環(huán)列表，將就緒任務(wù)輪流分配給各處理節(jié)點(diǎn)，直至所有有效任務(wù)都被成功分配到對(duì)應(yīng)節(jié)點(diǎn)中等待執(zhí)行。異構(gòu)最早完成時(shí)間HEFT(Heterogeneous Earliest Finish Time)[8]、預(yù)測(cè)最早完成時(shí)間PEFT(Predict Earliest Finish Time)[9]、約束最早完成時(shí)間CEFT(Constrained Earliest Finish Time)[10]、最小化調(diào)度長(zhǎng)度MSL(Minimizing Schedule Length)[11]和異構(gòu)選擇值HSV(Heterogeneous Selection Value)[12]等算法，都是通過平均處理時(shí)間和平均通信時(shí)間決定任務(wù)調(diào)度的優(yōu)先級(jí)，具有調(diào)度效率高、算法復(fù)雜度低等優(yōu)勢(shì)。其中,HEFT首先預(yù)計(jì)算所有任務(wù)在各個(gè)處理節(jié)點(diǎn)上的完成時(shí)間，然后將任務(wù)依次調(diào)度至其對(duì)應(yīng)的具有最小完成時(shí)間的處理節(jié)點(diǎn)上運(yùn)行，為了適應(yīng)在復(fù)雜異構(gòu)集群環(huán)境中的作業(yè)流調(diào)度系統(tǒng)性能需要，不少研究學(xué)者在該算法基礎(chǔ)上進(jìn)行了深入探討并提出了各自有效的解決方案[13,14]。針對(duì)有限資源環(huán)境中多作業(yè)流的調(diào)度問題，Zhao等人[15]描述了一種有向無環(huán)圖DAG(Directed Acyclic Graph)相對(duì)于當(dāng)前時(shí)刻滯后程度的量化方法，根據(jù)每個(gè)任務(wù)的滯后程度確定任務(wù)調(diào)度的優(yōu)先級(jí)，從而解決了多作業(yè)流執(zhí)行中的公平性問題。Bittencourt等人[16]分析了在網(wǎng)格中調(diào)度多個(gè)作業(yè)流時(shí)，4種不同策略對(duì)調(diào)度長(zhǎng)度和公平性的影響。Wu等人[17]采用包括遺傳算法、蟻群優(yōu)化和粒子群優(yōu)化等基于包的元啟發(fā)式隨機(jī)調(diào)度算法，提出了一種面向市場(chǎng)的云工作流分層調(diào)度策略(Market-Oriented Hierarchical Scheduling Strategy)，有效提高了任務(wù)調(diào)度效率，同時(shí)在完成時(shí)間、執(zhí)行成本等方面取得了良好的優(yōu)化效果。

上述各方案在傳統(tǒng)應(yīng)用作業(yè)流的調(diào)度系統(tǒng)中都表現(xiàn)出了良好的性能，但都存在關(guān)聯(lián)數(shù)據(jù)本地化差的問題，即無法保證將數(shù)據(jù)依賴性作業(yè)流的各個(gè)子任務(wù)分配至同一處理節(jié)點(diǎn)上執(zhí)行。對(duì)于密碼作業(yè)流而言，當(dāng)數(shù)據(jù)依賴性作業(yè)流的不同子任務(wù)被部署于不同處理節(jié)點(diǎn)上運(yùn)行時(shí)，節(jié)點(diǎn)之間運(yùn)算信息的交互過程不僅加大了系統(tǒng)通信性能的開銷和任務(wù)處理過程中密鑰匹配的難度，同時(shí)也為整個(gè)密碼服務(wù)系統(tǒng)的處理數(shù)據(jù)安全性帶來了嚴(yán)峻威脅。

2 模型描述

2.1 任務(wù)模型描述

本文利用有向無環(huán)圖DAG來對(duì)作業(yè)流JOB=(T,E)進(jìn)行建模，其中T={T1,T2,…,Tn}是任務(wù)節(jié)點(diǎn)集合，E是節(jié)點(diǎn)之間的邊集合，邊的屬性用于標(biāo)識(shí)相鄰2個(gè)任務(wù)之間是否存在關(guān)聯(lián)數(shù)據(jù)，取決于任務(wù)所在作業(yè)流的數(shù)據(jù)依賴性標(biāo)識(shí)。有序邊起點(diǎn)處對(duì)應(yīng)的任務(wù)節(jié)點(diǎn)稱為終點(diǎn)處任務(wù)節(jié)點(diǎn)的直接前序任務(wù)，終點(diǎn)處對(duì)應(yīng)的任務(wù)節(jié)點(diǎn)稱為起點(diǎn)處任務(wù)節(jié)點(diǎn)的直接后繼任務(wù)。沒有直接前序任務(wù)的任務(wù)節(jié)點(diǎn)稱為入口任務(wù)，沒有直接后繼任務(wù)的任務(wù)節(jié)點(diǎn)稱為出口任務(wù)。對(duì)于?ei,j∈E，若ei,j=1，則表示T上2個(gè)任務(wù)節(jié)點(diǎn)Ti,Tj∈T之間存在關(guān)聯(lián)數(shù)據(jù)和執(zhí)行依賴順序，這意味著在完成任務(wù)Ti之前不能調(diào)度任務(wù)Tj；若ei,j=0，則表示2個(gè)任務(wù)節(jié)點(diǎn)Ti,Tj∈T不屬于數(shù)據(jù)依賴性任務(wù)，其調(diào)度過程沒有先后之分。

如圖1所示的作業(yè)流,共有4個(gè)作業(yè)流集合，分別為：JOB1={T1,T7}，JOB2={T2,T5,T8}，JOB3={T3,T6,T10,T12}，J4={T4,T9,T11}。其中，作業(yè)流JOB1、JOB3和JOB4中各任務(wù)之間的邊權(quán)不等于0，為數(shù)據(jù)依賴性作業(yè)流；作業(yè)流JOB2中各任務(wù)之間的邊權(quán)等于0，不存在關(guān)聯(lián)數(shù)據(jù)，為非數(shù)據(jù)依賴性作業(yè)流。就JOB3而言，任務(wù)T3是整個(gè)作業(yè)流的入口任務(wù)，也是任務(wù)T6的直接前序任務(wù)；任務(wù)T12是整個(gè)作業(yè)流的出口任務(wù)，也是任務(wù)T10的直接后繼任務(wù)。對(duì)于任務(wù)集合T中的任一任務(wù)Ti，可以用一個(gè)多元組表示：

Ti={j_id,num,cmd,cyp,long,flag,data}

(1)

其中，j_id為任務(wù)所屬作業(yè)流標(biāo)識(shí)，也是密碼服務(wù)系統(tǒng)中請(qǐng)求作業(yè)流的唯一標(biāo)識(shí)，屬于同一作業(yè)流的各任務(wù)具有相同的j_id屬性；num為任務(wù)在其所屬作業(yè)流中的唯一標(biāo)識(shí)，屬于同一作業(yè)流的各任務(wù)具有不同的num屬性，屬于不同作業(yè)流的任務(wù)的num屬性可能相同，該屬性與j_id結(jié)合使用以保證任務(wù)處理中密鑰信息的快速匹配和處理結(jié)果的正確返回；cmd為任務(wù)的處理命令，常見的密碼服務(wù)處理命令有加密、解密、簽名、驗(yàn)簽和Hash運(yùn)算等；cyp為請(qǐng)求任務(wù)所使用的密碼算法標(biāo)識(shí)，包括該服務(wù)系統(tǒng)所支持的所有序列密碼算法、分組密碼算法、公鑰密碼算法和Hash算法等，該屬性結(jié)合cmd決定作業(yè)流任務(wù)所請(qǐng)求的密碼運(yùn)算功能；long為該任務(wù)中待處理數(shù)據(jù)的大小；flag是任務(wù)所在作業(yè)流的數(shù)據(jù)依賴性標(biāo)識(shí)；data是任務(wù)中待處理數(shù)據(jù)集。

Figure 1 Job stream DAG圖1 作業(yè)流DAG

在密碼服務(wù)中，存在著許多數(shù)據(jù)依賴性作業(yè)流，如Hash函數(shù)的運(yùn)算過程以及分組密碼加解密采用的CBC(Cipher Block Chaining)、OFB(Output FeedBack)、CFB(Cipher FeedBack)等工作模式中，直接前序任務(wù)的運(yùn)算結(jié)果會(huì)作為輸入條件之一參與其下一任務(wù)的數(shù)據(jù)運(yùn)算。假設(shè)JOB4是工作于CFB模式下的AES加密服務(wù)請(qǐng)求作業(yè)流，則入口任務(wù)T4在經(jīng)加密運(yùn)算后的輸出密文會(huì)作為輸入，生成加密其直接后繼任務(wù)T9的會(huì)話密鑰；同樣地，任務(wù)T9的加密運(yùn)算結(jié)果又會(huì)作為任務(wù)T11會(huì)話密鑰的生成輸入條件，直至完成對(duì)出口任務(wù)T11中數(shù)據(jù)的加密運(yùn)算，即可結(jié)束整個(gè)工作流的服務(wù)運(yùn)行。完整加密過程如圖2所示。

Figure 2 Complete procedure of AES encryption in CFB mode圖2 AES密碼算法的CFB加密模式

可見，對(duì)于密碼服務(wù)請(qǐng)求，其中任一作業(yè)流的入口任務(wù)與其它任務(wù)之間不存在關(guān)聯(lián)數(shù)據(jù)，在該類任務(wù)的調(diào)度過程中可與非數(shù)據(jù)依賴性作業(yè)流中的任務(wù)采取同一處理策略；而數(shù)據(jù)依賴性作業(yè)流中非入口任務(wù)與其直接前序任務(wù)之間存在著不可忽略的關(guān)聯(lián)數(shù)據(jù)，用于該類任務(wù)運(yùn)算處理的處理節(jié)點(diǎn)之間也需要進(jìn)行大量的數(shù)據(jù)交互。如何保護(hù)該類任務(wù)之間關(guān)聯(lián)數(shù)據(jù)交互過程中的安全性，同時(shí)避免整體服務(wù)系統(tǒng)因該過程而導(dǎo)致的通信性能開銷和作業(yè)流密鑰匹配難度，是本文算法的主要研究目標(biāo)。

特別說明的是，本文只考慮單一處理命令請(qǐng)求的密碼作業(yè)流。對(duì)于復(fù)雜處理命令請(qǐng)求作業(yè)流，如需要對(duì)某一明文數(shù)據(jù)進(jìn)行Hash運(yùn)算后，再對(duì)Hash運(yùn)算結(jié)果利用公鑰密碼算法進(jìn)行簽名時(shí)，則可以將Hash運(yùn)算和簽名運(yùn)算分別作為2個(gè)獨(dú)立的具有單一處理命令的密碼作業(yè)流進(jìn)行處理。

2.2 處理節(jié)點(diǎn)模型

云密碼服務(wù)系統(tǒng)是一個(gè)典型的分布式異構(gòu)系統(tǒng)，云中各密碼處理節(jié)點(diǎn)的密碼實(shí)現(xiàn)功能、數(shù)據(jù)處理速率、數(shù)據(jù)傳輸速率等特性都存在著巨大差異。為了實(shí)現(xiàn)密碼計(jì)算資源的按需配置，簡(jiǎn)化管理與調(diào)度的流程，對(duì)處理節(jié)點(diǎn)的狀態(tài)信息進(jìn)行統(tǒng)一定義和描述：

Nj={func,comput,commun}

(2)

其中，func表示對(duì)應(yīng)處理節(jié)點(diǎn)可實(shí)現(xiàn)的請(qǐng)求密碼功能，與任務(wù)的cmd屬性和cyp屬性相對(duì)應(yīng)；comput表示處理節(jié)點(diǎn)的數(shù)據(jù)處理速率；commun表示處理節(jié)點(diǎn)的數(shù)據(jù)傳輸速率。

對(duì)于密碼服務(wù)系統(tǒng)中的任一數(shù)據(jù)依賴性作業(yè)流，當(dāng)其入口任務(wù)按照相關(guān)調(diào)度策略被分配至某處理節(jié)點(diǎn)時(shí)，則該作業(yè)流中其余所有后繼任務(wù)與各節(jié)點(diǎn)之間的關(guān)聯(lián)數(shù)據(jù)量就已經(jīng)被確定，為本文關(guān)聯(lián)數(shù)據(jù)本地化的實(shí)現(xiàn)提供了理論依據(jù)，可以表示為處理節(jié)點(diǎn)-任務(wù)關(guān)聯(lián)數(shù)據(jù)矩陣(N-T)。以圖1中JOB3作業(yè)流為例，假設(shè)已經(jīng)完成對(duì)其入口任務(wù)T3的調(diào)度并將其分配至標(biāo)識(shí)為N3的節(jié)點(diǎn)，則此時(shí)處理節(jié)點(diǎn)-任務(wù)關(guān)聯(lián)數(shù)據(jù)矩陣為:

N1N2N3N4…Nn

(3)

容易發(fā)現(xiàn)，數(shù)據(jù)依賴性作業(yè)流中的每個(gè)后繼任務(wù)只與其直接前序任務(wù)的處理節(jié)點(diǎn)之間存在關(guān)聯(lián)數(shù)據(jù)，與其余節(jié)點(diǎn)之間的關(guān)聯(lián)數(shù)據(jù)均為0。

3 關(guān)聯(lián)數(shù)據(jù)本地化密碼調(diào)度算法

3.1 相關(guān)參數(shù)定義

為了方便描述本文調(diào)度算法的設(shè)計(jì)思路與工作過程，對(duì)該算法的相關(guān)參數(shù)及性能屬性進(jìn)行如下形式化定義：

定義1(任務(wù)執(zhí)行代價(jià)W(Tk)) 任務(wù)執(zhí)行代價(jià)是指在目標(biāo)運(yùn)算節(jié)點(diǎn)的數(shù)據(jù)處理速率下運(yùn)算完成當(dāng)前任務(wù)所需的時(shí)間。對(duì)于標(biāo)識(shí)為Nj的處理節(jié)點(diǎn)，則任務(wù)Tk所需的執(zhí)行代價(jià)為：

(4)

定義2(作業(yè)流的MakespanM(a)) 作業(yè)流的Makespan是指JOBa中最后一個(gè)任務(wù)執(zhí)行完成所用的時(shí)間：

(5)

其中，a表示作業(yè)流，NTar表示調(diào)度系統(tǒng)為任務(wù)Tk分配的運(yùn)行節(jié)點(diǎn)，Ti→NTar表示在任務(wù)Tk之前所有已分配至節(jié)點(diǎn)NTar上等待執(zhí)行的任務(wù)。

定義3(任務(wù)完成時(shí)間O(s)) 任務(wù)完成時(shí)間是指在調(diào)度算法s驅(qū)動(dòng)下，系統(tǒng)運(yùn)行完成指定任務(wù)集所需要的時(shí)間，因此，定義任務(wù)完成時(shí)間為作業(yè)流集中作業(yè)流的最大Makespan值。

定義4(運(yùn)行節(jié)點(diǎn)負(fù)載L(Nj)) 運(yùn)行節(jié)點(diǎn)負(fù)載即各目標(biāo)運(yùn)行節(jié)點(diǎn)的實(shí)時(shí)負(fù)載情況，可以用所有分配至該運(yùn)行節(jié)點(diǎn)的任務(wù)執(zhí)行代價(jià)之和來表示：

(6)

其中，?Ti→Nj表示所有調(diào)度至Nj的任務(wù)。

定義5(資源利用率U(Nj)) 資源利用率可以有效標(biāo)識(shí)系統(tǒng)資源單位時(shí)間的使用效益，平均資源利用率也是系統(tǒng)資源間負(fù)載狀況的衡量指標(biāo)。系統(tǒng)中運(yùn)算節(jié)點(diǎn)Nj的資源利用率定義為調(diào)度至Nj的所有任務(wù)的運(yùn)行時(shí)間之和與任務(wù)完成時(shí)間的比值：

(7)

設(shè)調(diào)度系統(tǒng)中共有|N|個(gè)運(yùn)算節(jié)點(diǎn)，則調(diào)度算法s的平均資源利用率為:

“堅(jiān)持創(chuàng)新發(fā)展，就是要把創(chuàng)新擺在國(guó)家發(fā)展全局的核心位置，讓創(chuàng)新貫穿國(guó)家一切工作，讓創(chuàng)新在全社會(huì)蔚然成風(fēng)”。以理論創(chuàng)新為引領(lǐng)，大港油田抓住油藏滲流場(chǎng)這個(gè)關(guān)鍵，開展精細(xì)油藏描述地質(zhì)模型升級(jí)研究，建立基于油藏地球物理的地質(zhì)模型研究方法，提高地質(zhì)模型研究精度；攻關(guān)滲流地球物理基礎(chǔ)理論，建立基于時(shí)移的多維的油藏滲流地球物理地質(zhì)模型，提升模型的時(shí)效性；開展?jié)B流場(chǎng)重構(gòu)基礎(chǔ)理論研究，建立多參數(shù)滲流描述模型、多維度流場(chǎng)評(píng)價(jià)模型和多方案的驅(qū)替模型。

(8)

定義6(不公平因子F(s)) 不公平因子是衡量多作業(yè)流調(diào)度算法s公平性的重要指標(biāo)。由于多作業(yè)流共享有限運(yùn)算資源，所以JOBa的調(diào)度長(zhǎng)度很可能比單獨(dú)運(yùn)行JOBa時(shí)要長(zhǎng)，假設(shè)Mown(a)為單獨(dú)運(yùn)行JOBa時(shí)的調(diào)度長(zhǎng)度，則JOBa的Sslowdown為：

Sslowdown(a)=M(a)/Mown(a)

(9)

那么,調(diào)度算法s的不公平因子為：

(10)

(11)

3.2 算法設(shè)計(jì)

在密碼作業(yè)流服務(wù)系統(tǒng)中，數(shù)據(jù)依賴性作業(yè)流與非數(shù)據(jù)依賴性作業(yè)流隨機(jī)交叉并發(fā)，其中數(shù)據(jù)依賴性作業(yè)流的入口任務(wù)和非數(shù)據(jù)依賴性作業(yè)流的各任務(wù)之間不存在關(guān)聯(lián)數(shù)據(jù)，因此該類任務(wù)的處理過程沒有數(shù)據(jù)本地化要求，節(jié)點(diǎn)資源的選擇調(diào)度更加靈活，可以按照任意先后順序?yàn)槠淦ヅ渥顑?yōu)處理節(jié)點(diǎn)；而數(shù)據(jù)依賴性作業(yè)流中非入口任務(wù)與其直接前序任務(wù)之間存在著嚴(yán)格的執(zhí)行順序約束，如果直接前序任務(wù)未能得到及時(shí)處理，則會(huì)嚴(yán)重阻塞該作業(yè)流中所有后續(xù)任務(wù)的執(zhí)行，同時(shí)應(yīng)保障關(guān)聯(lián)數(shù)據(jù)交互過程的安全性，避免數(shù)據(jù)遷移帶來的傳輸時(shí)延和通信代價(jià)。本文調(diào)度算法結(jié)合系統(tǒng)中各計(jì)算節(jié)點(diǎn)的實(shí)時(shí)負(fù)載狀態(tài)，采取數(shù)據(jù)依賴性作業(yè)流和非數(shù)據(jù)依賴性作業(yè)流分類調(diào)度的思想，一方面針對(duì)存在關(guān)聯(lián)數(shù)據(jù)的任務(wù)實(shí)現(xiàn)關(guān)聯(lián)數(shù)據(jù)本地化處理，另一方面針對(duì)不存在關(guān)聯(lián)數(shù)據(jù)的任務(wù)，盡可能實(shí)現(xiàn)系統(tǒng)在作業(yè)流處理中數(shù)據(jù)吞吐率、資源利用率和調(diào)度公平性最大化。調(diào)度結(jié)果在保障系統(tǒng)中所有任務(wù)請(qǐng)求密碼功能正確實(shí)現(xiàn)的基礎(chǔ)上，有效提高密碼服務(wù)系統(tǒng)的安全性與系統(tǒng)性能。

針對(duì)多作業(yè)流共享有限運(yùn)算資源的應(yīng)用問題，為了促進(jìn)各作業(yè)流調(diào)度過程的公平性，在參考HEFT算法的同時(shí)，由于本文算法對(duì)數(shù)據(jù)依賴性作業(yè)流的非入口任務(wù)進(jìn)行了關(guān)聯(lián)數(shù)據(jù)本地化處理，因此避免了用于處理該類任務(wù)不同處理節(jié)點(diǎn)之間關(guān)聯(lián)數(shù)據(jù)的通信代價(jià)，從而在確定不同作業(yè)流以及同一作業(yè)流中各任務(wù)優(yōu)先級(jí)時(shí)，只考慮任務(wù)的執(zhí)行代價(jià):

(12)

(13)

其中,Texit是出口任務(wù)。

策略1對(duì)于數(shù)據(jù)依賴性作業(yè)流的非入口任務(wù)，作業(yè)流調(diào)度單元統(tǒng)一維護(hù)作業(yè)流分配表，用于記錄分配至各處理節(jié)點(diǎn)的作業(yè)流歷史信息，通過在該表中查詢與當(dāng)前作業(yè)流標(biāo)識(shí)j_id所在記錄的處理節(jié)點(diǎn)標(biāo)識(shí)，將當(dāng)前任務(wù)分配至該處理節(jié)點(diǎn)，從而將后繼任務(wù)與其直接前序任務(wù)分配至同一處理節(jié)點(diǎn)上運(yùn)行，實(shí)現(xiàn)了前后任務(wù)關(guān)聯(lián)數(shù)據(jù)的本地化，避免了數(shù)據(jù)交互過程產(chǎn)生的傳輸開銷和安全性威脅。

策略2對(duì)于數(shù)據(jù)依賴性作業(yè)流的入口任務(wù)和非數(shù)據(jù)依賴性作業(yè)流的各任務(wù)，由于該類任務(wù)之間不存在關(guān)聯(lián)數(shù)據(jù)，其處理節(jié)點(diǎn)資源調(diào)度方法比較靈活，因此，通過設(shè)計(jì)良好的調(diào)度策略，可以有效彌補(bǔ)因其他任務(wù)運(yùn)算過程關(guān)聯(lián)數(shù)據(jù)本地化需求而導(dǎo)致的系統(tǒng)性能下降問題。為了提高任務(wù)處理的實(shí)時(shí)性和系統(tǒng)負(fù)載均衡性能，減少任務(wù)的等待時(shí)間，從而將該類任務(wù)分配至當(dāng)前系統(tǒng)時(shí)刻具有最小負(fù)載的運(yùn)行節(jié)點(diǎn)上等待執(zhí)行。

此外，為了減小數(shù)據(jù)依賴性作業(yè)流運(yùn)行節(jié)點(diǎn)的任務(wù)負(fù)載，預(yù)留較為充足的資源用于該類作業(yè)流中后續(xù)任務(wù)的處理。

在利用策略2完成任務(wù)Tk調(diào)度后，目標(biāo)運(yùn)行節(jié)點(diǎn)NTar的負(fù)載更新規(guī)則為：

(14)

4 算法仿真與性能分析

在Windows環(huán)境下，通過C語言編程對(duì)算法進(jìn)行仿真與性能測(cè)試，并在不同的CCR(CCR是通信代價(jià)與執(zhí)行代價(jià)的比值。對(duì)于單位任務(wù)，處理節(jié)點(diǎn)的通信代價(jià)=W(·)×CCR)值設(shè)置下，對(duì)本文算法、HEFT和RR 3種算法的任務(wù)完成時(shí)間、平均資源利用率和不公平因子隨數(shù)據(jù)依賴性作業(yè)流占比的變化情況進(jìn)行了對(duì)比與分析。由于不同請(qǐng)求密碼功能任務(wù)間的調(diào)度過程相似，故設(shè)置具有相同請(qǐng)求密碼功能的任務(wù)隊(duì)列進(jìn)行算法的仿真與性能測(cè)試。

首先生成300個(gè)單位任務(wù)，并將所有任務(wù)隨機(jī)分配給30個(gè)獨(dú)立作業(yè)流，然后根據(jù)數(shù)據(jù)依賴性作業(yè)流占比從中隨機(jī)選擇作業(yè)流修改各自對(duì)應(yīng)的數(shù)據(jù)依賴性標(biāo)識(shí)；設(shè)置處理節(jié)點(diǎn)群中處理節(jié)點(diǎn)數(shù)目為4，對(duì)于單位任務(wù)各節(jié)點(diǎn)的執(zhí)行代價(jià)W(·)∈{30,40,50,60}；作業(yè)流任務(wù)集各屬性設(shè)置方法如表1所示。

Table 1 Job stream task property settings

4.1 任務(wù)完成時(shí)間

按照上述方法設(shè)置處理節(jié)點(diǎn)群中各節(jié)點(diǎn)及任務(wù)屬性，并當(dāng)CCR值為0.1，0.2,0.3時(shí)，分別測(cè)試3種算法的任務(wù)完成時(shí)間(單位時(shí)間個(gè)數(shù))隨數(shù)據(jù)依賴性作業(yè)流占比的變化情況，如圖3所示。與其他2種調(diào)度算法相比，本文算法對(duì)數(shù)據(jù)依賴性任務(wù)進(jìn)行了關(guān)聯(lián)數(shù)據(jù)本地化處理，在任務(wù)的運(yùn)算過程中產(chǎn)生的通信代價(jià)為0，有效避免了CCR值對(duì)服務(wù)系統(tǒng)性能的影響。此外，與RR算法相比，本文算法更加精確地考慮了處理節(jié)點(diǎn)群中各節(jié)點(diǎn)的性能異構(gòu)，從執(zhí)行代價(jià)角度衡量了各節(jié)點(diǎn)的實(shí)時(shí)負(fù)載情況，顯著減少了服務(wù)系統(tǒng)的任務(wù)完成時(shí)間；與HEFT算法相比，本文算法在完成數(shù)據(jù)依賴性作業(yè)流入口任務(wù)的調(diào)度后，采用提前預(yù)算完整作業(yè)流執(zhí)行代價(jià)的方式，預(yù)留較為充足的資源用于該類作業(yè)流中后續(xù)任務(wù)的處理，在減少任務(wù)完成時(shí)間的同時(shí)，避免了數(shù)據(jù)依賴性作業(yè)流占比對(duì)服務(wù)系統(tǒng)性能的影響，提高了系統(tǒng)的穩(wěn)定性。

Figure 3 Task completion time changes with the proportion of data-dependent job streams圖3 任務(wù)完成時(shí)間隨數(shù)據(jù)依賴性作業(yè)流占比的變化

4.2 平均資源利用率

保持運(yùn)行節(jié)點(diǎn)及任務(wù)屬性不變，當(dāng)CCR值為0.1,0.2,0.3時(shí)，分別測(cè)試3種算法的平均資源利用率隨數(shù)據(jù)依賴性作業(yè)流占比的變化情況，如圖4所示。同樣地，由于關(guān)聯(lián)數(shù)據(jù)本地化的引入，CCR值不影響本文算法的平均資源利用率。通過執(zhí)行代價(jià)標(biāo)量節(jié)點(diǎn)負(fù)載和提前預(yù)算數(shù)據(jù)依賴性作業(yè)流執(zhí)行代價(jià)的方式，本文算法有效改善了異構(gòu)系統(tǒng)中各處理節(jié)點(diǎn)間的負(fù)載均衡，提高了系統(tǒng)整體資源利用率。

Figure 4 Average resource utilization rate changes with the proportion of data-dependent job streams圖4 平均資源利用率隨數(shù)據(jù)依賴性作業(yè)流占比的變化

4.3 不公平因子

保持運(yùn)行節(jié)點(diǎn)及任務(wù)屬性不變，當(dāng)CCR值為0.1,0.2,0.3時(shí)，分別測(cè)試3種算法的不公平因子隨數(shù)據(jù)依賴性作業(yè)流占比的變化情況，如圖5所示。在多作業(yè)流共享有限運(yùn)算資源的環(huán)境中，相比于RR算法，本文算法的不公平因子顯著降低，并且受數(shù)據(jù)依賴性作業(yè)流占比的影響較小，具有較好的穩(wěn)定性，但略高于HEFT算法，這是因?yàn)?種算法在處理單一作業(yè)流時(shí)的工作過程和調(diào)度結(jié)果完全一致，而在多作業(yè)流場(chǎng)景中，本文算法具有更小的Makespan，這是由于HEFT算法在該場(chǎng)景下是以增加任務(wù)完成時(shí)間為代價(jià)導(dǎo)致的。

Figure 5 Unfair factor changes with the proportion of data-dependent job streams圖5 不公平因子隨數(shù)據(jù)依賴性作業(yè)流占比的變化

5 結(jié)束語

針對(duì)云密碼服務(wù)系統(tǒng)中多作業(yè)流、多算法、多命令、多工作模式隨機(jī)交叉情況下的密碼應(yīng)用需求，本文提出了一種基于關(guān)聯(lián)數(shù)據(jù)本地化的密碼作業(yè)流調(diào)度算法，避免了因數(shù)據(jù)依賴性任務(wù)間關(guān)聯(lián)數(shù)據(jù)的交互而導(dǎo)致的系統(tǒng)通信性能開銷，進(jìn)一步提高了處理數(shù)據(jù)的安全性，為系統(tǒng)設(shè)計(jì)者簡(jiǎn)化了密鑰匹配和中間狀態(tài)管理的難度。此外，仿真實(shí)驗(yàn)表明，該算法在提高系統(tǒng)任務(wù)執(zhí)行效率、資源利用率和公平性等方面具有顯著優(yōu)勢(shì)，并且在不同CCR值和數(shù)據(jù)依賴性作業(yè)流占比情況下表現(xiàn)出了良好的穩(wěn)定性。