Real-Time Scheduling with Task Splitting on Multiprocessors
Real-Time Scheduling with Task Splitting on Multiprocessors
复制标题
DOI：
10.1109/rtcsa.2007.61
复制
发表时间：
2007-08
期刊：
影响因子：
--
通讯作者：
S. Kato;N. Yamasaki
中科院分区：
文献类型：
--
作者：
S. Kato;N. Yamasaki
本文提出了一种多处理机系统中具有高可调度性和少抢占的实时调度算法。该算法基于一种称为分区调度的非正统方法，该方法将每个任务分配给特定的处理器，如分区调度，但如果处理器上没有足够的剩余容量，则可以将任务分成两个处理器。我们描述了一个算法分配任务的处理器，以及调度每个处理器上分配的任务的算法。可扩展性分析提供了一个公式来计算算法的可扩展的每处理器利用率的上界。然后，我们证明了整个系统利用率的最小上界是50%。此外，我们提出了启发式程序，以提高可扩展性。仿真结果表明，该算法通常可以成功调度一个任务集，系统利用率远远高于50%，虽然最小上限为50%。我们还表明，该算法实现了更高的可扩展性与更少的抢占相比，现有的算法。
This paper presents a real-time scheduling algorithm with high schedulability and few preemptions for multiprocessor systems. The algorithm is based on an unorthodox method called portioned scheduling that assigns each task to a particular processor like partitioned scheduling but can split a task into two processors if there is not enough capacity remaining on a processor. We describe an algorithm for assigning tasks to processors as well as an algorithm for scheduling the assigned tasks on per-processor. The schedulability analysis provides a formula to calculate the upper bound of the schedulable per-processor utilization for the algorithm. We then prove that the least upper bound of the whole system utilization is 50%. In addition, we propose heuristic procedures to improve schedulability. The simulation results show that the algorithm can often successfully schedule a task set with system utilization much higher than 50%, though the least upper bound is 50%. We also show that the algorithm achieves higher schedulability with fewer preemptions compared to the existing algorithms.