混合關(guān)鍵任務(wù)可靠調(diào)度方法與調(diào)度性分析

景維鵬，霍帥起，陳廣勝，劉亞秋

(1. 東北林業(yè)大學(xué) 信息與計(jì)算機(jī)工程學(xué)院，黑龍江 哈爾濱 150040; 2. 黑龍江省林業(yè)生態(tài)大數(shù)據(jù)存儲(chǔ)與高性能(云)計(jì)算工程研究中心，黑龍江 哈爾濱 150040)

?

混合關(guān)鍵任務(wù)可靠調(diào)度方法與調(diào)度性分析

景維鵬1,2，霍帥起1,2，陳廣勝1,2，劉亞秋1,2

(1. 東北林業(yè)大學(xué) 信息與計(jì)算機(jī)工程學(xué)院，黑龍江 哈爾濱 150040; 2. 黑龍江省林業(yè)生態(tài)大數(shù)據(jù)存儲(chǔ)與高性能(云)計(jì)算工程研究中心，黑龍江 哈爾濱 150040)

為了解決云計(jì)算環(huán)境下混合關(guān)鍵性任務(wù)的可靠調(diào)度問題，提出了一種基于主副版本兩階段的混合關(guān)鍵任務(wù)可靠調(diào)度方法．算法首先對(duì)需要調(diào)度的混合關(guān)鍵性任務(wù)進(jìn)行優(yōu)先級(jí)劃分，按照調(diào)度截止期最短的原則將主版本任務(wù)調(diào)度到目標(biāo)虛擬機(jī)上，對(duì)副版本任務(wù)按照復(fù)制成本最低的原則使用重疊方法進(jìn)行調(diào)度；再對(duì)調(diào)度到不同虛擬機(jī)上的主副版本任務(wù)進(jìn)行可調(diào)度分析，對(duì)于不能滿足分析的任務(wù)啟動(dòng)更高關(guān)鍵性等級(jí)進(jìn)行處理．實(shí)驗(yàn)結(jié)果表明了混合關(guān)鍵任務(wù)可靠調(diào)度方法具有較高的可靠性和負(fù)載平衡能力．

云計(jì)算;混合關(guān)鍵性任務(wù);可靠調(diào)度;主副版本

隨著計(jì)算機(jī)和網(wǎng)絡(luò)技術(shù)的迅猛發(fā)展以及數(shù)據(jù)獲取手段的不斷豐富，在越來越多的領(lǐng)域出現(xiàn)了對(duì)海量、高速數(shù)據(jù)進(jìn)行實(shí)時(shí)處理的需求．例如在工程及運(yùn)輸領(lǐng)域?qū)崟r(shí)地對(duì)工作部件在運(yùn)行過程中產(chǎn)生的數(shù)據(jù)進(jìn)行有效的分析，可以及時(shí)了解部件的當(dāng)前工作狀態(tài)；在運(yùn)輸和生產(chǎn)運(yùn)行環(huán)節(jié)出現(xiàn)故障后，采用某些特定的解決措施，這樣有利于對(duì)作業(yè)環(huán)境中風(fēng)險(xiǎn)的控制[1]; 又如，在林業(yè)遙感應(yīng)用中需要對(duì)實(shí)時(shí)的遙感數(shù)據(jù)進(jìn)行處理、分析，從而為林業(yè)主管部門決策提供依據(jù)，這也需要對(duì)數(shù)據(jù)進(jìn)行實(shí)時(shí)、細(xì)粒度的處理．可以看到，這類具有海量數(shù)據(jù)分析與要求的云計(jì)算系統(tǒng)不但能處理周期的任務(wù)的需要，同時(shí)也要滿足系統(tǒng)偶發(fā)任務(wù)的實(shí)時(shí)處理的需要，這些任務(wù)有著不同的關(guān)鍵性等級(jí)，這類任務(wù)被稱之為實(shí)時(shí)關(guān)鍵任務(wù)，因此需要云計(jì)算系統(tǒng)依據(jù)任務(wù)特點(diǎn)能夠有效完成這類任務(wù)的調(diào)度．

