几种CPU调度策略

CPU调度

我们知道程序需要获取CPU资源以进行调度和执行。然后，当某个进程由于某种原因放弃了CPU并进入阻塞状态时，下一个获得要调度执行的CPU资源的进程将是谁？在下图中，由于阻塞，进程1放弃了CPU资源。此时，进程2刚刚完成IO操作，并且可以获得要调度的CPU资源。进程3的时间片轮换结束，并且它也可以获得要调度的CPU资源。然后，操作系统应该调度哪个进程来获取CPU资源？这涉及到我们操作系统的CPU调度策略。

根据生活中的例子，我们可以轻松想到以下两种策略

CPU调度的直观想法：

1.FIFO

谁先进入谁先被调度，是一种非常简单有效的方法。这就像去饭厅吃晚饭，谁先到谁先。但是这种策略会遇到一个问题：如果您遇到一个小任务，但是它是最后一个要输入的任务，那么您必须先完成之前的任务，然后才能执行此小任务，因此感觉很不愉快！因为我只是一个简单的任务，但是从打开此任务到结束它需要很长时间。这显然不能满足我们的需求，因此我们将考虑第二种策略，即先安排小任务，然后再安排大任务。

2.优先级

非常简单。首先执行简短的任务，但此时存在问题。尽管任务很短，但是其执行时间不一定很短。就像在银行业务中，客户填写一个表格，这是一个非常短的任务-只需填写一个表，但是这个表又长又长，那么这个短任务的执行时间就很长，如何我们知道这个短期任务将来会执行多久吗？因此，这种策略仍然存在问题。

那么，面对许多情况，如何设计调度算法？

首先，我们需要了解我们的算法应该做哪些改进？面向客户：银行调度算法的设计目标应该是用户满意；和面对流程：CPU调度的目标应该是流程满意度。

我们如何满足这一过程？是时候了。

该过程希望尽快结束任务。这意味着周转时间（从任务到任务结束）应该很短，并希望可以尽快响应用户的操作。这意味着响应时间（从操作发生到响应）应该很短。此外，系统消耗的时间更少，并且吞吐量（任务完成的数量）很大。系统需要在执行任务上花费更多的时间，并且不能总是做无关紧要的事情，例如频繁切换任务，切换堆栈，分配资源和其他事情。同时，系统必须合理分配任务。

那么，CPU调度策略如何合理？

首先，我们必须了解系统中的以下矛盾。

1.吞吐量和响应时间之间存在矛盾

响应时间短=>切换时间很多=>系统消耗高=>吞吐量低

由于响应时间短，因此必须频繁切换任务。这样，系统的很多时间都花在切换任务上。系统内部消耗大，吞吐量小。

2.前台任务和后台任务有不同的关注点

前台任务专注于响应时间，后台任务专注于周转时间。

前景任务，例如我们的Word文档。我们输入一个单词，需要立即显示在文档中。这是文档一词。该任务着重于响应时间。而在后台任务中，例如，我们的javac会编译Java代码。周转时间应该短一些，也就是说，从入口到结束的任务所花费的时间应该少一些，也就是说，完成编译的时间应该少一些。

3.受IO限制的任务和受CPU限制的任务各有其特点

IO受限的任务使用CPU的时间更少，而IO操作更长。受CPU限制的任务使用CPU的时间更长。

因此，为合理起见，有必要妥协和综合考虑上述矛盾。

结果，产生了以下CPU调度算法。

各种CPU调度算法

1.先到先得（FCFS）

这是先到先得的调度算法。哪个任务先出现，将先服务哪个任务。

如上所述，周转时间=任务结束的时间-任务到达的时间。因此，我们计算上述四个任务的平均周转时间。进程A的到达时间为0，进程B的到达时间为1，进程C的到达时间为2，进程D的到达时间为3。因此，根据FCFS调度算法，我们使用术语安排A，B，C，D。

