Linux内核CFS调度器的实现

本文简易而快速地介绍了Linux内核中完全公平类调度类CFS调度器的原理和实现。

原理

其实CFS(Completely Fair Scheduler)的核心原理很简单,就是使得每个进程都尽可能“公平”地获得运行时间。因此每次都选择过去运行得最少得进程运行。当然,作为一个调度器,它要满足的需求远不止于此。Linux的抢占式进程和在完全公平类fair_sched_class中支持优先级等一系列特性,使得CFS的设计变得比简单的选出运行时间最少要复杂得多。但是不要着急,我们一步一步来理解CFS的原理。

最小运行时间

为了避免过度频繁的抢占发生,Linux内核设置了每个Task(进程)的最小运行时间(或称运行时间粒度),在这个时间内,这个进程的CPU资源是不可被抢占的。除非进程主动让出CPU或者执行了阻塞的系统调用,一般而言进程都可以执行最少执行完这个时间。最小运行时间可以通过内核参数sched_min_granularity_ns来查看。

cat /proc/sys/kernel/sched_min_granularity_ns
3000000

时间片

CFS通过引入权重来保证高优先级的进程能够获得更多的CPU时间,进程间按照权重比例分配时间片。调度周期内分配给进程的运行时间按照这个公式计算:

运行时间tn=调度周期T * 进程权重w / 运行队列中全部进程的权重之和S

权重是一个和nice值有关的量,现在在Linux内核中的定义位于kernel/sched/core.c#L9516(文章发布时),数值如下:

const int sched_prio_to_weight[40] = {
 /* -20 */     88761,     71755,     56483,     46273,     36291,
 /* -15 */     29154,     23254,     18705,     14949,     11916,
 /* -10 */      9548,      7620,      6100,      4904,      3906,
 /*  -5 */      3121,      2501,      1991,      1586,      1277,
 /*   0 */      1024,       820,       655,       526,       423,
 /*   5 */       335,       272,       215,       172,       137,
 /*  10 */       110,        87,        70,        56,        45,
 /*  15 */        36,        29,        23,        18,        15,
};

其中nice值为0的权重NICE_0_LOAD=1024,nice值每差1,权重大约差1.25倍。这里的1.25计算依据来源于nice值差1,运行时间相差10%这样的设计。

虚拟运行时间

解决完每次分配多少时间的问题后,还有一个问题需要解决,就是下一个运行的进程是谁?CFS实现的原则是“完全的公平”,那么高优先级的进程如何保证多一点的运行时间?这就要引入一个概念,叫“虚拟运行时间”了。假设我们希望有如下的情况出现:

高优先级进程运行15ms=低优先级运行5ms

那么我们就将这个相等的量设置为一个“虚拟运行时间”,这样就可以保证高优先级进程运行的时间几乎总是低优先级的3倍。在Linux中,这个虚拟运行时间与实际运行时间的关系就是刚刚提到的权重:

虚拟运行时间=真实运行时间 * NICE_0_LOAD / 进程的权重

Linux在调度元素中定义了vruntime变量(include/linux/sched.h#L453),用于记录进程的累计虚拟运行时间,代码如下:

struct sched_entity {
	/* For load-balancing: */
	struct load_weight		load;
	struct rb_node			run_node;
	struct list_head		group_node;
	unsigned int			on_rq;

	u64				exec_start;
	u64				sum_exec_runtime;
	u64				vruntime;
	u64				prev_sum_exec_runtime;

	u64				nr_migrations;

	struct sched_statistics		statistics;
        ...
}

进程每次运行完毕后就会更新vruntime变量,至于如何挑选出vruntime最少的进程,这将由红黑树完成。

红黑树

红黑树是一种自平衡的二叉树,最左的叶子节点永远是key最小的节点。红黑树通过插入(更新)和删除时的操作保证这些原子操作之间红黑树永远是平衡的。

具体的操作参见https://www.jianshu.com/p/e136ec79235c

内核将调度队列上的进程按照vruntime排列成红黑树,这样选取最小vruntime的进程就变为了简单地选出最左边的叶子节点了。

最小vruntime

内核除了红黑树以外还维护一个min_vruntime变量,以记录此时最小的虚拟运行时间。

为什么需要这个min_vruntime?我们设想以下几种状况:

  • 新的进程加入了红黑树,那么它的vruntime应当是多少?
  • 休眠了10万年的进程等待到了它要求的事件,现在被唤醒了,它还保持原有的vruntime吗?
  • 进程被负载均衡迁移到另一个CPU上(另一个调度队列),那么它的vruntime如何改变?

由此可以看出,min_vruntime的作用就是帮助Linux内核解决这些情况。

深入阅读

默认图片
Easton Man
文章: 30

留下评论