同构多核平台上基于弱硬约束和优先级距离启发的任务划分算法  

Weakly-hard-constraintand Priority-distance Aware Partitioned Scheduling for Homogeneous Multicore Platforms

作　　者：龚伟强 韩建军[1] 张昌安 GONG Weiqiang;HAN Jianjun;ZHANG Chang’an(College of Computer Science and Technology,Huazhong University of Science and Technology,Wuhan 430074,China)

机构地区：[1]华中科技大学计算机科学与技术学院,武汉430074

出　　处：《计算机科学》2025年第4期101-109,共9页Computer Science

摘　　要：弱硬实时(Weakly-Hard Real-Time,WHRT)系统由于能够有效地利用计算资源,并且可以同时容忍部分作业的超时来保证系统的稳定性,因此在过去二十年中得到了极大的发展。然而,目前关于多核环境下弱硬实时任务调度的研究却较少,现有的基于全局调度的方案因任务迁移带来的高运行时开销,实际可行性受到了极大的限制;而作业级分区算法则通常忽略了弱硬约束下任务利用率的影响,因此任务集的可调度性性能不高。为了解决这些问题,基于单处理器的全局紧急调度(Global Emergency-Based Scheduling,GEBS),提出了一种弱硬约束启发的任务划分算法(Weakly-Hard-Constraint Aware Task Partition Algorithm,WHCA-TPA)和另一种优先级距离启发的任务划分算法(Priority-Distance-Aware Task Partition Algorithm,PDA-TPA)。WHCA-TPA考虑不同任务之间的干扰,对系统的利用率进行更合理的估计,并以此作为启发对任务进行更合理的分配。PDA-TPA通过减少同一核上不同优先级任务之间的抢占次数,来减少系统上下文切换的次数。将所提算法与现有的传统分区算法进行对比,大量的实验结果表明,WHCA-TPA在不同系统参数下都可以获得更高的可调度比例,并且和PDA-TPA在绝大部分情况下都能有效地降低运行时开销。As weakly-hard real-time(WHRT)system enables to effectively exploit computing resources while guaranteeing the system stability by tolerating accidentally temporal violation,it has been broadly developed in some real-life areas over the past two decades.However,there exist rather limited studies on the scheduling of WHRT tasks upon multicores.For the existing global scheduling based schemes,the high runtime overhead caused by task migration greatly restricts their practical viability;while the current job-level partitioned algorithm usually ignores the impacts of the utilizations of tasks under weakly-hard constraints,which may significantly degrade the schedulability performance of task sets.To address such issues,with the focus global emergency-based scheduling(GEBS)for uniprocessors,two task partitioning algorithms have been proposed:the weakly-hard-constraint aware task partitioning algorithm(WHCA-TPA)and the priority-distance aware task partitioning algorithm(PDA-TPA).Firstly,WHCA-TPA considers the interference between different tasks,providing a more reasonable estimate of system utilization,and uses it to allocate tasks more reasonably.In addition,PDA-TPA aims at reducing the number of preemptions between tasks to decrease the number of context switches,thus achieving lower runtime overhead.Ultimately,when compared to the existing conventional mapping schemes,extensive experimental results show that WHCA-TPA can achieve a higher schedulability ratio under various system parameters.Meanwhile,PDA-TPA and WHCA-TPA usually has lower runtime overhead in contrast with other mapping schemes.

关 键 词：多核处理器 实时系统 弱硬约束 利用率启发 分区算法 

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