微信服务号

微信订阅号

2025年3月24日 9:13 星期一
首页 > 过刊浏览>2014年第25卷第2期 >284-297. DOI:10.13328/j.cnki.jos.004534
PDF HTML阅读 XML下载 导出引用 引用提醒
多处理器混合关键性系统中的划分调度策略
作者:
基金项目:

国家科技支撑计划（2012BAF13B08）；中央高校基本科研业务费项目（FRFCUN100204001, FRFCUN110804003）；国家自然科学基金（61300022）


Partitioned Scheduling Policies on Multi-Processor Mixed-Criticality Systems
Author:
  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [21]
    • |
  • 相似文献 [20]
    • | | |
  • 文章评论
    摘要:

    多核处理器正越发广泛地应用到现代嵌入式系统的设计与实现当中，其强大的计算能力为将多个不同关键性级别的功能子系统集成到统一的共享资源平台提供了支持.混合关键性系统的调度问题即便在单处理器平台中都极具挑战性，在多处理器平台则更为困难.将目前资源利用率最高的单处理器混合关键性调度算法EY-VD扩展到多处理器平台中.首先，结合传统的划分调度策略提出了适用于多处理器混合关键性系统的MC-PEDF(mixedcriticality partitioned earliest deadline first)划分调度算法.尽管比之前的算法有更好的可调度性能，但传统的划分策略不能有效地平衡不同关键性级别下的负载，故其不完全适用于混合关键性系统.为了克服传统策略的不足，提出了划分调度策略OCOP(one criticality one partition).OCOP允许系统在关键性模式切换时对实时任务集进行重新划分，进而更好地平衡各个处理器在不同关键性模式中的资源利用率.基于OCOP，提出了第2种划分调度算法MC-MP-EDF(mixed-criticality multi-partitioned EDF).基于随机生成任务集的仿真实验结果表明，与MC-PEDF和已有的算法相比，MC-MP-EDF能够显著地提高系统的可调度性，尤其是在处理器数量较多的系统中.

    Abstract:

    Multi-Core processors are more and more widely used in embedded systems as they provide great computing capacities to integrate multiple functionalities with different criticality levels into a shared platform. The scheduling problem of mixed-criticality systems appears to be challenging, even on single-processor platforms. This work extends the state-of-the-art single-processor mixedcriticality scheduling algorithm EY-VD to multi-processor systems. To begin with, it integrates EY-VD into traditional workload partitioning schemes to get a multiprocessor mixed-criticality scheduling algorithm MC-PEDF (mixed-criticality partitioned earliest deadline first). Although MC-PEDF performs better than previous solutions, the study finds that the traditional workload partitioning schemes are not suitable for mixed-criticality systems as it does not explore the asymmetricity of workload on different criticality levels. To overcome this problem, a workload partitioning policy OCOP (one criticality one partition) is proposed. OCOP allows tasks to be reassigned to a different processor when criticality mode switch occurs, thus can better balance the resource utilization among processors on different criticality levels. Based on OCOP, the second partitioned scheduling algorithm MC-MP-EDF (mixed-criticality multi-partitioned EDF) is constructed. Experiments with randomly generated workload show that MC-MP-EDF can drastically improve the system schedulability comparing with MC-PEDF and other previous algorithms, especially for systems with more processors.

    参考文献
    [1] Vestal S. Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In: Proc. of the 28th IEEE Real-Time Systems Symp. (RTSS). IEEE, 2007. 239-243. [doi: 10.1109/RTSS.2007.47]
    [2] Bastoni A, Brandenburg BB, Anderson JH. An empirical comparison of global, partitioned, and clustered multiprocessor EDF Schedulers. In: Proc. of the 31st IEEE Real-Time Systems Symp. (RTSS). IEEE, 2010. 14-24. [doi: 10.1109/RTSS.2010.23]
    [3] Kelly OR, Aydin H, Zhao B. On partitioned scheduling of fixed-priority mixed-criticality task sets. In: Proc. of the 10th Int’l Conf. on Trust, Security and Privacy in Computing and Communications (TrustCom). IEEE, 2011. 1051-1059. [doi: 10.1109/TrustCom. 2011.144]
    [4] Baruah SK, Chattopadhyay B, Li H, Shin I. Mixed-Criticality scheduling on multiprocessors. Real-Time Systems, 2014,50(1): 142-177. [doi: 10.1007/s11241-013-9184-2]
    [5] Baruah SK, Bonifaci V, D’Angelo G, Marchetti-Spaccamela A, Van Der Ster S, Stougie L. Mixed-Criticality scheduling of sporadic task systems. In: Proc. of the 19th Annual European Symp. on Algorithms (ESA). Springer-Verlag, 2011. 555-566. [doi: 10.1007/978-3-642-23719-5_47]
    [6] Ekberg P, Yi W. Outstanding paper award: Bounding and shaping the demand of mixed-criticality sporadic tasks. In: Proc. of the 24th Euromicro Conf. on Real-Time Systems (ECRTS). IEEE, 2012. 135-144. [doi: 10.1109/ECRTS.2012.24]
    [7] Baruah SK, Mok AK, Rosier LE. Preemptively scheduling hard-real-time sporadic tasks on one processor. In: Proc. of the 11th Real-Time Systems Symp. (RTSS). IEEE, 1990. 182-190. [doi: 10.1109/REAL.1990.128746]
    [8] Baruah SK, Li H, Stougie L. Towards the design of certifiable mixed-criticality systems. In: Proc. of the Real-Time and Embedded Technology and Applications Symp. (RTAS). IEEE, 2010. 13-22. [doi: 10.1109/RTAS.2010.10]
    [9] Baruah SK, Burns A, Davis RI. Response-Time analysis for mixed criticality systems. In: Proc. of the 32rd Real-Time Systems Symp. (RTSS). IEEE, 2011. 34-43. [doi: 10.1109/RTSS.2011.12]
    [10] Baruah SK, Bonifaci V, D’Angelo G, Li H, Marchetti-Spaccamela A, Megow N, Stougie L. Scheduling real-time mixed-criticality jobs. IEEE Trans. on Computers, 2012,61(8):1140-1152. [doi: 10.1109/TC.2011.142]
    [11] Mollison MS, Erickson JP, Anderson JH, Baruah SK, Scoredos JA. Mixed-Criticality real-time scheduling for multicore systems. In: Proc. of the 10th Int’l Conf. on Computer and Information Technology (CIT). IEEE, 2010. 1864-1871. [doi: 10.1109/CIT.2010. 320]
    [12] Pathan RM. Schedulability analysis of mixed-criticality systems on multiprocessors. In: Proc. of the 24th Euromicro Conf. on Real- Time Systems (ECRTS). IEEE, 2012. 309-320. [doi: 10.1109/ECRTS.2012.29]
    [13] Li H, Baruah SK. Outstanding paper award: Global mixed-criticality scheduling on multiprocessors. In: Proc. of the 24th Euromicro Conf. on Real-Time Systems (ECRTS). IEEE, 2012. 166-175. [doi: 10.1109/ECRTS.2012.41]
    [14] De Niz D, Lakshmanan K, Rajkumar R. On the scheduling of mixed-criticality real-time task sets. In: Proc. of the 30th Real-Time Systems Symp. (RTSS). IEEE, 2009. 291-300. [doi: 10.1109/RTSS.2009.46]
    [15] Lakshmanan K, de Niz D, Rajkumar R, Moreno G. Resource allocation in distributed mixed-criticality cyber-physical systems. In: Proc. of the 30th Int’l Conf. on Distributed Computing Systems (ICDCS). IEEE, 2010. 169-178. [doi: 10.1109/ICDCS.2010.91]
    [16] Lakshmanan K, de Niz D, Rajkumar R. Mixed-Criticality task synchronization in zero-slack scheduling. In: Proc. of the 17th Real- Time and Embedded Technology and Applications Symp. (RTAS). IEEE, 2011. 47-56. [doi: 10.1109/RTAS.2011.13]
    [17] Li H, Baruah SK. An algorithm for scheduling certifiable mixed-criticality sporadic task systems. In: Proc. of the 31th Real-Time Systems Symp. (RTSS). IEEE, 2010. 183-192. [doi: 10.1109/RTSS.2010.18]
    [18] Guan N, Ekberg P, Stigge M, Yi W. Effective and efficient scheduling of certifiable mixed-criticality sporadic task systems. In: Proc. of the 32rd Real-Time Systems Symp. (RTSS). IEEE, 2011. 13-23. [doi: 10.1109/RTSS.2011.10]
    [19] Liu CL, Layland JW. Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of ACM, 1973,20(1): 46-61. [doi: 10.1145/321738.321743]
    [20] Audsley NC. Optimal priority assignment and feasibility of static priority tasks with arbitrary start times. Technical Report, YCS 164, Department of Computer Science, University of York, 1991.
    [21] Johnson DS. Near-Optimal bin packing algorithms [Ph.D. Thesis]. Boston: Massachusetts Institute of Technology, 1973.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

谷传才,关楠,于金铭,王义,邓庆绪.多处理器混合关键性系统中的划分调度策略.软件学报,2014,25(2):284-297

复制
分享
文章指标
  • 点击次数:5980
  • 下载次数: 8582
  • HTML阅读次数: 2696
  • 引用次数: 0
历史
  • 收稿日期:2013-05-07
  • 最后修改日期:2013-12-05
  • 在线发布日期: 2014-01-26
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19727358位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号