第十一章 CPU调度
CPU调度概念
CPU的调度要考虑以下几个问题：
- 调度的时机；
- 从就绪队列中挑选下一个占用CPU运行的进程；
- 从多个可用CPU里面挑选就绪进程可使用的CPU资源。
操作系统通过调度程序来完成CPU的调度，操作系统运行调度程序的条件：
- 进程从运行状态切换到等待状态；
- 进程退出；
对非抢占系统：只有当进程主动放弃CPU时，操作系统才能运行调度程序；
对抢占系统：如果分配给进程的时间片用完或者优先级更高的等待进程切换到就绪状态，那么在抢占系统中，操作系统就会运行调度程序；
调度准则
响应时间指标；
- 减少响应时间：及时处理用户的输入请求，尽快将输出反馈给用户。
- 减少平均响应时间的波动；
吞吐量指标；
- 增加吞吐量；
- 减少等待时间；
公平性指标；
- 保证每个进程占用相同的CPU时间；
- 保证每个进程的等待时间相同；
调度算法
先来先服务算法
短进程优先算法
最高响应比优先算法
响应比R=(w+s)/s，其中w为等待时间、s为执行的时间，然后选择就绪队列中响应比R值最高的进程。该调度算法不可抢占、关注进程的等待时间从而防止执行时间长的进程出现长时间等待的情况(“饥饿”)。
时间片轮转算法
时间片：分配CPU资源的基本时间单元；
给每个进程分配一个时间片占用CPU，一个时间片结束之后，按照先来先服务算法切换到下一个就绪进程。该调度算法存在额外的上下文切换造成的开销，需要选择一个合适的时间片长度(一般是10ms，能够保证上下文切换的开销占CPU处理的1%)
多级反馈队列算法
由于没有一个调度算法能够满足所有的需求(有的希望响应迅速，有的希望处理时间短)；为解决这个问题，操作系统使用多个队列，不同需求的就绪进程放到不同的就绪队列，根据需求的不同选择合适的调度算法，各队列按照一定的比例分配CPU处理时间；
进一步改进，让各个队列之间存在交流，这就是多级反馈队列。
- 时间片大小随优先级的增加而增加；
- 若进程在当前的时间片内没有完成，则降到下一(优先)级就绪队列；
算法执行过程如下图所示：
公平共享调度算法
强调资源访问的公平，将用户与进程分组，更重要的用户的进程分配更长的运行时间；同时保证不重要的组无法垄断资源；未使用的资源安装比例分配，没有使用完所分配资源的组获得更高的优先级。
进程切换中的调度
调度程序在进程切换时被调用，具体的使用时机见下图：
实时调度
对于实时操作系统，它的正确性依赖于时间与功能两方面。实时操作系统的性能主要考虑时间约束的及时性，而速度与平均性能相对不重要。因此，实时操作系统要求时间约束的可预测性。
时间约束分为硬时限与软时限；硬时限：错过任务时限会导致严重后果，必须验证操作系统在最坏情况下能够满足时限；软时限：通常能满足任务时限，若有时不能满足，则降低要求。
关于实时调度的调度算法，有以下两个：速率单调调度算法与最早截止时间优先算法。
速率单调调度算法：先执行周期最短的任务；
最早截止时间优先算法：先执行截止时间最早的任务；
多核CPU的进程分配
对于多个处理器的CPU，有下面两种方式来分配进程：
- 静态进程分配：进程从开始到结束都在一个固定的处理器上运行，每个处理器有自己的队列，此时调度的开销很小；
- 动态进程分配：进程在执行过程中可分配到任一空闲处理器上运行，所有处理器共享一个就绪队列，由于进程会在不同的处理器间切换，因此调度开销较大，然而这种进程分配能够保证各处理机是负载均衡的。
优先级反置
低优先级的进程占着高优先级申请的资源使得高优先级的进程进入等待状态，而这时优先级处于前面两个优先级之间的进程抢占了低优先级的进程；这一现象称为优先级反置。解决优先级反置有下面两种处理方法：
优先级继承：占用资源的低优先级进程在被抢占时继承申请资源的高优先级进程的优先级，并在释放资源后，优先级将为原来低的优先级；
优先级天花板协议：占用资源进程的优先级与所有可能申请该资源的进程的最高优先级相同；