本文已收录到：清华大学操作系统课程笔记 专题
处理机调度
处理机调度概念
处理机调度
调度时机
非抢占系统
可抢占系统
调度准则
调度策略：从就绪队列中选择进程
实现调度策略
例如在前面的缺页置换算法中，指标就是缺页的次数。
解释上图：我们发现，CPU执行一个计算，它的耗时通常在8ms以内，这就是我们分配时间片的重要依据。如果分配的时间片大于8ms，显然就会浪费。
当然是将就绪状态交给CPU。就绪进程有多个怎么选择？？——第一个问题
没执行完，被迫放弃CPU。——选择合适的时间片
用什么指标度量调度算法的好坏?
从硬件的角度来讲：
从用户的角度来讲：
似乎这是矛盾的吧？？？你总不能让硬件消耗低，用户感受还好。
不让吃饭，还要求能干活？？
吞吐量&延时
低延迟目标
吞吐量目标
公平性目标
不同场合，对公平性的定义是不一样的。
调度算法
先来先服务算法（FCFS）——按到就绪队列里的先后顺序
如果换一个顺序：
此算法周转时间跟顺序有很大的关系，如果不行排在需要很长的计算时间的进程后面，就会等很久。
短进程优先算法——考虑进程的特征
短作业优先（SJF）、短剩余时间优先（SRT）：一个进程正在执行，新来的进程比之前那个进程所消耗的剩余时间还短的话，我允许你插队，先执行。
短进程优先算法的优点：减少平均周转时间
考虑到进程的执行时间这一特征。选择执行时间最短的进程先执行。当然，这是预期时间。
队列中按照预期执行时间顺序排序，短时间最优先。
如果这时候来了一个进程，他的预期时间更少，则允许他抢先执行。
短进程优先算法有最优平均周转时间的特性，下面的周转时间一定比上面的大，所以调整执行顺序是可以减少平均周转时间的。
短进程优先算法可以保证最短的、最优的周转时间。
短进程优先算法的缺点：连续进来短进程会产生饥饿问题
由“用户”说自己的进程需要多久时间，如果超时就停止：
如果“用户”也不知道需要多久呢？跟前面的虚存置换一样，预测未来时间是不可能的。可以用历史的执行时间来预估将来的执行时间。
α表示衰减系数，越靠前面，权重逐渐降低。
如下图所示，黄色是实际时间，蓝色是预估时间，可以做到一定的拟合。
最高响应比优先算法（HRRN）——避免饥饿、考虑进程的等待时间
基本思想：选择就绪队列中响应比R值最高的进程。
R值计算方法是 R = (等待时间+执行时间)/执行时间。等待时间越长、执行时间越短的进程R值越高，越优先。
时间片轮转算法（RR）（lab6）——按时间片先来先服务，限制时间
时间片长度的选择，如果太小会产生大量的上下文切换影响系统开销。如果太长，极端情况下会退化为先来先服务算法。所以此算法的前提是选取合适的时间片。
多级队列调度算法（MQ）——上面的多个算法组合在一起。
多级反馈队列算法（MFQ）——一个进程可以“来回横跳”
刚在的多级队列调度算法中，各个队列之间是没有交流的。现在允许进程可以一会儿再队列A中，一会儿在队列B中。
下图重要，仔细观察。
- 每个进程刚上来都是在最高优先级，如果没在规定时间执行完，就会降级。
- 优先级越高的话，他的时间片越少。只管的感觉是——大家都很忙，每个人时间都很少，快节奏，而下面优先级低的就像小城市，大家都不着急，所以每个人时间就长点呗。
公平共享调度算法（FSS）——进程所占资源公平
ucore 4线程状态
ucore的调度时机和进程切换
