cpu调度-完全公平调度模式

本篇我们来讲讲另一种调度方式-公平调度方式。公平调度模式基于一个基本概念：相对于MLFQ优化周转时间和相应时间，公平调度模式是保证每个任务都获得一定比例的cpu时间。

基本概念：票据数量代表应该分配的多少

任务拥有多少票据的比例就应该分配多少比例的资源。假如有2个任务A和B，A拥有75张票据，B拥有25张票据，那么A应该占有75%的cpu时间，B占有25%的cpu时间。
奖池调度法通过经常（一个时间片的间隔）抽奖的方式来决定谁中奖了。系统中有任务A和任务B，一共票据数量有100张。其中A有75张票据，0号到74号。B拥有25张，75号到99号。然后开始抽奖，如果抽到0到74就选择A，否则选择B。调度器会把加载选择的进程状态然后运行它。
我们可以观察到，通过随机来保证正确的可能性，但并不是保证正确。这个很容易理解，如果随机的次数比较少，偶然性就比较大，如果随机次数很多，就很接近我们想要的比例了。
这里在谈谈随机的好处，随机的好处其一是不会有个特定的输出会导致性能很差，比如算法中的随机化快排就是为了避免特定的场景下有很差的性能。其二随机很轻量化，只需要跟踪很小的状态。比如要统计每个进程使用的cpu时间，需要运行每个进程后再统计。随机化只需要知道每个进程拥有票据的数量就可以了。其三随机速度很快，一个最简单的伪随机算法是线性同余法，只有一个加法和乘法的运算。

票据机制

乐透调度法提供了一些操作票据不同的方法。

• 票据货币化，允许任务给自己的子任务分发票据，这些票据最终可以兑换成全局票据。
  举个例子，用户A和B分别拥有100张票据，用户A运行了2个任务A1和A2，给它们分别500张内部票据（一共1000张）。B只运行了一个任务B1给它10张内部票据（一共10张）。系统把A1和A2的500张票据对应到全局票据上分别是50张。而B1的10张内部票据对应系统全局票据为100张。
  User A -> 500 (A’s currency) to A1 -> 50 (global currency)
  -> 500 (A’s currency) to A2 -> 50 (global currency)
  User B -> 10 (B’s currency) to B1 -> 100 (global currency)

• 票据转移。使用票据转移，一个进程可以临时性的把自己的票据交给另外一个进程。这个在client/server的环境中尤为有用，当client发送一个消息给server要求为它提供一些服务时，client可以把自己的票据交给server，最大化加快server的运行，运行完毕后，server归还client的票据。

• 通货膨胀在某些时候可能是比较有用的技术，一个进程可以临时的增加或者降低它的票据数量。当然，在相互竞争的场景下，进程之间相互不信任，这就没有意义了。一个贪婪的进程可以给自己派发大量的票据，进而得到几乎独占整个机器。通货膨胀可以应用到一组进程，大家相互信任彼此的，在这种场景下，一个进程如果知道自己需要更多cpu时间，它就可以提高自己票据数量，整个过程无需和其他进程进行商量。

乐透调度伪代码如下：

1 // counter: used to track if we’ve found the winner yet
2 int counter = 0;
3
4 // winner: use some call to a random number generator to
5 // get a value, between 0 and the total # of tickets
6 int winner = getrandom(0, totaltickets);
7
8 // current: use this to walk through the list of jobs
9 node_t *current = head;
10 while (current) {
11 counter = counter + current->tickets;
12 if (counter > winner)
13 break; // found the winner
14 current = current->next;
15 }
16 // ’current’ is the winner: schedule it...

实现

乐透调度法最令人惊奇是实现它的的简单性。只需有个好的随机数去选择票据。让我们假设使用链表来组织进程。下列是链表组织进程的示意图。

首先我们要随机出400以内的随机数，然后遍历链表就能选择合适的任务去运行了。为了让链表更高效的运行，最好从大到小的排序这个链表。排序后并不影响算法的正确性，但是可以减少遍历的次数，尤其是当有个进程拥有大量票据的情况下。

如何分配票据

为什么不能使用确定性

使用随机的策略的调度器只能提供大概的准确性，尤其对短任务而言这种调度方式不能提供准确性。因为这种原因 Waldspurger发明出步调度，一种确定的公平调度器。
步调度也是很直接的，每个任务都拥有步长，步长与拥有票据数量成反比。用上面的例子A，B，C分别拥有票据100，50，250。那么步长的计算，为一个较大的数，这里我么用10000 除票据数量。那么步长就分别是100，200，40。进程每次运行时，我们都用步长来递增计数器，通过这种方式来跟踪它的全局进度。
调度器决定下一个运行的进程通过步长，选择目前来说运行了最短的路径的进程。
伪代码如下：

curr = remove_min(queue); // pick client with min pass
schedule(curr); // run for quantum
curr->pass += curr->stride; // update pass using stride
insert(queue, curr); // return curr to queue

linux的完全公平的调度模式

