CPU调度
什么是CPU调度
按照一定的调度算法，从就绪队列中选择一个进程，把CPU的控制权交给被选中的进程。如果就绪 队列中没有就绪进程，系统会安排一个空闲进程或者idle进程上CPU执行。
CPU调度要解决的问题
- 进程调度的原则
- 进程调度的时机
- 进程调度的过程
调度的时机
- 进程正常终止或者因错误而终止
- 进程创建或者等待进程变成就绪态
- 进程从运行态变成阻塞态
- 进程从运行态变成就绪态
其实，当内核对中断、异常、系统调用处理后返回到用户态时会触发CPU调度
调度的过程
进程调度的过程其实就是进程切换的过程，所谓的进程切换主要包括两部分：
- 切换全局页目录以加载新的地址空间
- 切换内核栈和硬件上下文，具体步骤如下：
- 保存旧进程的上下文环境（程序计数器、程序状态、其他寄存器）
- 用新的转态和相关信息更新旧进程的PCB
- 把旧进程移到相应的进程队列中
- 将新进程的状态设置为运行态
总之，切换过程包括对原来运行进程各种状态的保存和新的进程各种状态的恢复
调度的成本
直接花销
- 保存以及恢复寄存器等
- 切换地址空间（相关指令比较昂贵）
间接花销
- 高速缓存、缓冲区缓存、TLB失效
调度算法
调度算法衡量指标
设计调度算法考虑问题
- PCB中需要记录的与CPU调度有关数据
-
优先级以及进程队列的组织
可以按照优先级来排队，如下图所示：
也可以在进程的运行过程中动态的改变其优先级，如下图所示：
- 抢占式与非抢占式组织
-
I/O密集与CPU密集型
一般来说会让I/O密集进程尽早上CPU运行
-
时间片
选择时间片时需要考虑进程切换的开销、对响应时间要求、CPU能力等、就绪进程个数等
批处理系统中调度算法
批处理是指用户将一批作业提交给操作系统后就不再干预，由操作系统控制它们自动运行。
先来先服务（FCFS）
又称作先进先出（FIFO），是按照进程就绪的先后顺序使用CPU，属于非抢占式调度
优点
- 公平
- 实现简单，维护队列即可
缺点
- 长进程后面等待的短进程等待时间比较长
例子
短作业优先（SJF）
具有最短完成时间的进程优先执行，属于非抢占式。
如果将其改成抢占式，则为最短剩余时间优先算法（SRTN），当一个新的就绪进程比当前运行进程具有更短的完成时间时，系统抢占当前进程，选择新的就绪进程执行。
优点
- 可以得到最短平均周转时间（前提是所有进程同时可运行）
缺点
- 不公平，有很多短任务的时候可能会导致长任务不能运行
最高响应比优先（HRRN）
调度时计算每个进程的相应比，选择所有进程中相应比最高的来执行。所谓的相应比为周转时间/处理时间，其推倒公式如下：
交互式系统
时间片轮转调度算法(RR)
其主要目标是改变短作业的平均响应时间，主要是通过如下的三种机制：
- 周期性切换
- 每个进程分配时间片
- 通过时钟中断轮换进程
时间片的选择
- 时间片大于交互时间
- 降级为先来先服务算法
- 延长段进程响应时间
- 时间片小于交互时间
- 因频繁切换导致响应时间变长
- 进程切换浪费CPU时间
优点
- 公平
- 有利于交互式计算，响应时间加快
- 对于时间长度大小不同的进程来说有利
缺点
- 进程切换浪费时间
- 对于时间长度大小相同的进程来说不利，可以与先来先服务比较平均响应时间
改进
对于上述的时间片轮转算法，对于IO密集型进程来说，可能存在不公平的问题。因为对于IO密集型进程，其大概率是在等待IO的执行结果，当被调度到CPU上时，其大概率是没有使用部分时间是在进行计算，因此会充分利用时间片。对于不能充分利用时间片的IO密集型进程来说，其会与CPU密集型进程一样的参与调度，所以对于其来说是不公平的。
因此，提出了虚拟轮转算法，其调度图如下：
如上图所示，IO进程从等待状态进入到就绪状态的时候，其进入到辅助队列中，当调度进程到CPU上运行的时候，其先从辅助队列中选择进程运行，直至辅助队列为空的时候才从就绪队列中选择CPU密集型进程调度运行。
最高优先级调度算法(HPF)
总是选择优先级比较高的进程运行，这个优先级可以是静态不变的，也可以是动态变化的。
优点
- 实现简单
缺点
- 不公平，优先级低的进程产生饥饿现象
问题
对于基于优先级的抢占式调度算法，会出现优先级反转问题。所谓的优先级反转问题就是指一个低优先级的进程持有一个高优先级进程所需要的资源，使得高优先级的进程等待低优先级的进程运行完才能运行的现象。
举个例子，假设现在有H进程为高优先级，L进程为低优先级，M进程为中优先级（CPU计算型）。如果L进程进入临界区，之后被M进程抢占，H进程也要进入临界区，但是因为L进程没有释放临界区，所以进入失败，被阻塞，此时M进程上CPU执行，L无法执行，所以H也无法执行。
针对上述问题，有三种解决方案：
- 对于进入临界区的进程，将其优先级设置为最高，不在临界区，优先级低
- 如果低优先级的继承阻碍高优先级进程的运行，则其继承高优先级的进程的优先级
- 进入临界区的继承禁止中断
多级反馈队列调度算法(MFQ)
如果不允许抢占：
- 设置多个就绪队列，第一个队列优先级最高
- 给不同就绪队列的进程分配不同的时间片，随着队列优先级别的降低，时间片增大
- 调度时，从优先级高队列调度
- 每个就绪队列按照时间片轮转进行调度
- 新创建的进程放到第一级队列
- 进程使用完时间片之后，将此进程放到下一个就绪队列中
- 由于阻塞而放弃CPU的使用进入相应的等待队列，当等待的事件发生时，进程回到原来的
如果允许抢占：
当有一个优先级更高的进程就绪时，可以抢占CPU，被强占的进程可以放回到原来的一级就绪队列中，其执行时间可以是剩余的时间片时间也可以是一个完整的时间片时间。
各个调度算法之间进行比较
