Linux进程调度CFS算法实现分析

网上讲CFS的文章很多，可能版本不一，理解不尽相同。我以问题追溯方式，跟踪源码写下我对CFS的理解，有的问题我也还没理解透，欢迎对内核有兴趣的朋友一起交流学习，源码版本是与LKD3配套的Linux2.6.34

背景知识：

(1)Linux的调度器类主要实现两类进程调度算法：实时调度算法和完全公平调度算法(CFS)，实时调度算法SCHED_FIFO和SCHED_RR，按优先级执行，一般不会被抢占。直到实时进程执行完，才会执行普通进程。而大多数的普通进程，用的就是CFS算法。

(2)进程调度的时机：

①进程状态转换时刻：进程终止、进程睡眠；

②当前进程的”时间片”用完；

③主动让出处理器，用户调用sleep()或者内核调用schedule()；

④从中断，系统调用或异常返回时；

(3)每个进程task_struct中都有一个structsched_entityse成员，这就是调度器的实体结构，进程调度算法实际上就是管理所有进程的这个se。

structtask_struct{

volatilelongstate;/*-1unrunnable,0runnable,>0stopped*/

void*stack;

atomic_tusage;

unsignedintflags;/*perprocessflags,definedbelow*/

unsignedintptrace;

intlock_depth;/*BKLlockdepth*/

#ifdefCONFIG_SMP

#ifdef__ARCH_WANT_UNLOCKED_CTXSW

intoncpu;

#endif

#endif

intprio,static_prio,normal_prio;

unsignedintrt_priority;

conststructsched_class*sched_class;

structsched_entityse;//进程调度实体

structsched_rt_entityrt;

…

}

CFS基于一个简单的理念：所有任务都应该公平的分配处理器。理想情况下，n个进程的调度系统中，每个进程获得1/n处理器时间，所有进程的vruntime也是相同的。

CFS完全抛弃了时间片的概念，而是分配一个处理器使用比来度量。

每个进程一个调度周期内分配的时间(类似于传统的“时间片”)跟三个因素有关：进程总数，优先级，调度周期

其他进程调度详细基础知识参见上篇博文：http://blog.chinaunix.net/uid-24708340-id-3778555.html

1.理解CFS的首先要理解vruntime的含义

简单说vruntime就是该进程的运行时间，但这个时间是通过优先级和系统负载等加权过的时间，而非物理时钟时间，按字面理解为虚拟运行时间，也很恰当。

每个进程的调度实体se都保存着本进程的虚拟运行时间。

structsched_entity{

structload_weightload;/*forload-balancing*/

structrb_noderun_node;

structlist_headgroup_node;

unsignedinton_rq;

u64exec_start;

u64sum_exec_runtime;

u64vruntime;//虚拟运行时间

u64prev_sum_exec_runtime;

…

}

而进程相关的调度方法如下

staticconststructsched_classfair_sched_class={

.next=&idle_sched_class,

.enqueue_task=enqueue_task_fair,

.dequeue_task=dequeue_task_fair,

.yield_task=yield_task_fair,

.check_preempt_curr=check_preempt_wakeup,

.pick_next_task=pick_next_task_fair,

.put_prev_task=put_prev_task_fair,

#ifdefCONFIG_SMP

.select_task_rq=select_task_rq_fair,

.rq_online=rq_online_fair,

.rq_offline=rq_offline_fair,

.task_waking=task_waking_fair,

#endif

.set_curr_task=set_curr_task_fair,

.task_tick=task_tick_fair,

.task_fork=task_fork_fair,

.prio_changed=prio_changed_fair,

.switched_to=switched_to_fair,

.get_rr_interval=get_rr_interval_fair,

#ifdefCONFIG_FAIR_GROUP_SCHED

.task_move_group=task_move_group_fair,

#endif

};

2.vruntime的值如何跟新？

时钟中断产生时，会依次调用tick_periodic()->update_process_times()->scheduler_tick()

voidscheduler_tick(void)

{

…

raw_spin_lock(&rq->lock);

update_rq_clock(rq);

update_cpu_load(rq);

curr->sched_class->task_tick(rq,curr,0);//执行调度器tick，更新进程vruntime

raw_spin_unlock(&rq->lock);

…

}

task_tick_fair()调用entity_tick()如下：

staticvoidentity_tick(structcfs_rq*cfs_rq,structsched_entity*curr,intqueued)

