操作系统简介
嘿哈布尔！ 我想提请您注意一系列文章——我认为是一本有趣的文学作品的翻译——OSTEP。 本材料非常深入地讨论了类 unix 操作系统的工作，即与进程、各种调度程序、内存和构成现代操作系统的其他类似组件一起工作。 你可以在这里看到所有材料的原件 . 请注意，翻译是非专业的（相当随意），但我希望我保留了一般意思。
关于这个主题的实验室工作可以在这里找到：
其他部分：
您也可以查看我的频道 =)
调度程序简介
问题的本质：如何制定调度器策略
底层的调度策略框架应该如何设计？ 关键假设应该是什么？ 哪些指标很重要？ 早期计算系统使用了哪些基本技术？
工作负载假设
在讨论可能的策略之前，我们首先对系统中运行的进程进行一些简单的题外话，这些进程统称为 工作量。 定义工作负载是构建策略的关键部分，您对工作负载了解得越多，您就能编写出更好的策略。
让我们对系统中运行的进程（有时也称为 工作 （任务）。 几乎所有这些假设都不现实，但却是思想发展所必需的。
- 每个任务运行相同的时间，
- 所有任务同时设定，
- 分配的任务一直持续到完成为止，
- 所有任务仅使用CPU，
- 每个任务的运行时间是已知的。
调度程序指标
除了一些关于负载的假设之外，还需要另一个用于比较不同调度策略的工具：调度程序指标。 度量只是对某事物的某种度量。 有许多指标可用于比较调度程序。
例如，我们将使用一个名为 周转时间 （周转时间）。 任务周转时间定义为任务完成时间与任务到达系统时间之间的差值。
T周转=T完成-到达
由于我们假设所有任务同时到达，则 Ta=0，因此 Tt=Tc。 当我们改变上述假设时，这个值自然会改变。
另一个指标—— 公平 （公平、诚实）。 生产力和公平性往往是规划中对立的特征。 例如，调度程序可能会优化性能，但代价是等待其他任务运行，从而降低公平性。
先进先出 (FIFO)
我们可以实现的最基本的算法称为 FIFO 或 先来（进来），先服务（出去）。 该算法有几个优点：它非常容易实现，它符合我们所有的假设并且很好地完成了工作。
让我们看一个简单的例子。 假设同时设置了 3 个任务。 但我们假设任务 A 比其他任务早到达一点，因此它会比其他任务更早出现在执行列表中，就像 B 相对于 C 一样。假设它们每个都会执行 10 秒。 在这种情况下，完成这些任务的平均时间是多少？
通过计算值 - 10+20+30 并除以 3，我们得到平均程序执行时间等于 20 秒。
现在让我们尝试改变我们的假设。 特别是假设 1，因此我们将不再假设每个任务需要相同的时间来执行。 这次 FIFO 会表现如何呢？
事实证明，不同的任务执行时间对 FIFO 算法的生产率具有极其负面的影响。 假设任务 A 需要 100 秒才能完成，而任务 B 和 C 仍各需要 10 秒。
从图中可以看出，系统的平均时间为(100+110+120)/3=110。 这种效应称为 护航效应，当资源的一些短期消费者将在重度消费者之后排队时。 这就像杂货店里的排队队伍，前面有一位顾客推着满满的购物车。 解决问题的最好方法是尝试更换收银机或者放松深呼吸。
最短工作优先
是否有可能以某种方式解决重量级进程的类似情况？ 当然。 另一种类型的规划称为最短工作优先 （SJF）。 它的算法也相当原始——顾名思义，最短的任务将首先启动，一个接着一个。
在此示例中，运行相同进程的结果将是平均程序周转时间的改进，它将等于 50 而不是 110，几乎好 2 倍。
因此，对于所有任务同时到达的给定假设，SJF 算法似乎是最优算法。 然而，我们的假设似乎仍然不现实。 这次我们改变假设 2，这次假设任务可以随时出现，而不是同时出现。 这会导致什么问题？
假设任务 A (100c) 首先到达并开始执行。 在 t=10 时，任务 B 和 C 到达，每个任务都需要 10 秒。 因此，平均执行时间为 (100+(110-10)+(120-10))3 = 103。调度程序可以采取什么措施来改进这一点？
最短完成时间优先 (STCF)
为了改善这种情况，我们省略了假设 3，即程序已启动并运行直至完成。 此外，我们需要硬件支持，正如您可能猜到的，我们将使用 计时器 中断正在运行的任务并 上下文切换。 这样，当任务B、C到达时，调度器可以做一些事情——停止执行任务A，将任务B和C放入处理中，完成后继续执行进程A。这样的调度器称为 STCFили 抢占式作业优先.
该规划器的结果将是以下结果：((120-0)+(20-10)+(30-10))/3=50。 因此，这样的调度程序对于我们的任务来说变得更加优化。
指标响应时间
因此，如果我们知道任务的运行时间并且这些任务只使用CPU，STCF将是最好的解决方案。 在早期，这些算法运行得很好。 然而，用户现在大部分时间都在终端上度过，并期望获得高效的交互体验。 于是，一个新的衡量标准诞生了—— 响应时间 （回复）。
响应时间计算如下：
响应=T首次运行−到达
因此，对于前面的示例，响应时间将为：A=0、B=0、C=10 (abg=3,33)。
事实证明，STCF 算法在 3 个任务同时到达的情况下不太好——它必须等到小任务完全完成。 因此，该算法对于周转时间指标有利，但对于交互性指标不利。 想象一下，如果您坐在终端前尝试在编辑器中输入字符，却不得不等待 10 秒以上，因为其他任务正在占用 CPU。 这不太令人愉快。
那么我们面临另一个问题——如何构建一个对响应时间敏感的调度器？
循环赛
开发了一种算法来解决这个问题 循环赛 （RR）。 基本思想非常简单：我们不是运行任务直到任务完成，而是运行任务一段时间（称为时间片），然后切换到队列中的另一个任务。 该算法重复其工作，直到完成所有任务。 在这种情况下，程序的运行时间必须是定时器中断进程的时间的倍数。 例如，如果定时器每x=10ms中断一个进程，那么进程执行窗口的大小应该是10的倍数并且是10,20或x*10。
让我们看一个例子：ABC 任务同时到达系统，每个任务都想运行 5 秒。 SJF 算法将在开始另一个任务之前完成每个任务。 相比之下，启动窗口 = 1s 的 RR 算法将完成以下任务（图 4.3）：
（再次 SJF（不利于响应时间）
（循环法（有利于响应时间）
RR算法的平均响应时间为(0+1+2)/3=1，而SJF算法的平均响应时间为(0+5+10)/3=5。
可以合理地假设时间窗口是 RR 的一个非常重要的参数；时间窗口越小，响应时间越长。 但是，不应将其设置得太小，因为上下文切换时间也会影响整体性能。 因此，执行窗口时间的选择由操作系统架构师设置，并且取决于计划在其中执行的任务。 切换上下文并不是唯一浪费时间的服务操作 - 正在运行的程序还对许多其他事物进行操作，例如各种缓存，并且每次切换都需要保存和恢复此环境，这也可能需要花费大量时间时间。
如果我们只讨论响应时间指标，RR 是一个很棒的调度程序。 但是，该算法的任务周转时间指标将如何表现？ 考虑上面的例子，当A、B、C的运行时间=5s并且同时到达时。 任务 A 将在 13 秒结束，B 将在 14 秒结束，C 将在 15 秒结束，平均周转时间为 14 秒。 因此，RR 是周转指标最差的算法。
更一般地说，任何 RR 类型的算法都是公平的；它在所有进程之间平均分配 CPU 时间。 因此，这些指标不断相互冲突。
因此，我们有几种对比算法，同时仍然有几个假设 - 任务时间已知并且任务仅使用 CPU。
与 I/O 混合
首先，我们去掉假设4，即进程只使用CPU；当然，情况并非如此，进程可以访问其他设备。
当任何进程请求 I/O 操作时，该进程就会进入阻塞状态，等待 I/O 完成。 如果I/O发送到硬盘，那么这样的操作可能需要长达几毫秒甚至更长的时间，并且此时处理器将处于空闲状态。 在此期间，调度程序可以让任何其他进程占用处理器。 调度程序必须做出的下一个决定是进程何时完成其 I/O。 当这种情况发生时，就会发生中断，操作系统会将调用 I/O 的进程置于就绪状态。
让我们看一下几个任务的示例。 它们每个都需要 50ms 的 CPU 时间。 然而，第一个将每 10ms 访问一次 I/O（也将每 10ms 执行一次）。 而进程B只是使用一个没有I/O的50ms处理器。
在此示例中，我们将使用 STCF 调度程序。 如果在调度程序上启动像 A 这样的进程，调度程序将如何表现？ 他将执行以下操作：首先他将完成流程 A，然后完成流程 B。
解决这个问题的传统方法是将进程 A 的每个 10 ms 子任务视为一个单独的任务。 因此，当开始使用 STJF 算法时，50 ms 任务和 10 ms 任务之间的选择是显而易见的。 然后，当子任务A完成时，进程B和I/O将被启动。 I/O 完成后，习惯上会再次启动 10ms 的进程 A，而不是进程 B。这样就可以实现重叠，即在第一个进程等待 CPU 的同时，CPU 被另一个进程使用。输入/输出。 结果，系统得到了更好的利用——当交互式进程等待 I/O 时，其他进程可以在处理器上执行。
神谕已不复存在
现在让我们尝试摆脱任务运行时间已知的假设。 这通常是整个列表中最糟糕和最不切实际的假设。 事实上，在一般的普通操作系统中，操作系统本身通常对任务的执行时间知之甚少，那么在不知道任务执行时间的情况下如何构建调度程序呢？ 或许我们可以用一些RR原理来解决这个问题？
总
我们研究了任务调度的基本思想，并研究了 2 个调度程序系列。 第一个首先启动最短的任务，从而增加周转时间，而第二个则在所有任务之间平均分配，从而增加响应时间。 两种算法都不好，而其他系列的算法都很好。 我们还研究了CPU和I/O的并行使用如何提高性能，但没有解决操作系统千里眼的问题。 在下一课中，我们将介绍一个回顾刚刚过去并尝试预测未来的规划器。 这就是所谓的多级反馈队列。
来源： habr.com