CFS 完全公平调度算法

简介

Complete Fair Schedule，是linux中对普通进程的一种调度算法，旨在使每个进程都运行相同多的运行次数.
其中vruntime是虚拟运行时间，是CFS给每个进程的一个计数器，vruntime越大表示该进程运行次数越多，那么下次轮到它的优先级也就越低。

实现

CFS的实现比较简单，CFS内部需要一个有序的数据结构，能快速获取vruntime最小的进程，并且由于每次调度进程vruntime值会增加，因此还需要该数据结构能快速插入。这里联想到了三个数据结构，一是跳表，二是红黑树，三是小根堆，然而既然是写linux内核怎么可能用lowB的跳表？并且小根堆可扩展性较弱，因此选择了红黑树。

整个过程是这样的。首先接收要调度的进程，将这些进程的key设为它们的pid，而参与红黑树计算的value设为它们的vruntime。这时vruntime都是1，但并不是每个进程都有相同的概率能被调度到。我们知道进程调度中有优先级（priority）的概念，优先级越高应该越容易被调度，那么我们不能单单通过vruntime来排序，而应该将priority和vruntime进行组合，即 value = vruntime / （log2（priority））。这个公式是我瞎猜的，不过公式应满足priority越大value越小。

这样我们得到一个红黑树，我们获取最左边的叶子，那就是最小值，把它取下来获取pid，调度pid进程。之后将它的vruntime++，再将它插入到红黑树当中