Linux内核——进程管理之CFS调度器（基于版本4.x）

《奔跑吧linux内核》3.2笔记，不足之处还望大家批评指正

建议阅读博文理解linux cfs调度器

　　进程大致可以分为交互式进程，批处理进程和实时进程。对于不同的进程采用不同的调度策略，目前linux内核中默认实现了4种调度策略，分别是deadline、realtime、cfs和idle，分别适用struct sched_class来定义调度类。

　　4种调度类通过next指针串联在一起，用户空间程序可以使用调度策略api函数（sched_setscheduler()）来设定用户进程的调度策略。

问题一：请简述对进程调度器的理解，早起linux内核调度器（包括o(n)和o(1)）调度器是如何工作的？

　　调度器是按一定的方式对进程进行调度的一种机制，需要为各个普通进程尽可能公平地共享cpu时间。

　　o(n)调度器发布与1992年，从就绪队列中比较所有进程的优先级，然后选择一个最高优先级的进程作为下一个调度进程。每一个进程有一个固定时间片，当进程时间片使用完之后，调度器会选择下一个调度进程，当所有进程都运行一遍后再重新分配时间片。这个调度器选择下一个调度进程前需要遍历整个就绪队列，花费o(n)时间。

　　o(1)调度器用于linux2.6.23内核之前，它为每个cpu维护一组进程优先级队列，每个优先级一个队列，这样在选择下一个进程时，只要查询优先级队列相应的位图即可知道哪个队列中有就绪进程，查询时间常数为o(1)。

问题二：请简述进程优先级、nice和权重之间的关系。

　　内核使用0~139的数值表示进程的优先级，数值越低优先级越高。优先级0~99给实时进程使用，100~139给普通进程使用。在用户空间由一个传统的变量nice值映射到普通进程的优先级(100~139)。

　　nice值从-20~19，进程默认的nice值为0。这可以理解为40个等级，nice值越高，则优先级越低，反之亦然。（nice每变化1，则相应的进程获得cpu的时间就改变10%）。

　　权重信息即为调度实体的权重，为了计算方便，内核约定nice值为0的权重值为1024，其他的nice值对应相应的权重值可以通过查表的方式来获取，表即为prio_to_weight。

问题三：请简述cfs调度器是如何工作的。

　　cfs调度器抛弃以前固定时间片和固定调度周期的算法，采用进程权重值的比重来量化和计算实际运行时间。引入虚拟时钟的概念，每个进程的虚拟时间是实际运行时间相对nice值为0的权重的比例值。进程按照各自不同的速率比在物理时钟节拍内前进。nice值小的进程，优先级高且权重大，其虚拟时钟比真实时钟跑得慢，但是可以获得比较多的运行时间；反之，nice值大的进程，优先级低，权重也低，其虚拟时钟比真实时钟跑得快，获得比较少的运行时间。cfs调度器总是选择虚拟时钟跑得慢的进程，类似一个多级变速箱，nice值为0的进程是基准齿轮，其他各个进程在不同变速比下相互追赶，从而达到公正公平。

问题四：cfs调度器中的vruntime是如何计算的？

　　vruntime=(delta_exec*nice_0_weight)/weight。其中，delta_exec为实际运行时间，nice_0_weight为nice为0的权重值，weight表示该进程的权重值。在update_curr()函数中，完成了该值的计算，此时，为了计算高效，将计算方式变成了乘法和移位vruntime=(delta_exec*nice_0_weight*inv_weight)>>shift，其中inv_weight=2^32/weight，是预先计算好存放在prio_to_wmult中的。

问题五：vruntime是何时更新的？

　　创建新进程，加入就绪队列，调度tick等都会更新当前vruntime值。

问题六：cfs调度器中的min_vruntime有什么作用？

　　min_vruntime在cfs就绪队列数据结构中，单步递增，用于跟踪该就绪队列红黑树中最小的vruntime。

问题七：cfs调度器对新创建的进程和刚唤醒的进程有何关照？

　　对于睡眠进程，其vruntime在睡眠期间不增长，在唤醒后如果还用原来的vruntime值，会进行报复性满载运行，所以要修正vruntime，具体在enqueue_entity()函数中，计算公式为vruntime+=min_vruntime，vruntime=max(vruntime, min_vruntime-sysctl_sched_lantency/2)。

　　对于新创建的进程，需要加上一个调度周期的虚拟是时间(sched_vslice())。首先在task_fork_fair()函数中，place_entity()增加了调度周期的虚拟时间，相当于惩罚，se->vruntime=sched_vslice()。接着新进程在添加到就绪队列时，wake_up_new_task()->activate_task()->enqueue_entity()函数里，se->vruntime+=cfs_rq->min_vruntime。

问题八：如何计算普通进程的平均负载load_avg_contrib？runnable_avg_sum和runnable_avg_period分别表示了什么含义？

　　load_avg_contrib=runnable_avg_sum*weight/runnable_avg_period。

　　runnable_avg_sum为调度实体的可运行状态下总衰减累加时间。

　　runnable_avg_period记录的是上一次更新时的总周期数（一个周期是1024us），即调度实体在调度器中的总衰减累加时间。

　　runnable_avg_sum越接近runnable_avg_period，则平均负载越大，表示该调度实体一直在占用cpu。

问题九：内核代码中定义了若干个表，请分别说出它们的含义，比如prio_to_weight、prio_to_wmult、runnable_avg_yn_inv、runnable_avg_yn_sum。

　　prio_to_weight表记录的是nice值对应的权重值。

　　prio_to_wmult表记录的是nice值对应的权重值倒转后的值inv_weight=2^32/weight。

　　runnable_avg_yn_inv表是为了避免cpu做浮点计算，提前计算了公式2^32*实际衰减因子（第32ms约为0.5）的值，有32个下标，对应过去0~32ms的负载贡献的衰减因子。

　　runnable_avg_yn_sum表为1024*（y+y^2+…+y^n），y为实际衰减因子，n取1~32。（实际衰减因子下图所示）

图 实际衰减因子

问题十：如果一个普通进程在就绪队列里等待了很长时间才被调度，那么它的平均负载该如何计算？

 　　一个进程等待很长时间之后（过了很多个period），原来的runnable_avg_sum和runable_ave_period值衰减后可能变成0，相当于之前的统计值被清0。