OS-report02

 

​ Inside the Linux 2.6 Completely Fair Scheduler 阅读报告

概述

​ CFS 全称 Completely Fair Scheduler,也就是完全公平调度器。CFS 是 Linux 内核的一部分,负责对进程的调度。在 CFS 投入使用之前,Linux 内核曾经使用过队列,O(1) 调度器作为内核的默认调度器。

​ CFS 的目标就是对进程进行公平的调度,保证每个进程能够持有公平数量的占用处理器的时间。为了达到这个目的,CFS 引入了虚拟时间和衰退因数的概念来取代优先级。同时,维护一棵红黑树来进行加入任务,取出下一个调度的任务等操作,由于红黑树上的操作复杂度是 $O(\log n)$ ,因此 CFS 的效率非常优秀。

结构

​ CFS 定义了 sched_entity 类来作为 task_struct 的成员以追踪任务信息。sched_entity 包括 rb_node 类,rb_node 类用来维护红黑树上当前任务对应的节点,记录父节点颜色,左右子节点信息。整棵树的根节点储存在 cfs_rq(CFS ready queue)类中。通过 cfs_rq 就可以遍历整棵红黑树。

​ 整棵红黑树满足:左子节点任务的虚拟时间 $\le$ 该节点任务的虚拟时间 $\le$ 右子节点任务的虚拟时间。因此要找到虚拟时间最小的节点,只需要向左遍历到叶节点。

调度方式

​ 在可以发生抢占或者当前运行任务主动放弃处理器的时候,调度器只需要调用 schedule() 函数,找到造成抢占的任务。当前任务返回红黑树(如果进程是主动放弃处理器,需要直接从 cfs_rq 中删除不用返回红黑树)调用 pick_next_task() 来找到当前虚拟时间最小的节点,通过调用 task_of() 函数找到对应的任务,并将任务提供给处理器进行运行。

​ CFS 采用虚拟时间而非真实时间的目的就是引入衰退因数作为优先级的替代品。衰退因数和任务的优先级有关,优先级高的任务衰退因数较小,反之衰退因数比较大。衰退因数与程序运行时虚拟时间的增长速度的成正比,也就是衰退因数越小,虚拟时间的增长越慢,程序越慢被抢占,直观上非常符合我们对于优先级的定义。同时也可以发现,因为虚拟时间很大程度上受衰退因数影响,调度器对于任务具体运行时间是没有概念的。

​ 采用虚拟时间和衰退因数的好处在于不需要为每个优先级都建立一个队列,也不需要遍历每个任务来找到下一个运行的任务,在 $O(n)$ 和 $O(1)$ 的调度器之间做了一个折中。

成组调度

​ 如果在单独任务的调度上,CFS 并没有给我非常直观的”完全公平“感受,成组调度可以说是非常好的诠释了”公平调度“的理念。对于形如一个服务派生出许多任务来进行并行处理的情况,显然把每个任务都相同对待是不公平(或者叫不完全公平?)的,但是如果采用传统的设定优先级的方法给每个任务设置低优先级,对于这个服务又不公平。CFS 引入了成组调度的概念,派生出任务的服务进程跨进程共享虚拟时间。

​ 不仅仅是公平方面,成组调度对于需要合作的任务有很大好处。需要合作的任务可以共同获得处理器的控制权,减少因为同步而造成的阻塞,减少了上下文切换的成本。

总结

​ CFS 为 Linux 内核提供了一个兼顾高效和易操控性的进程调度器。每次 $O(\log n)$ 的操作相比简单的遍历更加高效,而虚拟时间和衰退因数的引入避免了多个任务队列的需要,让整个调度器更加容易操控。CFS 也为成组调度提供了一个简单的方法。相比于之前的 Linux 调度器,CFS 更加能够适应进程数增加的趋势。