前置知识
列表调度，也被称为基于优先级列表的调度，是一种通过为进程分配优先级来构建有序列表的调度技术。它的基本运作方式是：系统会建立一个包含在特定时刻准备好执行的进程列表。然后，根据处理器（CPU）的可用状态（即空闲或忙碌），空闲的处理器会从该列表中选取进程并执行它们。
让我们通过一个具体的例子来深入理解列表调度。
示例：
假设我们共有 7 个进程：P1, P2, P3, P4, P5, P6, P7，它们之间存在以下依赖关系：
- P3 依赖于 P1 和 P2（只有当 P1 和 P2 都执行完毕后，P3 才能开始执行）。
- P4 依赖于 P3 和 P6（只有当 P3 和 P6 都执行完毕后，P4 才能开始执行）。
- P6 依赖于 P5。
依赖关系如下图所示：
让我们假设系统受到两个处理器的限制，且这两个处理器当前都是空闲的。由于 P1、P2、P5 和 P7 是独立的（无依赖项），我们假设它们最初都在“就绪列表”中等待并准备好执行。
进程的分步执行过程：
- 我们只有两个空闲的处理器，因此让 P1 和 P2 首先获得执行。
- P1 和 P2 离开就绪列表，P3 进入就绪列表。此时，P3、P5、P7 位于就绪列表中。
- 假设在就绪队列现有的 3 个进程中，P3 和 P5 接下来获得执行。因此，P3 和 P5 离开就绪列表，P6 进入就绪列表。此时 P4 还不会进入就绪列表，因为它还依赖于尚未执行的 P6。
- 此时 P6 和 P7 在就绪列表中。因此，P6 和 P7 接下来获得执行。
- P6 和 P7 离开就绪列表，P4 进入就绪列表，最终 P4 获得执行，所有进程终止。
每一步的就绪列表状态如下图所示：
大家可以看到，整个执行过程在 4 个单位时间 后结束。但是，这个时间可能会根据操作系统使用的具体调度机制而有所不同。
调度算法如何影响执行时间
为了说明执行时间取决于所使用的调度算法，让我们考虑另一种情况：
- 假设这次 P5 和 P7 首先开始执行，而不是 P1 和 P2。
- 之后，P5 和 P7 移出就绪列表，P6 进入就绪列表。
- 此时 P1、P2、P6 在就绪列表中。假设 P2 和 P6 获得执行。
- P2 和 P6 移出就绪列表。随后 P1 获得执行。
- P1 移出就绪列表，P3 进入就绪列表，然后 P3 获得执行。
- 最后，P4 获得执行，所有进程执行完毕。
该执行过程的就绪列表状态如下所示：
大家可以看到，如果我们改变了进程执行的顺序，总共花费了 5 个单位时间。这证明了调度顺序对整体效率有直接影响。
算法策略
在列表调度中，优先级通常在调度过程开始之前静态确定。第一步是选择具有最高优先级的进程，第二步是选择最佳可能的资源（处理器）。
我们可以使用的一些调度策略包括：
- 最长路径算法
- 最长处理时间
- 关键路径法
算法的最终目标是最大化 CPU 利用率并最小化延迟。因此，无论哪种调度算法，只要能帮助我们根据具体的进程情况实现这一目标，都是可以使用的。