對(duì)于實(shí)時(shí)任務(wù)的調(diào)度問題，文獻(xiàn)[2]已證明最早期限優(yōu)先(Earliest Deadline First，EDF)方法是實(shí)時(shí)任務(wù)調(diào)度的最佳調(diào)度算法；文獻(xiàn)[3]則表明了EDF算法在混合關(guān)鍵任務(wù)系統(tǒng)中的可調(diào)度性能較差；針對(duì)目前已有的混合關(guān)鍵任務(wù)的調(diào)度算法[4-5]存在不同關(guān)鍵級(jí)別任務(wù)調(diào)度不均衡的問題，一些改進(jìn)這種不均衡問題的方法相繼被提出[6-7]．然而這些算法的可調(diào)度性都不理想．文獻(xiàn)[8]通過計(jì)算任務(wù)的資源利用率來確定是否在虛擬截止期前使用EDF調(diào)度算法，從而提高調(diào)度算法的可調(diào)度性；文獻(xiàn)[9]則在文獻(xiàn)[8]的基礎(chǔ)上提出可變虛擬截止期的調(diào)度算法EY來平衡系統(tǒng)在不同的關(guān)鍵等級(jí)可調(diào)度性；文獻(xiàn)[10]提出了一種針對(duì)混合關(guān)鍵偶發(fā)任務(wù)的截止期調(diào)整方法，該方法能夠在任務(wù)的高關(guān)鍵等級(jí)和低關(guān)鍵等級(jí)通過調(diào)整相對(duì)釋放時(shí)間進(jìn)行調(diào)整，從而提高系統(tǒng)的可調(diào)度性．

針對(duì)多處理器系統(tǒng)中的混合關(guān)鍵任務(wù)性實(shí)時(shí)調(diào)度問題，文獻(xiàn)[11]將不同關(guān)鍵等級(jí)任務(wù)進(jìn)行封裝，然后在多虛擬機(jī)系統(tǒng)利用任務(wù)的優(yōu)先級(jí)進(jìn)行調(diào)度；文獻(xiàn)[12]將EY算法進(jìn)行擴(kuò)展，使其可以適用于多處理器系統(tǒng)的混合關(guān)鍵實(shí)時(shí)任務(wù)的調(diào)度；文獻(xiàn)[13] 提出了一種中央處理器(Central Processing Unit，CPU)速率可變的混合關(guān)鍵實(shí)時(shí)任務(wù)多處理器調(diào)度方法，該方法能有效提高虛擬機(jī)利用率．然而上述方法更多將調(diào)度混合關(guān)鍵實(shí)時(shí)任務(wù)的目標(biāo)放到任務(wù)的不同關(guān)鍵等級(jí)情況下的可調(diào)度性方面，忽略了任務(wù)在可靠性、服務(wù)質(zhì)量(Quality of Service，QoS)、安全性等方面的要求．目前，針對(duì)混合關(guān)鍵任務(wù)性實(shí)時(shí)任務(wù)調(diào)度的云計(jì)算系統(tǒng)的可靠調(diào)度問題研究較少，而在云計(jì)算環(huán)境下解決任務(wù)可靠調(diào)度的方法中，基于主副版本的調(diào)度方法被認(rèn)為是一種簡單而又高效的方法．

