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

时间:2021-08-07 14:36:26

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

建议阅读博文https://www.cnblogs.com/openix/p/3262217.html理解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。(实际衰减因子下图所示)

Linux内核——进程管理之CFS调度器(基于版本4.x)图 实际衰减因子

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

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