这四个任务的平均周转时间=（5-0)+（65-1)+（165-2)+（175-3)/ 4 = 10 1.

因此，由于短任务可能在系统中占较大比例，因此稍后输入的那些短任务将必须等待大量任务的执行，然后CPU才能为这些短任务提供服务。在这种情况下，即使服务时间很短，许多短任务的周转时间也相对较长。我们可以尝试提前执行短期任务，提前执行短期任务，并减少以短期任务为主的系统的平均周转时间。由此，我们产生了一种CPU调度算法，该算法优先考虑短期任务。

2. SJF（短作业优先，短作业优先）

这也非常简单，即首先在较短的服务时间内安排了哪个任务。还是上面的四个过程。

进程A的服务时间为5，进程B的服务时间为60，进程C的服务时间为100，进程D的服务时间为10。因此，根据简短的CPU调度算法工作优先级，我们依次安排A，D，B，C。

所以，这四个任务的平均周转时间=（5-0)+（15-3)+（75-1)+（175-2)/ 4 = 66.

很明显，在以短作业为主的系统中，具有短作业优先级的调度算法的平均周转时间比以先到先得的调度算法的平均周转时间要短。

现在问题再次出现。如果迫切需要任务C的任务（例如Word文档任务），则它必须快速响应用户的按键输入请求，这意味着响应时间应该很短。显然，上面的SJF调度策略没有考虑响应时间的问题，因此任务C仅具有较短的周转时间和较长的响应时间（必须等待A，D，B任务完成才能响应C）。

由此，我们想到了基于时间片旋转的调度。

3. RR算法（按时间片进行循环调度）

以上述四个过程为例。

按时间片旋转的调度算法是设置一个时间片，例如10个CPU时间，然后在A，B，C和D四个进程之间不断切换。每个进程的执行时间为10 ，时间到达时，切换到下一个流程执行时间10，直到所有执行完成。

为每个进程分配10个CPU时间，并执行循环调度，以使每个进程的响应时间变短。

如果时间片设置得太大，则响应时间将太长。如果将时间片设置得太小，则整个系统会不断切换进程，并且切换进程会浪费大量系统时间，从而导致系统吞吐量变小。妥协后，时间片设置为10〜100ms，切换时间为0.1〜1ms。

说到这一点，SJF算法专注于系统的平均周转时间，而RR算法专注于系统的响应时间，但是如果系统需要较小的响应时间和较小的周转时间，该怎么办？同一时间？

例如，word关心响应时间，而javac编译Java程序更关心周转时间。如果同时存在两种类型的任务该怎么办？

也就是说，前台任务更关心响应时间，因为前台任务直接与用户交互并且需要快速响应用户请求，而后台任务更关心周转时间并且需要快速结束任务。

一个非常直观的想法。为前台任务和后台任务定义两个队列。前景使用RR算法，背景使用SJF算法。仅在没有前台任务时安排后台任务。

但这会引起问题。如果总是有前台任务，那么将永远不会安排后台任务。我想告诉你一个有趣的故事：1973年，一位工作人员关闭了MIT IBM7094计算机，发现一个进程是在1967年提交的，但尚未运行。

这时，我们可以动态增加后台任务的优先级，但是一旦执行了后台任务（由SJF安排），前台任务的响应时间就必须变长。

如果我们将时间片用于前后任务，则它将退化为RR算法。

因此，仍然有许多问题在等待我们发现并找到解决方案。

例如，我们如何知道哪些任务是前台任务，哪些是后台任务？前台任务没有后台任务吗？后台任务不适用于前台任务吗？ SJF中的短期分配优先级如何体现？如何判断工作时间？

到目前为止，已经对这些问题进行了疯狂的讨论和研究。有兴趣了解这方面的知识的人士可以阅读相关文献，或阅读以下Linux CPU调度算法源代码。一个CPU的调度算法必须考虑很多事情。可以看出，我们的操作系统确实是人类的伟大发明。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/shoujiruanjian/article-323496-1.html