基于利用率和负载均衡的多核实时调度算法研究

针对分区调度算法在实时多处理器系统中处理器利用率不高的现象,提出一种基于利用率和负载均衡的分区调度算法BUWBPA(Based on Utilization and Workload Balance Partition Algorithm)。该算法在满足任务实时性要求的基础上,以寻求高利用率和负载均衡为目标进行任务分配,将任务分配分成两个阶段:第一个阶段以高利用率为原则,选择任务集内利用率最高的任务先分配;第二个阶段以负载均衡为原则,根据处理器数选择利用率总和等于1或接近于1的任务进行分配,并且在此阶段对于未达到充分利用的处理器,选取可能调度的零星任务,对任务进行再次重新分配,以达到负载均衡和系统最大利用率。实验证明,该算法在实现最大利用率的前提下能很好地达到负载均衡。

An Efficient BUWBP( Based on Utilization and Workload Balance Partition) Algorithm for Multiprocessor Real-Time System

The partition algorithm cannot achieve the high-utilization for the multiprocessor system.We propose a new heuristic partition scheduling algorithm which can achieve the high-utilization and make workload balance.Sections 1,2 and 3 of the full paper explain BUWBP algorithm mentioned in the title,which we believe is more efficient than previous ones.The core of section 1,2 and 3 consists of:"It has two phases:in the first phase,we allocate the tasks to the cores;in the second phase,we choose the complementary or similar complementary element for the allocated task of each core.Subsection 1.2 gives ten definitions and four theorems." Simulation results,presented in Fig.2 and Table 1,and their analysis show preliminarily that our BUWBP algorithm can indeed find better utilization and make the workload balance for the cores.