Research on multi-core scheduling method for Sporadic task by line tree mode

线性树模型的Sporadic任务多核调度方法研究

School of Computer Science and Engineering, Xi'an Technological University, Xi'an 710021, China

Received: 13 October 2021

Abstract

At present, most of the scheduling models for real-time periodic tasks are established based on independent fixed periodic tasks and few by considering the task model with period allowed to change and the processor model in the scheduling process. In this paper, a task model and processor model based on line tree(LT) for sporadic real-time periodic tasks are designed, and a transformation algorithm from task line tree(TLT) model to processor line tree(PLT) model is proposed. The algorithm takes the least common multiple of all real-time periodic tasks as the benchmark of layer number, and based on the complete job replacement rule, the minimum common multiple of all real-time periodic tasks is used as the reference of layer number. In order to achieve the optimal multiprocessor scheduling result, the method of replacing the empty node of non-migrating job with the node of migrating job and the condition of allowing job to publish tasks ahead of time with variable cycle are used. Experimental results show that comparing with PEDF, GEDF and RMFF, the present method not only has higher core utilization and lower time loss rate, but also reduces the number of context switching and migration.

摘要

当前大多数的实时周期任务的调度模型都是以相互独立的固定周期任务为中心，很少考虑周期允许变化的任务模型以及处理器在调度过程中的模型。针对Sporadic实时周期任务，设计了一种基于线性树(line tree, LT)的任务模型和处理器模型，并提出了任务线性树(task line tree, TLT)模型到处理器线性树(processer line tree, PLT)模型的转化算法。该算法将所有实时周期任务的最小公倍数作为层数基准，根据完整job替换法则，利用迁移job的节点替换同层的非迁移job的空节点，利用任务周期可变，job可提前发布的情况达到最优的多核调度结果。实验结果表明，所提方法相比PEDF、GEDF以及RMFF算法，不仅具有较高的核利用率和较低的时限丢失率，同时减少了上下文切换次数和迁移次数。