【OSTEP】进程调度: 介绍 | Convoy护航效应 | 最短任务优先(SJF) | 最短完成时间优先(STCF) | 轮转 RR | 结合I/O

💭 写在前面

本系列博客为复习操作系统导论的笔记，内容主要参考自：

• Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau, Operating Systems: Three Easy PiecesA. Silberschatz, P. Galvin, and G. Gagne,
• Operating System Concepts, 9th Edition, John Wiley & Sons, Inc., 2014, ISBN 978-1-118-09375-7.Microsoft. MSDN(Microsoft Developer Network)[EB/OL]. []. .

0x00 调度介绍（Scheduling: Introduction）

Workload assumptions：

1. Each job runs for the same amount of time.  （每项任务的运行时间相同）

2. All jobs arrive at the same time.  （所有任务在同一时间就位）

3. All jobs only use the CPU (i.e., they perform no I/O).  （所有任务只是用CPU）

4. The run-time of each job is known.    （每个任务的运行时间是已知的）

Performance metric（性能指标）：

• Turnaround time（运行周期）: The time at which the job completes minus the time at which the job arrived in the system.  （完成任务所需的事件 减去 任务就位于系统的时间）

• Waiting time（等待时间）: The amount of time a process has been waiting in the ready queue （一个进程在准备队列中等待的时间）

Another metric is fairness（公平性）：

• Performance and fairness are often at odds in scheduling.（性能和公平性在调度中往往是不一致的）

0x01 Algorithm1：先进先出 （FIFO）

First Come, First Served (FCFS) （先到先得）：

• Very simple and easy to implement.  （简单且易于实施）

Example:

• A arrived just before B which arrived just before C.
• Each job runs for 10 seconds.

𝑨𝒗𝒆𝒓𝒂𝒈𝒆 𝒕𝒖𝒓𝒏𝒂𝒓𝒐𝒖𝒏𝒅 𝒕𝒊𝒎𝒆 =

0x02 护航效应（Convoy Effect）

FCFS -> Convoy，shit！

❓ 为什么 FIFO 没那么厉害？ 因为会出现护航效应！即 车队效应！

一些好事较少的潜在资源消费者被排在重量级的资源消费者之后，这意味着需要等很长时间。

假设每个工作的运行时间 不再 相同，举个例子：

• A 刚好在 B 之前就位，而 B 刚好在 C 之前到达。
• A 跑了100秒，B 和 C 各跑了10 秒。

𝑨𝒗𝒆𝒓𝒂𝒈𝒆 𝒕𝒖𝒓𝒏𝒂𝒓𝒐𝒖𝒏𝒅 𝒕𝒊𝒎𝒆 =

❓ 到底什么是护航效应，为什么护航效应不好？

💡 举个例子：你去超市购物，只是买了个巧克力，但是只有一个收银台，排在你前面的人买了两购物车的东西，结账估计都得结10分钟，虽然你的巧克力只需要10秒就能结完了，但这是排队，你必须等，也就是你也得陪着你前面的人，等20分钟！就是这种感觉。你会感觉如何？这让人心态爆炸！

🔑 解决方案：你要么换个队伍（前提是有），要么就摆平心态好好等，深呼吸~ 心理暗示，一会就好，一会就好~~

Convoy Effec：假设有一个CPU密集型（大突发时间）进程，在准备队列中，其他几个进程的突发时间相对爆发时间较少，但有输入/输出（I/O）约束（经常需要I/O操作）。

然后会发生以下情况：

• I/O绑定的进程首先被分配CPU时间。由于它们的CPU密集度较低。由于它们的CPU密集度较低，很快就会被执行，然后转到I/O队列。
• 现在，CPU密集型进程被分配CPU时间。由于它的突发时间很高，它需要时间来完成。
• 当CPU密集型进程被执行时，I/O绑定的进程。完成他们的I/O操作并被移回准备队列。
• 然而，I/O绑定的进程要等待，因为CPU密集型进程仍未完成 ——  This leads to I/O devices being idle.  （这就导致了I/O设备的闲置）。