{

update_curr(cfs_rq);

…

if(cfs_rq->nr_running>1||!sched_feat(WAKEUP_PREEMPT))

check_preempt_tick(cfs_rq,curr);//检查当前进程是否需要调度

}

这里分析两个重要函数update_curr()和check_preempt_tick()

staticvoidupdate_curr(structcfs_rq*cfs_rq)

{

structsched_entity*curr=cfs_rq->curr;

u64now=rq_of(cfs_rq)->clock;

unsignedlongdelta_exec;

if(unlikely(!curr))

return;

//delta_exec获得最后一次修改后，当前进程所运行的实际时间

delta_exec=(unsignedlong)(now-curr->exec_start);

if(!delta_exec)

return;

__update_curr(cfs_rq,curr,delta_exec);

curr->exec_start=now;//运行时间已保存，更新起始执行时间

if(entity_is_task(curr)){

structtask_struct*curtask=task_of(curr);

trace_sched_stat_runtime(curtask,delta_exec,curr->vruntime);

cpuacct_charge(curtask,delta_exec);

account_group_exec_runtime(curtask,delta_exec);

}

}

主要关心__update_curr()函数

staticinlinevoid__update_curr(structcfs_rq*cfs_rq,structsched_entity*curr,unsignedlongdelta_exec)

{

unsignedlongdelta_exec_weighted;

schedstat_set(curr->exec_max,max((u64)delta_exec,curr->exec_max));

curr->sum_exec_runtime+=delta_exec;//累计实际运行时间

schedstat_add(cfs_rq,exec_clock,delta_exec);

delta_exec_weighted=calc_delta_fair(delta_exec,curr);//对delta_exec加权

curr->vruntime+=delta_exec_weighted;//累计入vruntime

update_min_vruntime(cfs_rq);//更新cfs_rq最小vruntime(保存所有进程中的最小vruntime)

}

关注calc_delta_fair()加权函数如何实现

/*

*delta/=w

*/

staticinlineunsignedlong

calc_delta_fair(unsignedlongdelta,structsched_entity*se)

{

if(unlikely(se->load.weight!=NICE_0_LOAD))

delta=calc_delta_mine(delta,NICE_0_LOAD,&se->load);

returndelta;

}

若当前进程nice为0，直接返回实际运行时间，其他所有nice值的加权都是以0nice值为参考增加或减少的。

/*

*delta*=weight/lw

*/

staticunsignedlong

calc_delta_mine(unsignedlongdelta_exec,unsignedlongweight,

structload_weight*lw)

{

u64tmp;

if(!lw->inv_weight){

if(BITS_PER_LONG>32&&unlikely(lw->weight>=WMULT_CONST))

lw->inv_weight=1;

else

lw->inv_weight=1+(WMULT_CONST-lw->weight/2)

/(lw->weight+1);//这公式没弄明白

}

tmp=(u64)delta_exec*weight;

/*

*Checkwhetherwe'doverflowthe64-bitmultiplication:

*/

if(unlikely(tmp>WMULT_CONST))

tmp=SRR(SRR(tmp,WMULT_SHIFT/2)*lw->inv_weight,

WMULT_SHIFT/2);

else

tmp=SRR(tmp*lw->inv_weight,WMULT_SHIFT);//做四舍五入

return(unsignedlong)min(tmp,(u64)(unsignedlong)LONG_MAX);

}

当nice!=0时，实际是按公式delta*=weight/lw来计算的weight=1024是nice0的权重，lw是当前进程的权重，该lw和nice值的换算后面介绍，上面还书的lw计算公式没弄明白，总之这个函数就是把实际运行时间加权为进程调度里的虚拟运行时间，从而更新vruntime。

更新完vruntime之后，会检查是否需要进程调度

回到staticvoidentity_tick(structcfs_rq*cfs_rq,structsched_entity*curr,intqueued)

{

update_curr(cfs_rq);

…

if(cfs_rq->nr_running>1||!sched_feat(WAKEUP_PREEMPT))

check_preempt_tick(cfs_rq,curr);//检查当前进程是否需要调度

}

更新完cfs_rq之后，会检查当前进程是否已经用完自己的“时间片”

/*

*Preemptthecurrenttaskwithanewlywokentaskifneeded:

*/

staticvoid

check_preempt_tick(structcfs_rq*cfs_rq,structsched_entity*curr)

