wiki.osdev.org 系列之 - Scheduling Algorithms

type

Post

status

Published

slug

2022/12/08/wiki-osdev-org-scheduling-algorithms.html

summary

调度算法是指定分配给进程和线程多少CPU时间的算法。

1 Interactive Scheduling Algorithms（交互式调度算法）

1.1 Round Robin（轮询法）

Round Robin 是最简单的抢占式调度算法。仅使用一个进程队列。当系统定时器触发时，队列中的下一个进程被切换，被抢占的进程被放回队列中。

每个进程都被分配了一个时间片或“量子”。这个量程决定了进程在被抢占之前可以运行的系统计时器滴答数。例如，如果计时器以 100Hz 的频率运行，并且进程的时间片大小为为 10 个时钟滴答，则它可能运行 100 毫秒（10/100 秒）。为实现这一点，运行的进程被赋予一个变量，该变量从它的时间片开始，然后在每个时钟滴答过程中进行递减操作，直到它变成零。该进程还可以通过执行

阻塞系统调用（即 
I/O）

来放弃其时间片，就像在其他抢占式算法中一样。

在 Round Robin 算法中，每个进程被赋予相等的时间片；最大的问题是如何选择时间片的大小。

以下是一些注意事项：量程越小，用于上下文切换的时间比例就越大。

交互式进程应该在被抢占之前进行 I/O，以避免不必要的抢占。

时间片越大，用户体验越“滞后”——应避免超过 100 毫秒的时间片。

一个常用的时间片折衷值是在 20 毫秒到 50 毫秒之间。

Round Robin 的优点包括其简单性和严格的“先到先得”性质。缺点包括缺少优先级系统：大量的低权限进程可能会使一个高权限进程饿死。

1.2 Priority-Based Round Robin（基于优先级的轮询）

优先级调度类似于轮询调度，但是允许进程的层次结构。使用多个进程队列，每个优先级一个。只要优先级更高的队列中有进程，它们就会先运行。例如，如果您有 2 个队列，"high"和"low"，在这种状态下：


"high": X
"low": xterm, vim, firefox

第一个运行的进程是 X，然后如果它阻塞（可能是 I/O），状态将是：


"high":
"low": xterm, vim, firefox

下一个运行的进程是 xterm。如果将进程“kswapd”添加到“high”，它将获得下一个时间片：


"high": kswapd
"low": vim, firefox, xterm

优先级调度器中通常使用 4 到 16 个队列。

该算法的优点是简单，对优先级的支持合理。缺点（或可能的优点）是特权进程可能会将非特权进程完全饿死。这并不是一个问题，因为进程(特别是守护进程，通常是特权的)通常会因为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.

1.2.1 SVR2 Unix Implementation（SVR2 Unix 实现）

经典的 UNIX 系统以轮询的方式调度同等优先级的进程，每个进程运行固定的时间片。如果一个更高优先级的进程变得可运行，它将抢占当前进程（如果它不是在内核模式下运行，因为经典的 UNIX 内核是不可抢占的）即使进程没有完成它的时间片。这样，高优先级进程可能会饿死低优先级进程。为了避免这种情况，在计算进程优先级时引入了一个新的因素:“使用率”因子。

这个因素允许内核动态地改变进程优先级。当进程未运行时，内核会周期性地增加其优先级。当进程获得一些 CPU 时间时，内核会降低其优先级。该方案将潜在地防止任何进程的饥饿，因为最终任何等待进程的优先级将上升到足以被调度的程度。

所有用户空间优先级都低于最低系统优先级。用户进程的使用因子是根据该进程消耗的实时计算时间来计算的。在最后一个实时单元中使用大量计算时间的进程被分配低用户优先级。由于交互性进程的特点是计算与实时的比率较低，因此无需任何特殊安排即可维持交互响应。

如果没有符合执行条件的进程，CPU 将空闲直到下一次中断，这将在最多一个时钟滴答后发生。处理中断后，内核再次尝试调度一个进程运行。

References

Ken Thompson，“UNIX 实施”，2.3 - 同步和调度，贝尔实验室

Maurice J. Bach，“UNIX 操作系统的设计”，第 8 章 - 进程调度和时间，Prentice Hall

1.3 Shortest Process Next（最短进程优先）

交互式系统的 SRTN（最短剩余时间）版本。这里的问题是我们不能说出用户的下一个命令是什么。该算法需要预测:)

1.4 Lottery Scheduling（抽签调度或彩票调度）

抽签调度是一种简单的算法，从统计上保证每个可运行进程的处理器时间的可变比例。这个概念很像彩票（抽签）。在每个调度决策中，每个可运行的进程都会获得一些“彩票”（签）。然后生成一个随机数，对应于特定的票（签）。拿到该票（签）的进程获得了时间片。

