共享资源约束下多核实时任务分配算法

Multicore real-time task allocation algorithms with shared resource constraints

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

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 alloca- tion 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 pref- erentially co-locates tasks that may incur resource sharing conflicts to avoid blocking between tasks on dif- ferent 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）.