Please wait a minute...
J4  2014, Vol. 48 Issue (1): 113-117    DOI: 10.3785/j.issn.1008-973X.2014.01.017
计算机技术﹑电信技术     
共享资源约束下多核实时任务分配算法
刘加海1,杨茂林2,雷航2,廖勇2
1. 浙江大学城市学院 信息与电气工程学院,浙江 杭州 310015;
2. 电子科技大学 信息与软件工程学院,四川 成都 611731
Multicore real-time task allocation algorithms with shared resource constraints
LIU Jia-hai1, YANG Mao-lin2, LEI Hang2, LIAO Yong2
1. School of Information and Electrical Engineering,Zhejiang University City College, Hangzhou 310015, China|
2. School of Information and Software Engineering, University of Electronic Science and Technology, Chengdu 611731, China
 全文: PDF(586 KB)   HTML
摘要:

为了提高多核实时系统任务分配效率,研究分组固定优先级调度策略下的任务分配算法.通过分析核间任务阻塞对任务最坏情况响应时间产生的影响,提出由于任务间共享资源冲突而引发了任务分配故障问题;指出负载非均衡算法,如First-fit算法、Best-fit算法容易引发任务分配故障.为了避免该问题,提出基于分组与负载均衡的任务分配算法.该算法将存在访问共享资源冲突的任务分配到同一核上,以避免核间任务阻塞;当这些任务无法分配到同一核上时,将这些任务依次分配到当前负载最轻的核上以避免任务分配故障.可调度性分析实验表明,采用该算法可以避免任务分配故障,减少分配任务所需的处理器核数(比Worst-fit算法少10%~40%).

Abstract:

The task allocation algorithm was  analyzed under partitioned fixed priority scheduling policy in order to increase the efficiency of task allocation in multicore real-time systems. The impact of blockings between tasks on different cores on the worst case response time of tasks was analyzed, and a task allocation failure problem incurred by resource sharing conflicts was pointed out. Load-unbalancing algorithms like first-fit and best-fit can easily trigger such task allocation problem. A grouping and load-balancing based task allocation algorithm was proposed in order to avoid such problem. The proposed algorithm preferentially co-locates tasks that may incur resource sharing conflicts to avoid blocking between tasks on different cores, and allocates the tasks that can not be allocated to the same core to the lightest-loaded core to avoid task allocation failure. Schedulability experiments show that the proposed algorithm can avoid task allocation failure and reduce the number of cores needed for task allocation (about as less as 10%~40% than that of the worst-fit algorithm needed).

出版日期: 2014-01-01
:  TP 301.6  
作者简介: 刘加海(1960-),男,教授, 从事计算机应用、信号处理、电子器件等研究.E-mail: Ljhqyyq@yahoo.com.cn
服务  
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章  

引用本文:

刘加海,杨茂林,雷航,廖勇. 共享资源约束下多核实时任务分配算法[J]. J4, 2014, 48(1): 113-117.

LIU Jia-hai, YANG Mao-lin, LEI Hang, LIAO Yong. Multicore real-time task allocation algorithms with shared resource constraints. J4, 2014, 48(1): 113-117.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2014.01.017        http://www.zjujournals.com/eng/CN/Y2014/V48/I1/113

[1] DAVIS R I, BURNS A. A survey of hard real-time scheduling for multiprocessor systems [J]. ACM Computing Survey, 2011, 43(4): 144.
[2] 刘加海,杨茂林.基于多核处理器平台的公平调度算法 [J]. 浙江大学学报:工学版,2011,45(9):1566-1570.
LIU Jia-hai, YANG Mao-lin. Fair scheduling algorithm on multi-core processor based platforms [J]. Journal of Zhejiang University: Engineering Science, 2011, 45(9): 1566-1570.
[3] ANDREA B, BRANDENBURG B B, ANDERSON J H. An empirical comparison of global, partitioned, and clustered multiprocessor EDF schedulers [C] // Proceeding of the 31st Real-Time System Symposium (RTSS). San Diego: IEEE, 2010: 14-24.
[4] RAJKUMAR R. Synchronization in real-time systems: a priority inheritance approach [M]. [S.l.]: Kluwer Academic Publishers, 1991.
[5] SCHLIECKER S, ERNST R. Real-time performance analysis of multiprocessor systems with shared memory [J]. ACM Transactions on Embedded Computing Systems, 2010, 10(2): 127.
[6] SCHLIECKER S, NEGREAN M, ERNST R. Response time analysis on multicore ECUs with shared resources [J]. IEEE Transactions on Industrial Information, 2009, 5(4): 402-413.
[7] YANG Mao-lin, LEI Hang, LIAO Yong. Synchronization analysis for hard real-time multicore systems [J]. Applied Mechanics and Materials, 2013, 241244:2246-2252.
[8] GAREY M R, JOHNSON D S. Computers and intracta- bility: a guide to the theory of NP-completeness [M]. New York:  Freeman, 1979.
[9] 涂登彪,谭光明,孙凝晖. 无锁同步的细粒度并行介度中心算法[J].软件学报,2011,22(5):986-995.
TU Deng-biao, TAN Guang-ming, SUN Ning-hui. Fine-grained parallel betweenness centrality algorithm without lock synchronization [J]. Journal of Software, 2011, 22(5): 986-995.
[10] 兰舟,孙世新. 基于动态关键任务的多处理器任务分配算法 [J]. 计算机学报, 2007, 30(3): 454-462.
LAN Zhou, SUN Shi-xing. An algorithm of allocating tasks to multiprocessors based on dynamic critical task [J]. Chinese Journal of Computers, 2007, 30(3): 454-462.
[11] OH Y, SON S H. Allocating fixed priority periodic tasks on multiprocessor systems [J]. Real-Time Systems, 1995, 9(3): 207-239.
[12] BINI E, BUTTAZZO G C. Measuring the performance of schedulability tests [J]. Real-Time Systems, 2005, 30(1/2): 129-154.
[13] LIU C L, LAYLAND J W. Scheduling algorithms for multiprogramming in a hard-real-time environment [J]. Journal of the ACM, 1973, 20(1): 46-61.

[1] 赵诗奎, 方水良, 顾新建. 柔性车间调度的新型初始机制遗传算法[J]. J4, 2013, 47(6): 1022-1030.
[2] 张俊超, 岳茂雄, 刘华锋. 结构先验约束的动态PET图像重建[J]. J4, 2012, 46(6): 961-966.
[3] 方水良, 姚嫣菲, 赵诗奎. 柔性车间调度的改进遗传算法[J]. J4, 2012, 46(4): 629-635.
[4] 刘加海,杨茂林. 基于多核处理器平台的公平调度算法[J]. J4, 2011, 45(9): 1566-1570.