基于启发式算法降低比例公平调度开销策略  

A Strategy to Reduce Proportional Fair Scheduling Cost Based on Heuristic Algorithm

作　　者：管银凤 张凤登[1] 朱长昊 GUAN Yinfeng;ZHANG Fengdeng;ZHU Changhao(School of Optical-Electrical and Computer Engineering,University of Shanghai for Science and Technology,Shanghai 200093,China)

机构地区：[1]上海理工大学光电信息与计算机工程学院,上海200093

出　　处：《控制工程》2023年第6期1062-1070,共9页Control Engineering of China

摘　　要：在多处理器系统中已经证明了比例公平(proportion fair,Pfair)算法是调度周期任务最优的全局调度算法。然而在该算法的最坏执行情况下,任务在每个调度时刻均产生切换或迁移,导致系统开销过大。针对这一问题,对Pfair算法进行深入研究后发现,任务的分配过程是一个重要原因。基于此,提出基于启发式算法的模拟退火比例公平(simulated annealing-proportion fair,SA-Pfair)调度算法,即在Pfair算法做出调度决策后,用启发式算法将任务分配给处理器,以弥补原算法的不足。最后,采用LITMUS-RT平台对SA-Pfair算法和以此为基础设计的调度器进行仿真。结果表明,新算法在一定程度上减少了任务的切换次数以及50%以上的任务迁移总量,且能够有效地降低调度过程中的系统开销。It has been proved that proportion fair(Pfair) algorithm is an optimal global scheduling algorithm for periodic tasks in multi-processor systems.However,in the worst case,the preemption or migration of tasks may occur at every scheduling moment during the implementation of this algorithm,which makes the system overhead too high.In order to solve this problem,we find that the task allocation process is an important reason after further research on Pfair algorithm.On this basis,a simulated annealing proportional fair(Simulated AnnealingProportion fair,SA-Pfair) scheduling algorithm based on heuristic algorithms is proposed,which means that tasks are allocated to processors after scheduling decisions made by the Pfair algorithms,in order to compensate for the shortcomings of the original algorithms.Finally,LITMUS-RT platform is used to simulate the SA-Pfair scheduling algorithm and the scheduler based on it.The results show that the new algorithm can reduce the number of task preemption,and the total number of task migration by more than 50% to a certain extent,and can effectively reduce the system overhead in the scheduling process.

关 键 词：多处理器 比例公平调度算法 周期性任务 SA-Pfair调度算法 任务迁移 

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