對(duì)于單關(guān)鍵性任務(wù)的實(shí)時(shí)調(diào)度通?？梢允褂萌终{(diào)度和劃分調(diào)度兩種方法[14]: 全局調(diào)度方法是指在任務(wù)執(zhí)行時(shí)可以被調(diào)度到任意的虛擬機(jī)上執(zhí)行，而劃分調(diào)度方法是在執(zhí)行前將任務(wù)劃分到指定的虛擬機(jī)，在執(zhí)行時(shí)則就在已指定的虛擬機(jī)上執(zhí)行．文獻(xiàn)[15]已證明了劃分調(diào)度方法具有更好的可調(diào)度性．綜上，筆者提出一種滿足混合關(guān)鍵實(shí)時(shí)任務(wù)可靠劃分調(diào)度策略．該策略能在有效平衡不同關(guān)鍵等級(jí)任務(wù)可調(diào)度性前提下，提高調(diào)度系統(tǒng)的可靠性．

1 任務(wù)模型

考慮典型的異構(gòu)虛擬機(jī)和實(shí)時(shí)任務(wù)集構(gòu)成的云計(jì)算系統(tǒng)．以下進(jìn)行形式化定義:

定義1 云計(jì)算系統(tǒng)一組虛擬機(jī)集合描述為P={P1，P2，…，PM}，其中M代表虛擬機(jī)數(shù)．

定義2 對(duì)于混合關(guān)鍵實(shí)時(shí)任務(wù)模型，與文獻(xiàn)[17]的相同．集合v=(v1，v2，v3，…，vN)，表示系統(tǒng)中的一組混合關(guān)鍵任務(wù)．與傳統(tǒng)的隨機(jī)任務(wù)不同，將每個(gè)關(guān)鍵性混合關(guān)鍵任務(wù)定義為一個(gè)四元組，其中，Ti為實(shí)時(shí)偶發(fā)任務(wù)的周期，即兩個(gè)相鄰任務(wù)的最小時(shí)間間隔; Di表示任務(wù)的相對(duì)截止期; ζi表示作業(yè)的關(guān)鍵性等級(jí); Ci表示任務(wù)的最差執(zhí)行時(shí)間．為了簡化系統(tǒng)的描述和算法，假設(shè)系統(tǒng)中存在兩個(gè)關(guān)鍵性作業(yè)，其中Ci(tHI)和Ci(tLO)分別表示在高、低兩個(gè)關(guān)鍵等級(jí)時(shí)作業(yè)在所有異構(gòu)虛擬機(jī)上的最差執(zhí)行時(shí)間，通常情況下，Ci(tLO)< Ci(tHI)，任務(wù)的利用率分別被定義為 ui(tLO)= Ci(tLO)/Ti和 ui(tHI)= Ci(tHI)/Ti．

定義3 混合關(guān)鍵實(shí)時(shí)任務(wù)vi的絕對(duì)截止期 di= ri+ Di，其中ri表示任務(wù)的釋放時(shí)間，任務(wù)完成時(shí)間表示為fi，三者的關(guān)系為 ri≤ fi≤ di．

2 混合關(guān)鍵任務(wù)可靠調(diào)度策略

在調(diào)度器模型的基礎(chǔ)上，使用主副版本技術(shù)提出一種適用于混合關(guān)鍵實(shí)時(shí)任務(wù)調(diào)度的可靠調(diào)度策略及可靠性調(diào)度方法．

2.1 主副版本任務(wù)調(diào)度

在混合關(guān)鍵任務(wù)可靠調(diào)度方法(Mixed-Criticality Reliability Scheduling Strategy，MCRSS)中，任務(wù)的優(yōu)先級(jí)是按照關(guān)鍵性(關(guān)鍵性等級(jí))的降序排序，對(duì)于具有相同關(guān)鍵性等級(jí)的任務(wù)則按照任務(wù)的平均利用率的降序排列進(jìn)行調(diào)度．調(diào)度器每次為混合關(guān)鍵任務(wù)選擇虛擬機(jī)時(shí)，按照固定的順序在虛擬機(jī)中選擇第1個(gè)滿足條件的虛擬機(jī)進(jìn)行調(diào)度．調(diào)度主版本任務(wù)的目標(biāo)是確認(rèn)主版本任務(wù)可以盡早地完成，因此，在云計(jì)算環(huán)境中選擇任務(wù)執(zhí)行時(shí)間最短的虛擬機(jī)進(jìn)行調(diào)度，因而

(1) 副版本任務(wù)不能與其主版本任務(wù)調(diào)度到相同的虛擬機(jī)上．

2.2 可調(diào)度性分析

文獻(xiàn)[8]對(duì)混合關(guān)鍵實(shí)時(shí)任務(wù)在高、低兩個(gè)關(guān)鍵級(jí)的虛擬截止期做了規(guī)定．由于不同關(guān)鍵等級(jí)的任務(wù)被調(diào)度到不同虛擬機(jī)上，首先是按照每個(gè)任務(wù)的低關(guān)鍵模式進(jìn)行執(zhí)行，Di(tLO)、Ci(tLO)分別表示任務(wù)vi在低關(guān)鍵模式下的截止期和任務(wù)的完成時(shí)間，低關(guān)鍵模式下的任務(wù)vi的虛擬截止期為

其中，t為當(dāng)前時(shí)間．在低關(guān)鍵模式下的主副版本任務(wù)在虛擬機(jī)上的優(yōu)先級(jí)是按照其釋放的時(shí)間ri與虛擬截止期之和，即

在虛擬機(jī)上隊(duì)列中，任務(wù)的主版本與副版本任務(wù)按照式(3)所示的優(yōu)先級(jí)進(jìn)行調(diào)度，相同情況下副版本任務(wù)的優(yōu)先級(jí)高于主版本優(yōu)先級(jí)，可以按照搶占的方式搶占當(dāng)前優(yōu)先級(jí)低的任務(wù)，并插入所分配虛擬機(jī)的就緒隊(duì)列中等待調(diào)度．在低關(guān)鍵模式的可靠性檢測過程中，首先對(duì)主版本任務(wù)的任務(wù)完成時(shí)間與虛擬截止期進(jìn)行判斷，即任務(wù)vi的主版本任務(wù)的最晚開始時(shí)間應(yīng)滿足:

當(dāng)在云計(jì)算系統(tǒng)中正在執(zhí)行的任務(wù)不能在任務(wù)的虛擬截止期之前完成，或是其開設(shè)時(shí)間小于式(4)的開始時(shí)間時(shí)，則系統(tǒng)有兩種模式可供選擇，一種是系統(tǒng)進(jìn)入到高關(guān)鍵模式，另一種則是系統(tǒng)開設(shè)調(diào)度其副版本任務(wù)，下面分別就兩種情況的時(shí)間開銷進(jìn)行說明．

如果任務(wù)切換到高關(guān)鍵性模式，則所有在該虛擬機(jī)隊(duì)列中等待執(zhí)行的作業(yè)將被終止執(zhí)行，并被清除出隊(duì)列．此時(shí)系統(tǒng)中保留一個(gè)正在執(zhí)行作業(yè)，該作業(yè)的執(zhí)行時(shí)間為

高關(guān)鍵模式下的任務(wù)vi的虛擬截止期為

高關(guān)鍵性作業(yè)的優(yōu)先級(jí)將被修改作業(yè)的釋放時(shí)間與高關(guān)鍵模式下的虛擬截止期之和為式(7)所示，系統(tǒng)按照該優(yōu)先級(jí)將任務(wù)插入到高關(guān)鍵性作業(yè)優(yōu)先級(jí)隊(duì)列進(jìn)行調(diào)度．

進(jìn)行不同關(guān)鍵等級(jí)模式切換的時(shí)間開銷為

因此，其副版本任務(wù)的最晚開始執(zhí)行時(shí)間為

3 實(shí)驗(yàn)結(jié)果與分析

通過可調(diào)度任務(wù)數(shù)量集與總?cè)蝿?wù)數(shù)量的百分比，以及不同失效概率下云計(jì)算系統(tǒng)的可靠性這兩個(gè)方面來驗(yàn)證MCRSS算法的性能．仿真實(shí)驗(yàn)采用與文獻(xiàn)[8]中相同的混合關(guān)鍵任務(wù)的生成方法，隨機(jī)生成的偶發(fā)混合關(guān)鍵任務(wù)的具體參數(shù)設(shè)置如下:

(1) 每組測試中實(shí)時(shí)周期任務(wù)集合100≤N≤1000;

(2) 測試的任務(wù)是兩個(gè)關(guān)鍵等級(jí)即高關(guān)鍵等級(jí)HI和低關(guān)鍵等級(jí)LO;

(4) 任務(wù)的執(zhí)行時(shí)間在[1，α Ti]之間均勻分布，α值分別設(shè)為0.2，0.8．實(shí)驗(yàn)重復(fù)進(jìn)行10次，以10次的平均值為最終結(jié)果;

通過兩組實(shí)驗(yàn)測試實(shí)時(shí)關(guān)鍵任務(wù)集的可調(diào)度性．兩組實(shí)驗(yàn)分別選取隨機(jī)生成的實(shí)時(shí)關(guān)鍵任務(wù)隊(duì)列，其中任務(wù)集的規(guī)模分別是100個(gè)和 1 000 個(gè)．測試在云計(jì)算平臺(tái)計(jì)算節(jié)點(diǎn)數(shù)為20情況下，MCRSS算法與MC-MP-EDF[17]以及P-EDF[17]在不同雙關(guān)鍵實(shí)時(shí)任務(wù)的平均利用率條件下，任務(wù)集的可接受比率．

圖1表明在任務(wù)集為100情況下，MCRSS、MC-MP-EDF和P-EDF算法相比，能有效提高任務(wù)的可接受比率，這是由于MCRSS采用主副兩個(gè)版本任務(wù)的虛擬截止期的測試，同時(shí)采用主副版本兩個(gè)版本的調(diào)度，也能有效提高算法的可調(diào)度性．圖2表明在任務(wù)集為 1 000 情況下，MCRSS與MC-MP-EDF和P-EDF算法的可調(diào)度性．可以看到，隨著任務(wù)數(shù)量的增加，任務(wù)集的可調(diào)度性降低，但是MCRSS依然有較大優(yōu)勢．MC-MP-EDF和P-EDF性能相差不多，原因是兩種算法選用完全相同任務(wù)的劃分方法．

圖1 任務(wù)集為100的可接受比率(可調(diào)度性)圖2 任務(wù)集為1000的可接受比率(可調(diào)度性)

