基于Linux的多核实时任务调度算法改进

Improved multi-core real-time task scheduling algorithm based on Linux

摘要:

嵌入式实时系统通常被实现为多任务系统,以满足多个外部输入的响应时间的最后期限约束。Linux内核中已经实现了基于EDF(Earliest Deadline First)调度算法的DL调度器,使得实时任务能在截止期限内运行完成。但对于多核处理器,由于实时任务在EDF算法下会出现Dhall效应,论文对 Linux内核中实时任务调度算法进行了改进。在EDF算法的基础上,实现LLF(Least Laxity First)调度算法并对其加以改进,通过降低任务上下文切换频率以及减少松弛度的计算来减小调度过程中的颠簸现象。实验证明该方法既避免了Dhall效应,又减少了任务上下文切换带来的系统开销,并使得任务能在截止期限内完成调度,取得了较好的调度性能。

Abstract:

Embedded real-time systems are often implemented as multi-tasking systems to meet deadline constraints on the response time of multiple external inputs. The DL scheduler based on the EDF (Earliest Deadline First) scheduling algorithm has been implemented in the Linux kernel, so that real-time tasks can be completed within the deadline. But for multi-core processors, real-time tasks will have Dhall effect under the EDF algorithm. In view of the above problems, this paper proposes an improved method for real-time task scheduling algorithms in the Linux kernel. Based on the EDF algorithm, the LLF (Least Laxity First) scheduling algorithm is implemented and improved. It reduces the jitter in the scheduling process by reducing the task context switching frequency and reducing the slack calculation. Experiments show that this method not only avoids the Dhall effect, but also reduces the system overhead caused by task context switching, and enables tasks to be scheduled within deadlines, and achieves better scheduling performance.