今天来点硬核东西，进度调度概述，在讲调度之前，总是要吹一波水，其实我的吹水能力并不好，但是也没办法，相关专题的第一篇都是吹水中度过。

15.1 调度简介

我们现在的操作系统，基本都是多道程序设计系统，因为CPU只有一个（多核的后面再讲），所以会出现很多个进程在竞争CPU，主要多个进程处于就绪状态，就有可能。同一个时间，一个CPU只能执行一个进程，这个进程在运行态，其他进程要么在就绪态，要么在阻塞态，关于进程的状态可以看一下这篇，回忆一下重学计算机（十、进程的状态）。

当这个进程阻塞时，调度程序就会选择下一个运行的进程，那这个选择算法就是调度算法，也是我们接下来重点学习的部分。

15.1.1 何时调度

我们接下来先看看进程何时需要调度：

1. 在创建一个新进程之后，需要确定是运行父进程还是子进程。
2. 在一个进程退出时必须做出调度决策。
3. 当一个进程阻塞在IO和信号量上或由于其他原因阻塞，必须选择另一个进程运行。
4. 在一个IO中断发生时，必须做出调度决策。

这些点我们先了解，之后分析linux调度的时候，再详细来看看。

15.1.2 抢占和非抢占

多任务系统可以划分为两类：非抢占多任务和抢占多任务。

非抢占式：

选择一个进程开始运行，直到这个进程阻塞或者主动释放CPU，才有可能被调度程序选择另外的进程，就像上的2,3一样。如果这个进程一直运行，那也没有办法，其他进程只能干等着。

优点：优点就是调度程序实现简单吧。

缺点：如果这个进程没有主动让出CPU，其他进程就会饿死。

抢占式：

抢占式就比较霸道，调度程序选择一个进程开始运行，直到这个进程运行某一个时间段（时间片），如果在这时间片中进程仍在运行，调度程序就会把这个进程挂起，然后重新选择另一个进程运行。

优点：不会出现一个进程一直在运行的情况。

缺点：抢占调度可能会导致竞争。如果两个进程共享数据，当一个进程在操作的时候，另一个进程来抢占了CPU，然后去读取共享数据，就会出现问题。（这个后面会介绍到锁，不要着急，哈哈）

15.1.3 调度算法分类

毫无疑问，不同环境需要不同的调度算法。之所以出现这种情形，是因为不同的应用领域有不同的目标。（linux系统就比较适合做服务器，windows不太适合，当然也可以做服务器）

下面我们划分出三种环境：

1. 批处理

   批处理系统就是相当于CPU密集型，专门做一些密集的计算，批处理一些图片等操作。这一类情况用户不会等待一个快速的响应，因为都知道，这种操作不会很快就反应的，所以这种系统可以用非抢占式或者是分配一个长的时间片，这样就减少了切换进程的消耗。

2. 交互式

   交互式相当于IO密集型，用户会去点击一些按键，或者输入一个数据，所以需要快速反应，所以这种需要抢占式。

3. 实时

   实时系统，适用于一个任务优先级很高，需要在很短的时间内执行。

15.1.4 调度算法的目标

设计一个程序，总是需要一个目标，那调度算法的目标是什么呢？

不同环境（批处理、交互式、实时）的目标可能不一样，下面我们来看一看

15.2 简介调度算法

上面介绍了一些进程调度的一些概念，接下来就看一些具体的调度算法，看看CPU是怎么从就绪队列中选择进程的。

15.2.1 先到先得服务

最简单的是非抢占式的先来先得服务算法。非抢占式(First-come First-server,FCFS)

介绍：这个算法简单到实现一个调度队列就可以了，先请求的CPU进程会进入调度队列，后请求CPU的进程后进入调度队列，当CPU空闲的时候，它就会取到队列头部的进程，进行运行。直到这个进程主动释放CPU，然后会把这个进程添加到队尾，CPU会再次获取队头的进程，一次循环。（太简单，图都不想画了）

优点：优点还是程序简单，容易理解。

缺点：就是平均等待时间很长。如果有一个CPU密集型进程和多个IO密集型进程，按这种排队的玩法，也就是要等得CPU密集型进程计算完了，主动释放CPU，后面的IO密集型进程才能得到CPU，这样子，黄花菜都凉了了。。。。。但是吧，这种算法就适合单纯的批处理系统。

例子：假如有如下一组进程，它们在时间0到达，CPU执行长度按ms计：

如果进程按照P1、P2、P3的顺序到达，并且按FCFS顺序处理，那么得到的调度图：

我们计算一下周转时间：

