操作系统简介
嘿哈布尔！ 我想提请您注意一系列文章——我认为是一本有趣的文学作品的翻译——OSTEP。 本材料非常深入地讨论了类 unix 操作系统的工作，即与进程、各种调度程序、内存和构成现代操作系统的其他类似组件一起工作。 你可以在这里看到所有材料的原件 . 请注意，翻译是非专业的（相当随意），但我希望我保留了一般意思。
关于这个主题的实验室工作可以在这里找到：
其他部分：
您也可以查看我的频道 =)
规划：多级反馈队列
在本次讲座中，我们将讨论开发最著名的方法之一的问题
规划，这就是所谓的 多级反馈队列 （MLFQ）。 MLFQ 调度程序于 1962 年由 Fernando J. Corbató 在一个名为
兼容的分时系统（CTSS）。 这些作品（包括后来的作品
Multics）随后被提名为图灵奖。 调度程序是
随后改进并获得了现有的外观
一些现代系统。
MLFQ 算法试图解决两个基本的重叠问题。
首先，它试图优化周转时间，正如我们在上一讲中讨论的那样，它是通过从队列最前面开始的方法来优化的
短期任务。 然而，操作系统不知道这个或那个进程将运行多长时间，并且这个
操作SJF、STCF算法的必要知识。 其次, MLFQ 尝试
使系统对用户做出响应（例如，对于坐着的用户）
等待任务完成时盯着屏幕），从而最大限度地减少时间
回复。 不幸的是，像 RR 这样的算法减少了响应时间，但是
对周转时间指标产生不良影响。 因此我们的问题是：如何设计
可以满足我们的要求但同时又一无所知的调度程序
一般来说，该过程的性质是什么？ 调度器如何学习任务的特征，
它启动哪个从而做出更好的调度决策？
问题的本质：在知识不完善的情况下如何规划任务的设置？
如何设计一个同时最小化响应时间的调度程序
用于交互式任务，同时在不知情的情况下最大限度地减少周转时间
了解任务执行时间？
注：我们从之前的事件中吸取教训
MLFQ 队列是一个很好的系统示例，它可以学习
过去的事件可以预测未来。 此类方法常常
在操作系统中发现（以及计算机科学的许多其他分支，包括分支
硬件预测和缓存算法）。 类似的徒步旅行
当任务具有行为阶段并因此可预测时触发。
然而，人们应该小心使用这种技术，因为预测非常容易。
可能会被证明是错误的，并导致系统做出比
将完全没有知识。
MLFQ：基本规则
考虑 MLFQ 算法的基本规则。 尽管该算法的实现
有几种，基本方法是相似的。
在我们将考虑的实现中，MLFQ 将有几个
单独的队列，每个队列都有不同的优先级。 任何时候，
准备执行的任务位于同一个队列中。 MLFQ 使用优先级，
决定运行哪个任务来执行，即具有更高的任务
优先级（队列中优先级最高的任务）将首先启动
队列。
当然，一个特定队列中可以有多个任务，所以
因此他们将具有相同的优先级。 在这种情况下，将使用该机制
RR 用于这些任务中的启动计划。
因此，我们得出 MLFQ 的两个基本规则：
- 规则1：如果优先级（A）>优先级（B），任务A将运行（B将不会）
- 规则2：如果优先级(A) = 优先级(B)，则A&B使用RR启动
基于上述，规划 MLFQ 的关键要素是
是优先事项。 而不是给每个人一个固定的优先级
任务时，MLFQ 根据观察到的行为改变其优先级。
例如，如果某个任务在等待键盘输入时不断在 CPU 上退出，
MLFQ 将保持进程优先级高，因为这就是
交互过程应该有效。 相反，如果任务是持续不断的
长时间是CPU密集型的，MLFQ会降级它
优先权。 因此，MLFQ 将研究进程运行时的行为。
和使用行为。
让我们画一个例子来说明队列在某个时刻可能是什么样子
时间然后你会得到这样的东西：
在该方案中，2个进程A和B位于具有最高优先级的队列中。 过程
C 位于队列的中间，进程 D 位于队列的最后。 根据上述
根据 MLFQ 算法的描述，调度器只会执行具有最高优先级的任务
根据RR优先级，任务C、D将无法工作。
当然，静态快照无法全面了解 MLFQ 的工作原理。
准确理解情况如何随时间变化非常重要。
尝试1：如何更改优先级
此时，您需要决定MLFQ将如何改变优先级
任务（以及任务在队列中的位置）在其生命周期期间。 为了
其中，您需要记住工作流程：一定数量
运行时间短的交互式任务（因此频繁发布
CPU）和几个长时间使用 CPU 的任务，同时
此类任务的响应时间并不重要。 这样你就可以进行第一次尝试
使用以下规则实现 MLFQ 算法：
- 规则3：当一个任务进入系统时，它被放入具有最高优先级的队列中
- 优先。
- 规则 4a：如果任务使用其整个时间窗口，那么它
- 优先级降低。
- 规则 4b：如果任务在其时间窗口到期之前释放 CPU，则它
- 保持相同的优先级。
示例 1：单个长时间运行的任务
从这个例子中可以看出，准入任务设置为最高
优先事项。 经过 10ms 的时间窗口后，进程的优先级会降低。
调度程序。 在下一个时间窗口之后，任务最终降级为
系统中的最低优先级，保留在原处。
示例 2：选择一个简短的任务
现在让我们看一个 MLFQ 如何尝试接近 SJF 的示例。 在那里面
例如，两个任务：A，这是一个持续长时间运行的任务
占用CPU和B，是一个短交互任务。 认为
当任务 B 到达时，A 已经运行了一段时间。
该图显示了该场景的结果。 任务 A 与任何任务一样，
CPU使用率处于最低水平。 任务 B 将在时间 T=100 到达并且将
放入最高优先级队列。 由于运行时间较短，
它将在到达最后一个队列之前完成。
从这个例子中，你应该明白该算法的主要目标：因为该算法不
知道一项长任务或短任务，那么首先他假设该任务
短并给予它最高优先级。 如果这真的是一个很短的任务，那么
它会运行得很快，否则如果它是一个很长的任务，它会运行得很慢
优先级下降，很快就会证明她确实是一个长期的任务，不
需要回应。
示例 3：I/O 怎么样？
现在让我们看一个 I/O 示例。 如规则 4b 中所述，
如果进程在没有完全使用其处理器时间的情况下释放处理器，
然后它保持相同的优先级。 这条规则的意图非常简单。
- 如果交互式作业执行大量 I/O，例如等待
从用户击键或鼠标，这样的任务将释放处理器
在指定的窗口之前。 我们不想忽略这样一个优先任务，
因此它将保持在同一水平。
此示例展示了算法如何处理此类进程 - 交互式任务 B，执行前仅需要 CPU 1 毫秒
I/O 进程和一个长时间占用 CPU 的作业 A。
MLFQ 使进程 B 保持最高优先级，因为它继续
释放CPU。 如果B是一个交互任务，那么本例的算法就达到了
其目的是快速启动交互式任务。
当前MLFQ算法存在的问题
在前面的示例中，我们构建了 MLFQ 的基本版本。 而且他似乎
很好、公平地完成了它的工作，在之间公平地分配 CPU 时间
长任务并允许短任务或访问频繁的任务
快速处理 I/O。 不幸的是，这种方法包含几个
严重的问题。
首先、饥饿问题：如果系统会有很多交互
任务，那么它们将消耗所有处理器时间，因此很长一段时间不会消耗任何处理器时间
该任务将没有机会被执行（他们正在挨饿）。
其次，聪明的用户可以编写他们的程序，以便
愚弄调度程序。 欺骗在于为了强迫而做某事
调度程序给进程更多的CPU时间。 该算法
上面描述的很容易受到此类攻击：在时间窗口实际上之前
结束后，需要执行一次I/O操作（对某些，无论是哪个文件）
从而释放CPU。 这样的行为会让你保持在同样的状态
队列本身并再次获得更大百分比的 CPU 时间。 如果你这样做
这是正确的（例如，在释放 CPU 之前运行 99% 的窗口时间），
这样的任务可以简单地独占处理器。
最后，程序可以随着时间的推移改变其行为。 那些任务
使用CPU的可以变得交互式。 在我们的例子中，类似
任务不会像其他任务那样得到调度程序的适当处理
（原始）交互式任务。
向观众提问：在现代世界中，可以对调度程序进行哪些攻击？
尝试 2：提高优先级
让我们尝试改变规则，看看是否可以避免出现问题
饥饿。 我们可以做什么来确保相关
CPU 任务将得到它们的时间（即使不长）。
作为问题的简单解决方案，您可以定期提出建议
增加系统中所有此类任务的优先级。 有很多方法
为了实现这一点，让我们尝试实现一些简单的例子：
所有任务同时具有最高优先级，因此新规则：
- Rule5：经过一段时间S后，将系统中的所有任务转移到最高队列。
我们的新规则同时解决了两个问题。 一、流程
保证不会挨饿：最高队列中的任务将共享
根据 RR 算法的处理器时间，因此所有进程都会收到
处理器时间。 其次，如果以前使用过某个进程
只有处理器变得交互，它才会保留在最高的队列中
收到后优先级一次性增加到最高。
让我们看一个例子。 在这种情况下，考虑一个进程使用
CPU 和两个交互的短进程。 在图中的左侧，该图显示了没有优先级提升的行为，因此在两个交互式任务到达系统后，长时间运行的任务开始饥饿。 在右图中，每 50ms 执行一次优先级增加，因此所有进程都保证接收处理器时间并定期启动。 本例以50ms为例，实际这个数字要高一些。
很明显，增加周期性上升时间 S 会导致
逻辑问题：应该设置什么值？ 当之无愧的其中之一
系统工程师 John Ousterhout 将系统中的此类量称为“voo-doo”
恒定，因为它们在某种程度上需要黑魔法才能正确
接触。 而且，不幸的是，S有这样的味道。 如果您也设置该值
大而长的任务将会挨饿。 如果你把它设置得太低，
交互式任务将无法获得正确的 CPU 时间。
尝试 3：更好的会计
现在我们还有一个问题需要解决：如何不
允许欺骗我们的调度程序吗？ 造成这种可能性的罪魁祸首是
规则 4a、4b 允许作业通过释放处理器来保持其优先级
在规定的时间到期之前。 怎么处理呢？
这种情况下的解决方案可以被认为是更好地计算每个节点上的 CPU 时间
MLFQ 级别。 而不是忘记程序使用的时间
处理器在分配的时间内，应将其考虑并保存。 后
该进程已用完分配的时间，应将其降级到下一个进程
优先级。 现在，进程如何使用时间并不重要——如何
不断地在处理器上计算或作为一组调用。 因此，
规则 4 应重写为以下形式：
- Rule4：当一个任务用完当前队列中分配的时间后（无论它释放了多少次CPU），该任务的优先级就会降低（它在队列中向下移动）。
让我们看一个例子：
»
该图显示了如果您尝试像这样欺骗调度程序会发生什么
如果按照前面的规则4a、4b就是左边的结果。 与新
规则就是右边的结果。 在保护之前，任何进程都可以在完成之前调用 I/O，并且
因此，在启用保护后，无论行为如何，都可以控制 CPU
I/O，他仍然会在队列中下降，因此无法不诚实地
接管CPU资源。
改善MLFQ等问题
经过上述改进，出现了新的问题：主要问题之一
问题 - 如何参数化这样的调度程序？ 那些。 应该是多少
队列？ 队列中程序窗口的大小应该是多少？ 如何
计划通常应优先考虑，以避免饥饿和
考虑到程序行为的变化？ 对于这些问题，没有简单的办法
响应并且仅进行负载和后续配置的实验
调度程序可以带来一些令人满意的平衡。
例如，大多数 MLFQ 实现允许您分配不同的
不同队列的时间段。 高优先级队列通常是
间隔短。 这些队列由交互式任务组成，
之间的切换非常敏感，应该需要 10 或更少
多发性硬化症。 相反，低优先级队列由长时间运行的任务组成，这些任务使用
中央处理器。 在这种情况下，长时间间隔非常合适（100 毫秒）。
在此示例中，有 2 个任务在高优先级队列 20 中工作
ms 分为 10ms 窗口。 中间队列（40ms 窗口）和低优先级队列 20ms
队列时间窗口变为 40 毫秒，任务完成其工作。
MLFQ 在 Solaris 操作系统中的实现是一类分时调度程序。
调度程序将提供一组表来准确定义它应该如何进行
改变进程在其生命周期中的优先级，大小应该是多少
要分配的窗口以及提高任务优先级的频率。 行政人员
系统可以与该表进行交互并使调度程序发挥作用
不同。 该表默认有60个队列，并逐渐增加
窗口大小从 20 毫秒（高优先级）到几百毫秒（最低优先级），以及
还每秒提升一次所有任务。
其他 MLFQ 调度程序不使用表或任何特定的
相反，本章中描述的规则，它们使用以下方法计算优先级
数学公式。 例如，FreeBSD 中的调度程序使用以下公式：
根据进程的时长计算任务的当前优先级
使用了CPU。 此外，CPU 使用率会随着时间的推移而下降，因此
因此，优先级增加与上面描述的有些不同。 这是真实的
称为衰减算法。 从 7.1 版本开始，FreeBSD 使用了 ULE 调度程序。
最后，许多规划师还有其他功能。 例如，一些
调度程序为操作系统的操作保留更高的级别，从而
因此，任何用户进程都无法获得最高优先级
系统。 有些系统允许您提供建议以提供帮助
调度程序正确确定优先级。 例如，使用命令 不错
您可以增加或减少任务的优先级，从而增加或减少
减少程序占用CPU时间的机会。
MLFQ：总结
我们描述了一种称为 MLFQ 的规划方法。 他的名字
总结操作原理 - 它有多个队列并使用反馈
确定任务的优先级。
规则的最终形式如下：
- Rule1：如果优先级（A）>优先级（B），任务A将运行（B将不会）
- Rule2：如果优先级(A) = 优先级(B)，则A&B使用RR启动
- Rule3：当任务进入系统时，被放入最高优先级队列中。
- Rule4：当一个任务用完当前队列中分配的时间后（无论它释放了多少次CPU），该任务的优先级就会降低（它在队列中向下移动）。
- Rule5：经过一段时间S后，将系统中的所有任务转移到最高队列。
MLFQ 很有趣，原因如下 - 而不是需要有关以下内容的知识
提前了解任务的性质，算法学习任务过去的行为并设置
相应的优先事项。 因此，他尝试同时坐在两把椅子上 - 实现小任务（SJF、STCF）的表现并诚实地运行长任务，
CPU 负载作业。 因此，许多系统，包括 BSD 及其衍生产品，
Solaris、Windows、Mac 使用某种形式的算法作为调度程序
MLFQ 作为基线。
其他材料：
- （计算）
来源： habr.com