CFS学习总结

最近在学些CFS，网上关于CFS的博客很多，但是没有人能够给一个指导性的建议来辅助我看代码。所以自己总结了一下。
CFS完全公平调度算法的公平是体现在每个进程的vruntime上，CFS总是优先调度vruntime值最小的进程。但是由于进程的nice/priority的存在，使得每一个进程不可能真正的做到公平。

Linux内核使用struct load_weight来计算每一个进程的权重。这个权重就是真实的时间跟vruntime之间的比值。换句话说，就是优先级高的进程，它的虚拟时间走起来就比较慢，也就是说它能够获得更多的实际运行时间。

Struct laod_weight里面之所以有两个成员完全是为了计算的方便。inv_weight = ～0UL/weight。

当scheduler更新一个进程的相关信息（when ？）的时候,会根据本次实际运行时间以及weight来计算其对entity的vruntime的delta贡献值。如果一个进程的vruntime不是runqueue里面最小(letfmost)的了，就需要做进程切换。换句说，一个runqueue上的各个进程之间抢夺CPU资源的竞争，是由它的运行时间以及优先级/weight来决定的。

那么PELT的作用是什么？ PELT是per-entity load tracking的缩写。What is load ？ load balance的load,也就是负载。PELT虽然是基于per-entity的load记录，但是它的最终目的是为了平衡SMP中的各个CPU，不至于使得一些CPU处于明显的空闲，另外一些CPU处于极度繁忙状态，最大化系统的throughput。

PELT是如何计算每一个entity的load的呢？

 Linux scheduler将系统时间（wall clock）人为分为一个个小的时间段，为了计算的方便为1ms(1024us).PELT认为每一个时间段对于现在的load的贡献值是不一样的，所以假如了一个衰减系数(y)。那么一个load的计算公式为：u_0 + u_1*y + u_2*y^2 + u_3*y^3 + ... （其中u_x为每一段的时间，单位为us）。衰减系数是多少呢？y³² = ?.

那么load的最大值是多少呢？1024(1+y+y² + y³ + ... ) = 1024*(y/1-y) = 47742（请查考幂级数求和公式）。

如何求一个load在内核函数__update_load_avg中有着详细的描述（各种trick）。或者参照http://blog.csdn.net/helloanthea/article/details/30081627. 但是内核代码中的函数跟这篇blog中的函数稍有差别。在新的内核代码中，load的计算中加入了weight的归一化。即认为两个不同的task，其运行时间是一样的，由于优先级/weight的不同，其对于runqueue的load的贡献值也不同。

讲完了load的计算，那么load是如何发挥作用的呢？

find_idlest_group及find_idlest_cpu中都是用了weighted_cpuload去获得了一个runqueue的总的load，以此作为选择cpu的一个依据。这些都在select_task_rq_fair函数中有所体现。

总来的来说，weight和load是两个独立的衡量标准，一个用来衡量runqueue内部的task的竞争的考量，一个用于衡量runqueue之间的balance。当然load的计算上也考虑了weight的影响。