Day6 让 scheduler 规划未来

tags: 铁人赛

前言

昨天讲到了行程的生老死别，那麽行程是如何被挑中，成为那百中选一能够执行的行程呢？那就不得不提到排程器(scheduler) 这个重要的挑选者了。

排程器 (scheduler )

凡事皆有轻重缓急，行程也是一样，每一个行程依据类型以及时限可以分成不同的优先权，优先权高的必然有必须早点完成的必要性，优先权低的可以先搁置，先把重要的行程先完成。
排程器(scheduler)就是负责完成将行程依照轻重缓急排序的演算法，能让资源在有限的情况下，完成最合理的顺序，这就是排程器背负的任务。
在排程演算法之前要先知道，排程本身的运作是需要耗费系统资源的，排程本身就是需要CPU的运算资源，会与其他行程争抢运行时间，所以并不是让很多时间让排程器做出最好的排序就是一个好的结果，而是要在尽可能短的时间内完成最好的解。

如上图，如果红色的区域是排程的时间，那麽当然希望能在最短的时间完成排程，才不会占用到实际的行程的执行时间。
以下提及一个经典的排程演算法 MLFQ 与两个 Linux 旧版使用的 O(n), O(1) 演算法。

经典排程演算法 (Multi-Level Feedback Queue, MLFQ)

上图是 MLFQ的精神，同时有多个队列，每一条队列里的行程都是同样优先级的，更重要的事情是这些行程的优先权是可以被排程器修改的，关於 MLFQ还有更多的规则，详细都在以下这篇文章。

Linux 2.4 O(n)排程器

Linux 这麽伟大的作业系统，一开始的排程器也是相当的简陋，排程器要维护两个连结串列(link list)，每次一个当成目前要执行的串列，另一个必须等到目前执行的串列为空时，才切换到另一个串列。每一次排程器从当下的串列头拿出一个行程执行，执行结束後，将该行程移动到另一个等待串列，并且依照优先权插入，直到目前执行的串列为空时，才换成另一个串列开始执行，也因为每次行程结束後需要依照正确的优先权插入另一个串列，所以最糟糕需要O(n)的时间复杂度。

Linux 2.6 O(1)排程器

在O(1)的排程器里，一样用到两个array，两个array的每一格都含有一个位元，与一个串列，该位元是为了确定串列是否为空，如果串列为空，则位元值设为0，反之则设1。这麽做可以将寻找下个行程的过程变成在一个bitarray内找到最高位是1的bit ，这个行为可以用 CPU 指令 : Find first set/one 达成。
详细步骤为以下

大致的排程步骤如下:

1. 在 active bitarray 里，寻找 left-most bit 的位置 x;
2. 在 active priority array（APA）中，找到对应 queue APA[x];
3. 从 APA[x] 中 dequeue 一个 process，dequeue 後，如果 APA[x] 的 queue 为空，那麽将 active bitarray 里第 x bit 设定为 0;
4. 对於目前执行完的行程，重新计算其 priority，然後 enqueue 到 expired priority array（EPA）相应的 queue EPA[priority];
5. 若 priority 在 expired bitarray 里对应的 bit 为 0，将其设定 1;
6. 如果 active bitarray 全为 0，将 active bitarray 和 expired bitarray 交换;

参考资料 : Linux核心设计：不只挑选任务的排程

目前Linux 使用的是CFS 演算法，会在明天介绍。