完全公平调度算法 关于完全公平调度算法的研究与分析
时间：2019-04-25 03:36:59 来源：雅意学习网 本文已影响 人 
摘要：GFS调度法是Linux最新研制的调度算法，表现出很强的有异性。GFS涉及能够有效促进处理器资源的公平与共享。本文主要分析了GFS调度算法的特性与工作流程，从算法分析与Hackbench测试两方面对CFS与O（1）性能进行对比分析与研究
关键词：完全公平调度法；计算机技术；公平
中图分类号：TP316.81 文献标识码：A 文章编号：1674-7712 (2012) 06-0159-01
一、引言
操作系统的一项核心功能表现在进程调度方面，进程调度主要是对处理器资源进行合理公平的分配。调度算法应该以实现效率与公平作为其目标，并促进周转时间、吞吐量、响应时间等目标之间的平衡[1]。Linux从使用调度算法以来，不断经历了O（1）、RSDL、SD、CFS调度算法，CFS相对O（1）有了很大的进步，简化了代码，突出了公平的核心思想。
二、CFS概述
GPS采用virtual runtime来描述CPU上的执行时间，在调度的过程中，CFS为保证每个进程有基本相似的执行时间，会选择执行时间最小的进程来运行，从而达到任务执行时间的相对平衡。CFS调度法相对于O（1）来讲有了很大的进步，比如能够区分交互式进程，不跟踪睡眠时间，所以代码思路相对简单。另外还增加了组调度的功能，以保证组与用户的公平。同时不再采用优先级数组，将就绪态进程插入红黑树，并以此来选择下一个调度进程。一般每一个调度模块都需要执行调度类以为其制定一组函数，以简化需要修改进程杜奥杜算法时的程序。
三、CFS算法
（一）周期性调度函数
系统时钟中断调用周期性调度函数，即Scheduler-tick()，对运行队列信息进行更新并执行相关调度操作，其主要流程表现如下：
（1）对本地CPU的运行队列负载、时间戳等信息进行更新，之后转入CFS调度类task_tick函数——task_tick_fair()
（2）对GFS运行队列和执行进程相关信息进行更新，更新在update-curr()中进行。这种操作构成函数中断处理的重要内容和核心步骤。
（3）对是否需要抢占当前进程进行有效判断，这一过程在check_preempt_tick()中进行。
首先，需要对CFS队列中每一进程被调度以此的时间周期period进行计算；
其次，对目前进程所允许占用的时间，即ideal_runtime进行计算，表现为：ideal_runtime=period*curr-＞load.weight/cfs_rq-＞load[2]
cfs_rq-＞load为cfs_rq的负载，这一数值的增加在进程出列时则会减小，curr-＞load.weight为nice对应的weight数值。通过上述公式能够发现，系统负载与ideal_runtime之间呈现负相关；nice与se-＞load.weight、ideal_runtime呈现负相关。
再次，计算进程已经占用的CPU时间。
delta_exec=curr-＞sum_exec_runtime-curr-＞prev_sum_exec_runtime[3]。
式中prev_sum_exec_runtime代表进程被切换到CPU时sum_exec_runtime。
最后，比较进程占用CPU时间delta_exec是否比ideal_runtime要大。如果执行时间超过ideal_runtime则会用resched_task（）设置此进程的抢占标志位，同时在tick中断返回过程中调用schedule（）完成调度。
（二）主调度函数
schedule（）即主调度函数，包括主动与被动两种方式，schedule（）功能表现为在运行队列中选择被调度的进程，同时对调度信息进行有效更新。主调度函数如下：
（1）禁止初始化局部变量、清除调度标志位、内核抢占、执行相关锁操作等；
（2）在put_prev_task_fair（）中将目前执行的程序放到运行队列。
首先，对当前运行进程up-data_curr（）和cfs-rq进行有效更新；其次，在进程插入红黑树后，排序键值key在_enqueue_entity中变为：se_＞vruntime-cfs_rq-＞min_vruntime。
（3）在pick_next_task_fair（）中将CPU分配到下一个被调度的进程中。
首先，选择结点se（红黑树最左侧），之后进行两次条件判断，分别为是否被cfs_rq-＞next抢占、是否被cfs_rq-＞last抢占。之后决定下一个被调度进程。
其次，在选出下一个被调度进程之后，需要采用set_next_entity（）设置所选择的进程的信息，在_dequeue_entity（）中实现。
四、CFS总结
从上述分析中可以发现CFS与之前的调度器有很大不同，发生了很大的改进。CFS突出完全公平的思想，以对进程执行时间的追逐来调度任务，通过以红黑树代替之前采用的优先级数组来决定被调度的进程，将调度类引入以有效增强代码的可维护性与内核调度程序的扩展性。同时代码中也将之前较难理解的公式进行去除，使得整个思路相对清楚，也提高了算法的实用性。但CFS同时也有一些负面的报告，需要在以后的研究中不断完善。
参考文献：
[1]朱旭,杨斌,刘海涛.完全公平调度算法分析[J].成都信息工程学院学报,2010,25(1):18-21
[2]王辉,李津生,洪佩琳.802.11WLAN中一种基于循环队列的分布式公平队列调度算法[J].电子与信息学报,2004,26(10):1540-1547
[3]赵旭,夏靖波.基于RTAI的Linux系统实时性研究与改进[J].计算机工程,2010,36(14):288-290