通過兩組實(shí)驗(yàn)來測試在不同的負(fù)載情況下，任務(wù)集為[100，1 000] 的實(shí)時(shí)關(guān)鍵任務(wù)的性能．所有實(shí)時(shí)關(guān)鍵任務(wù)的最大負(fù)載 α= max{U1，U2，…，UN}，其中 Ui= Ci/ Ti; 性能度量標(biāo)準(zhǔn)為給定任務(wù)集進(jìn)行調(diào)度所需虛擬機(jī)數(shù)與任務(wù)集負(fù)載和的比值，即定義 U= U1+ U2+ …+ UN．α為0.8，表示任務(wù)的緊迫度較高；α為0.2，則緊迫度較低．由于任務(wù)的最大負(fù)載與負(fù)載和已知，設(shè)M為任務(wù)的實(shí)際完成時(shí)間．在主副版本的調(diào)度過程中，任務(wù)的實(shí)際完成時(shí)間，應(yīng)為其副版本任務(wù)的執(zhí)行時(shí)間(Makespan)．由圖3和圖4可以看到，隨著任務(wù)的不斷增加，算法MCRSS的 M/U 小于FTRMFF[18]和TPFTRM[18]兩種方法的．其原因是MCRSS能依據(jù)主版本任務(wù)運(yùn)行的情況，使用被動(dòng)和重疊的方式進(jìn)行調(diào)度，因此其具有較好的性能．而FTRMFF采用固定的重疊方式，而TPFTRM采用可調(diào)節(jié)的副版本重疊方式，因此其性能優(yōu)于FTRMFF．

圖3 α=02時(shí)，3種算法性能比較圖4 α=08時(shí)，3種算法性能比較

4 結(jié) 束 語

筆者提出了一種在云計(jì)算系統(tǒng)中針對(duì)混合關(guān)鍵任務(wù)的主副版本調(diào)度策略．該策略能有效地提高混合關(guān)鍵任務(wù)的調(diào)度性能和可靠性．實(shí)驗(yàn)結(jié)果表明， MCRSS的性能優(yōu)于其它算法，適合于異構(gòu)集群環(huán)境，尤其是任務(wù)達(dá)到速度變化較大，節(jié)點(diǎn)動(dòng)態(tài)加入或退出集群等情況，使得系統(tǒng)具有較強(qiáng)的靈活性和可靠性．

