cfs调度之 入/出 队列

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 < sysctl_sched_min_granularity) 
return; 

if (cfs_rq->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或新建的进程抢占当前进程去运行的机会. 

现在想不到用一种数学模型来证明这个问题...