{

unsignedlongideal_runtime,delta_exec;

ideal_runtime=sched_slice(cfs_rq,curr);//ideal_runtime是理论上的处理器运行时间片

delta_exec=curr->sum_exec_runtime-curr->prev_sum_exec_runtime;//该进程本轮调度累计运行时间

if(delta_exec>ideal_runtime){//假如实际运行超过调度器分配的时间，就标记调度标志

resched_task(rq_of(cfs_rq)->curr);

/*

*Thecurrenttaskranlongenough,ensureitdoesn'tget

*re-electedduetobuddyfavours.

*/

clear_buddies(cfs_rq,curr);

return;

}

/*

*Ensurethatataskthatmissedwakeuppreemptionbya

*narrowmargindoesn'thavetowaitforafullslice.

*Thisalsomitigatesbuddyinducedlatenciesunderload.

*/

if(!sched_feat(WAKEUP_PREEMPT))

return;

if(delta_exec<sysctl_sched_min_granularity)

return;

if(cfs_rq->nr_running>1){

structsched_entity*se=__pick_next_entity(cfs_rq);

s64delta=curr->vruntime-se->vruntime;

if(delta>ideal_runtime)

resched_task(rq_of(cfs_rq)->curr);

}

}

当该进程运行时间超过实际分配的“时间片”，就标记调度标志resched_task(rq_of(cfs_rq)->curr);，否则本进程继续执行。中断退出，调度函数schedule()会检查此标记，以选取新的进程来抢占当前进程。

3.如何选择下一个可执行进程

CFS选择具有最小vruntime值的进程作为下一个可执行进程，CFS用红黑树来组织调度实体，而键值就是vruntime。那么CFS只要查找选择最左叶子节点作为下一个可执行进程即可。实际上CFS缓存了最左叶子，可以直接选取left_most叶子。

上面代码跟踪到timertick中断退出，若“ideal_runtime”已经用完，就会调用schedule()函数选中新进程并且完成切换。

asmlinkagevoid__schedschedule(void)

{

if(prev->state&&!(preempt_count()&PREEMPT_ACTIVE)){

if(unlikely(signal_pending_state(prev->state,prev)))

prev->state=TASK_RUNNING;

else

deactivate_task(rq,prev,1);//如果状态已经不可运行，将其移除运行队列

switch_count=&prev->nvcsw;

}

pre_schedule(rq,prev);

if(unlikely(!rq->nr_running))

idle_balance(cpu,rq);

put_prev_task(rq,prev);//处理上一个进程

next=pick_next_task(rq);//选出下一个进程

…

context_switch(rq,prev,next);/*unlockstherq*///完成进程切换

…

}

如果进程状态已经不是可运行，那么会将该进程移出可运行队列，如果继续可运行

put_prev_task()会依次调用put_prev_task_fair()->put_prev_entity()

staticvoidput_prev_entity(structcfs_rq*cfs_rq,structsched_entity*prev)

{

/*

*Ifstillontherunqueuethendeactivate_task()

*wasnotcalledandupdate_curr()hastobedone:

*/

if(prev->on_rq)

update_curr(cfs_rq);

check_spread(cfs_rq,prev);

if(prev->on_rq){

update_stats_wait_start(cfs_rq,prev);

/*Put'current'backintothetree.*/

__enqueue_entity(cfs_rq,prev);

}

cfs_rq->curr=NULL;

}

__enqueue_entity(cfs_rq,prev)将上一个进程重新插入红黑树(注意，当前运行进程是不在红黑树中的)

pick_next_task()会依次调用pick_next_task_fair()

staticstructtask_struct*pick_next_task_fair(structrq*rq)

{

structtask_struct*p;

structcfs_rq*cfs_rq=&rq->cfs;

structsched_entity*se;

if(!cfs_rq->nr_running)

returnNULL;

do{

se=pick_next_entity(cfs_rq);//选出下一个可执行进程

set_next_entity(cfs_rq,se);//把选中的进程(left_most叶子)从红黑树移除，更新红黑树

cfs_rq=group_cfs_rq(se);

}while(cfs_rq);

p=task_of(se);

hrtick_start_fair(rq,p);

returnp;

}

set_next_entity()函数会调用__dequeue_entity(cfs_rq,se)把选中的下一个进程即最左叶子移出红黑树。

最后context_switch()完成进程的切换。

4.何时更新rbtree

①上一个进程执行完ideal_time，还可继续执行时，会插入红黑树；

②下一个进程被选中移出rbtree红黑树时；