基于上述的关于公平调度模式的准备工作，当前的linux的调度模式使用轮询的方式达到相似的目标。这种调度模式叫做Completely Fair Scheduler(CFS)，实现它的方式具有高效性和可扩展性。
为了很高效的实现，在CFS整个设计中就只准备花少量时间来做调度决策，它使用了十分聪明的数据结构来组织任务。最近的研究表明，调度器的高效性是很令人惊奇的重要，在研究Google的数据中心表明，甚至通过积极的优化，调度本身仍然占据了5%的整个数据中心的cpu时间。减少调度的负载架构现代调度器的关键目标。

基本操作

大部分基于此概念的调度器都使用定长的时间片，但是CFS有些不同。它的目标是在多个竞争的进程之间公平的划分cpu时间，通过简单的统计virtual runtime (vruntime)，物理时间的一个比例。
随着每个进程的运行，调度器会统计virtual runtime。每个进程大部分情况下以相同的速率增加，当调度决策发生时，调度器会选择一个最小vruntime的进程去运行。
这就带来一个问题，调度决策应该何时发生，多久发生一次？如果CFS决策太频繁了 ，公平性保证了，但是会带来性能的消耗（太多的上下文切换），如果CFS决策时间太久了，公平性就难以保障了。
CFS通过一个参数来控制调度时间。第一个为sched latency，CFS使用这个值来进行判断多久决策一次，一个典型的数值为48ms，当系统中有n个进程运行时，sched latency / n为调度周期。
举个例子，假设系统中有4个进程在运行，用sched latency除以4，所以到达每个进程的时间片为12ms，调度器首选选出一个进程运行直到用完时间片，然后在最小vruntime的进程去运行，循环如此。需要注意的是当任务数量发生变化时，时间片长度也会动态发生变化。
如果我们系统中有很多进程运行时呢，是不是可能会导致太短的时间片呢？为了解决这个问题CFS引入了第二个参数min_granularity，通常这个值被设置成6ms，当划分后的时间片长度小于min_granularity，就强制设置成min_granularity的值，目的在于避免太多的调度消耗。
举个例子系统中有10个进程运行，时间片长度本该是4.8ms，有了min_granularity所以时间片长度被设置成6ms了。
CFS利用了周期性的时钟中断，当中断发生时，CFS就有机会进行调度决策了。就算一个任务拥有不是整数倍调度周期的时间片，也没关系，因为vruntime被精确记录了，随着时间的增加，慢慢就会拿到合适的cpu时间的。

权重

CFS同样可以控制进程的权重，允许系统管理员给某些进程更多的cpu时间。这里并不是票据而是进程的nice等级，nice值从-20到19之间，默认值为0。正数代表低优先级，负数代表高优先级。具体优先级对应的权重如下

static const int prio_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,
};

根据权重值，可以计算每个进程的时间片长度，计算公式如下：

除此之外，vruntime的计算方法也发生改变了。

这里注意2个概念，调度器的调度周期以及每个进程划分的时间片。是否加入不同权重后，调度器的调度周期也发生改变呢？调度进行决策周期和时钟周期有关而时钟周期固定周期发生的，所以可能发生的情况是时间片是不同的，但是决策周期是相同的。时钟中断大概是每2ms到3ms发生一次，这个在内核编译期间就决定的，可能会稍微丢失一点精度。

使用红黑树

调度器必须要高效，现在谈论到一个问题，如何调度器找到下一个需要调度的任务。现代操作系统可能运行1000个任务呢，不可能使用链表去遍历。
CFS解决进程的组织任务通过红黑树，通过vruntime的大小，红黑树是二叉平衡树，对比简单的树而言，简单的树可能最坏情况下退化成链表。红黑树只需要简单的一些维护的工作就可以保证树的高度在logN。CFS并不把所有的进程都维护在这个数据结构上，只是包含running以及runable状态的进程。如果进程阻塞了，就从这里移除。红黑树插入，查找以及删除都是logN的复杂度，有良好的性能。

处理在I/O以及sleep的进程

假想一个场景，有2个正在运行的进程A和B，A都是继续运行的，这时候B睡眠了10秒。如果按照之前的调度策略保持vruntime保持不变的话，A唤醒后，接下来会独占cpu10秒钟以便能补上之前落后的10秒的时间，这显然是不能接受的。
CFS在这种情况下回修改刚刚唤醒后的任务的vruntime为在集合中能查找到的最小的vruntime的值。通过这种方式来避免饿死任务发生的可能性，但是一个经常睡眠一小段时间的任务就不能获得它本该公平获得的cpu时间了。

最后的总结

我们谈到了比例分配调度的方式，提到了3种方式：乐透法，步长法以及linux的完全公平调度模式。完全公平的调度方法有点像具有权重的RR调度法。
没有任何一个调度器是完美的，公平调度模式也有它的问题，比如对经常I/O的程序不够友好，还有个问题就是如何分配进程的权重，这个问题任然存在。其他的调度器比如MLFQ会自动调整进而更容易部署。
好消息是很多场景下对这些问题并不敏感，完全公平的调度能很高效的运行。比如在一个数据中心中，需要分配1/4的cpu给windows VM，剩下的给linux安装程序。按比例分配会很简单和高效。