操作系统介绍

哈Ha！ 我想提请您注意我认为是OSTEP的一系列有趣文献的翻译文章。 本文相当深入地讨论了类Unix操作系统的工作，即处理组成现代OS的进程，各种调度程序，内存和其他类似组件。 您可以在这里看到所有材料的原始材料。 请注意，翻译是非专业地进行的（相当自由），但是我希望我保留了一般的含义。

有关此主题的实验室工作可以在这里找到：

• 原始的
• 原始的
• 我的个人适应

其他部分：

• 第1部分：简介
• 第2部分：抽象：过程
• 第3部分：Process API简介
• 第4部分：计划程序简介
• 第5部分：MLFQ调度程序

您可以通过电报查看我的频道=）

规划：多级反馈队列

在本讲座中，我们将讨论开发最著名的方法之一的问题。
规划称为多级反馈队列 （MLFQ）。 MLFQ调度程序最早是由Fernando J.Corbató于1962年在称为兼容时间共享系统（CTSS）的系统中描述的。 这些作品（包括后来在Multics上的作品）随后被授予图灵奖。 随后对调度程序进行了改进，并获得了某些现代系统中已经可以找到的外观。

MLFQ算法尝试解决2个基本的交叉问题。
首先 ，他尝试优化周转时间，正如我们在上一讲中所讨论的那样，它是通过从最短任务队列的开头开始进行优化的。 但是，操作系统不知道该过程将持续多长时间，这是SJF，STCF算法的操作所必需的知识。 其次 ，MLFQ尝试使系统响应用户（例如，在等待任务完成时坐在屏幕上凝视的用户），从而使响应时间最小化。 不幸的是，像RR这样的算法会减少响应时间，但是它们对周转时间指标的影响非常大。 因此，我们要解决的问题是：如何设计一个既可以满足我们的要求又同时又不了解流程本质的调度程序？ 调度程序如何才能了解所启动任务的特征，从而做出更好的计划决策？

问题的实质：在没有完善知识的情况下如何计划任务制定？ 如何开发一种调度程序，同时使交互式任务的响应时间最小化，同时又使周转时间最小化，而又不知道完成任务的时间？

注意：从以前的事件中学习

MLFQ阵容是一个可以从过去的事件中学习以预测未来的系统的很好的例子。 在OS（以及计算机科学的许多其他分支，包括硬件预测分支和缓存算法）中经常发现类似的方法。 当任务具有行为阶段并可以预测时，类似的行程就起作用。

但是，应谨慎使用这种技术，因为预测很容易被证明是错误的，并导致系统做出比根本没有知识的情况更糟糕的决策。

MLFQ：基本规则

考虑MLFQ算法的基本规则。 尽管此算法有多种实现方式，但基本方法相似。

在我们将考虑的实现中，在MLFQ中将有几个单独的队列，每个队列将具有不同的优先级。 任何时候，准备执行的任务都在一个队列中。 MLFQ使用优先级来确定要运行的任务，即 优先级较高的任务（队列中优先级较高的任务）将首先启动。

毫无疑问，一个特定的队列中可以有多个任务，因此它们将具有相同的优先级。 在这种情况下，将使用RR引擎来安排这些任务之间的启动。

因此，我们得出了MLFQ的两个基本规则：

• 规则1：如果优先级（A）>优先级（B），任务A将启动（B将不启动）
• 规则2：如果优先级（A）=优先级（B），则使用RR启动A＆B

基于以上所述，MLFQ规划的关键要素是优先级。 MLFQ不会为每个任务设置固定的优先级，而是根据观察到的行为更改其优先级。

例如，如果在等待键盘输入时某个任务不断退出CPU上的工作，则MLFQ将在较高级别上保持该进程的优先级，因为这是交互式进程应如何工作。 相反，如果任务长时间长时间不间断地大量使用CPU，则MLFQ将降低其优先级。 因此，MLFQ将在进程运行时研究其行为并使用该行为。

让我们举一个例子，说明队列在某个时间点的外观，然后我们得到如下信息：



在此方案中，2个进程A和B在队列中具有最高优先级。 进程C在中间的某个地方，进程D在队列的尽头。 根据上面对MLFQ算法的描述，调度程序将根据RR仅执行具有最高优先级的任务，并且任务C，D将不工作。

自然地，静态快照不会提供有关MLFQ工作原理的完整信息。
准确了解图片随时间的变化非常重要。

尝试1：如何更改优先级

此时，您需要确定MLFQ在其生命周期中将如何更改任务的优先级（从而改变任务在队列中的位置）。 为此，您需要牢记工作流程：运行时间短（因此频繁释放CPU）的许多交互式任务以及在其所有工作时间都使用CPU的多个长任务，而此类任务的响应时间并不重要。 因此，您可以尝试使用以下规则来实现MLFQ算法：

