CFS笔记(1)

本文主要来自内核文档中 /scheduler/sched-design-CFS.txt

1. CFS的思想:
可以从 CFS 的字面意思看出来, CFS stands for “Completely Fair Scheduler”. 把 CPU 的资源表示成 100%, CFS 希望做到每个进程使用了 1 / nr_running 的资源.

2. CFS 的实现:
为了实现这个理念, CFS 使用的主要数据是虚拟运行时 virtual runtime. 这个数据存放在每个进程的 p->se.vruntime 中. 在理想情况下, 在任何时刻, 所有的进程的 p->se.vruntime 都是相同的, 这表明它们公平共享 CPU 的资源.

CFS 基于 vruntime 采取的逻辑也是简单的: 总是选取 vruntime 最小的进程执行. CFS 使用基于 vruntime 的红黑树维护就绪进程表, 每次选取树中最左侧的节点上 CPU 来做到这一点. 每次调度器被调用时, 更新 CPU 上进程的 vruntime, 当这个进程不再是树中最左侧节点时, 进程被树中最左侧节点抢占.

CFS 维护 rq->cfs.min_vruntime 记录最小的 vruntime, 同时这也用来将新激活的进程放到树的左侧. 显然这个变量的值是单调增的.

CFS 的在设计时引入了调度类 Scheduling Class 的概念. 类由 sched_class 结构实现. 类的 CFS 实例定义为: const struct sched_class fair_sched_class. 类中主要有这么几个接口:

enqueue_task()
在一个进程进入可运行状态时调用. 将进程实体放入红黑树, 并更新 nr_running.

dequeue_task()
与 enqueue_task() 相反, 在进程不能继续运行时调用, 将进程从红黑树中提出, 更新 nr_running.

check_preempt_cur()
检查加入就绪队列的进程是否抢占当前进程.

pick_next_task()
选出下一个运行的进程.

set_curr_task()
当进程改变其调度类或进程组时调用.

task_tick()
在时钟中断时调用, 可能发生抢占.

3. 一些细节:
CFS 能达到纳秒(ns, 10^-9s)级的粒度. CFS 中没有之前(O(1)之类)调度算法中时间片的概念.

通常来说, CFS 对于每个进程公平; 这种公平也能配置为对进程组公平. 这需要配置 CONFIG_FAIR_GROUP_SCHED. 可以使用两个独立的方法对任务进行分组, 分别基于 uid(CONFIG_FAIR_USER_SCHED) 和 cgroup pseude(CONFIG_FAIR_CGROUP_SCHED) 文件系统. 后者使得管理员可以根据需要创建组.