操作系统介绍
哈Ha！ 我想提请您注意一系列文章-我认为是OSTEP的有趣文献的翻译。 本文相当深入地讨论了类Unix操作系统的工作，即处理组成现代OS的进程，各种调度程序，内存和其他类似组件。 您可以
在这里看到所有材料的原始材料。 请注意，翻译是非专业地进行的（相当自由），但是我希望我保留了一般的含义。
有关此主题的实验室工作可以在这里找到：
其他部分：
您可以通过
电报查看我的频道=）
调度程序简介
问题的实质：如何制定计划者政策
基本调度程序策略框架应如何开发？ 关键假设是什么？ 哪些指标很重要？ 早期计算中使用了哪些基本技术？工作量假设
在讨论可能的策略之前，我们将首先简化一些有关系统中正在运行的进程的题外话，统称为
工作负载 。 通过将工作负载定义为构建策略的关键部分，您对工作负载的了解越多，您编写的策略就越好。
我们对系统中运行的进程做出以下假设，有时也称为
作业 （任务）。 这些假设几乎都是不现实的，但是对于思想的发展是必要的。
- 每个任务运行相同的时间，
- 所有任务都同时设置，
- 即将完成的任务，
- 所有任务仅使用CPU，
- 每个任务的运行时间是已知的。
调度程序指标
除了有关负载的一些假设外，仍然需要一些工具来比较各种计划策略：调度程序指标。 指标只是对事物的度量。 有许多指标可用于比较计划者。
例如，我们将使用一个称为周转时间的指标。 任务的周转时间定义为完成任务所需的时间与任务进入系统的时间之差。
周转=完成-到达由于我们假定所有任务都同时到达，因此Ta = 0，因此Tt = Tc。 当我们改变以上假设时，该值自然会改变。
另一个指标是
公平 （公平，诚实）。 生产力和诚实度通常是计划中的相反特征。 例如，调度程序可以优化性能，但是以等待其他任务运行为代价，从而降低了完整性。
先进先出（FIFO）
我们可以实现的最基本的算法称为FIFO或
先入先出 。 该算法具有多个优点：实现非常简单，并且符合我们所有的假设，可以很好地完成工作。
考虑一个简单的例子。 假设同时设置了3个任务。 但是，假设任务A的出现时间比其他所有人都要早一些，因此它比其他任务相对于C早在其他任务的执行列表中。假设每个任务都需要10秒才能完成。 完成这些任务的平均时间是多少？
计算值-10 + 20 + 30并除以3，我们得出程序的平均执行时间为20秒。
现在，让我们尝试更改我们的假设。 特别是假设1，因此我们将不再假设每个任务花费相同的时间。 FIFO这次将如何显示自己？
事实证明，任务的不同执行时间会对FIFO算法的生产率产生极大的负面影响。 假设任务A将执行100秒，而B和C仍将分别为10。
从图中可以看出，系统的平均时间为（100 + 110 + 120）/ 3 = 110。 此效应称为
车队效应 ，即资源的某些短期使用者将在大量使用者之后排队。 当有一辆满满的手推车的顾客站在您面前时，它看起来像是一家杂货店生产线。 解决该问题的最佳方法是尝试更换收银员或放松并深呼吸。
最短的工作第一
是否可以通过繁重的过程以某种方式解决类似的情况？ 当然可以 另一种调度方式称为
最短作业优先 （SJ）。 它的算法也很原始-顾名思义，最短的任务将依次启动。
在此示例中，启动相同进程的结果将是程序平均周转时间的改善，它将是
50而不是110 ，这几乎好了2倍。
因此，对于所有任务同时到达的给定假设，SJF算法似乎是最佳算法。 但是，我们的假设似乎仍然不现实。 这次，我们更改了假设2，这次我们设想任务可以随时保留，而不是同时保留。 这会导致什么问题？
想象一下，任务A（100秒钟）首先到达并开始执行。 在时间t = 10时，任务B，C到达，每个任务将花费10秒。 因此，平均执行时间为（100+（110-10）+（120-10））\ 3 =103。计划者可以采取什么措施来改善这种情况？
最短完成时间（STCF）
为了改善这种情况，我们忽略了假设3，该程序已启动并运行直到完成。 此外，我们将需要硬件支持，并且您可能已经猜到了，我们将使用
计时器来中断正在执行的任务并
切换上下文 。 因此，调度程序可以在任务B和C到达时做一些事情-停止任务A的执行并将任务B和C置于处理中，并在完成后继续执行进程A。此调度程序称为
STCF或
Preemptive Job First 。
此调度程序的结果将是以下结果：（（120-0）+（20-10）+（30-10））/ 3 = 50。 因此，这样的调度程序对于我们的任务来说甚至变得更加优化。
公制响应时间
因此，如果我们知道任务的运行时间并且这些任务仅使用CPU，那么STCF将是最佳解决方案。 而且在早期，这些算法就可以很好地工作。 但是，现在用户大部分时间都在终端上度过，并期望从终端进行富有成效的交互式交互。 因此诞生了一个新的指标-
响应时间 （response）。
响应时间计算如下：
Tresponse = Tfirstrun-到达因此，对于前面的示例，响应时间将如下所示：A = 0，B = 0，B = 10（abg = 3.33）。
事实证明，在同时完成3个任务的情况下，STCF算法不是很好-它必须等待直到小任务完全完成。 因此，该算法对周转时间度量有利，但对交互性度量不利。 想象一下坐在终端上试图在编辑器中键入字符，您将不得不等待10秒钟以上，因为处理器还要处理其他一些任务。 这不是很愉快。
因此，我们面临另一个问题-如何构建对响应时间敏感的调度程序？
轮循
为了解决这个问题，开发了
Round Robin （RR）算法。 基本思想很简单：我们将启动任务一定时间（称为时间量），而不是开始完成任务，然后从队列中切换到另一个任务。 该算法重复其工作，直到完成所有任务。 在这种情况下，程序运行时间必须是计时器中断过程的时间的倍数。 例如，如果计时器每x = 10ms中断一次进程，则进程执行窗口的大小应为10的倍数，并且应为10.20或x * 10。
让我们看一个示例：ABV任务同时到达系统中，并且每个任务都需要工作5秒钟。 SJF算法将在开始另一个任务之前完成每个任务。 相反，启动窗口= 1s的RR算法将执行以下任务（图4.3）：
（再次SJF（响应时间差）
（Round Robin（有益于响应时间）该算法的平均响应时间为RR（0 + 1 + 2）/ 3 = 1，而SJF（0 + 5 + 10）/ 3 = 5。
逻辑上认为时间窗口对于RR是非常重要的参数，它越小，响应时间就越高。 但是，您不能将其设置得太小，因为切换上下文的时间也将影响整体性能。 因此，执行窗口的时间由OS架构师设置，并取决于计划在其中执行的任务。 切换上下文并不是唯一花费时间的服务操作-正在运行的程序需要更多操作（例如，各种缓存），并且每次有必要保存和恢复该环境时，这也要花费很多时间。
如果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调用过程置于就绪状态。
考虑几个任务的例子。 它们每个都需要50毫秒的处理器时间。 但是，第一个将每10ms访问一次I / O（也将执行10ms）。 而进程B只是使用一个50ms的处理器而没有I / O。
在此示例中，我们将使用STCF调度程序。 如果您在进程上运行类似A的进程，调度程序将如何运行？ 他将进行以下操作-首先完全执行过程A，然后执行过程B。
解决此问题的传统方法是将进程A的每个10毫秒子任务解释为一个单独的任务。 因此，当从STJF算法开始时，在50 ms任务和10 ms任务之间的选择是显而易见的。 然后，当子任务A完成时，将启动过程B和I / O。 I / O完成后，通常会重新启动10毫秒的进程A而不是进程B。因此，当第一个进程正在等待I / O的另一个进程使用CPU时，有可能实现重叠。 结果是，该系统得到了更好的利用-当交互进程正在等待I / O时，可以在处理器上执行其他进程。
甲骨文不再
现在，让我们摆脱假设任务时间已知的假设。 这通常是整个列表中最糟糕，最不现实的假设。 实际上，在普通的标准操作系统中，操作系统本身通常对完成任务所花费的时间了解甚少，因此，如何在不知道任务将花费多长时间的情况下构建调度程序？ 也许我们可以使用RR的某些原理来解决此问题？
总结
我们研究了任务计划的基本思想，并回顾了2个计划者系列。 第一个在开始时开始执行最短的任务，因此增加了周转时间，第二个在所有任务之间均被撕裂，从而增加了响应时间。 两种算法都是不好的，而其他家族算法是好的。 我们还研究了CPU和I / O的并行使用如何提高性能，但是并没有解决OS透视问题。 在下一课中，我们将考虑一个计划者，他要研究不久的过去并试图预测未来。 它称为多级反馈队列。