几种CPU调度策略

CPU调度

我们知道，程序需要获得CPU的资源才能被调度和执行，那么当一个进程由于某种原因放弃CPU然后进入阻塞状态，下一个获得CPU资源去被调度执行的进程会是谁呢？下图中，进程1因为阻塞放弃CPU资源，此时，进程2刚IO操作结束，可以获得CPU资源去被调度，进程3的时间片轮转结束，也同样可以获得CPU资源去被调度，那么，此时的操作系统应该安排哪个进程去获得CPU资源呢？这就涉及到我们操作系统的CPU调度策略了。

根据生活中的例子，我们很容易想到以下两种策略

CPU调度的直观想法：

1.FIFO

谁先进入，先调度谁，这是一种非常简单有效的方法，就好比我们去饭堂打饭，谁先到就给谁先打饭。但是这种策略会遇到一个问题：如果遇到一个很小的任务，但是它是最后进入的，那么必须得前面一大堆任务结束完后才能执行这个小小的任务，这样就感觉很不划算呀！因为我只是简简单单的一个小任务，但是从打开这个任务到结束这个任务要很久。这显然不符合我们的需求，因而我们会想到第2种策略，就是先调度小任务，后调度大任务。

2.Priority

很简单，就是任务短的优先执行，但是此时又有问题了，任务虽然短，但是它的执行时间不一定短，就好比在一个银行业务中，客户填写一个表，这是一个非常短的任务吧——就单单填个表，但是这个表很长很长，那么这个短任务它的执行时间就很长了，我们怎么知道这个短的任务将来会执行多长的时间呢？所以，这样的策略还是依然有问题。

那么，面对诸多的场景，如何设计调度算法呢？

首先，我们要明白我们的算法应该让什么更好呢？面对客户：银行调度算法的设计目标应该是用户满意；而面对进程：CPU调度的目标应该是进程满意。

那怎么才能让进程满意呢？那就是时间了。

进程希望尽早地结束任务，这就是周转时间(从任务到达到任务结束)要短，而且希望用户的操作能够尽快地被响应，这就是响应时间(从操作发生到响应)要短。而且系统内耗时间要少，吞吐量(任务的完成量)要大，系统需要把更多的时间用再任务的执行上，而不能老是去做无关紧要的事情，例如：频繁切换任务，切换栈，分配资源等事情。同时，系统还要去合理地调配任务。

那么，CPU的调度策略如何做到合理呢？

首先得明白系统中有以下的几种矛盾。

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

响应时间小=>切换次数多=>系统内耗大=>吞吐量小

由于需要较短的响应时间，那么就得频繁地切换任务，这样系统的很多时间都花在切换任务上面了，系统的内耗大了，吞吐量就小了。

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

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

前台任务例如我们的word文档，我们打一个字，需要立马显示在文档中，这就是word文档这个任务关注的是响应时间；而后台任务中，例如我们的javac编译java代码，它的周转时间要小，即该任务从进入到结束所花的时间要小，即编译完成的时间要小。

3.IO约束型任务和CPU约束型任务各有各的特点

IO约束型任务就是使用CPU的时间较少，进行IO操作的时间较长，CPU约束型的任务就是使用CPU的时间较长。

因此，要做到合理，需要折中、综合考虑以上的几种矛盾。

由此，产生了以下一些CPU的调度算法。

各种CPU调度算法

1.First Come，First Served(FCFS)

就是先来先服务的调度算法，哪个任务先进来，就为哪个任务先服务。

我们上面说过，周转时间=任务结束的时间-任务到达的时间，因此，我们算一算以上四个任务的平均周转时间。进程A到达时间为0时刻，进程B到达时间为1时刻，进程C到达时间为2时刻，进程D到达时间为3时刻，因此，按照FCFS调度算法，我们一词调度A、B、C、D.

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

那么，因为一个系统中，可能短任务占的比重较多，那些后来进入的短任务，就得等前面一大堆的任务执行完后，CPU才为这些短任务服务，这样的话，很多短任务即使服务时间短，但是它们的周转时间都比较长。我们可以尝试着把短任务提前，短任务提前了，减少以短任务为主的系统的平均周转时间，由此我们产生了短作业优先的CPU调度算法。

2.SJF(Short Job First，短作业优先)

也很简单，就是哪个任务的服务时间短就先调度哪个。还是上面那四个进程。

进程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的调度算法就要考虑这么多东西了，可以看到，我们的操作系统真的是人类的一项很伟大的发明。