③新建进程；

④进程由睡眠态被激活，变为可运行态时；

⑤调整优先级时也会更新rbtree；

5.新建进程如何加入红黑树

新建进程会做一系列复杂的工作，这里我们只关心与红黑树有关部分

Linux使用fork，clone或者vfork等系统调用创建进程，最终都会到do_fork函数实现，如果没有设置CLONE_STOPPED，do_fork会执行两个与红黑树相关的函数:copy_process()和wake_up_new_task()

(1)copy_process()->sched_fork()->task_fork()

staticvoidplace_entity(structcfs_rq*cfs_rq,structsched_entity*se,intinitial)

{

u64vruntime=cfs_rq->min_vruntime;//以cfs的最小vruntime为基准

/*

*The'current'periodisalreadypromisedtothecurrenttasks,

*howevertheextraweightofthenewtaskwillslowthemdowna

*little,placethenewtasksothatitfitsintheslotthat

*staysopenattheend.

*/

if(initial&&sched_feat(START_DEBIT))

vruntime+=sched_vslice(cfs_rq,se);//加上一个调度周期内的"时间片"

/*sleepsuptoasinglelatencydon'tcount.*/

if(!initial&&sched_feat(FAIR_SLEEPERS)){

unsignedlongthresh=sysctl_sched_latency;

/*

*Convertthesleeperthresholdintovirtualtime.

*SCHED_IDLEisaspecialsub-class.Wecareabout

*fairnessonlyrelativetootherSCHED_IDLEtasks,

*allofwhichhavethesameweight.

*/

if(sched_feat(NORMALIZED_SLEEPER)&&(!entity_is_task(se)||

task_of(se)->policy!=SCHED_IDLE))

thresh=calc_delta_fair(thresh,se);

/*

*Halvetheirsleeptime'seffect,toallow

*foragentlereffectofsleepers:

*/

if(sched_feat(GENTLE_FAIR_SLEEPERS))

thresh>>=1;

vruntime-=thresh;

}

/*ensurewenevergaintimebybeingplacedbackwards.*/

vruntime=max_vruntime(se->vruntime,vruntime);

se->vruntime=vruntime;

}

计算新进程的vruntime值，加上一个“平均时间片”表示刚执行完，避免新建进程立马抢占CPU。

(2)调用wake_up_new_task函数

voidwake_up_new_task(structtask_struct*p,unsignedlongclone_flags)

{

…

rq=task_rq_lock(p,&flags);

update_rq_clock(rq);

activate_task(rq,p,0);//激活当前进程，添加入红黑树

check_preempt_curr(rq,p,WF_FORK);//确认是否需要抢占

…

}

更新时钟，激活新建的进程activate_task()会调用

staticvoidenqueue_task(structrq*rq,structtask_struct*p,intwakeup,boolhead)

{

if(wakeup)

p->se.start_runtime=p->se.sum_exec_runtime;

sched_info_queued(p);

p->sched_class->enqueue_task(rq,p,wakeup,head);

p->se.on_rq=1;

}

将新建的进程加入rbtree；

6.唤醒进程调用try_to_wake_up()->activate_task()->enqueue_task_fair()->enqueue_entity()

注意enqueue_entity函数调用place_entity对进程vruntime做补偿计算，再次考察place_entity(cfs_rq,se,0)

staticvoidplace_entity(structcfs_rq*cfs_rq,structsched_entity*se,intinitial)

{

u64vruntime=cfs_rq->min_vruntime;//以cfs的最小vruntime为基准

/*

*The'current'periodisalreadypromisedtothecurrenttasks,

*howevertheextraweightofthenewtaskwillslowthemdowna

*little,placethenewtasksothatitfitsintheslotthat

*staysopenattheend.

*/

if(initial&&sched_feat(START_DEBIT))

vruntime+=sched_vslice(cfs_rq,se);//一个调度周期内的"时间片"

/*sleepsuptoasinglelatencydon'tcount.*/

if(!initial&&sched_feat(FAIR_SLEEPERS)){

unsignedlongthresh=sysctl_sched_latency;

/*

*Convertthesleeperthresholdintovirtualtime.

*SCHED_IDLEisaspecialsub-class.Wecareabout

*fairnessonlyrelativetootherSCHED_IDLEtasks,

*allofwhichhavethesameweight.

*/

if(sched_feat(NORMALIZED_SLEEPER)&&(!entity_is_task(se)||

task_of(se)->policy!=SCHED_IDLE))

thresh=calc_delta_fair(thresh,se);

/*

*Halvetheirsleeptime'seffect,toallow

*foragentlereffectofsleepers:

*/

if(sched_feat(GENTLE_FAIR_SLEEPERS))

thresh>>=1;

vruntime-=thresh;//对于睡眠进程唤醒，给予vruntime补偿

}

/*ensurewenevergaintimebybeingplacedbackwards.*/

vruntime=max_vruntime(se->vruntime,vruntime);//避免通过睡眠来获得运行时间

se->vruntime=vruntime;

}

