cfs调度之 入/出 队列

wangxingchao201

cfs进程的出入队列操作是基本function.这里细细地分析下这两个小东西做什么事情.
enqueue_task_fair and dequeue_task_fair 是sched_class的两个hook.在诸如唤醒,设置nice level等操作时,
会调用到这两个函数.
               
               
               
               
唤醒抢占:
check_preempt_wakeup:检测被唤醒的进程是否能抢占当前的进程,一旦当前进程满足被抢占的条件,立即置调度标志.
tick中断抢占:
check_preempt_tick:在时间中断scheduler_tick()里,检测当前runqueue里的current是否可以被"重新调度".这和上面的抢占不一样,这是一次公平的给其它进程得以运行的机会.
scheduler_tick(){
...
curr->sched_class->task_tick(rq, curr, 0);
...
}
从当前进程开始遍历其父亲,检测是否可以让出cpu给其它进程去运行.
有两个条件: 队列里进程数大于1； 没有置抢占.
这两个条件任何一个满足,就跑到check_preempt_tick()去做进一步检测.
代码是:
if (cfs_rq->nr_running > 1 || !sched_feat(WAKEUP_PREEMPT))
check_preempt_tick(cfs_rq, curr);
我们认为,有多于一个进程时,别的进程就应该得到运行的机会.
当只有一个进程,这时候也没有抢占功能,可能此进程一直运行下去,也不好.故需要检测下其是否应当让出cpu.
这个函数会:
1) 是否执行时间超过了ideal_runtime. 超过其"时间片"了.超过了则应该放弃cpu,让其它进程跑.否则:
2)是否开抢占了,开的话继续向下走:
3)是否超过抢占粒度时间,超过再往下走:
4)如果此时进程就多于1个, 正式给队列里其它进程一个抢占当前进程的机会:
选择最左结点与当前进程的vruntime比较,看其是否超过1)中计算的ideal_runtime,超过则置调度标志.
为什么两次检测和判断呢? 明天再分析,先回家睡觉.
2 楼路题了,没有写题目时的出入队列问题,而是写了抢占和tick对当前进程的影响,我后面再补上.
前天晚上遗留的问题,即在tick里检测当前进程是否放弃cpu时,check_preempt_tick()做了两次对ideal_runtime的比较.
代码:
check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
unsigned long ideal_runtime, delta_exec;
ideal_runtime = sched_slice(cfs_rq, curr);
delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
if (delta_exec > ideal_runtime) { //如果运行时间超过slice,让出cpu.这个很好理解.旧的调度器是这样.
resched_task(rq_of(cfs_rq)->curr);
/*
* The current task ran long enough, ensure it doesn't get
* re-elected due to buddy favours.
*/
clear_buddies(cfs_rq, curr);
return;
}
/*
* Ensure that a task that missed wakeup preemption by a
* narrow margin doesn't have to wait for a full slice.
* This also mitigates buddy induced latencies under load.
*/
if (!sched_feat(WAKEUP_PREEMPT))
return;
if (delta_exec nr_running > 1) {
struct sched_entity *se = __pick_next_entity(cfs_rq);
s64 delta = curr->vruntime - se->vruntime;
if (delta > ideal_runtime) //这儿要满足的条件有:抢占打开并且运行队列里有>1个进程在运行. 如果curr与 红黑树中最左侧结点此时的差值也大于ideal_runtime,就重新调度. 这是cfs让人很迷惑的地方.我会在下面解释.
resched_task(rq_of(cfs_rq)->curr);
}
}
假设这两种情况:
1. 正常选择红黑树最左结点curr,运行到tick时检测其运行时间是否超过其ideal_runtime,有的话让出cpu.
2. 如果此时curr没有运行完其ideal_runtime,运行队列里又有多个进程,且抢占特性打开.要从rb-tree取最左结点,其vruntime与curr的差值若超过ideal_vruntime,表示抢占当前进程.
curr 被选择之前即是最左侧结点,在这个计算时间点它的运行时间比ideal_runtime要小,那么它现在的vruntime之差delta与ideal_runtime相比是什么意思呢? delta的增值可是由delta_exec换算出来的.即:
delta = delta_exec * (1024/load) .这个数值增长非常慢的. 和第一种情况比较下,即ideal_runtime满足下面条件时,可以调度当前进程:
(delta_exec > ideal_time) || (delta_exec*n -b > ideal_time)
这儿的n指得就是由delta_exec计算vruntime时的比例,其与task的 nice相关. 对于一个高优先级(nice)的进程,这个数是很小的. b代表最左结点的vruntime,要让后面的条件满足,b就要很小才行.而且b是在curr运行之后新加入红黑树的最左侧结点.不然后面的条件不会满足.
这样给了一些唤醒的 sleeper或新建的进程抢占当前进程去运行的机会.
现在想不到用一种数学模型来证明这个问题...


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u3/110888/showart_2159272.html