Day8 初探CFS 中

前言

昨天要处里要返回台北的家当，所以只有简单的介绍CFS 是什麽，以及CFS使用了什麽样的资料结构，今天让我们来看看到底CFS内部到底在做什麽事情。

vruntime

首先要了解的就是vruntime， 在CFS 里面vruntime有着举足轻重的地位，vruntime 代表的意义就是 virtual runtime，顾名思义就是行程到目前为止所运行的虚拟时间，所以对CFS 而言，为了公平起见，让大家都能够享有公平的运行时间，CFS会挑出vruntime最小的行程执行，也就是利用昨天讲过的RB-tree的 left-most node。

那麽到底vruntime为何而生呢？ 先想想CFS 会挑选vruntime 最小的行程执行， 优先权比较高的行程，应该要拥有优先执行的权利，所以应该要找到一个方法，可以让优先权比较高的行程，能够拥有相对小的vruntime，才能够让这些行程优先执行。

在Linux 里面会透过 p->se.load 读取行程p的权重资讯， 在Linux内的权重，会用nice 值来表示，范围由 -20~19 数字越大代表优先权越小，行程默认的 nice 值是0，可以理解成总共有40个阶级。 如果有一个行程 nice值由0 变成1，代表该行程相对於其他nice 值是0 的行程，获得的时间要少10% ，因此nice值少1 ，代表优先权上升，也代表获得的CPU时间会多10%，Linux内规定，当nice值是0的时候，权重值是1024。

在nice值的计算上，Linux用了很有趣的技巧，与其每次都计算到底比例是多少，不如直接建一个表作近似就可以了!! 在vruntime的部分， Linux 用了两个表，两个列表都放在 kernel/shed/core.c 中

第一个是nice值对应的权重值

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,
};

第二个是 2^32 / 权重值

const u32 sched_prio_to_wmult[40] = {
 /* -20 */     48388,     59856,     76040,     92818,    118348,
 /* -15 */    147320,    184698,    229616,    287308,    360437,
 /* -10 */    449829,    563644,    704093,    875809,   1099582,
 /*  -5 */   1376151,   1717300,   2157191,   2708050,   3363326,
 /*   0 */   4194304,   5237765,   6557202,   8165337,  10153587,
 /*   5 */  12820798,  15790321,  19976592,  24970740,  31350126,
 /*  10 */  39045157,  49367440,  61356676,  76695844,  95443717,
 /*  15 */ 119304647, 148102320, 186737708, 238609294, 286331153,
};

第二个表我们会在明天用到，第一个表就是用来近似的。
举个简单的例子，如果有两个行程 nice值都是0，权重值都是1024，两个行程都能得到50%的 CPU时间，如果其中一个行程的nice值变成1， 这样他获得的 CPU时间应该会变成 45% 约等於 820/(1024+820)， 反之nice 值为0的行程获得的 CPU时间会是 55% 约等於 1024/(1024+820)，也因为使用了查表计算，能够将计算简化。

今天讲完了权重表格的用法与CFS的概念，明天要看看到底 vruntime如何计算，以及第二个表格到底要做什麽用。