当initial=1时，新建进程vruntime=cfs最小vruntime值+时间片，放入红黑树最右端。

当initial=0时，表示唤醒进程，vruntime要减去一个thresh.这个thresh由调度周期sysctl_sched_latency加权得到虚拟时间，这样做可以对睡眠进程做一个补偿，唤醒时会得到一个较小的vruntime,使它可以尽快抢占CPU(可以快速响应I/O消耗型进程)。

注意注释/*ensurewenevergaintimebybeingplacedbackwards.*/

这个设计是为了给睡眠较长时间的进程做时间补偿的，既使其可以快速抢占，又避免因太小的vruntime值而长期占用CPU。但有些进程只是短时间睡眠，这样唤醒时自身vruntime还是大于min_vruntime的，为了不让进程通过睡眠获得额外运行时间补偿，最后vruntime取计算出的补偿时间和进程本身的vruntime较大者。从这可以看出，虽然CFS不再区分I/O消耗型，CPU消耗型进程，但是CFS模型对IO消耗型天然的提供了快速的响应。

7.改变进程优先级，如何调整rbtree

Linux中改变进程优先级会调用底层的set_user_nice()

voidset_user_nice(structtask_struct*p,longnice)

{

…

dequeue_task(rq,p,0);//把进程从红黑树中取出

…

p->static_prio=NICE_TO_PRIO(nice);//将nice(-20~19)值映射到100~139,0~99是实时进程优先级

set_load_weight(p);

…

enqueue_task(rq,p,0,false);

}

set_user_nice把进程从红黑树取出，调整优先级(nice值对应权重)，再重新加入红黑树.

set_load_weight()函数是设置nice值对应的权重，

staticvoidset_load_weight(structtask_struct*p)

{

if(task_has_rt_policy(p)){

p->se.load.weight=0;

p->se.load.inv_weight=WMULT_CONST;

return;

}

/*

*SCHED_IDLEtasksgetminimalweight:

*/

if(p->policy==SCHED_IDLE){

p->se.load.weight=WEIGHT_IDLEPRIO;

p->se.load.inv_weight=WMULT_IDLEPRIO;

return;

}

p->se.load.weight=prio_to_weight[p->static_prio-MAX_RT_PRIO];

p->se.load.inv_weight=prio_to_wmult[p->static_prio-MAX_RT_PRIO];

}

数组prio_to_weight[]是将nice值(-20~19)转化为以nici0(1024)值为基准的加权值,根据内核注释每一个nice差值，权重相差10%，即在负载一定的条件下，每增加或减少一个nice值，获得的CPU时间相应增加或减少10%

staticconstintprio_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,

};

上面calc_delta_mine()函数用到这个数组加权值，这个转化过程还没弄明白，有明白的朋友，指点一二，不胜感激

/*

*Inverse(2^32/x)valuesoftheprio_to_weight[]array,precalculated.

*

*Incaseswheretheweightdoesnotchangeoften,wecanusethe

*precalculatedinversetospeeduparithmeticsbyturningdivisions

*intomultiplications:

*/

staticconstu32prio_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,

};

最后，说下对CFS“完全公平”的理解：

①不再区分进程类型，所有进程公平对待

②对I/O消耗型进程，仍然会提供快速响应(对睡眠进程做时间补偿)

③优先级高的进程，获得CPU时间更多(vruntime增长的更慢)

可见CFS的完全公平，并不是说所有进程绝对的平等，占用CPU时间完全相同，而是体现在vruntime数值上，所有进程都用虚拟时间来度量，总是让vruntime最小的进程抢占，这样看起来是完全公平的，但实际上vruntime的更新，增长速度，不同进程是不尽一样的。CFS利用这么个简单的vruntime机制，实现了以往需要相当复杂算法实现的进度调度需求，高明！