# 调度，第 1 部分：调度过程 > 原文：<https://github.com/angrave/SystemProgramming/wiki/Scheduling%2C-Part-1%3A-Scheduling-Processes> ## 关于调度的思考。 [CPU 调度](https://en.wikipedia.org/wiki/Scheduling_(computing))是有效选择在系统 CPU 内核上运行哪个进程的问题。在繁忙的系统中，将有比 CPU 内核更多的可立即运行的进程，因此系统内核必须评估应该在 CPU 上运行哪些进程以及哪些进程应放在就绪队列中以便稍后执行。 多线程和多 CPU 内核的额外复杂性被认为是对这个初始展示的干扰，因此在此忽略。 非母语人士的另一个问题是“时间”的双重含义：“时间”一词可用于时钟和经过时间的上下文。例如“第一个过程的到达时间是上午 9 点。”并且，“算法的运行时间是 3 秒”。 ## 如何测量调度以及哪种调度程序最佳？ 调度会影响系统的性能，特别是系统的 _ 延迟 _ 和 _ 吞吐量 _。吞吐量可以通过系统值来度量，例如 I / O 吞吐量 - 每秒写入的字节数，或者每单位时间可以完成的小进程数，或者使用更高级别的抽象，例如客户数量每分钟处理的记录。延迟可以通过响应时间（进程可以开始发送响应之前的经过时间）或等待时间或周转时间（完成任务所经过的时间）来度量。不同的调度程序提供不同的优化权衡，可能适合或不适合所需的使用 - 没有针对所有可能的环境和目标的最佳调度程序。例如，“shortest-job-first”将最小化所有作业的总等待时间，但在交互式（UI）环境中，最好将响应时间最小化（以某些吞吐量为代价），而 FCFS 看起来直观公平且易于实现但是遭遇了康宏效应。 ## 什么是到达时间？ 进程首次到达就绪队列并准备开始执行的时间。如果 CPU 空闲，则到达时间也将是执行的开始时间。 ## 什么是先发制人？ 在没有抢占的情况下，进程将一直运行，直到它们无法再进一步利用 CPU。例如，以下条件将从 CPU 中删除进程，并且可以为其他进程调度 CPU：进程由于信号而终止，被阻塞等待并发原语或正常退出。因此，一旦调度了一个进程，即使具有高优先级的另一个进程（例如，较短的作业）出现在就绪队列上，它也将继续。 通过抢占，如果将更优选的进程添加到就绪队列，则可以立即移除现有进程。例如，假设在 t = 0 时使用 Shortest Job First 调度程序，有两个进程（P1 P2），执行时间为 10 和 20 ms。 P1 已预定。 P1 立即创建一个新进程 P3，执行时间为 5 毫秒，并将其添加到就绪队列中。没有先发制人，P3 将在 10ms 后运行（P1 完成后）。通过抢占，P1 将立即从 CPU 中逐出，而是放回到就绪队列中，而 P3 将由 CPU 执行。 ## 哪些调度员遭受饥饿？ 任何使用优先级形式的调度程序都可能导致饥饿，因为可能永远不会调度早期进程（分配 CPU）。例如，对于 SJF，如果系统继续有许多要安排的短作业，则可能永远不会安排更长的作业。这一切都取决于[类型的调度程序](https://en.wikipedia.org/wiki/Scheduling_(computing)#Types_of_operating_system_schedulers)。 ## 为什么可以将一个进程（或线程）放在就绪队列上？ 当一个进程能够使用 CPU 时，该进程被置于就绪队列中。一些例子包括： * 阻止进程等待存储或套接字中的`read`完成，现在可以使用数据。 * 已创建新进程并准备启动。 * 进程线程在同步原语（条件变量，信号量，互斥锁）上被阻止，但现在能够继续。 * 阻止进程等待系统调用完成，但已传递信号并且信号处理程序需要运行。 在考虑线程时可以生成类似的示例。 ## 效率措施 `start_time`是进程的挂钟开始时间（CPU 开始工作）`end_time`是进程的结束挂钟（CPU 完成进程）`run_time`是所需的 CPU 时间总量`arrival_time`是进程进入调度程序的时间（CPU 可能无法启动它） ## 什么是'周转时间'？ 从进程到达到结束的总时间。 `turnaround_time = end_time - arrival_time` ## 什么是'响应时间'？ 从进程到达到 CPU 实际开始工作所花费的总延迟（时间）。 `response_time = start_time - arrival_time` ## 什么是“等待时间”？ 等待时间是 _ 总 _ 等待时间，即进程在就绪队列上的总时间。一个常见的错误是认为它只是就绪队列中的初始等待时间。 如果没有 I / O 的 CPU 密集型进程需要 7 分钟的 CPU 时间才能完成，但需要 9 分钟的挂钟时间才能完成，我们可以得出结论，它已被放置在就绪队列中 2 分钟。对于那些 2 分钟，该过程已准备好运行但没有分配 CPU。工作等待时无关紧要，等待时间为 2 分钟。 `wait_time = (end_time - arrival_time) - run_time` ## 什么是车队效应？ “Convoy 效应是持续备份 I / O 密集型进程的地方，等待占用 CPU 的 CPU 密集型进程。这导致 I / O 性能不佳，即使对于 CPU 需求很小的进程也是如此。” 假设 CPU 当前已分配给 CPU 密集型任务，并且存在一组处于就绪队列中的 I / O 密集型进程。这些进程只需要很少的 CPU 时间，但它们无法继续，因为它们正在等待从处理器中删除 CPU 密集型任务。在 CPU 绑定进程释放 CPU 之前，这些进程一直处于饥饿状态。但很少会释放 CPU（例如，在 FCFS 调度程序的情况下，我们必须等到进程因 I / O 请求而被阻止）。 I / O 密集型进程现在可以最终满足他们的 CPU 需求，他们可以快速完成这些需求，因为他们的 CPU 需求很小，并且 CPU 再次被分配回 CPU 密集型进程。因此，整个系统的 I / O 性能受到所有进程的 CPU 需求饥饿的间接影响。 这种效果通常在 FCFS 调度程序的上下文中讨论，但循环调度程序也可以展示长时间量子的康宏效应。 ## Linux 调度 截至 2016 年 2 月，Linux 默认使用 _ 完全公平调度程序 _ 进行 CPU 调度，使用预算公平调度“BFQ”进行 I / O 调度。适当的调度会对吞吐量和延迟产生重大影响。延迟对于交互式和软实时应用（如音频和视频流）尤为重要。有关详细信息，请参阅此处的讨论和比较基准[ [https://lkml.org/lkml/2014/5/27/314](https://lkml.org/lkml/2014/5/27/314) ]。 以下是 CFS 的日程安排 * CPU 创建一个红黑树，其中包含进程虚拟运行时（runtime / nice_value）和睡眠公平性（如果进程正在等待某些内容，则在等待时将其提供给 CPU）。 * （好的值是内核优先处理某些进程的方式，优先级越低） * 内核根据此度量标准选择最低的一个，并安排该进程下一次运行，将其从队列中取出。由于红黑树是自平衡的，因此保证$ O（log（n））$（选择 min 进程是相同的运行时） 虽然它被称为公平调度程序，但存在一些问题。 * 调度的进程组可能具有不平衡负载，因此调度程序粗略地分配负载。当另一个 CPU 获得空闲时，它只能查看组计划的平均负载而不是单个核心。因此，只要平均值很好，空闲 CPU 就不会从正在燃烧的 CPU 中获取工作。 * 如果一组进程正在运行，则在非相邻核心上存在错误。如果两个核心超过一跳，负载平衡算法甚至不会考虑该核心。这意味着如果 CPU 是空闲的并且正在做更多工作的 CPU 超过一跳，它将不会进行工作（可能已经修补）。 * 线程在一个核心子集上进入休眠状态后，当它被唤醒时，它只能在它正在睡眠的核心上进行调度。如果这些核心现在是公共汽车