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