操作系统需要遵循一定的规律去安排进程的运行，既要照顾到每个进程也要安排好它们的优先级。
两种类型的调度器
长期调度器(long-term scheduler)用于决定什么进程应该在就绪态以及被终止。短期调度器(Short-term scheduler)用于决定哪一个处于就绪态的进程需要被移到运行态。
两种类型的调度
之前我们讲行程控制器的时候，提到它有一个记录调度信息的值。它里面包含了一个进程/线程的优先级信息。利用这个优先级信息，就可以对进程进行竞争调度了。
竞争调度(Preemptive scheduling)允许进程之间相互竞争被运行，而非竞争调度(Non-preemptive scheduling)没有这个竞争。
注: 竞争调度和非竞争调度，经常被称为抢占和非抢占调度。
调度规则
决定一个进程优先级的因素有很多，操作系统需要参考调度规则(scheduling rules)来给出优先级。下面这些是常见的参考信息。
| 参数 | 解释 |
|---|---|
| 到达时间(arrival) | 进程到达就绪队列的时间 |
| 离开时间(Departure) | 进程离开就绪队列的时间 |
| CPU运行时长(Attained CPU time) | 进程在运行态的时长 |
| 进程生命（Real time in system） | 进程从创建开始在系统里面的时长 |
长期调度和短期调度都需要到这些信息，但是相对来说长期调度不需要这么频繁的操作。另外，对于短期调度来说，它的到达时间是从进程被放进就绪队列的时候开始的，也就是t1, t4这两个时间(见下图)，而长期调度则是t1；对于短期调度来说，它的CPU时间是该次CPU开始运行到结束的时长，这是从t2, t5开始算起的，而长期调度则是记录所有这些运行时间的总和。不过，我觉得不同操作系统的参数和计算方式也是不尽相同的。
批处理任务
批处理任务(Batch process)是指那些无需人工干预的进程。计算机会提取需要的数据，然后一个个处理它们再输出。
先进先出算法(First-In-First-Out algorithm, FIFO)
这是最简单的调度算法了。先进到就绪队列的进程，被最先执行。在进程$P_{1}$运行到$t_{1}$的时候，进程$P_{2}$进入到了就绪队列，$P_{2}$就会被延迟到$t_{2}$，也就是$P_{1}$终止了以后才开始运行。
最短进程优先算法
最短进程优先算法(Shortest Job Next algorithm, SJN), 光看名字就知道是什么意思了。系统会对进程的CPU时间进行一个估算，然后把需要CPU时间最短的进程排在前面。如上图，在$P_{1}$还在运行的时候，$P_{2}$和$P_{3}$被放进了就绪队列。当p1运行结束的时候，系统会选择能更快结束的$P_{3}$来运行。其次才是较之更长的$P_{2}$运行。
最短剩余时间优先
最短剩余时间优先算法(Shortest Remaining Time First algorithm, SRTF)会根据进程所需要剩余的时间来决定转换的对象。上图中，当$P_{1}$执行到$t_{1}$的时候，$P_{3}$被放进了就绪队列。因为p3剩下还需要的CPU时间比$P_{1}$少，于是被调度到运行状态。当3运行完了以后，就绪队列里面有$P_{1}$和$P_{2}$两个进程。因为p1剩下所需要的CPU时间比$P_{2}$少，于是$P_{1}$被优先执行。
算法的性能
我们对比一下这些算法的性能。在比较之前我们要了解几个概念
- 周转时间(Turnaround Time): 进程从就绪状态一直到运行状态结束的时间
- 平均周转时间(Average Turnaround Time): 所有进程周转时间的平均数
- 进程饥饿(Starvation)：一个进程相对于其它进程而言长久的被留在就绪状态，我们称这个现象为进程饥饿。
如上图所示，在就绪队列中有三个进程$P_{1}$,$P_{2}$,$P_{3}$我们用白色框来表示延迟的时间。延迟时间加上运行的时间就是周转时间。由此我们可得平均周转时间公式
$$\frac{1}{n}\sum_{i=0}^{n}t_{i}+r_{1}$$
其中，$t_{i}$为进程$i$的周转时间，$r_{i}$为进程$i$的运行时间。
如果用FIFO算法，$P_{2}$需要延迟3个单位的时间再执行，$P_{3}$需要延迟7个单位的时间再执行。平均周转时间(ATT)是
$$ATT_{FIFO}=\frac{\left(0+4\right)+\left(3+5\right)+\left(7+1\right)}{3}=6.66667$$
依此计算，我们找到SJN和SRTF的平均周转时间
$$ATT_{SJN}=\frac{\left(0+4\right)+\left(2+1\right)+\left(4+5\right)}{3}=5.33333$$
$$ATT_{SRTF}=\frac{\left(1+4\right)+\left(4+5\right)+\left(0+1\right)}{3}=5.00$$
我们看到在上图这种情况下，SRTF这种算法是最高效的，因为所有进程从等待到执行再到阻塞或者结束的平均时间是最短的。然而，这并不意味着SRTF和SJN两种算法一定优于FIFO。因为我们看到图中SRTF和SJN都将$P_{2}$延后了，如果出现一个进程，它需要的时间比一般的进程都要久，进程饥饿这种情况就会出现。在最坏的情况下$P_{2}$永远都不会被执行！
交互进程
跟批处理任务不同，交互进程(Inveractive Process)需要和用户交互。比如说我们经常使用的终端就是一个交互进程。给这些进程调度有不一样的一些算法。
轮询调度算法
现在很多人直接用轮询调度算法的英文名Round-Robin Sheduling, 更熟悉的叫法:时间片轮转算法，RR算法，或者Round-Robin算法。
我们把时间分成很小的单位，称之为时间片^1 (Time Quantum, 通常是10-100毫秒不等)。它会将就绪队列里面的进程，以每个1单位时间片的运行时间轮流跑这些进程，直到结束(见下图, 注意横坐标单位)。
多层调度算法
RR算法将所有的进程都一视同仁了，多层调度算法(Multilevel Scheduling)在RR算法的基础上区分了进程的优先级。
如上图所示，所有的进程都会被分配到一个多层优先级列队中。这个算法会先从最高优先级的进程开始，用RR算法一层层的往下运行。如果在执行的过程中有新的更高优先级的进程进入了队列，这个算法会跳到那个最高的优先级进程重新向下执行。
多层反馈算法
在多层调度算法的基础上，多层反馈算法(Multilevel Feedback algorithm, MLF)会改变进程的优先级，而且每层的时间片长度是不一样的。进程在第i层运行一段时间后会降级到i-1层，在i-1层它能被运行 $2\times$ 第i层运行的次数，之后再到下一层中。最低优先级的进程可以运行无限长以保证所有进程都能跑完。
| 优先级 | 运行次数 |
|---|---|
| N | 1 |
| N-1 | 2 |
| N-2 | 4 |
| N-3 | 8 |
| … | … |
| 1 | $\infty$ |
当然，这个算法对运行次数的增率在不同的操作系统中也是有不同的策略的。由上表可见，多层反馈算法对短进程是欢迎的，越短的进程能越快被完成, 而越长的进程会在下一层中给以更多的时间片来完成。
时间片的影响
响应时间(Response Time)是一个进程的响应所需要的时长。我们敲下的键盘，点击的鼠标都有一个响应时间。时间片的长短影响了程序的响应时间。如下图，红色方块是响应时间。时间片越长，响应时间越长，CPU时间的使用率越低。
实时进程
实时进程(real-time process)相比交互进程，需要一直持续运转。它要达到一定的速度才能够不停的输出。常见的实时进程：流媒体播放器。想想如果不能够实时的输入和输出，听到的一定是噪音，看到的一定是连环画【笑】。
跟交互进程一样，实时进程需要将时间切割成片段，称之为周期(period，一个周期是毫秒甚至微秒之间)。
速率单调
速率单调算法(Rate-monotonic algorithm, RM)算法通过周期来调度进程。在这个算法里面，越短的进程优先权越高。在一个周期之内，某些进程的输入必须要被在该周期内处理掉。
如上图，$P_{1}$的周期是4，所需的CPU时间是1；$P_{2}$的周期是5，所需的CPU时间是3。因为$P_{1}$$P_{1}$比$P_{2}$短，所以它的优先权更高。速率单调算法会优先选择$P_{1}$执行，在$P_{1}$执行完后，因为还在$P_{2}$的周期内，所以可以选择$P_{2}$运行；很快，因为进入了$P_{1}$的第二次周期，其优先权较高，所以调度算法选择执行$P_{1}$。依此类推，就是速率单调算法了。
最早截止时间优先调度
就像名字一样，最早截止时间优先调度(earliest deadline first, EDF)会将那些最早截止的进程先执行。
如上图，和速率单调中的图一样，$P_{1}$的周期是3，所需的CPU时间是1；$P_{2}$的周期是4，所需的CPU时间是3。因为$P_{1}$的截止时间$t_{3}$比$P_{2}$的$t_{4}$早，所以它的优先权更高。在执行完$P_{1}$后，因为还在$P_{2}$的周期内，所以可以选择$P_{2}$运行。在$P_{2}$运行期间，新的$P_{1}$周期出现在$t_{3}$。因为新的$P_{1}$截止时间在$t_{6}$，而目前正在运行的$P_{2}$截止时间比之较早，所以选择$P_{2}$继续运行。依此类推，就是最早截止时间优先调度了。
算法的性能
对于实时进程来说，最好的状态是所有的进程都能在其周期内完成所需的运算。我们称一个调度可行(feasible)，如果所有的进程都能在其周期内完成所需的运算。
用进程的总CPU时间除以进程的周期，我们可以得到一个CPU利用率(CPU utilization rate)^2
$$U=\sum_{i}^{n}\frac{T_{i}}{D_{i}}$$
其中，i为某一进程。如果T大于D的话，这些算法是不可用的。
对比RM和EDF
从上面两个图中我们发现，EDF下$P_{1}$和$P_{2}$没有丢失，而RM下第一个$P_{2}$运行少了一个单位的时间。
综合解决方案
通用的操作系统同时要能够给批处理进程，交互进程，和实时进程调度。所以我们需要一个综合的解决方案。
双层调度
双层调度(2-tier approach)将进程分成两组，一组是实时进程，另一组是批处理进程和交互进程。
对于第一组实时进程，优先级高的进程因为速度快，而且短，只要用FIFO调度就好了，对于优先级低的进程就使用RR；而另一组的批处理以及交互进程可以用MLF调度。
带变动优先权的双层调度
在双层调度的基础上加上了权重，除了实时进程不变之外，其它类型的进程会一开始被分配一个足够低的优先权，在运行过之后，那些请求的资源响应越快的进程，优先权会被提高。比如一个进程如果是需要访问远程计算机的资源，而网络带来的延迟很高需要等待，那么它的优先权会被降低；一个进程如果只和键盘打交道，而键盘的响应速度十分快，它的优先权就会被提高。