Scheduling Algorithms
调度算法(scheduling algorithm)是指示分配给 进程和线程CPU时间的算法。 任何调度算法的目标都是满足许多标准:
- 任何任务都不能缺乏资源 - 所有任务都必须在CPU时间获得机会;
- 如果使用优先级，则低优先级任务不得阻止高优先级任务;
- 调度程序必须随着越来越多的任务而很好地扩展，理想情况下时间复杂度是O(1)。例如，在linux内核中已经实现了此目标。
交互式调度算法
轮询
轮询是抢先调度器最简单的算法。 仅使用单个进程队列。 当系统定时器触发时，队列中的下一个进程会切换到CPU中，并且将被抢占的进程被放回队列中。
每个过程都被分配一个时间片或 “quantum”。 该quantum决定了该过程在被抢占之前可能运行的系统计时器的数量。 例如，如果计时器以100Hz运行，并且进程的量子是10个周期，则它可以运行100毫秒 (10/100秒)。 为了实现这一点，运行过程被赋予一个变量，该变量从其quantum值开始，然后在每个周期上递减，直到达到零。 与其他抢占算法一样，该过程还可以通过执行阻塞系统调用 (即i/O) 来放弃其quantum。
在轮询算法中，每个过程都被赋予相等的quantum; 最大的问题是如何选择时间quantum。
以下是一些注意事项:
quantum越小，上下文切换中使用的时间比例越大。
交互式进程在被抢占之前应该做I/O操作，这样就避免了不必要的抢占。
随着quantum增大，应避免100毫秒以上的“滞后”用户体验 。
通常选择的量子折衷方案在20毫秒至50毫秒之间。
轮询的优点包括简单和严格的 “先到先得” 性质。 缺点包括缺乏优先级系统: 许多低特权的进程可能会使一个高特权进程陷入饥饿状态。
基于优先级的轮询
优先级调度类似于轮询，但允许进程的层次结构。 使用多个进程队列，每个优先级一个。 只要优先级更高的队列中有进程，它们就会首先运行。 例如，如果你有2个队列，“高” 和 “低”，在这种状态下:
"high": X
"low": xterm, vim, firefox
运行的第一个进程将是X，然后如果它被阻止 (可能是由于I/O)，状态将是:
"high":
"low": xterm, vim, firefox
将运行的下一个进程将是xterm。 如果将过程 “kswapd” 添加到 “high”优先级中，则它将获得下一个quantum:
"high": kswapd
"low": vim, firefox, xterm
优先级调度程序中通常使用4到16个队列。
该算法的优点是简单且拥有对优先级的合理支持。 缺点 (或可能的优点) 是特权进程可能会完全饿死非特权进程（译者注：低优先级进程一直得不到CPU时间）。 实际上这倒不像它看起来那样有问题，因为进程 (特别是守护进程，通常是有特权的) 通常被I/O阻止。
让我们看一下队列中有三个进程的轮询调度程序: A B C:
A(time 0) B(time 10) C(time 10) A's time slice is zero: let's do round robin scheduling: B(time 10) C(time 10) A(time 10) ... one clock tick occurs ... the next one ... B(time 8) C(time 10) A(time 10) ... several clock ticks occur ... b's time slice is worn out ... C(time 10) A(time 10) B(time 10) ... ten clock ticks later ... A(time 10) B(time 10) C(time 10) ... now A has its share of CPU time again.
SVR2 Unix实现
经典UNIX系统以循环方式安排了 “同等优先” 进程，每个进程都运行固定的时间。 如果更高优先级的进程变得可运行，它将抢占当前进程 (如果它 “不是” 在内核模式下运行，因为经典UNIX内核是非抢占式的)，即使该进程没有完成它的时间quantum。 这样，高优先级进程可能会使低优先级进程挨饿。 为了避免这种情况，引入了计算进程优先级的新因素: “使用” 因子。
此因子允许内核动态地改变进程优先级。 当进程未运行时，内核会定期提高其优先级。 当进程收到一些CPU时间时，内核会降低其优先级。 该方案将潜在地防止任何进程饥饿，因为最终任何等待进程的优先级将上升到足以被安排。
所有用户空间优先级均低于最低系统优先级。 用户进程的使用因子是通过进程消耗的计算时间到实时的量来计算的。 在最后一个实时单元中使用了大量计算时间的进程就会被分配较低的用户优先级。 由于交互式过程的特征是计算与实时的比率低，因此无需任何特殊安排即可维持交互式响应。
如果没有符合执行条件的进程，则CPU会闲置直到下一个中断，这将在一个时钟滴答之后 “最多” 发生。 处理中断后，内核再次尝试调度要运行的进程。
参考
Ken Thompson，《UNIX实现》，2.3 - 同步和调度，贝尔实验室
Maurice J. Bach, "The Design of the UNIX Operating System", Chapter 8 - Process Scheduling and Time, Prentice Hall
最短进程优先
这里开始讨论用于交互式系统的SRTN (Shortest Remaining Time Next 其余最短进程优先)调度算法。 问题是，我们不能明确用户的下一个命令将是什么。 这个算法需要预测 :)
彩票调度
彩票调度是一种简单的算法，可在统计上保证每个可运行进程的处理器时间的可变比例。 这个概念很像彩票。 在每个调度决策中，每个可运行的进程都被赋予一定数量的 “彩票”。然后生成一个随机数，对应于一个特定的票据。 获得票据的进程获得了quantum。
尽管不能绝对保证将平等对待进程，但在抢先多任务系统中调度事件的频率意味着它概率上非常接近公平策略。 给定一个进程的票据数除以票据总数是给定该进程的quantum的统计分数。 例如，如果为这些过程提供了以下数量的票证:
foo - 5
bar - 7
bash - 4
给每个处理器时间的分数应为:
foo - 5/16 - 31%
bar - 7/16 - 44%
bash - 4/16 - 25%
如你所见，创建一个细粒度的优先级系统就可以变通解决了: 只需为更高优先级的进程提供更多票据即可。
彩票调度的优势包括细粒度的优先级和统计公平性。 缺点包括需要可靠的随机数发生器和非绝对保证，尤其是在具有大quantum的系统上。
你需要实现一个 随机数生成器 来使用这个算法。
批量调度算法
先到先得
这种调度方法用于批处理系统，它是非抢占式的。 它仅实现一个队列，该队列按任务的顺序保存任务。
任务到达的顺序对于周转时间非常重要:
Task1(24) Task2(6) Task3(6)
avg. Turnaround-Time = (24 + 30 + 36) / 3 = 30 time units (this assumes all tasks arrive at time 0)
Task1(6) Task2(6) Task3(24)
avg. Turnaround-Time = (6 +12 +36) / 3 = 18 time units (this assumes all tasks arrive at time 0)
优势:
-简单
-公平
问题:
-车队效应
-任务到达顺序对于平均周转时间非常重要
最短工作优先 (SJF)
也是非先发制人的。 它选择运行队列中可用的最短作业/进程。
此调度算法假定运行时间是事先已知的。
优势:
-接近最佳 (周转时间)
问题:
-仅当所有作业/流程同时可用时，才是最佳的
-通常运行时间不知道...
下一次最短剩余时间
SJF的先发制人版本 (最短工作优先)。 Schedulre选择剩余运行时间最少的作业/进程。
优势:
-可能是最佳的 (巡回时间)
问题:
-同样必须知道运行时间
下一个最高响应率
实时调度算法
实时调度算法是一类特殊的算法，它们要求可以保证进程在截止时间之前必须完成。 这些算法能够工作的唯一方法是，它们至少知道一个过程的截止时间是什么时候，以及这个过程需要多少系统时间。 只有在系统没有过载 (overloaded主观术语，过分忙碌) 的情况下，才能保证线程在截止日期之前完成。
每个任务必须被调度X t 次每秒，或者每个Y t 毫秒 (Y t = 1000 / X t)。 该任务的每次运行最多需要Zt 毫秒。 然后，此任务将创建Lt = Zt / Yt 的负载。
整个系统有一个负载L，它是所有任务负载的总和: L = E Lt。 如果系统负载超过0.7 (在某些罕见情况下，它可能会稍大一些，但我们不计算它们)，则系统无法使用速率单调调度来调度。 如果此系统负载超过1.0，则对于任何实时系统都是不可调度的。 请注意，对于普通系统，任何负载都是可能的，包括非常大的负载。 不过，这样的情况下系统将非常不可用。
速率单调调度
速率单调调度是一种可以保证所有实时线程都不会超过其截止日时间的调度方法。
系统的负载可能会有所不同，但是存在基于利用率的测试，如果满足，则可以保证系统始终是可调度的。 作为示例，具有一个进程的系统的利用率限制是100% 的 (因为不需要抢占)。具有3个进程的系统的利用率限制约为69%。
基于利用率的测试是 “足够的”，但不是 “必要的”。 如果进程集通过了基于利用率的测试，则它将是可调度的。 但是，可以构造未通过使用测试但实际上 (琐碎地) 可调度的过程集。
RMS调度通过根据每个任务的间隔为其分配优先级来工作。 间隔最短的任务获得最高优先级，间隔最大的任务获得最低优先级 (尽管仍然是实时的)。 然后，这些任务的运行类似于优先轮询抢占 [#Round-Robin]。 这意味着，任何可以运行的任务都会运行，如果某个任务运行，但优先级更高的任务可用，则运行优先级高的进行代替。
如果你的系统基于 轮询 调度程序，则这是进行实时调度的最简单方法。
最早期限优先 Earliest Deadline First
EDF调度程序中的每个任务都分配了一个 _deadline_ (例如，将来必须完成任务的时刻)。 每次将任务插入系统或完成时，调度程序都会查找具有最接近截止时间的任务，并选择其执行。 为了确保调度程序仍然能够满足每个截止日期，“监视器” 必须评估每个新任务是否会使系统过载，并拒绝执行。
为了实现基于EDF的系统，必须知道任务的截止时间 (可以选择计算为 “未来不超过X毫秒”) 和执行任务所需的预期时间 (监视器要求)。 QoS网络路由器通常实现EDF调度的变体。
同样，EDF系统有一个基于利用率的测试。 然而，限制更简单-无论集合中有多少个进程，它总是100% 的。 这使得可调度性的动态分析更加容易。 不仅如此，EDF利用测试既是 “足够的” 又是 “必要的”，因此可以依靠它来提供可调度性的准确指示。
有关更多信息，请参阅Burns & Wellings的 “实时系统和编程语言”。