Convoy Effect (Continued)：

• 当CPU密集型进程结束时，它被送到I/O队列中，以便它可以访问I/O设备。
• 同时，与I/O绑定的进程获得他们所需的CPU时间并移回I/O队列。
• 然而，由于CPU密集型进程仍在访问I/O设备，他们不得不等待。因此，the CPU is sitting idle now （CPU现在是闲置的）

FIFO调度器的问题

• FIFO：当短任务必须等待任务时，周转时间和等待时间会非常大（因为有车队效应）。

想一想新的调度器？

• SJF（最短任务优先）。选择具有最小运行时间的任务。

为了解决这个问题，需要放宽假设条件（工作必须保持运行直到完成为止）。我们还需要调度程序本身的一些机制。

0x03 Algorithm 2：最短任务优先（SJF）

Run the shortest job first, then the next shortest, and so on

• Non-preemptive scheduler

Example:

• A 刚好在 B 之前就位，而 B 刚好在 C 之前到达。
• A 跑了 100 秒，B 和 C 各跑了 10 秒。

𝑨𝒗𝒆𝒓𝒂𝒈𝒆 𝒕𝒖𝒓𝒏𝒂𝒓𝒐𝒖𝒏𝒅 𝒕𝒊𝒎𝒆 =

SJF with Late Arrivals from B and C

让我们放宽假设2： Jobs can arrive at any time.

举个例子：

• A在 t=0 时到达，需要运行100秒。
• B和C在 t=10 时到达，各自需要运行10秒。

𝑨𝒗𝒆𝒓𝒂𝒈𝒆 𝒕𝒖𝒓𝒏𝒂𝒓𝒐𝒖𝒏𝒅 𝒕𝒊𝒎𝒆 =

这三项工作的平均时间是 103.33。从图中可以看出，即使 B 和 C在 A 到达不久之后到达，他们仍然是要被迫等待 A完成，同样是遭遇了护航问题。

0x04 Algorithm3：最短完成时间优先（STCF）

Add preemption to SJF → Shortest Time-to-Completion First (STCF).

• Also known as Preemptive Shortest Job First (PSJF) or Shortest Remaining Time First (SRTF).

向 SJF 添加抢占的行为，称为 最短完成时间优先（STCF），或称为抢占式最短作业优先（PSJF）调度程序。

每当新工作进入系统时，他就会确定剩余工作和新工作中谁的剩余时间最少，然后调度该工作。

STCF 最短完成时间优先：

• 确定剩余工作和新工作。
• 安排剩余时间最少的工作。

举个例子：

• A在 t = 0 时到达，需要运行100秒。
• B 和 C 在 t =10 时到达，各自需要运行10秒。

𝑨𝒗𝒆𝒓𝒂𝒈𝒆 𝒕𝒖𝒓𝒏𝒂𝒓𝒐𝒖𝒏𝒅 𝒕𝒊𝒎𝒆 =

0x05 SJF之弊端：确定下一个CPU突发长度 （Determining Next CPU Burst Length）

SJF is optimal in that it gives minimum average waiting and turnaround time for a given set of processes（SJF是最优的，因为它为给定的流程集提供了最小的平均等待和周转时间的时间）

• Moving a short process before a long one decreases the waiting time of the short processes more than it increases the waiting time of the long process. （将一个短流程移到一个长流程之前，会减少短流程的等待时间，而不是增加长流程的等待时间。进程的等待时间比增加长进程的等待时间要多）
• The difficulty is knowing the length of the CPU burst ➔ can estimate the length（困难在于知道CPU突发的长度 ➔ 可以估计长度 ）

估算可以通过使用以前的CPU爆发的长度，使用指数平均法（Exponential Averaging）来完成：

指数平均法的例子：

预测下一个 CPU 突发长度：

0x06 新度量指标：响应时间（Response Time）

The time from when the job arrives to the first time it is scheduled.

📚 响应时间定义从任务到达系统到首次运行的时间：

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

遗憾的是， STCF和相关方法在响应时间上不是很理想。

