混合关键任务可靠调度方法与调度性分析

景维鹏，霍帅起，陈广胜，刘亚秋

(1. 东北林业大学 信息与计算机工程学院，黑龙江 哈尔滨 150040; 2. 黑龙江省林业生态大数据存储与高性能(云)计算工程研究中心，黑龙江 哈尔滨 150040)



混合关键任务可靠调度方法与调度性分析

景维鹏1,2，霍帅起1,2，陈广胜1,2，刘亚秋1,2

(1. 东北林业大学 信息与计算机工程学院，黑龙江 哈尔滨 150040; 2. 黑龙江省林业生态大数据存储与高性能(云)计算工程研究中心，黑龙江 哈尔滨 150040)

为了解决云计算环境下混合关键性任务的可靠调度问题，提出了一种基于主副版本两阶段的混合关键任务可靠调度方法．算法首先对需要调度的混合关键性任务进行优先级划分，按照调度截止期最短的原则将主版本任务调度到目标虚拟机上，对副版本任务按照复制成本最低的原则使用重叠方法进行调度；再对调度到不同虚拟机上的主副版本任务进行可调度分析，对于不能满足分析的任务启动更高关键性等级进行处理．实验结果表明了混合关键任务可靠调度方法具有较高的可靠性和负载平衡能力．

云计算;混合关键性任务;可靠调度;主副版本

随着计算机和网络技术的迅猛发展以及数据获取手段的不断丰富，在越来越多的领域出现了对海量、高速数据进行实时处理的需求．例如在工程及运输领域实时地对工作部件在运行过程中产生的数据进行有效的分析，可以及时了解部件的当前工作状态；在运输和生产运行环节出现故障后，采用某些特定的解决措施，这样有利于对作业环境中风险的控制[1]; 又如，在林业遥感应用中需要对实时的遥感数据进行处理、分析，从而为林业主管部门决策提供依据，这也需要对数据进行实时、细粒度的处理．可以看到，这类具有海量数据分析与要求的云计算系统不但能处理周期的任务的需要，同时也要满足系统偶发任务的实时处理的需要，这些任务有着不同的关键性等级，这类任务被称之为实时关键任务，因此需要云计算系统依据任务特点能够有效完成这类任务的调度．

对于实时任务的调度问题，文献[2]已证明最早期限优先(Earliest Deadline First，EDF)方法是实时任务调度的最佳调度算法；文献[3]则表明了EDF算法在混合关键任务系统中的可调度性能较差；针对目前已有的混合关键任务的调度算法[4-5]存在不同关键级别任务调度不均衡的问题，一些改进这种不均衡问题的方法相继被提出[6-7]．然而这些算法的可调度性都不理想．文献[8]通过计算任务的资源利用率来确定是否在虚拟截止期前使用EDF调度算法，从而提高调度算法的可调度性；文献[9]则在文献[8]的基础上提出可变虚拟截止期的调度算法EY来平衡系统在不同的关键等级可调度性；文献[10]提出了一种针对混合关键偶发任务的截止期调整方法，该方法能够在任务的高关键等级和低关键等级通过调整相对释放时间进行调整，从而提高系统的可调度性．

针对多处理器系统中的混合关键任务性实时调度问题，文献[11]将不同关键等级任务进行封装，然后在多虚拟机系统利用任务的优先级进行调度；文献[12]将EY算法进行扩展，使其可以适用于多处理器系统的混合关键实时任务的调度；文献[13] 提出了一种中央处理器(Central Processing Unit，CPU)速率可变的混合关键实时任务多处理器调度方法，该方法能有效提高虚拟机利用率．然而上述方法更多将调度混合关键实时任务的目标放到任务的不同关键等级情况下的可调度性方面，忽略了任务在可靠性、服务质量(Quality of Service，QoS)、安全性等方面的要求．目前，针对混合关键任务性实时任务调度的云计算系统的可靠调度问题研究较少，而在云计算环境下解决任务可靠调度的方法中，基于主副版本的调度方法被认为是一种简单而又高效的方法．