P1=10, P2=20, P3=30
周 转 时 间 ： ( 10 + 20 + 30 ) / 3 = 20 m s 周转时间：(10+20+30)/3 = 20 ms 周转时间：(10+20+30)/3=20ms

平 均 等 待 时 间 ： ( 0 + 10 + 20 ) / 3 = 10 m s 平均等待时间：(0+10+20)/3 = 10ms 平均等待时间：(0+10+20)/3=10ms

这种玩法看着真和谐，但是如果进程是这样的呢：

那情况会变成啥样：

周 转 时 间 = ( 40 + 50 + 60 ) / 3 = 50 m s 周转时间 = (40+50+60)/3 = 50ms 周转时间=(40+50+60)/3=50ms

平 均 等 待 时 间 ： ( 0 + 40 + 50 ) / 3 = 30 m s 平均等待时间：(0+40+50)/3 = 30ms 平均等待时间：(0+40+50)/3=30ms

差别还真的不是一点半点，如果有一个占用时间比较长的进程存在，会导致其他短时间进程得不到运行，针对这个问题，改进了一下算法，就是下面的最短作业优先。

15.2.2 最短作业优先

最短作业优先（shortest-Job-First, SJF）调度算法，非抢占式。

介绍：这个调度算法，是把每个进程下次执行的时间关联起来，也会存在一个调度队列，这个队列存储的方式跟FCFS不一样，时间短的排在对头，时间长的在队尾，有点像最小堆的做法。当CPU空闲的时候，也是获取队头元素（时间最短的），如果释放了，会再次计算下一次执行时间，插入队列中。如果两个时间一样，那就按照FCFS先到先得的算法。

优点：相对FCFS算法有所改进，平均等待时间变短，因为会把短进程先执行。

缺点：如果短时间的进程没有在就绪态，长时间的进程在就绪态，还会导致短时间进程没有得到执行。

例子：针对上一节的问题，来分析一下这个算法

调度队列：

周 转 时 间 ： ( 10 + 20 + 60 ) / 3 = 30 m s 周转时间： (10+20+60)/3 = 30ms 周转时间：(10+20+60)/3=30ms

平 均 等 待 时 间 ： ( 0 + 10 + 20 ) / 3 = 10 m s 平均等待时间： (0+10+20)/3 = 10ms 平均等待时间：(0+10+20)/3=10ms

提升的很大啊。

但是，如果t=0的时候，只有P1就绪，t=10的时候P2、P3才就绪，这样的调度队列就会变回原来的：

所以对于这种情况，再次优化调度算法，变成抢占式的，也就是最短剩余时间优先。

难点：这个算法的难点，是如何计算下一次CPU执行的时间，还是老套路，可以预测，根据以前的时间来预判下一次执行的时间。

τ_n+1 = at_n + (1-a)τ_n

t_n：第n个CPU执行长度

τ_n+1：为下次CPU执行预测值

τ_n：存储了过去的历史

a：是权重

这个公式了解一下就可以了，知道有这么回事就ok。

15.2.3 最短剩余时间优先

最短剩余时间优先是抢占版的最短剩余时间优先算法。（Shortest Time-to-Completion First，STCF）

介绍：这个算法底层实现应该就是最小堆了，调度程序总是选择剩余时间最短的，如果一个新的进程进入就绪状态，并且这个进程运行时间最短，调度程序会把当前进程挂起，然后切换到新进程中。

例子：还是针对上一节的情况：如果t=0的时候，只有P1就绪，t=10的时候P2、P3才就绪。

如果具备抢占式，调度情况会变成这样：

看到跟之前的图的区别了么，区别就是P1执行10ms，所以剩余时间只有30ms了。

通过上面分析，有没有发现一个问题，就是不管如果安排，再次调用P2的时候，所有进程都轮了一圈，如果P2是一个需要快速响应的进程，那等循环了一圈之后，再响应，电脑都可以砸了（开个玩笑，不要这么暴力）。

所以引入我们熟知的时间片，也就是不让每一个进程都执行完了，才释放CPU，我们需要主动的固定一个时间片，如果进程达到了这个时间片，还在运行的话，不好意思，直接强行挂起当前进程，开启下一个进程，相当于掀桌子。

15.2.4 轮转调度

轮转（Round-Robin，RR）调度算法是专门为分时系统设计的，抢占式。

介绍：该算法也是存在一个就绪队列，调度程序为就绪队列中的每一个进程分配固定的时间片。调度程序从就绪队列中取到一个进程，开始运行，直到这个进程在时间片内主动释放CPU，或者是到了时间片被强制挂起，调度程序又开始获取下一个就绪进程，这个进程如果被挂起的话，就会再次添加到队尾。

