五、多级反馈队列调度算法

• 是UNIX的一个分支BSD5.3版所采用的调度算法
• 是一个综合调度算法（折中权衡）
• 设置多个就绪队列，第一级队列优先级最高
• 给不同就绪队列的进程分配长度不同的时间片，第一级队列时间片最小；随着队列优先级别的降低，时间片增大。
• 当第一级队列为空时，就在第二级队列调度，以此类推
• 各级队列按照时间片轮转方式进行调度
• 当一个新创建进程就绪后，进入第一级队列
• 进程用完时间片而放弃cpu，进入下一级就绪队列
• 由于阻塞而放弃cpu的进程进入相应的等待队列，一旦等待的事件发生，该进程回到原来一级就绪队列

以上所说都是属于非抢占式的，如果允许抢占，则当有一个优先级更高的进程就绪时，可以抢占cpu，被抢占的进程回到原来一级就绪队列的末尾。

1
说明：当一个进程总是用完时间片，那么其就会一直降级，这样我们就可以知道这是一个cpu型进程，于是就区分出了cpu型和I/O型进程，同时可以知道这种调度算法偏好I/O型进程。当然也做了一些弥补，即优先级低的进程时间片较大。

六、各种调度算法的比较

2

七、多处理器调度算法设计

• 不仅要决定选择哪一个进程执行，还需要决定在哪一个cpu上执行
• 要考虑进程在多个cpu之间迁移时的开销
  1、高速缓存失效、TLB失效
  2、尽可能使进程总是在同一个cpu上执行
  • 如果每个进程可以调度到所有cpu上，假如进程上次在cpu1上执行，本次被调度到cpu2，则会增加高速缓存失效、TLB失效；如果每个进程尽量调度到指定的cpu上，各种失效就会减少。
• 考虑负载均衡问题

7.1 典型系统所采用的调度算法

• UNIX： 动态优先数法
• BSD5.3：多级反馈队列法
• Linux：抢占式调度
• Windows：基于优先级的抢占式多任务调度
• Solaris：综合调度算法

7.2 Windows线程调度

• 调度单位是线程
• 采用基于动态优先级的、抢占式调度，结合时间配额的调整

基本思想：

• 就绪线程按优先级进入相应的队列
• 系统总是选择优先级最高的就绪线程运行
• 同一优先级的各线程按时间片轮转进行调度
• 多cpu系统中允许多个线程并行运行

引发线程调度的条件：
之前我们提到了四个条件：

• 线程正常终止或由于某种错误而终止
• 新线程创建或一个等待的线程变成就绪
• 当一个线程从运行态进入阻塞态
• 当一个线程从运行态变为就绪态

这里还有两个条件：

• 一个线程的优先级改变
• 一个线程改变了它的亲和（Affinity）处理机集合（比如允许一个线程在多个处理机上执行，但是如果其他的处理机空闲，则此线程也不能在其上进行执行）

Windows线程优先级：

• 分成了三类：

  
  3

线程的时间配额：

• 时间配额不是一个时间长度值，而一个称为配额单位的整数
• 一个线程用完了自己的时间配额时，如果没有其他相同优先级的线程，Windows将重新给该线程分配一个新的时间配额，让它继续执行。实质就是不会一定让一个线程一直运行直到其结束，首先给其分配一个时间配额，运行完之后再次检查，如果没有运行完则再次分配时间配额，让其运行，这个过程不是连续的，是有间断的。

时间配额的一种特殊作用：

• 假设用户首先启动了一个运行时间很长的电子表格计算程序，然后切换到一个游戏程序（需要复杂图形计算并显示，是CPU型）
• 如果前台的游戏进程提高它的优先级，则后台的电子表格计算进程就几乎得不到CPU时间了
• 但增加游戏进程的时间配额，则不会停止执行电子表格计算，只是给游戏进程的CPU时间多一些而已。

调度策略：

• 主动切换
  某个线程可能在运行过程中需要输入输出，此时进入阻塞态，此时cpu会选择新的线程进行执行。
• 抢占
  如果上面所说的阻塞线程被唤醒，同时其优先级又更高，那么就会去抢占执行。当线程被抢占时，它被放回相应优先级的就绪队列的队首
  • 处于实时优先级的线程在被抢占时，时间配额被重置为一个完整的时间配额
  • 处于可变优先级的线程在被抢占时，时间配额不变，重新得到cpu后将运行剩余的时间配额
    这里的实时优先级和可变优先级有什么区别？？？？难道实时优先级就是按创建顺序产生的优先级，而可变优先级就是优先级可变的？
• 时间配额用完
  假设线程A的时间配额用完
  • A的优先级没有降低
    1、如果队列中有其他就绪线程，选择下一个线程执行，A回到原来的就绪队列末尾
    2、如果队列中没有其他就绪线程，系统会给A重新分配时间配额，让其继续执行
  • A的优先级降低，此时Windows将选择一个更高优先级的线程执行

线程优先级提升与时间配额调整：
为什么一个线程的时间配额用完后其优先级会被降低，这是因为之前此线程的优先级被提升过。

• Windows的调度策略
  • 如果体现对某类线程具有倾向性？
  • 如何解决由于调度策略中潜在的不公平性而带来的饥饿现象？
  • 如何改善系统吞吐量、响应时间等整体特征？
• 解决方案
  • 提升线程的优先级
    下列五种情况，Windows会提升线程的当前优先级：
    1、I/O操作完成
    2、信号量或事件等待结束
    3、前台进程中的线程完成了一个等待操作
    4、由于窗口活动而唤醒窗口线程
    5、线程处于就绪态超过了一定的时间还没有运行（即“饥饿”现象）
    在Windows中线程优先级的提升只是针对可变优先级范围内（1-15）的线程优先级
  • 给线程分配一个很大的时间配额

几个线程优先级提升的例子：
1、I/O操作完成后的线程优先级提升

• 在完成I/O操作后，Windows将临时提升等待该操作线程的优先级，保证该线程能更快上CPU运行进行数据处理

• 优先级的提升值由设备驱动程序决定，提升建议值保存在系统文件“Wdm.h”或“Ntddk.h”中

• 优先级的提升幅度与对I/O请求的响应时间要求是一致的，响应时间要求越高，优先级提升幅度越大

• 设备驱动程序在完成I/O请求时通过内核函数IoCompleteRequest来指定优先级提升的幅度

• 为避免不公平，在I/O操作完成唤醒等待线程时会将该线程的时间配额减一

• 2、饥饿线程的优先级提升

• 系统线程“平衡集管理器”每秒钟扫描一次就绪队列，发现是否存在等待时间超过300个时钟中断间隔的线程

• 平衡集管理器将这些线程的优先级提升到15，并分配给它一个长度为正常值的4倍的时间配额

• 当被提升的线程用完它的时间配额后，立即衰减到原来的基本优先级