5.6 Windows Scheduling
ch5-1 Windows & Linux scheduling.pdf
Windows 2000/XP 线程状态
Windows 2000/XP 把线程状态分成下面七种状态
与单挂起进程模型很相似，主要区别在于从就绪状态到运行状态的转换中间多上一个备用状态
- 初始化状态(Initialized)：线程创建过程中的线程状态
- 就绪状态(Ready)：线程已获得除处理机外的所需资源，正等待调度执行。
-
备用状态(Standby)：已选择好线程的执行处理机，正等待描述表切换，以进入运行状态
- 系统中每个处理机上只能有一个处于备用状态的线程
-
运行状态(Running)：已完成描述表切换，线程进入运行状态。
- 线程会一直处于运行状态，直到被抢占、 时间片用完、线程终止或进入等待状态。
-
等待状态(Waiting)：线程正等待某对象，以同步线程的执行。
- 当等待事件出现时，等待结束，并根据优先级进入运行或就绪状态。
-
转换状态(Transition)：转换状态与就绪状态类似，但线程的内核堆栈位于外存。
- 当线程等待事件且它的内核堆栈处于外存时，线程进入转换状态；
- 当线程内核堆栈被调回内存时，线程进入就绪状态。
- 终止状态(Terminated)：线程执行完就进入终止状态；如执行体有一指向线程对象的指针，可将处于终止状态的线程对象重新初始化，并再次使用。
Windows 2000/XP 的线程调度特征
- 调度单位是线程而不是进程
- 采用严格的抢占式动态优先级调度
- 依据优先级和分配时间配额来调度
具体而言
- 每个优先级的就绪线程排成一个先进先出队列；
- 当一个线程状态变成就绪时，它可能立即运行或排到相应优先级队列的尾部。
- 总运行优先级最高的就绪线程；
- 完全的事件驱动机制，在被抢占前没有保证的运行时间
- 进入就绪事件；
- 时间配额用完事件；
- 优先级改变事件；
- 亲合处理机集合改变事件；
- 在同一优先级的各线程按时间片轮转算法进行调度；
- 在多处理机系统中多个线程并行运行w
线程优先级 （THREAD PRIORITY）
有 32 个优先级，分为了三类
线程得到的优先权是相对于它们的进程优先权类而言的
开始时由 CreateProcess 设置了 6 个进程优先权类，并且每个类有一个基本优先权值
线程优先权在进程基本优先权的 ±2 范围之内，作为结果的 7 个线程优先权的符号名称如下
IDLE 等于该优先级类里的最低优先级，TIME-CRITICAL 等于该优先级类里的最高优先级
实时优先级
如果用户进程在实时优先级运行时间过多，它将可能阻塞关键系统 功能的执行，阻塞系统线程的运行；但不会阻塞硬件中断处理。
一般线程是可变优先级，要把线程的优先级提升到实时优先级，需要有升高线程优先级的权限
中断优先级与线程优先级的关系
- 区分线程优先级和中断优先级：
- ???????????
线程时间配额
时间配额是一个线程从进入运行状态到 Windows 2000/XP 检查 是否有其他优先级相同的线程需要开始运行 之间的时间总和
类似时间片，过了时间配额如果有其它相同优先级就切换，没有就再给现在这个线程分配一个时间配额
时间配额不是一个时间长度值，而一个称为配额单位(quantum unit)的整数
时间配额的计算
缺省，即处于系统 default 状态时，在 Windows 2000 专业版中线程时间配额为 6；而在 Windows 2000 服务器中线程时间配额为 36。
- 时钟中断导致时间配额减少
每次时钟中断，时钟中断服务例程 从线程的时间配额中减少一个固定值 3。
如果没有剩余的时间配额，系统将触发时间配额用完处理，选择另外一个线程进入运行状态。
- 在等待完成时允许减少部分时间配额
当优先级小于 14 的线程执行一个等待函数(如 WaitForSingleObject 或 WaitForMultipleObjects)时，它的时间配额被减少 1 个时间配额单位。
当优先级大于等于 14 的线程在执行完等待函数后，它的时间配额被重置。
这种部分减少时间配额的做法可解决线程在时钟中断触发前进入等待状态所产生的问题。
如果不这样，一个线程可能永远不减少它的时间配额。
例如，一个线程运行一段时间后进入等待状态，再运行一段时间后又进入等待状态，但在时钟中断出现时它都不是当前线程，则它的时间配额永远也不会因为运行而减少。
调度数据结构
- 就绪位图(KiReadySummary)
- 每一位指示一个调度优先级的就绪队列中是否有线程等待运行。
- B0 与调度优先级 0 相对应，B1 与调度优先级 1 相对应，等等。
- 空闲位图(KiIdleSummary)
- 空闲位图中的每一位指 示一个处理机是否处于空闲状态。
- 调度器自旋锁(KiDispatcherLock)
调度策略
主动切换
进程等待时转入 waiting 状态，同时从就绪队列选取进程进入允许状态
通常进入等待状态线程的时间配额不会被重置，而是在等待事件出现时，线程的时间配额被减 1，相当于 1/3 个时钟间隔；
如果线程的优先级大于等于 14，在 等待事件出现时，线程的时间配额被重置。
抢占
当一个高优先级线程进入就绪状态时，正在处于运行状态的低优先级线程被抢占。
被抢占的线程放回相应优先级的就绪队列的 队首
可能在以下两种情况下出现抢占：
- 高优先级线程的等待完成，即一个线程等待的事件出现。
- 一个线程的优先级被增加或减少
用户态下运行的线程可以抢占内核态下运行的线程
在判断一个线程是否被抢占时，并不考虑线程处于用户态还是内核态，调度器只是依据线 程优先级进行判断。
关于被抢占线程的时间额外
- 处于实时优先级的线程在被抢占时，时间配额被重置为一个完整的时间配额；
- 处于动态优先级的线程在被抢占时，时间配额不变，重新得到处理机使用权后将运行到剩余的时间配额用完。
时间配额用完
线程完整用完一个规定的时间片值时，重新赋予新时间片值，优先级降一级（不低于基本优先级），放在相应优先级就绪队列的尾部
- 如果刚用完时间配额的线程优先级降低了
- 寻找一个优先级高于该线程降低后的优先级的就绪线程。
- 如果刚用完时间配额的线程的优先级没有降低，并且有其他优先级相同的就绪线程
- 选择相同优先级的就绪队列中的下一个线程进入运行状态
- 刚用完时间配额的线程分配一个新的时间配额，并排到就绪队列的队尾
- 如果没有优先级相同的就绪线程可运行
- 刚用完时间配额的线程将得到一个新的时间配额并继续运行。
线程结束
线程完成运行时，状态从运行状态转到终止状态
线程优先级提升
在下列 5 种情况下，Windows 2000 会提升线程的当前优先级：
- I/O 操作完成
- 信号量或事件等待结束
- 前台进程中的线程完成一个等待操作
- 由于窗口活动而唤醒图形用户接口线程
- 线程处于就绪状态超过一定时间，但没能进入运行状态(处理机饥饿)
Windows 2000 永远不会提升实时优先级范围内(16 至 31)的线程优先级。
优先级提升策略仅适用于可变优先级范围(0 到 15)内的线程。
不管线程的优先级提升幅度有多大，提升后的优先级都不会超过 15 而进入实时优先级。
线程优先级提升是以线程的基本优先级为基点的，不是以线程的当前优先级为基点。
提升后的线程用完一个时间配额后，线程会降低一个优先级，并运行另一个时间配额，如此反复，直到恢复原来的基本优先级。
I/O 操作完成
完成 I/O 操作后将临时提升等待该操作线程的优先级，同时时间配额减 1，让其有更多的机会立即开始处理得到的结果，同时保证公平
线程优先级的提升幅度与 I/O 请求的响应时间要求是一致的，响应时间要求越 高，优先级提升幅度越大
事件或信号量等待结束
当一个等待执行事件对象或信号量对象的线程完成等待后，它的优先级将提升一个优先级。
前台线程等待结束
对于前台进程中的线程，一个内核对象上的等待操作完成时，内核会提升线程的当前优先级(不是线程的基本优先级)，以使它更有可能马上进入运行状态，有效改进前台应用的响应时间特征
图形用户接口线程被唤醒
拥有窗口的线程在被窗口活动唤醒(如收到窗口消息)时将得到一个幅度为 2 的额外优先级提升，改进交互应用的响应时间
对处理机饥饿线程的优先级提升
系统线程每秒检查一次就绪队列，有排队很久的就把该线程的优先级提升到 15，并分配给 它一个长度为正常值两倍的时间配额；
当被提升线程用完它的时间配额后，该线程的优先级立即衰减到它原来的基本优先级
对称多处理机系统上的线程调度
亲合关系(Affinity)
亲合掩码描述该线程可以（或更适合）在哪些处理机上运行
线程的亲合掩码是从进程的亲合掩码继承得到的
线程的首选处理机和第二处理机
首选处理机(ideal processor)：线程运行时的偏好处理机
第二处理机(last processor)：线程第二个选择的运行处理机
就绪线程的运行处理机选择
线程进入运行状态时，首先试图调度该线程到一个空闲处理机上运行
如果有多个空闲处理机，线程调度器的调度顺序
- 线程的首选处理机
- 线程的第二处理机
- 当前执行处理机(正在执行调度器代码的处理机)
- 将依据处理机标识从高到低扫描系统中的空闲处理机状态，选择找到的第一个空闲处理机
- 如果在被选中的处理机上没有线程可被抢占
- 新线程放入相应优先级的就绪队列，并等待调度执行
- 如果被选中的处理机已有一个线程处于备用状态(即下一个在该处理机上运行的线程)，并且该线程的优先级低于正在检查的线程
- 则正在检查的线程取代原处于备用状态的线程，成为该处理机的下一个运行线程
- 如果已有一个线程正在被选中的处理机上运行，检查当前运行线程的优先级是否低于正在检查的线程
- 如果正在检查的线程优先级高，则标记当前运行线程为被抢占，系统会发出一个处理机间中断，以抢占正在运行的线程，让新线程在该处理机上运行。
为特定的处理机调度线程
在多处理机系统，不能简单地从就绪队列中取第一个线程，要在亲合掩码限制下寻找一个满足下列条件之一的线程。
- 线程的上一次运行是在该处理机上；
- 线程的首选处理机是该处理机；
- 处于就绪状态的时间超过 2 个时间配额；
- 优先级大于等于 24；
如果找不到满足上述条件的，就从就绪队列的队首取第一 个线程进入运行状态
最高优先级就绪线程可能不处于运行状态
有可能出现这种情况，一个比当前正在运行线程优先级更高的线程处于就绪状 态，但不能立即抢占当前线程
空闲线程
如果在一个处理机上没有可运行的线程，会调度空闲线程
线程优先级为 0，只在没有其他线程要运行时才运行
由于在多处理机系统中可能两个处理机同时运行空闲线程，所以系统中的每个 处理机都有一个对应的空闲线程