对于单关键性任务的实时调度通常可以使用全局调度和划分调度两种方法[14]: 全局调度方法是指在任务执行时可以被调度到任意的虚拟机上执行，而划分调度方法是在执行前将任务划分到指定的虚拟机，在执行时则就在已指定的虚拟机上执行．文献[15]已证明了划分调度方法具有更好的可调度性．综上，笔者提出一种满足混合关键实时任务可靠划分调度策略．该策略能在有效平衡不同关键等级任务可调度性前提下，提高调度系统的可靠性．

1 任务模型

考虑典型的异构虚拟机和实时任务集构成的云计算系统．以下进行形式化定义:

定义1 云计算系统一组虚拟机集合描述为P={P1，P2，…，PM}，其中M代表虚拟机数．

定义2 对于混合关键实时任务模型，与文献[17]的相同．集合v=(v1，v2，v3，…，vN)，表示系统中的一组混合关键任务．与传统的随机任务不同，将每个关键性混合关键任务定义为一个四元组，其中，Ti为实时偶发任务的周期，即两个相邻任务的最小时间间隔; Di表示任务的相对截止期; ζi表示作业的关键性等级; Ci表示任务的最差执行时间．为了简化系统的描述和算法，假设系统中存在两个关键性作业，其中Ci(tHI)和Ci(tLO)分别表示在高、低两个关键等级时作业在所有异构虚拟机上的最差执行时间，通常情况下，Ci(tLO)< Ci(tHI)，任务的利用率分别被定义为 ui(tLO)= Ci(tLO)/Ti和 ui(tHI)= Ci(tHI)/Ti．

定义3 混合关键实时任务vi的绝对截止期 di= ri+ Di，其中ri表示任务的释放时间，任务完成时间表示为fi，三者的关系为 ri≤ fi≤ di．

2 混合关键任务可靠调度策略

在调度器模型的基础上，使用主副版本技术提出一种适用于混合关键实时任务调度的可靠调度策略及可靠性调度方法．

2.1 主副版本任务调度

在混合关键任务可靠调度方法(Mixed-Criticality Reliability Scheduling Strategy，MCRSS)中，任务的优先级是按照关键性(关键性等级)的降序排序，对于具有相同关键性等级的任务则按照任务的平均利用率的降序排列进行调度．调度器每次为混合关键任务选择虚拟机时，按照固定的顺序在虚拟机中选择第1个满足条件的虚拟机进行调度．调度主版本任务的目标是确认主版本任务可以尽早地完成，因此，在云计算环境中选择任务执行时间最短的虚拟机进行调度，因而

(1) 副版本任务不能与其主版本任务调度到相同的虚拟机上．

2.2 可调度性分析

文献[8]对混合关键实时任务在高、低两个关键级的虚拟截止期做了规定．由于不同关键等级的任务被调度到不同虚拟机上，首先是按照每个任务的低关键模式进行执行，Di(tLO)、Ci(tLO)分别表示任务vi在低关键模式下的截止期和任务的完成时间，低关键模式下的任务vi的虚拟截止期为

其中，t为当前时间．在低关键模式下的主副版本任务在虚拟机上的优先级是按照其释放的时间ri与虚拟截止期之和，即

在虚拟机上队列中，任务的主版本与副版本任务按照式(3)所示的优先级进行调度，相同情况下副版本任务的优先级高于主版本优先级，可以按照抢占的方式抢占当前优先级低的任务，并插入所分配虚拟机的就绪队列中等待调度．在低关键模式的可靠性检测过程中，首先对主版本任务的任务完成时间与虚拟截止期进行判断，即任务vi的主版本任务的最晚开始时间应满足:

当在云计算系统中正在执行的任务不能在任务的虚拟截止期之前完成，或是其开设时间小于式(4)的开始时间时，则系统有两种模式可供选择，一种是系统进入到高关键模式，另一种则是系统开设调度其副版本任务，下面分别就两种情况的时间开销进行说明．

如果任务切换到高关键性模式，则所有在该虚拟机队列中等待执行的作业将被终止执行，并被清除出队列．此时系统中保留一个正在执行作业，该作业的执行时间为

高关键模式下的任务vi的虚拟截止期为

