Please wait a minute...
J4  2014, Vol. 48 Issue (1): 113-117    DOI: 10.3785/j.issn.1008-973X.2014.01.017
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
Download:   PDF(586KB) HTML
Export: BibTeX | EndNote (RIS)      


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
CLC:  TP 301.6  
Cite this article:

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.

URL:     OR



[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] ZHAO Shi-kui, FANG Shui-liang, GU Xin-jian. Genetic algorithm with new initialization mechanism for flexible job shop scheduling[J]. J4, 2013, 47(6): 1022-1030.
[2] ZHANG Jun-chao, YUE Mao-xiong, LIU Hua-feng. Dynamic PET image reconstruction with Geometrical structure
prior constraints
[J]. J4, 2012, 46(6): 961-966.
[3] FANG Shui-liang, YAO Yan-fei, ZHAO Shi-kui. Improved genetic algorithm for flexible job shop scheduling[J]. J4, 2012, 46(4): 629-635.
[4] LIU Jia-hai, YANG Mao-lin. Fair scheduling algorithm on multi-core platforms based platforms[J]. J4, 2011, 45(9): 1566-1570.