基于半划分调度的Linux实时调度算法改进  

Improved Real-time Scheduling Algorithm of Linux Based on Semi-partitioned Scheduling

作　　者：李辉[1] 刘志红 LI Hui;LIU Zhihong(The 28th Research Institute of China Electronic Science&Technology Group Inc.,Nanjing 210007;Wuhan Dameng Database Co.,Ltd.,Wuhan 430073)

机构地区：[1]中国电子科技集团公司第二十八研究所,南京210007 [2]武汉达梦数据库股份有限公司,武汉430073

出　　处：《计算机与数字工程》2022年第7期1615-1619,共5页Computer & Digital Engineering

摘　　要：传统的多处理器实时任务调度算法分为划分调度算法和全局调度算法。近年来,半划分调度算法逐渐受到广泛关注,该算法综合全局调度和划分调度的行为特性,可以改善全局调度算法系统开销大和划分调度算法处理器利用率低的问题。Linux内核中已经实现了基于GEDF(Global Earliest Deadline First)算法的deadline调度器,但是对于多处理器处理器GEDF调度算法会产生Dhall效应。文章对Linux内核中实时调度算法做了改进;在EDF(Earliest Deadline First)算法的基础上,加入半划分调度的思想,在实时任务处理器利用率差别较大时也能成功调度,提高Linux实时任务可调度性的同时降低了上下文切换频率,从而降低了上下文切换带来的系统开销。Traditional multiprocessor scheduling algorithm can be divided into partitioned scheduling algorithm and global scheduling algorithm.In recent years,semi-partitioned scheduling algorithm has gradually attracted widespread attention.This algo⁃rithm can well integrate the behavior characteristics of global scheduling and partition scheduling,reduce the system load of global scheduling algorithm and improve the processors'utilization of partition scheduling algorithm.A deadline scheduler based on the GEDF(Global Earliest Deadline First)algorithm has been implemented in the Linux kernel,but for multi-core processors,the GEDF scheduling algorithm will have a Dhall effect.The article improves the real-time scheduling algorithm in the Linux kernel.And on the basis of the EDF(Earliest Deadline First)algorithm,the idea of semi-division scheduling is added,which can be suc⁃cessfully scheduled even when the processor utilization of real-time tasks differs greatly,improving the schedulability of Linux re⁃al-time tasks and reducing the frequency of context switching,thereby reducing the system overhead caused by context switching.

关 键 词：实时任务 多核处理器 调度算法 半划分调度 EDF 

分 类 号：TP316.2[自动化与计算机技术—计算机软件与理论]