一种针对依赖性周期任务的实时多核调度算法

针对软实时系统中的一类同时具有依赖性与周期性的任务,提出一种基于单行树矩阵(MST)的动态因子均衡调度算法SMD(schedule on matrix of the single tree and dynamic load factor)。该算法通过对MST矩阵的特性进行分析,将任务划分为若干并行集,再综合考虑已执行时间、任务间的依赖关系及任务最早截止时间几个要素,以动态因子的形式对任务进行实时调度。最后,还以证明的形式给出了可充分调动的任务集的充分条件,并以此为基础随机生成了测试任务集,进行了对比实验。实验表明,与文献中现有经典算法相比,新算法使处理器利用率提升近15%,任务丢失率降低2%。

New scheduling algorithm for real-time multiprocessor systemsaimed to independent and periodic multi-tasks

With the aim to work out a kind of task, which is meanwhile based on the dependence and period, this paper proposed a schedule algorithm based-on matrix of the single tree and dynamic load factor, named SMD. SMD dynamically aggregated jobs into several parallel sets by analyzing the feature of the MST(matrix of the single tree). Then, SMD scheduled the real-time tasks with judging the value of the dynamic factor by compromising executed-time, task dependence and deadline. Finally, it gave a proof of how to generate an appropriate task set and do an experiment based on this proof. The experimental results demonstrate that compared with the classic algorithm, SMD enhances CPU-utilization by nearly 15% and reduce the miss-rate by 2% respectively.