• 规则3：当任务进入系统时，它以最高
• 优先级。
• Rule4a：如果任务使用分配给它的整个时间窗口，则其任务
• 优先级下降。
• Rule4b：如果任务在其时间窗口到期之前释放了CPU，则它将
• 仍然具有相同的优先级。

示例1：一个长期运行的任务

如本例所示，准入任务的优先级最高。 在10毫秒的时间窗口后，调度程序会降低进程的优先级。 在下一个时间窗口之后，任务最终会下降到系统中的最低优先级，并保留在那里。



示例2：他们提出了一个简短的任务

现在，让我们看一个有关MLFQ如何尝试更接近SJF的示例。 在此示例中，有两个任务：A，这是一个长期运行的任务，不断占用CPU； B，这是一个简短的交互式任务。 假设在任务B到达时A已经工作了一段时间。



在此图中，脚本的结果可见。 像使用CPU的任何任务一样，任务A位于最底部。 任务B将到达T = 100，并将被放在优先级最高的队列中。 由于她的工作时间很短，因此它将在到达最后阶段之前结束。

从此示例中，应该理解该算法的主要目标：由于该算法不知道长任务或短任务，因此首先假定任务是短任务并赋予其最高优先级。 如果这是一个很短的任务，那么它将很快完成；否则，如果它是一个长任务，它将优先缓慢地向下移动，并很快证明这是一个很长的任务，不需要响应。

示例3：I / O呢？

现在看一下I / O示例。 如规则4b所述，如果某个进程在没有充分利用处理器时间的情况下释放了处理器，则该进程将保持相同的优先级。 该规则的意图非常简单-如果交互式任务执行许多I / O操作，例如，等待用户按下键或鼠标，则此类任务将在分配的窗口之前释放处理器。 我们不想优先忽略此类任务，因此它将保持在同一水平。



此示例说明算法如何在此类进程中工作-交互式任务B（执行I / O进程仅需要1ms的CPU）和较长的任务A（其始终使用CPU）。

MLFQ始终保持进程B的最高优先级。
释放CPU。 如果B是一个交互式任务，则该算法便达到了快速启动交互式任务的目标。

当前的MLFQ算法存在问题

在前面的示例中，我们构建了MLFQ的基本版本。 而且，他似乎很好地完成了工作，在长任务之间诚实地分配了处理器时间，并允许短任务或密集访问I / O的任务迅速解决。 不幸的是，这种方法包含几个严重的问题。

首先是饥饿的问题：如果系统中有很多交互式任务，那么它们将消耗所有处理器时间，因此将无法执行单个长任务（它们正在挨饿）。

其次 ，聪明的用户可以编写他们的程序，以便
欺骗计划者。 诀窍是做点什么
调度程序可以使进程拥有更多的处理器时间。 的算法
上面描述的很容易受到此类攻击：在时间窗口实际上之前
结束后，您需要执行I / O操作（对于某些文件，无论是哪个文件）
从而释放CPU。 此行为将使您保持原样
队列本身，并再次获得更大比例的CPU时间。 如果完成
这是正确的（例如，释放CPU之前有99％的窗口时间）
这样的任务可以简单地垄断处理器。

最后，程序可以随时间改变其行为。 那些任务
使用CPU的用户可以进行交互。 在我们的示例中，类似
任务不会像其他任务一样受到调度程序的适当处理
（初始）交互式任务。

向听众提问：在现代世界中，可以对计划者进行哪些攻击？

尝试2：提高优先级

让我们尝试更改规则，看看是否可以避免出现问题
空腹。 我们该怎么做才能确保相关
CPU任务将获得时间（即使时间不长）。
作为解决问题的简单方法，您可以定期提供
增加系统中所有此类任务的优先级。 有很多方法。
为此，让我们尝试以简单的示例为例：
所有任务同时具有最高优先级，因此新规则为：

• 规则5 ：经过一定的S时间后，将系统中的所有任务转移到最高优先级。

我们的新规则可以立即解决两个问题。 一，流程
保证不饿死：优先级最高的任务将共享
根据RR算法的处理器时间，因此所有进程都将收到
处理器时间。 其次，如果以前使用过某些流程
只有处理器变得交互式，然后它将与更高的处理器保持一致
优先级一次之后，将优先级提高到最高。
考虑一个例子。 在这种情况下，请考虑使用


