CPU调度
即按一定的调度算法从就绪队列中选择一个进程， 把CPU的使用权交给被选中的进程，其任务是控制、协调进程对CPU的竞争。
调度算法衡量指标
吞吐量：每单位时间完成的进程数目
周转时间：每个进程从提出请求到运行完成的时间
响应时间：从提出请求到第一次回应的时间
进程调度算法
批处理系统
目标：吞吐量，周转时间，cpu利用率，包含以下四种调度算法：
- 先来先服务（FCFS）
- 短作业优先（SJF）
- 最短剩余时间优先（SRTN）
- 最高响应比优先（HRRN）
先来先服务（FCFS）
- First Come First Serve
- 按照进程就绪的先后顺序使用CPU
- 非抢占
长进程后面的短进程需要等很长时间，不利于用户体验。
短作业优先（SJF）
- Shortest Job First
- 具有最短完成时间的进程优先执行
- 非抢占式
最短剩余时间优先（SRTN）
- Shortest Remaining Time Next
- SJF的抢占式版本，即当一个新就绪的进程比当前运行进程具有更短的完成时间时，系统抢占当前进程， 选择新就绪的进程执行
短作业优先的调度算法可以得到最短的平均周转时间，但随着源源不断的短任务到来，可能使长的任务长时间得不到运行，即产生 “饥饿”现象。
最高响应比优先（HRRN）
- Highest Response Ratio Next
- 调度时，首先计算每个进程的响应比R；之后，总是选择R最高的进程执行
- 响应比R = 周转时间 / 处理时间 =（处理时间 + 等待时间）/ 处理时间 = 1 +（等待时间 / 处理时间）
交互式系统
目标：响应时间，包含以下三种调度算法：
- 时间片轮转（RR）
- 最高优先级（HPF）
- 多级反馈队列（Multiple feedback queue）
时间片轮转
- Round Robin
- 将所有就绪进程按 FCFS 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。
时间片轮转算法中选择合适的时间片很重要：
- 如果太长，会降级为先来先服务算法，延长短进程的响应时间
- 如果太短，进程切换会浪费CPU时间
最高优先级
- Highest Priority First
- 选择优先级最高的进程投入运行
- 优先级可以是静态不变的，也可以是动态调整的
- 不公平
- 会导致优先级翻转问题，解决方案：1、优先级天花板；2、优先级继承
优先级翻转是当一个高优先级任务通过信号量机制访问共享资源时，该信号量已被一低优先级任务占有，因此造成高优先级任务被许多具有较低优先级任务阻塞，实时性难以得到保证。
例如：有优先级为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运行。
解决优先级翻转问题有优先级天花板(priority ceiling)和优先级继承(priority inheritance)两种办法。
优先级天花板是当任务申请某资源时， 把该任务的优先级提升到可访问这个资源的所有任务中的最高优先级， 这个优先级称为该资源的优先级天花板。这种方法简单易行， 不必进行复杂的判断， 不管任务是否阻塞了高优先级任务的运行， 只要任务访问共享资源都会提升任务的优先级。
优先级继承是当任务A 申请共享资源S 时， 如果S正在被任务C 使用，通过比较任务C 与自身的优先级，如发现任务C 的优先级小于自身的优先级， 则将任务C的优先级提升到自身的优先级， 任务C 释放资源S 后，再恢复任务C 的原优先级。这种方法只在占有资源的低优先级任务阻塞了高优先级任务时才动态的改变任务的优先级，如果过程较复杂， 则需要进行判断。
多级反馈队列
设置多个就绪队列，第一级队列优先级最高，给不同就绪队列中的进程分配长度不同的时间片，第一级队列时间片最小；随着队列优先级别的降低，时间片增大。当第一级队列为空时，在第二级队列调度，以此类推。当一个新创建进程就绪后，进入第一级队列，进程用完时间片而放弃CPU，进入下一级就绪队列。由于阻塞而放弃CPU的进程进入相应的等待队列，一旦等待的事件发生，该进程回到原来一级就绪队列。
调度算法总结
| 调度算法 | 占用CPU方式 | 吞吐量 | 响应时间 | 开销 | 对进程的影响 | 饥饿问题 |
|---|---|---|---|---|---|---|
| FCFS | 非抢占式 | 不强调 | 可能很慢，特别是当进程的执行时间差别很大时 | 最小 | 对短进程不利；对I/O型的进程不利 | 无 |
| RR | 抢占式(时间片用完时) | 若时间片小，吞吐量会很低 | 为短进程提供好的响应时间 | 较大 | 公平对待 | 无 |
| SJF | 非抢占式 | 高 | 为短进程提供好的响应时间 | 可能较大 | 对长进程不利 | 可能 |
| SRTN | 抢占式(到达时) | 高 | 提供好的响应时间 | 可能较大 | 对长进程不利 | 可能 |
| HRRN | 非抢占式 | 高 | 提供好的响应时间 | 可能较大 | 很好的平衡性 | 无 |
| Feedback | 抢占式(时间片用完时) | 不强调 | 不强调 | 可能较大 | 对I/O型进程有利 | 可能 |
参考资料
- Tanenbaum A S, Bos H. Modern operating systems[M]. Prentice Hall Press, 2014.
- 北京大学操作系统原理（Operating Systems）
- 计算机操作系统
- 优先级翻转