处理机调度
一. 概念
调度时机包括进程主动让出CPU（有进程从运行状态切换到等待状态（因为要等待某一事件）/ 进程退出）和进程由运行状态转换为就绪状态（因为时间片用完或有另外一个进程从等待变成了就绪，急迫占用CPU））。调度时机来了，处理机完成调度。
进程（应用程序）处于两种模式之间来回切换——CPU计算和进行IO操作（此时CPU处于等待状态）
二. 调度算法的准则
CPU使用率：在进程执行等待IO操作时，处理机是否能及时的找到另一个进程来占用CPU执行。能的话，CPU处于忙状态的时间比就会提高。
调度算法中，单位时间能执行更多的进程（高吞吐量）叫快。
处理机调度算法三大目标：
三. 调度算法
- 先来先服务算法
前两行是就绪队列里的排法和取法。
假设三个任务基本同时到达 - 短进程优先算法
短剩余时间优先算法：
假设一个进程正执行且预期执行时间很长，这时来了一个新的进程，它预期的执行时间比当前正在执行的进程剩下的时间短，这时允许新进程抢先。
横坐标r(i)代表第i个进程执行完花费的时间（包括等待时间）。
优点：
这里C3.C4.C5是进程P3.P4.P5的单独执行时间。修改后P4执行完需要的时间是r2+r4-r3=r4-C3
缺点： - 最高响应比优先调度算法
等的时间越长，优先级越高，可以得到CPU的使用权。 - 时间片轮转算法（结合了先来先服务）
每个进程分到1/n的时间
最好的FCFS相当于短进程优先，差的相当于长进程优先。 - 多级队列调度算法
就绪队列分子队列，如前台和后台
队列之间采用时间片算法
每个队列调度策略不同，如前台时间片，后台先进先出 - 多级反馈队列算法
时间片P是基本单位，优先级越低分得的时间片越长
CPU密集型进程优先级会逐步降低，IO密集型进程停留在高优先级上因为每一次计算时间都很短。 - 公平共享调度算法
调度就是发生在由内核态返回用户态之前做的工作。
四. 实时调度和多处理机调度
1.实时调度：对时间有要求的调度算法
要在指定的时间内完成相应的功能
使用率是重要指标
可以给出任务的执行时序满足所有任务的对实现的要求，这个系统就是可调度的
静态：事先把执行顺序排出来，按照顺序调度
动态：无法事先给出执行顺序
速率单调调度算法：频率越高周期越短的优先级越高；周期越短先执行，周期越长后执行。
2.多处理机调度
有多个处理机的系统中，如何调度
一个进程到底分配到那个处理机上运行，分配的方法有两类，静态进程分配（一个进程从头到尾都在一个处理机上执行，起头有个分配，之后就变成单处理机系统上的调度算法），动态进程分配（一个进程不一定从头到尾都在一个处理机上执行）
五. 优先级反置——调度算法可能引起这种现象
T1已经占用了资源L1，高优先级进程T2处于等待状态。在高优先级进程T2进入阻塞状态后，在低优先级进程T1还没有得到CPU使用权投入运行之前，T3进入运行状态。这种现象为优先级反置。在基于优先级的可抢占的调度机制中，当系统强制使高优先级任务等待低优先级任务时，可能出现优先级反置。
为处理这个现象，可采用两种做法。
（1）优先级继承
高优先级T1申请资源时，如果他申请的是正在运行的低优先级进程T3所占用的资源，这时低优先级进程T3会被提升到高优先级，可进入执行状态。等到T3释放资源，T3的优先级由变成低优先级，T1就可以获取到资源。
（2）优先级天花板协议
此时进程占用资源时，其他任何进程都不会阻止它使用这个资源