CPU和两个交互的，简短的过程。 在图的左侧，该图显示了不增加优先级的行为，因此，当两个交互式任务到达系统后，长任务开始挨饿。 在右图中，每50ms优先级增加一次，因此保证所有进程都将接收处理器时间，并将定期启动。 以这种情况下的50ms为例，实际上这个数字有些大。
显然，增加S周期性增加的时间会导致
逻辑问题：应设置什么值？ 荣幸之一
系统工程师John Ousterhout在voo-doo之类的系统中称相似的数量
恒定，因为他们以某种方式要求黑魔法正确
展示。 并且，不幸的是，S具有这种香气。 如果您也设定值
大-漫长的任务将开始挨饿。 如果将值设置得太低，
交互式任务将不会获得适当的处理器时间。

尝试3：最佳会计

现在我们还有一个问题需要解决：怎么不
让我们欺骗我们的计划者？ 犯了这个机会是
规则4a，4b，它允许任务保持优先级，从而释放处理器
在分配的时间到期之前。 如何应对呢？
在这种情况下，该解决方案可以认为是对每个CPU时间的最佳考虑
MLFQ级别。 而不是忘记程序使用的时间
处理器在指定的时间段内，您应该考虑并保存它。 之后
该过程已经花费了分配的时间，应该减少到下一个
优先级。 现在，无论流程如何使用时间-
不断在处理器上进行计算或进行多次调用。 这样
规则4应改写如下：

• 规则4 ：任务用完当前队列中分配给它的时间后（无论它释放了CPU多少次），该任务的优先级就会降低（它会向下移动到队列中）。

让我们看一个例子：
”

该图显示了如果您尝试欺骗调度程序会发生什么，如何
如果符合先前的规则4a，4b，则结果在左侧。 快乐新
规则是右边的结果。 在保护之前，任何进程都可以调用I / O，直到完成和
因此，启用保护后，无论行为如何，都可以主导CPU
I / O，它仍然会掉线，因此不会不诚实
占用CPU资源。

改善MLFQ和其他问题

通过以上改进，出现了新问题：主要问题之一
问题-如何参数化这样的调度程序？ 即 应该多少
阵阵？ 队列中程序窗口的大小应为多少？ 怎么
应经常增加计划的优先级，以避免饥饿和
考虑到程序行为的变化？ 对于这些问题，绝非易事
响应，仅在负载和后续配置下进行实验
规划器可能会导致一些令人满意的平衡。

例如，大多数MLFQ实现都允许您分配不同的
时间间隔到不同的队列。 高优先级队列通常
分配短间隔。 这些队列由交互式任务组成，
两者之间的切换非常敏感，应花费10或更少
毫秒 相反，低优先级队列由使用
中央处理器 在这种情况下，很长的时间间隔非常适合（100ms）。


在此示例中，有2个任务在高优先级队列20中工作
ms，被Windows中断10ms。 中等队列中的时间为40毫秒（窗口为20毫秒），低优先级
队列时间窗口变为40毫秒，任务完成了工作。

Solaris OS MLFQ实现是一类分时调度程序。
调度程序提供了一组表，这些表确定了应如何精确确定
改变流程在生命周期中的优先级，大小应该是多少
选定的窗口以及您需要多长时间提高一次任务的优先级。 管理员
系统可以与此表进行交互并使调度程序运行
以不同的方式。 默认情况下，此表中有60个增量队列。
窗口大小从20毫秒（高优先级）到几百毫秒（最低优先级），以及
还每秒提升一次所有任务。

其他MLFQ计划人员不使用表格或任何特定的
相反，他们使用以下方法计算优先级：
数学公式。 因此，例如，FreeBSD中的调度程序将公式用于
根据流程的多少来计算任务的当前优先级
使用过的CPU。 此外，CPU的使用会随着时间的流逝而衰减，因此
因此，优先级增加与上述情况有所不同。 是这样
称为衰减算法。 从7.1版开始，FreeBSD使用ULE调度程序。

最后，许多计划者还具有其他功能。 例如，一些
规划人员为操作系统保留了最高级别，因此
这样，任何用户进程都无法获得最高优先级
系统。 一些系统允许您提供帮助的技巧。
调度程序以正确设置优先级。 例如，使用nice命令
您可以增加或减少任务的优先级，从而增加或
减少程序占用处理器时间的机会。

MLFQ：摘要

我们描述了一种称为MLFQ的计划方法。 他的名字
—
.
:

• Rule1 : () > (), ( )
• Rule2 : () = (), RR
• Rule3 : , .
• Rule4 : ( CPU) ( ).
• Rule5 : S .

MLFQ —
,
. — (SJF, STCF) ,
CPU . , BSD ,
Solaris, Windows, Mac
MLFQ .

:

1. manpages.debian.org/stretch/manpages/sched.7.en.html
2. en.wikipedia.org/wiki/Scheduling_ (computing)
3. pages.lip6.fr/Julia.Lawall/atc18-bouron.pdf
4. www.usenix.org/legacy/event/bsdcon03/tech/full_papers/roberson/roberson.pdf
5. chebykin.org/freebsd-process-scheduling