CPU 调度
CPU 调度是按照调度算法从一堆就绪的队列中选择一个进程，将 CPU 的使用权交给此进程。调度算法的主要目的控制、协调进程对于 CPU 的竞争。
调度算法的衡量指标
吞吐量：每个单位时间内完成的进程数目，越大越好；
周转时间：每个进程从提出申请到运行完成所需要的时间，越短越好；
响应时间：从提出请求到第一次响应的时间，越短越好；
CPU 利用率、等待时间：CPU 做有效工作的时间比例、每个进程在就绪队列中的等待时间；
进程调度算法
不同的系统环境选择不同的进程调度算法。
批处理系统中的调度算法
批处理系统没有太多的用户操作，所以调度算法的目标在于：吞吐量、周转时间、CPU利用率。
包含四种算法：
- 先来先服务（FCFS）
- 短作业优先（SJF）
- 最短剩余时间优先（SRTN）
- 最高响应比优先（HRRN）
* 先来先服务
FCFS，First Come First Serve
- 按照进程就绪的先后顺序使用CPU
- 非抢占式
FCFS 实现简单、公平，但是长进程后面的短进程需要等待很长的时间，不利于用户体验。
* 短作业优先
SJF，Shortest Job First
- 具有最短完成时间的进程优先执行
- 非抢占式
- 目的在于先完成短的作业，改善短作业的周转时间
短作业优先在所有进程可以同时运行时，可以得到最短的平均周转时间。但是不公平，如果不断有短任务到来，可能会导致长任务长时间得不到运行，从而产生了“饥饿”现象。
* 最短剩余时间优先
SRTN，Shortest Remaining Time Next
SJF 的抢占式版本，即当一个新就绪进程的整个运行时间比当前进程的剩余运行时间短时，系统抢占当前运行的进程，选择新就绪的进程运行。
* 最高响应比优先
HRRN，Highest Response Ratio Next
- 最高响应比优先是一个综合的算法。
- 调度时，首先计算每个进程的响应比 R，之后总是选择 R 最高的进程进行。
- 响应比 R = 周转时间 / 处理时间 = （处理时间 + 等待时间）/ 处理时间 = 1 + 等待时间 / 处理时间。如果一个进程的等待时间很长，那么它的响应比也就越高，就能得到更加优先的执行。
交互式系统中的调度算法
交互式系统着重于进程的响应时间。包含三种调度算法：
- 时间片轮转算法（RR）
- 最高优先级调度算法（HPF）
- 多级反馈队列（Multiple Feedback Queue）
* 时间片轮转算法
RR，Round Robin
- 周期性的切换进程，目的是为短任务改进平均响应时间。
- 将所有的进程按照 FCFS 的原则排成一个队列。每次调度时，为队首的进程分配一个时间片。当时间片用完时，计时器发出中断，调度程序停止该进程的运行，并将它送到就绪队列的末尾，然后给队首的新进程分配一个时间片。
选择合适的时间片很重要：
- 如果太长，会降级为 FCFS 算法，同时延长了短进程的响应时间。
- 如果太短，会延长长进程的响应时间，同时增加 CPU 进程切换的开销。
优缺点：
- 公平，有利于交互式计算，响应的时间快。
- 由于进程切换，轮转算法会花费较高的开销。
- 当所有进程的运行时间相同时，进程的平均周转时间很长。
* 最高优先级调度算法
HPF，Highest Priority First
- 选择优先级最高的算法运行。
- 优先级可以是静态不变，也可以是动态调整。优先级可以用通过优先数来决定，同时就绪队列可以按照优先级组织。
- 实现简单，但是不公平，会造成低优先级进程的饥饿现象。
- 会出现优先级翻转问题。
优先级翻转是当一个高优先级任务通过信号量机制访问共享资源时，该信号量已被一低优先级任务占有，造成高优先级任务被许多具有较低优先级任务阻塞，导致进程的实时性难以得到保证。
例如：有优先级为 A、B 和 C 三个任务，优先级 A>B>C，任务 A，B 处于挂起状态，等待某一事件发生，任务 C 正在运行，此时任务 C 开始使用某一共享资源 S。在使用中，任务 A 等待事件到来，任务 A 转为就绪态，因为它比任务 C 优先级高，所以立即执行。当任务 A 要使用共享资源 S 时，由于其正在被任务 C 使用，因此任务 A 被挂起，任务 C 开始运行。如果此时任务 B 等待事件到来，则任务 B 转为就绪态。由于任务 B 优先级比任务 C 高，因此任务 B 开始运行，直到其运行完毕，任务 C 才开始运行。直到任务C 释放共享资源 S 后，任务 A 才得以执行。在这种情况下，优先级发生了翻转，任务 B 先于任务 A 运行。
解决优先级翻转的方法有优先级上限和优先级继承：
- 优先级上限：当任务申请某资源时， 把该任务的优先级提升到可访问这个资源的所有任务中的最高优先级， 这个优先级称为该资源的优先级天花板。这种方法简单易行， 不必进行复杂的判断， 不管任务是否阻塞了高优先级任务的运行， 只要任务访问共享资源都会提升任务的优先级。
- 优先级继承：当任务 A 申请共享资源 S 时， 如果 S 正在被任务 C 使用，通过比较任务 C 与自身的优先级，如发现任务 C 的优先级小于自身的优先级， 则将任务 C 的优先级提升到自身的优先级， 任务C 释放资源 S 后，再恢复任务 C 的原优先级。这种方法只在占有资源的低优先级任务阻塞了高优先级任务时才动态的改变任务的优先级。如果过程较复杂， 则需要进行判断。
* 多级反馈队列
Multiple Feedback Queue
设置多个就绪队列，每个队列的优先级和时间片也不同。第一级队列的时间片最小，优先级最高，随着队列的优先级降低，队列对应的时间片增大。当第一级队列为空时，从第二级别队列中调度，以此类推。当一个新进程就绪后，进入第一级队列，进程用完时间片后放弃 CPU，进入下一级别就绪队列。由于阻塞而放弃 CPU 的进程进入到相对应的等待队列，一旦等待的事情发生，该进程返回到原来的就绪队列中。
进程调度算法总结
| 调度算法 | 占用CPU方式 | 吞吐量 | 响应时间 | 开销 | 对进程的影响 | 是否存在饥饿问题 |
|---|---|---|---|---|---|---|
| FCFS | 非抢占式 | 不强调 | 可能很慢，特别适当进程的执行时间差别很大的时候； | 最小 | 对短进程不利；对I/O进程不利； | 无 |
| SJF | 非抢占式 | 高 | 为短进程提供最好的响应时间 | 可能较大 | 对长进程不利 | 可能 |
| SRTN | 抢占式 | 高 | 提供好的响应时间 | 可能较大 | 对长进程不利 | 可能 |
| HRRN | 非抢占式 | 高 | 提供好的响应时间 | 可能较大 | 很好的平衡性 | 无 |
| RR | 抢占式（时间片用完） | 如果时间片很小，吞吐量很低 | 为短进程提供好的响应时间 | 较大 | 公平对待 | 无 |
| FeedBack | 抢占式（时间片用完） | 不强调 | 不强调 | 可能较大 | 对I/O进程有利 | 可能 |