举个例子，如果三个工作同时到达，第三个工作必须等待前两个工作全部运行后才能运行。这种方法虽然有很好的周转时间，但是对于响应时间和交互性来说是非常糟糕的。假设你在终端前输入，不得不等待十秒才能看到系统回应，只是因为其他一些工作已经在你之前被调度，你肯定会觉得很不爽。

How can we build a scheduler that is sensitive to response time?

因此，为了解决这个问题，我们该如何构建响应时间敏感的调度程序？

0x07 Algorithm4：轮转（RR）

为了解决刚才的问题，我们将介绍一种新的调度算法，我们称之为 轮转 （Round-Robin），简称为 。

Time-slicing Scheduling（时间片调度）

• Each process gets a small unit of CPU time (time quantum), usually 10-100 milliseconds. After this time has elapsed, the process is preempted and added to the end of the ready queue.（每个进程得到一个小单位的CPU时间（时间量子），通常为10-100ms。在这个时间过后，该进程被抢占并添加到就绪队列的末端。）
• The length of a time slice must be a multiple of the timer-interrupt period.（时间片长度必须是时钟中断周期的倍数）

轮转轮转，顾名思义，就是轮着运行，RR 在一个时间片（time slice，有时称为调度因子）内运行一个工作，然后切换到运行队列中的下一个任务，而不是一股脑地运行一个任务直到结束。它反复执行，直到所有任务完成。

因此， RR 有时被称为时间切片（time-slicing），请注意，时间片长度必须是时钟中断周期的倍数。因此，如果时钟中断是每 10ms 中断一次，则时间片可以是 10ms, 20ms 或 10ms 任何其他倍数。

如果在准备队列中有 n 个进程，time quantum 是 q，那么每个进程最多可以获得1/n的CPU时间，每次最多可以获得q个时间单位的分块单位。没有进程的等待时间超过（n-1) x q个时间单位。

表现（Performance）：

• q large → FCFS。
• q small → 相对于上下文切换而言，q 必须得大。

RR 是公平的，但在衡量标准上地表现并不理想，比如周转时间或等待时间。

0x08 时间片的长度是关键（The Length of Time Slice is Critical.）

较短的时间片

• 更好的响应时间。
• 上下文切换的成本 将主导整体性能。

较长的时间片

• 摊销（amortize）了切换的成本
• 响应时间更差

🔺 总结： Deciding on the length of the time slice presents a trade-off to a system designer

（决定时间片的长度对系统设计者来说是需要 权衡利弊 的）

Time Quantum vs Turnaround Time（时间量子与周转时间）：

平均周转时间不一定随着时间量子的增加而改善。如果时间量子太大，RR调度就变成FCFS策略。80%的CPU突发事件应短于时间量子。

0x09 结合 I/O （Incorporating I/O）

首先，我们将放宽假设3，All programs perform I/O （所有程序都执行 I/O ）

举个例子：

• A 和 B 各需要50ms的CPU时间。
• A 运行了 10ms，然后发出一个 I/O 请求。（每个I/O需要10ms）
• B 只是使用了 50ms 的CPU，没有执行任何 I/O。
• 调度器先运行A，然后再运行B。

重叠（overlap）：

这样我们就看到了调度程序可能如何结合 I/O，通过将每个 CPU 突发作为一项工作，调度程序确保 "交互" 的进程正常运行。当这些交互式作业正在执行 I/O 时，其他 CPU 密集型作业将运行，从而更好地利用处理器。

当一个工作发起一个 I/O 请求时：

• 工作被阻断，等待 I/O 完成
• 调度器应该在 CPU 上安排另一个工作

当 I/O 完成的时：

• 一个中断被提出
• 操作系统将该进程从阻塞状态移回准备状态

📌 [ 笔者 ]   王亦优
📃 [ 更新 ]   2022.10.1
❌ [ 勘误 ]   /* 暂无 */
📜 [ 声明 ]   由于作者水平有限，本文有错误和不准确之处在所难免，
              本人也很想知道这些错误，恳望读者批评指正！