这个轮转调度需要中断定时器支持，时间片的时间也是中断定时器的长度的倍数，这个我们后面看到切换进程的时候，再详细看。

优点：等待时间较短，响应时间很快。

缺点：周转时间会变长，并且时间片的长度也不好确定。（需要考虑进程切换的时间）

例子：我们就来举一个例子看看：

就他吧，还是用上一节的例子，来做这一节的分析。我们用4ms做为时间片

后面就不画了，选了一个难受的例子，P1要执行10个时间片，才能执行完。
平 均 等 待 时 间 ： ( 0 + 4 + 8 ) / 3 = 4 m s 平均等待时间： (0+4+8)/3 = 4ms 平均等待时间：(0+4+8)/3=4ms
刚好是时间片的时间，在看之前的平均等待时间10ms，确实响应时间快了不少，但是周转时间就会变长：

这个就不算了，因为这个P1需要10个时间片，按现在P1都没执行完，所以这个周转时间会更长。

所以存在一个取舍问题吧，要想优化周转时间就选择SJF，STCF。要想响应时间快，就选择RR。

难点：时间片长度的定义。

RR算法的性能很大程度取决于时间片的大小。在一种极端的情况下，如果时间片很大，那么RR算法与FCFS算法一样。相反，如果时间片很小（比如1ms），那么RR算法可以导致大量的上下文切换。（都在做上下文切换了）。在实践中，大多数现代操作系统的时间片为10~100ms，上下文切换的时间一般少于10ms。

15.2.5 优先级调度

介绍：轮转调度做了一个隐含的假设，即所有的进程同等重要，这种假设不存在的，在我们自己的计算上，也存在优先级很高的事件，比如接收一个邮件，所以优先级调度是有存在的必要的。

优先级调度也可以分为抢占式和非抢占式，当一个进程到达就绪队列时，比较它的优先级与当前运行的进程的优先级。如果新达到进程的优先级高于当前运行进程的优先级，那么抢占优先级调度算法就会抢占CPU。非抢占优先级调度算法只是将新的进程加入到就绪队列的头部。

优点：比较紧急的进程，可以优先得到CPU。

缺点：优先级低的进程可能会一直得不到CPU，解决的方案是：动态调整优先级，这个我们分析linux的时候就明白了。

例子：就不用举例子了吧，SJF算法就是一种简单的优先级算法，执行时间短的优先。

如果优先级等级有4级的话，每一级都有很多进程，可以组成这种模型：

同一个优先级可以用RR调度的策略。

15.2.6 多级队列调度

可能是收到优先级调度的影响，现在调度算法也进入了多级队列调度。

介绍：进程通常分为前台进程和后台进程，我们根据几种进程类型定义多级队列。前台队列可以使用RR算法调度（响应要快），后台队列可以采用FCFS算法调度。队列之间应用调度，通常采用固定优先级抢占调度。

我也不知道学生进程是啥。

优点：根据不同的进程类型，分别使用不同的调度算法

缺点：会存在低优先级饿死的情况。

15.2.7 多级反馈队列调度

多级反馈队列（Multi-Level Feedback Queue，MLFQ）就是解决多级队列中低优先级饿死的情况。

一个新进程到达，这种算法是如何处理的呢？

1. 当一个新的进程到达，将它放到最高优先级队列中。（最高优先级队列的时间片为1个，越往后时间片越大）
2. 如果新进程运行了一个时间片后，没有主动让出CPU，则降低优先级。
3. 如果新锦成运行了一个时间片后，主动让你CPU，则优先级不变。

这种操作兼容了STCF调度算法的优点，时间短的优先级高。

但是如果当前系统上存在很多交互进程，那CPU密集进程就会出现饿死。为了解决这个问题，设立了如下规则，在系统运行S时长之后，将优先级低的进程往优先级高的队列移，防止进程被饿死。

为了防止过多进程在最高优先级队列中，可以给给优先级最高队列按照RR算法调度，进程执行完一个时间片后，可以降低一下优先级。这样更利用全部的进程都参与调度。

15.3 总结

这一次讲的进程调度的算法是真的多，讲到最后的一个多级反馈队列调度，虽然分析的感觉兼容了很多种情况，确实算是一种比较好的解决方案了，但是由于兼容的太多，导致调度程序比较难写，特别是那么多个参数，想想就头大，不过幸运的是linux不是用MLFQ的方式实现的，而是用另一种方式，linux调度的算法也确实精妙，不愧是大佬，下一节我们就来分析一下linux的调度算法。