BlockLune's Blog
首页 标签 关于 |

进程调度 - OSTEP 笔记

发表于 2024-12-25
许可证 CC BY-NC-SA 4.0 noteoperating-systemostepprocessprocess-scheduling

目录

这是我的 OSTEP 系列笔记的一部分，此篇主要包含了进程调度的相关知识，包括调度指标和各种调度策略的说明。

调度指标

为了比较不同调度策略，我们需要一些指标。这些指标包括：

  • 周转时间 (turnaround time): 任务的完成时间减去任务到达的时间，即：

    周转时间完成时间到达时间

  • 响应时间 (response time): 任务到达到任务首次运行的时间，即：

    响应时间首次运行到达时间

平均版本的这两个指标（即平均周转时间和平均响应时间）都是各自的和除以任务数。

像周转时间这样的指标可以归类为 性能指标。另一类指标是 公平性指标。性能和公平往往是矛盾的。

先进先出

先进先出（First In First Out 或 FIFO）调度，也称为 先到先服务（First Come First Served 或 FCFS）。这种调度遵循非常简单的原则：哪个任务先到，就先执行哪个。

先进先出

如图 7.1 所示，A、B、C 三个任务先后到达，每个任务都需要运行 10s。按照先进先出的原则，系统依次运行 A、B、C。假设 A、B、C 只是略微有所先后，大致都在 0 时刻到达。由图 7.1，A、B、C 的完成时间分别是时刻 10、20、30。所以，它们的周转时间分别是 10s、20s、30s。平均周转时间为 20s（）。

图 7.2 是另一个例子，展示了一种极端情况。A、B、C 仍然大约都在 0 时刻到达，但这种情况中的 A 需要运行 100s，B、C 仍然是运行 10s。这时，A、B、C 的完成时间分别为时刻 100、110、120，周转时间分别为 100s、110s、120s，平均周转时间是 110s（）！这被称为 “护航效应” —— 由于一个长任务被排在了一系列短任务之前，导致平均周转时间陡增。

最短任务优先

顾名思义，最短任务优先（Shortest Job First，SJF） 就是先运行耗时最短的任务，然后是次短的项目，如此进行下去。

还是以图 7.2 这个例子为例，即 100s 的 A 和 10s 的 B 和 C 这三个任务的情况。使用最短任务优先调度策略，B、C 将会被优先调度，形成下面图 7.3 中所示的运行顺序：

最短任务优先

在这种情形下，平均周转时间为 50s（）。

但是，如果 A、B、C 并不是同时到达的呢？图 7.4 展示了 A 在 0 时刻到达，随后 B、C 在 10 时刻到达的情形。这种情况下，A 已经在运行了，B、C 不得不等待其完成。这种情况下的平均周转时间为 103.33s，即 。

最短完成时间优先

上面介绍到的调度都是 非抢占式的（non-preemptive），即一个任务一旦开始运行，其他任务必须等待它结束后才能运行。但是，几乎所有现代化的调度程序都是 抢占式的（preemptive）。下面要介绍的就是这样一种调度策略。

最短完成时间优先（Shortest Time-to-Completion First，STCF） 又称 抢占式最短作业优先（Preemptive Shortest Job First，PSJF）。当新任务进入系统时，这种调度策略会从剩余任务和新任务中选择剩余时间最短的任务进行调度。

对图 7.4 中的例子使用 STCF 策略进行调度，会得到图 7.5 所示的情形：

最短完成时间优先

在这样的调度下，平均周转时间缩短到 50s。

轮转

(To Be Continued)