虽然不能绝对保证进程将被平等对待，但鉴于在抢占式多任务系统中调度事件的频率（非常大），这意味着它能够做到非常接近。分配给进程的票数除以总票数是分配给该进程的时间片的统计分数。例如，如果这些进程获得了这个数量的票据：


foo - 5
bar - 7
bash - 4

分配给每个进程的处理器时间的分数应该是：


foo - 5/16 - 31%
bar - 7/16 - 44%
bash - 4/16 - 25%

正如您所看到的，创建一个细粒度的优先级系统是很简单的：只需给更高优先级的进程更多的票据即可。

彩票调度的优势包括细粒度优先级和统计公平性。缺点包括需要可靠的随机数生成器和非绝对保证，尤其是在具有大时间片的系统上。

您需要实现一个随机数生成器才能使用此算法。

2 Batch Scheduling Algorithms（批处理调度算法）

2.1 First Come First Served（先来先服务）

这种调度方法用于批处理系统，具有非抢占性。它只实现了一个队列，该队列按任务进入的顺序保存任务。

任务到达的顺序对于周转时间非常重要：


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)

优势：

简单的

公平的

问题：

护航效应(车队的效果)

任务到达的顺序对于平均周转时间非常重要

2.2 Shortest Job First (SJF)（最短作业优先）

也是非抢先的。它选择运行队列中可用的最短作业/进程。

该调度算法假定运行时间是事先已知的。

优点:

接近最佳(周转时间)

问题:

只有当所有作业/进程同时可用时才是最优的

通常运行时间是未知的…

2.3 Shortest Remaining Time Next（最短剩余时间优先）

SJF（Shortest Job First）的抢占式版本。 Schedulre 选择剩余运行时间最短的作业/进程。

优势：

可能是最佳的（周转时间）

问题：

运行时间必须是已知的

2.4 Highest Response Ratio Next（最高响应比优先）

3 Real-Time Scheduling Algorithms（实时调度算法）

实时调度算法是一类特殊的算法，要求它们可以保证进程在截止日期之前完成。让这些算法能够工作的唯一方法是，它们至少知道进程的截止日期是什么时候，以及进程占用了系统多少时间。只有当系统没有过载（主观术语）时，线程才能保证在截止日期之前完成。

每个任务必须每秒调度次，或每毫秒 (调度一次。每次运行该任务最多需要毫秒。然后，此任务会创建的负荷。

系统作为一个整体有一个负载，它是所有任务负载的总和：。如果系统负载超过（在极少数情况下它可能会稍微大一些，但我们不计算它们）使用速率单调调度无法调度系统。如果此系统负载超过，则对于任何实时系统都是不可调度的。请注意，对于普通系统，任何负载都是可能的，包括非常大的负载。但是，它们会使系统非常不可用。

3.1 Rate Monotonic Scheduling(速率单调调度)

速率单调调度是一种调度实时线程的方法，可以保证没有线程会超过它们的截止日期。

系统的负载可能会有所不同，但有一个基于利用率的测试，如果满足测试要求，就可以保证系统始终是可调度的。例如，具有一个进程的系统的利用率限制是 100%（因为不需要抢占）。具有 3 个进程的系统的利用率限制约为 69%。

基于利用率的测试就足够了，但不是必需的。如果进程集通过了基于利用率的测试，那么它将是可调度的。然而，可以构建未通过利用率测试但实际上（平凡）可调度的进程集。

RMS 调度的工作原理是根据每个任务的时间间隔为每个任务分配一个优先级。间隔最短的任务获得最高优先级，间隔最大的任务获得最低优先级（尽管仍然是实时的）。然后，这些任务的运行类似于优先级抢占[#Round-Robin]。这意味着，任何可以运行的任务都会运行，如果一个任务运行但有更高优先级的任务可用，则更高优先级的任务将运行。

如果您的系统基于轮询调度程序，这是进行实时调度的最简单方法。

3.2 Earliest Deadline First（最早到期优先）

EDF 调度程序中的每个任务都被分配了一个_最后期限_（例如，任务必须在未来某一时刻完成）。每次将任务插入系统或完成任务时，调度程序都会查找最接近截止日期的任务并选择它执行。为了确保调度程序仍然能够满足每个截止日期，'监视器必须评估每个新任务是否会使系统过载，如果它会，则拒绝执行。

为了实现基于 EDF 的系统，必须知道任务的截止日期（可以选择计算为“未来不超过 X 毫秒”）和执行任务所需的预期时间（由监视器要求）。 QoS 网络路由器通常会实现 EDF 调度的变体。

同样，EDF 系统有一个基于利用率的测试。然而，限制更简单 - 无论集合中有多少进程，它始终为 100%。这使得可调度性的动态分析更容易。不仅如此，EDF 利用率测试是充分且必要的，因此可以依赖它来提供可调度性的准确指示。

有关详细信息，请参阅 Burns & Wellings 的“实时系统和编程语言”。

4 See Also