高关键性作业的优先级将被修改作业的释放时间与高关键模式下的虚拟截止期之和为式(7)所示，系统按照该优先级将任务插入到高关键性作业优先级队列进行调度．

进行不同关键等级模式切换的时间开销为

因此，其副版本任务的最晚开始执行时间为

3 实验结果与分析

通过可调度任务数量集与总任务数量的百分比，以及不同失效概率下云计算系统的可靠性这两个方面来验证MCRSS算法的性能．仿真实验采用与文献[8]中相同的混合关键任务的生成方法，随机生成的偶发混合关键任务的具体参数设置如下:

(1) 每组测试中实时周期任务集合100≤N≤1000;

(2) 测试的任务是两个关键等级即高关键等级HI和低关键等级LO;

(4) 任务的执行时间在[1，α Ti]之间均匀分布，α值分别设为0.2，0.8．实验重复进行10次，以10次的平均值为最终结果;

通过两组实验测试实时关键任务集的可调度性．两组实验分别选取随机生成的实时关键任务队列，其中任务集的规模分别是100个和 1 000 个．测试在云计算平台计算节点数为20情况下，MCRSS算法与MC-MP-EDF[17]以及P-EDF[17]在不同双关键实时任务的平均利用率条件下，任务集的可接受比率．

图1表明在任务集为100情况下，MCRSS、MC-MP-EDF和P-EDF算法相比，能有效提高任务的可接受比率，这是由于MCRSS采用主副两个版本任务的虚拟截止期的测试，同时采用主副版本两个版本的调度，也能有效提高算法的可调度性．图2表明在任务集为 1 000 情况下，MCRSS与MC-MP-EDF和P-EDF算法的可调度性．可以看到，随着任务数量的增加，任务集的可调度性降低，但是MCRSS依然有较大优势．MC-MP-EDF和P-EDF性能相差不多，原因是两种算法选用完全相同任务的划分方法．

图1 任务集为100的可接受比率(可调度性)图2 任务集为1000的可接受比率(可调度性)

通过两组实验来测试在不同的负载情况下，任务集为[100，1 000] 的实时关键任务的性能．所有实时关键任务的最大负载 α= max{U1，U2，…，UN}，其中 Ui= Ci/ Ti; 性能度量标准为给定任务集进行调度所需虚拟机数与任务集负载和的比值，即定义 U= U1+ U2+ …+ UN．α为0.8，表示任务的紧迫度较高；α为0.2，则紧迫度较低．由于任务的最大负载与负载和已知，设M为任务的实际完成时间．在主副版本的调度过程中，任务的实际完成时间，应为其副版本任务的执行时间(Makespan)．由图3和图4可以看到，随着任务的不断增加，算法MCRSS的 M/U 小于FTRMFF[18]和TPFTRM[18]两种方法的．其原因是MCRSS能依据主版本任务运行的情况，使用被动和重叠的方式进行调度，因此其具有较好的性能．而FTRMFF采用固定的重叠方式，而TPFTRM采用可调节的副版本重叠方式，因此其性能优于FTRMFF．

图3 α=02时，3种算法性能比较图4 α=08时，3种算法性能比较

4 结 束 语

笔者提出了一种在云计算系统中针对混合关键任务的主副版本调度策略．该策略能有效地提高混合关键任务的调度性能和可靠性．实验结果表明， MCRSS的性能优于其它算法，适合于异构集群环境，尤其是任务达到速度变化较大，节点动态加入或退出集群等情况，使得系统具有较强的灵活性和可靠性．

[1] 崔星灿, 禹晓辉, 刘洋, 等. 分布式流处理技术综述[J]. 计算机研究与发展, 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]王吉, 包卫东, 朱晓敏. 虚拟化云平台中实时任务容错调度算法研究[J]. 通信学报, 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]谷传才, 关楠, 于金铭, 等. 多处理器混合关键性系统中的划分调度策略[J].软件学报, 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

中央高校基本科研业务费专项资金资助项目(2572014EB05-4)；黑龙江省自然科学基金重点资助项目(ZD201403)；林业公益性行业科研专项经费资助项目(201504307)

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

10.3969/j.issn.1001-2400.2016.06.027

TP306

A

1001-2400(2016)06-0158-06