因为CFS中的就绪队列是一棵以vruntime为键值的红黑树,虚拟时间越小的进程越靠近整个红黑树的最左端。因此,调度器每次选择位于红黑树最左端的那个进程,该进程的vruntime最小。(对应之前的min_vruntime)
其中vruntime以下公式计算它的增长数值:
条件 公式当前进程的nice != NICE_0_LOAD vruntime += delta_exec * NICE_0_LOAD / 进程权重
当前进程的nice == NICE_0_LOAD vruntime += delta_exec
其中delta_exce为"内核计算当前和上一次更新负荷权重时两次的时间的差值", 计算公式为:delta_exec = 当前时间 - 上次更新时间
因此权重越大的进程的vruntime的增长率会越小,更容易排在红黑树偏左端,进而更容易被调度,而权重小的则相反。
计算完vruntime之后,就要进行设置红黑树。
2.6红黑树 2.6.1什么是红黑树?红黑树是一种在插入或删除结点时都需要维持平衡的二叉查找树,并且每个结点都具有颜色属性:
一个结点要么是红色的,要么是黑色的。
根结点是黑色的。
如果一个结点是红色的,那么它的子结点必须是黑色的,也就是说在沿着从根结点出发的任何路径上都不会出现两个连续的红色结点。
从一个结点到一个NULL指针的每条路径上必须包含相同数目的黑色结点。
如下图所示:
可以很明显的看出,该树的最左端的值是最小的。取走最左端的端点后,需要重新平衡红黑树。
2.6.2重新设置min_vruntime的红黑树代码如下:
static void update_min_vruntime(struct cfs_rq *cfs_rq)
{
/*初始化vruntime的值
*相当于如下的代码
*if (cfs_rq->curr != NULL)
* vruntime = cfs_rq->curr->vruntime;
*else
* vruntime = cfs_rq->min_vruntime;
*/
u64 vruntime = cfs_rq->min_vruntime;
if (cfs_rq->curr)
vruntime = cfs_rq->curr->vruntime;
/* 检测红黑树是都有最左的节点, 即是否有进程在树上等待调度
* cfs_rq->rb_leftmost(struct rb_node *)存储了进程红黑树的最左节点
* 这个节点存储了即将要被调度的结点 */
if (cfs_rq->rb_leftmost) {
/* 获取最左结点的调度实体信息se, se中存储了其vruntime
* rb_leftmost的vruntime即树中所有节点的vruntiem中最小的那个 */
struct sched_entity *se = rb_entry(cfs_rq->rb_leftmost,
struct sched_entity,
run_node);
/* 如果就绪队列上没有curr进程
* 则vruntime设置为树种最左结点的vruntime
* 否则设置vruntiem值为cfs_rq->curr->vruntime和se->vruntime的最小值 */
if (!cfs_rq->curr) /* 此时vruntime的原值为cfs_rq->min_vruntime*/
vruntime = se->vruntime;
else /* 此时vruntime的原值为cfs_rq->curr->vruntime*/
vruntime = min_vruntime(vruntime, se->vruntime);
}