Volume 40, Number 4, August 2022
|Page(s)||935 - 943|
|Published online||30 September 2022|
Research on multi-core scheduling method for Sporadic task by line tree mode
School of Computer Science and Engineering, Xi'an Technological University, Xi'an 710021, China
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算法，不仅具有较高的核利用率和较低的时限丢失率，同时减少了上下文切换次数和迁移次数。
Key words: / real-time scheduling / line tree / scheduling model / scheduling algorithm
关键字 : 多核 / 实时调度 / 线性树 / 调度模型 / 调度算法
© 2022 Journal of Northwestern Polytechnical University. All rights reserved.
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.