|
|
论文:2012,Vol:30,Issue(4):617-621 |
|
|
引用本文： |
|
|
张奕, 程小辉, 蔡皖东, 詹涛. 混合关键度驱动的实时调度研究[J]. 西北工业大学 |
|
|
Zhang Yi, Cheng Xiaohui, Cai Wandong, Zhan Tao. An Effective Algorithm of Mixed-Criticality Driven Real-Time Scheduling[J]. Northwestern polytechnical university |
|
|
|
|
|
|
|
| 混合关键度驱动的实时调度研究 |
|
| 张奕1,2, 程小辉2, 蔡皖东1, 詹涛1 |
|
1.西北工业大学 计算机学院,陕西 西安 710072;
2.桂林理工大学 信息科学与工程学院,广西 桂林 541004 |
| 摘要: |
| 针对当前运行于不可预测开放环境下的嵌入式多使命复杂关键型系统,需要减少运行成本和处理不可预测工作负载情况的问题,文章提出一种混合关键度驱动的非对称式过载保护最小空闲调度策略。系统过载时,为共享同一处理器的不同关键度任务提供非对称式保护,禁止低关键度任务干扰高关键度任务,完全避免了传统的"关键度反转"问题。在恢复暂时阻塞的不同关键度任务时,在速率单调调度的基础上,引入关键度主导的截止期驱动动态调度策略,可使潜在处理器利用率达到100%。实验结果表明,这种新算法的综合性能优于当前已有的混合关键度任务调度算法。 |
| 关键词:
算法
关键度
计算机体系结构
分布式计算系统
反转问题
数学模型
实时系统
调度
混合关键度
速率单调调度
截止期驱动调度
|
|
| An Effective Algorithm of Mixed-Criticality Driven Real-Time Scheduling |
|
| Zhang Yi1,2, Cheng Xiaohui2, Cai Wandong1, Zhan Tao1 |
|
1. Department of Computer Science and Technology, Northwestern Polytechnical University, Xi'an, 710072 China;
2. College of Information Science and Engineering, Guilin University of Technology, Guilin, 541004, China |
| Abstract: |
| In many cases unexpected workload spikes are likely to occur due to unpredictable changes in the physi-cal environment. In this paper we present a mixed-criticality driven asymmetric overload-protected shortest slackscheduling algorithm that implements an alternative protection scheme to avoid the criticality inversion problem.Sections 1 through 4 of the full paper explain our algorithm mentioned in the title，which we believe is new and ef-fective and whose core consists of: “This algorithm can be used with rate monotonic based preemptive schedulerwith deadline driven scheme to resume the blocked tasks. The potential processor utilization of the new algorithmcan reach 100%. Section 1 briefs relevant past research. Section 2 deals with the model of the objects to be sched-uled and relevant semantics. Section 3 deals with the problem of criticality inversion. Section 4 deals with our algo-rithm mentioned in the title. "The experimental results，presented In Figs. 2 through 5 and Table 2，show prelimi-narily that our new algorithm provides performance higher than those of two existing algorithms for mix-criticalitytask scheduling. |
| Key words:
algorithms
computer architecture
distributed computing systems
inverse problems
mathematicalmodels
real time systems
scheduling;mixed-criticality
rate monotonic scheduling
deadline drivenschedulin
|
|
| 收稿日期: 2011-09-20
修回日期:
|
| DOI: |
| 基金项目: 国家自然科学基金(61063001/F02020)；桂林理工大学科研启动费资助 |
| 通讯作者:
Email： |
| 作者简介: 张奕(1977-),女,西北工业大学博士研究生,主要从事嵌入式关键系统及中间件研究。
|
|
| 相关功能 |
|
|
|
|
| 作者相关文章 |
|
| 张奕 在本刊中的所有文章 |
| 程小辉 在本刊中的所有文章 |
| 蔡皖东 在本刊中的所有文章 |
| 詹涛 在本刊中的所有文章 |
|
|
|
|
|
|
|
|
参考文献: |
|
|
[1] Erl T. Service-Oriented Architecture: Concepts，Technology，and Design. Prentice Hall, 2005
[2] Niz D D, Lakshmanan K, Rajkumar R R. On the Scheduling of Mixed-Criticality Real-Time Task Sets. Proceedings of the Real-Time Systems Symposium, 2009, 291-300
[3] 谭朋柳，金 海，张明虎. 用于开放式系统的二维优先级实时调度. 电子学报, 2006, 34(10):1773-1777Tan Pengliu, Jin Hai, Zhang Minghu. Two-Dimensional Priority Real-Time Scheduling for Open Systems. Acta Electronica Sini-ca, 2006, 34(10):1773-1777 (in Chinese)
[4] Brandt S A，Banachowski S，Lin C，Bisson T. Dynamic Integrated Scheduling of Hard Real-Time，Soft Real-Time and Non Re-al-Time Processes. Proceedings of the 24 th IEEE RTSS, 2003
[5] 龚育昌，王立刚，陈香兰等. 一种严格按比例派发服务的混合实时调度算法. 软件学报, 2006, 17(3):611-619Gong Yuchang，Wang Ligang，Chen Xianglan，et al. A Hybrid Real-Time Scheduling Algorithm Based on Rigorously Propor-tional Dispatching of Serving. Journal of Software, 2006, 17(3):611-619 (in Chinese)
[6] Li H，Baruah S. Load-Based Schedulability Analysis of Certifiable Mixed-Criticality Systems. http:/ /www. cs. unc. edu/～baru-ah/Pubs. shtml, 2010
[7] Liu C，Layland J. Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment. Journal of the ACM, 1973，20 (l):46-61
[8] Lakshmanan K，Niz D，Rajkumar R，et al. Resource Allocation in Distributed Mixed-Criticality Cyber-Physical Systems. Pro-ceedings of the 30 th International Conference on Distributed Computing Systems (ICDCS), 2010, 169-178 |
|
|
|
相关文献: |
|
|
1．赵付青, 张建林, 王俊彪, Jonrinaldi Jonrinaldi.基于改进SCE算法的Job Shop调度方法研究[J]. 西北工业大学, 2014,32(1): 152-157 |
|
|
2．郑炜, 李知隆, 靳如一.基于频率差异积分的故障定位算法研究[J]. 西北工业大学, 2013,31(3): 435-439 |
|
|
3．杜洪涛, 李战怀.基于数据价值的云存储动态备份一致性机制[J]. 西北工业大学, 2013,31(6): 979-984 |
|
|
4．尤涛, 杨凯, 杜承烈, 钟冬, 朱怡安.基于动态关键路径与边消除的任务复制分配算法[J]. 西北工业大学, 2013,31(6): 985-990 |
|
|
5．刘宁, 史浩山, 郭淑霞, 杨博.基于虚拟阵列的ESPRIT相干信号DOA估计[J]. 西北工业大学, 2013,31(6): 997-1001 |
|
|
6．杨洁, 王新民, 谢蓉.基于改进APF的无人机编队航迹规划[J]. 西北工业大学, 2013,31(2): 200-205 |
|
|
7．黄姝娟, 朱怡安, 李兵哲, 陆伟.基于利用率和负载均衡的多核实时调度算法研究[J]. 西北工业大学, 2012,30(1): 117-123 |
|
|
8．夏平, 周兴社, 谢必昌.适应动态安全需求的实时任务调度算法研究[J]. 西北工业大学, 2012,30(5): 657-662 |
|
|
9．张萌, 赵磊, 樊晓桠, 田杭沛.面向混杂流计算的适应性存储器体系结构[J]. 西北工业大学, 2012,30(6): 961-967 |
|
|
|
|
|
|
