一种共享资源敏感的实时任务分配算法  

A Shared Resource-Aware Real-Time Task Allocation Algorithm

作　　者：杨茂林[1] 雷航[1] 廖勇[1] 

机构地区：[1]电子科技大学信息与软件工程学院,成都611731

出　　处：《计算机学报》2014年第7期1455-1465,共11页Chinese Journal of Computers

基　　金：国家自然科学基金(61103041);国家"八六三"高技术研究发展计划重大项目(2012AA010904);中央高校基本科研业务费项目(ZYGX2012J070);华为基金项目(IRP-2012-02-07);开源项目(www.aCoral.org);电子科技大学优秀博士生学术支持计划项目(YBXSZC20131028)资助~~

摘　　要：为提高多核实时系统分组固定优先级调度策略下的任务分配效率,该文对FIFO(First In First Out)自旋机制下任务阻塞时间,以及自旋等待造成的可调度性损失进行了定量分析,提出了一种新的任务相关度评价方法以衡量核间任务的相关性,并基于该方法提出了共享资源敏感的任务分配算法.该算法包含任务分组策略和任务组拆分策略.任务分组策略将存在共享资源冲突的任务划分为相关任务子集,尽可能将相关任务子集分配到同一核上,以避免核间任务相互阻塞造成可调度性损失;任务组拆分策略则根据任务相关度评价结果,对无法分配到同一核上的相关任务子集进行拆分,并将拆分出的任务分配到当前负载最轻的核上,以减小自旋造成的可调度性损失.实验结果表明,该算法任务集合接受率高于同类算法,而系统自旋损失低于同类算法.In order to improve the efficiency of task allocation under partitioned fixed priority scheduling in multi-core real-time systems, we quantitatively analyzed the task blocking time and schedulability losses resulted from FIFO-spin mechanisms. Subsequently, we presented a new task correlation analysis to evaluate the correlation between tasks on different cores, based on which we proposed a novel shared resource-aware task allocation algorithm. The proposed algorithm includes task-grouping policy and task group-splitting policy. The task-grouping policy chooses the tasks that involve in resource contentions to compose relative sub-task-sets, and co-locates as many such sets as possible, so as to avoid remote blockings; while the task group- splitting policy splits the sub-task-sets that can not be allocated to the same core based on the task correlation analysis, and allocates the tasks split from the original sub-task-sets to the least- loaded core, so as to reduce spin-related schedulability losses. Experimental evaluation results indicate that the proposed algorithm outperforms the similar algorithms in terms of both the task-set acceptance ratio and the spin-related （schedulability） losses.

关 键 词：多核处理器 实时系统 实时调度 任务分配算法 自旋机制 

分 类 号：TP316[自动化与计算机技术—计算机软件与理论]