[1] 崔星燦, 禹曉輝, 劉洋, 等. 分布式流處理技術(shù)綜述[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 52(2): 318-332.

CUI Xingcan, YU Xiaohui, LIU Yang, et al. Distributed Stream Processing: a Survey[J]. Journal of Computer Research and Development, 2015, 52 (2): 318-332.

[2]BARUAH S, BONIFACI V, D'ANGELO G, et al. Preemptive Uniprocess or Scheduling of Mixed-criticality Sporadic Task Systems[J]. Journal of the ACM, 2015, 62(2): 14.

[3]VESTAL S. Preemptive Scheduling of Multi-criticality Systems with Varying Degrees of Execution Time Assurance[C]//Proceedings of the 28th IEEE International Real-time Systems Symposium. Piscataway: IEEE, 2007: 239-243.

[4]DE NIZ D, LAKSHMANAN K, RAJKUMAR R. On the Scheduling of Mixed-criticality Real-time Task Sets[C]//Proceedings of the Real-time Systems Symposium. Piscataway: IEEE, 2009: 291-300.

[5]LI H, BARUAH S. An Algorithm for Scheduling Certifiable Mixed-criticality Sporadic Task Systems[C]//Proceedings of the 31th Real-time Systems Symposium. Piscataway: IEEE, 2010: 183-192.

[6]BARUAH S K, BUMS A, DAVIS R I. Response-time Analysis for Mixed Criticality Systems[C]//Proceedings of the 32nd Real-time Systems Symposium. Piscataway: IEEE, 2011: 34-43.

[7]BURNS A, FLEMING T, BARUAH S. Cyclic Executives, Multi-core Platforms and Mixed Criticality Applications[C]//Proceedings of the 27th Euromicro Conference on Real-time Systems,. Piscataway: IEEE, 2015: 3-12.

[8]BARUAH S K, BONIFACI V, D’ANGELO G, et al. Mixed-criticality Scheduling of Sporadic Task Systems[C]//Lecture Notes in Computer Science: 6942 LNCS. Heidelberg: Springer Verlag, 2011: 555-566.

[9]EKBERG P, WANG Y. Outstanding Paper Award: Bounding and Shaping the Demand of Mixed-criticality Sporadic Tasks[C]//Proceedings of the 24th Euromicro Conference on Real-time Systems. Piscataway: IEEE Computer Society, 2012: 135-144.

[10]EKBERG P, WANG Y. Bounding and Shaping the Demand of Generalized Mixed-criticality Sporadic Task Systems[J]. Real-time Systems, 2014, 50(1): 48-86.

[11]BARUAH S, BONIFACI V, D’ANGELO G, et al. Scheduling Real-time Mixed-criticality Jobs[J]. IEEE Transactions on Computers, 2012, 61(8): 1140-1152.

[12]BARUAH S, CHATTOPADHYAY B, LI H, et al. Mixed-criticality Scheduling on Multiprocessors [J]. Real-time Systems, 2014, 50(1): 142-177.

[13]BARUAH S. Implementing Mixed-criticality Synchronous Reactive Programs Upon Uniprocessor Platforms [J]. Real-time Systems, 2014, 50(3): 317-341.

[14]CARPENTER J, FUNK S, HOLMAN P, et al. A Categorization of Real-time Multiprocessor Scheduling Problems and Algorithms[EB/OL].[2015-02-20]. http://www.docin.com/p-902276394.html.

[15]BASTONI A, BRANDENBURG B B, ANDERSON J H. An Empirical Comparison of Global, Partitioned, and Clustered Multiprocessor EDF Schedulers[C]//Proceedings of the 31st IEEE Real-time Systems Symposium. Piscataway: IEEE, 2010: 14-24.

[16]王吉, 包衛(wèi)東, 朱曉敏. 虛擬化云平臺(tái)中實(shí)時(shí)任務(wù)容錯(cuò)調(diào)度算法研究[J]. 通信學(xué)報(bào), 2014, 35(10): 171-180.

WANG Ji, BAO Weidong, ZHU Xiaomin. Fault-tolerant Scheduling Alorithm for Real-time Tasks in Virtualized Cloud[J]. Journal on Communications, 2014, 35(10):171-180.

[17]谷傳才, 關(guān)楠, 于金銘, 等. 多處理器混合關(guān)鍵性系統(tǒng)中的劃分調(diào)度策略[J].軟件學(xué)報(bào), 2014, 25(2): 284-297.

GU Chuancai, GUAN Nan, YU Jinming, et al. Partitioned Scheduling Policies on Multi-processor Mixed-criticality System[J]. Journal of Software, 2014, 25(2): 284-297.

[18]AL-OMARI R, SOMANI A K, MANIMARAN G. An Adaptive Scheme for Fault-tolerant Scheduling of Soft Real-time Tasks in Multiprocessor Systems[J]. Journal of Parallel and Distributed Computing, 2005, 65(5): 595-608.

(編輯：王 瑞)

Novel mixed-criticality reliability scheduling strategy and schedulability test

JINGWeipeng1,2，HUOShuaiqi1,2，CHENGuangsheng1,2，LIUYaqiu1,2

(1. The College of Information and Computer Engineering, Northeast Forestry Univ., Harbin 150040, China; 2. Heilongjiang Province Engineering Technology Research Center For Forestry Ecological Big Data Storage and High Performance (Cloud) Computing, Harbin 150040, China)

In order to solve the reliable scientific workflow scheduling problem for the Mixed-Criticality task in cloud computing, we proposed the Mixed-Criticality reliability scheduling strategy (MCRSS) based on Primary/Backup. First, the priority of the primary Mixed-Criticality task is determined and the task is scheduled for the virtual processor with the deadline being the shortest, the backup is the virtual processor with the cost of copy being the lowest. Second, the schedulability test of the primary and backup task are proposed. If the task does not satisfy the schedulability test, then the task will change to high criticality. Experimental results show that the MCRSS algorithm is of high reliability and load balancing capabilities.

cloud computing;mix-criticality task;reliable scheduling;primary/backup

2016-03-16

中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(2572014EB05-4)；黑龍江省自然科學(xué)基金重點(diǎn)資助項(xiàng)目(ZD201403)；林業(yè)公益性行業(yè)科研專項(xiàng)經(jīng)費(fèi)資助項(xiàng)目(201504307)

景維鵬(1979-)，男，副教授，博士，E-mail: nefujwp@163.com．

10.3969/j.issn.1001-2400.2016.06.027

TP306

A

1001-2400(2016)06-0158-06