线程的调度

概述

Windows 实现了一个由优先级驱动，抢占式的调度系统，也就是最高优先级的可运行的（就绪状态下的）线程总是先运行。

有一种现象称之为“处理器亲合（processor affinity）”，即线程可能受处理器限制，只运行在那些允许它运行的处理器上。缺省的设置是线程可运行在任何可用的处理器上，用户可以通过使用一个Win32的调度函数修改处理器的“亲合性”。

当一个线程被选择运行，它所运行的时间称之为“时间片”。Windows中断这个线程，去查找是否有别的同优先级或更高优先级的线程正在等待执行，或者这个线程的优先级需要被降低，在这之前这个线程运行的时间长度就是一个“时间片”。不同的线程，其时间片的值可以不同，Window 2000专业版和服务器版的时间片的值是不同的。然而，因为Windows实现的是一种抢占式的调度，一个线程可能未完成其时间片。如果另外有一个更高优先级的线程就绪，正在运行的这个线程就可能在未完成其时间片前被抢占。事实上，一个线程甚至会在未开始其时间片前就被抢占了，而要等待下一次被选择运行。

Windows的没有单独的调度模块或程序，调度的代码是在内核中实现的，广泛分布在内核中那些与调度相关的事件发生的地方。这些负责调度的程序被总称为“内核的调度器”。线程调度发生在DPC/Dispatch级别。

以下这些事件发生时会触发线程调度：

• 变成就绪状态的线程。例如：一个新创建的线程，或者从等待状态释放出来的线程。
• 因其时间片结束而离开运行状态的线程，它或者结束了，或者进入等待状态。
• 线程的优先级改变了，是因为系统调用，或者是Windows自己改变了优先级。
• 正在运行的线程的处理器亲合性改变了。

在每一个上述情况的衔接点，Windows必须决定下一个运行的线程是哪一个。一旦选择了一个新的线程运行，Windows将对其执行一个上下文转换的操作，即保存正在运行的线程的相关的机器状态，装载另一个线程的状态，开始新线程的执行。

Windows的调度是以线程为粒度调度的。调度的决策被严格限制在以线程为基础，并不考虑这个线程属于哪一个进程。当考虑到进程并不运行，而仅为其线程提供资源和运行的上下文环境时，这种方法就有意义了，例如，进程A有10个可运行的线程，进程B有2个可运行的线程，而且这12个线程的优先级别相同，那么，每一个线程将会使用1/12的CPU时间，而不是将CPU 50%的时间分配给进程A，50% 的时间分配给进程B。

为了明白线程调度算法，必须首先明白Windows所使用的优先级别。

线程优先级别

如Figure 6-12图示：Windows内部使用32个优先级别，从0-31。这些数值被分成以下几类：

• 16个实时级别(16-31)
• 15个变化的级别(1-15)
• 1个系统级别(0), 被保留用作0页线程

线程优先级别是从两个不同的方面来分配的：一个是从Win32应用程序编程接口，另一个是从Windows的内核。

Win32 API的进程在创建时所分配的优先级包括：Real-time, High, Above Normal, Normal, Below Normal, and Idle，进程中各个线程的相关优先级包括：Time-critical, Highest, Above-normal, Normal, Below-normal, Lowest, and Idle。 应用程序默认的优先级为Normal。

运行在内核模式的线程可以被用户模式的线程抢占掉，这与线程的状态无关，优先级是决定性因素。

在Win32 API中，每个线程的优先级都是它所属的进程的优先级和自己相关的线程优先级二者的组合。从Win32优先级映射到Windows内部数字式的优先级如Figure 6-13图示：

线程的实时优先级

在动态范围内，用户可以可以升高或降低应用程序中线程的优先级。但是，如果要将进程升高到实时范围内，就必须拥有升高调度优先级的权力。如果没有这个权力而企图将一个进程升高到实时优先级，操作不会失败，只是高级级别(High class)将被使用。

很多Windows的重要的内核模式的系统线程是在实时优先级范围内的，如果用户进程花费了过多的时间运行在这个范围内，可能会阻碍了重要的系统功能，如内存管理器、缓冲管理器、本地和网络文件系统，甚至是一些设备驱动程序。因为硬件中断拥有比任何线程都高的优先级，所以不会被阻碍。

在实时范围内的线程性能上有一点不同，当它被抢占时，其线程时间量会被重新设置。

虽然Windows有一套优先级称之为“实时”，但它们并不是通常意义上定义的实时。因为Windows并没有提供真正的实时操作系统功能，例如确保中断时间间隔，或者是让线程得到一个确保的执行时间。

时间片（quantum）

前面已经提到，“时间片”就是在Windows检查是否有另外一个同优先级的线程要执行前，线程运行的时间。如果一个线程结束了它的时间片，而又没有另外一个同优先级的线程，Windows重新调度这个线程运行另外一个时间片。每个线程都有一个时间片的数值，它代表了线程可以运行多长时间，直到时间片届满。这个数值不是一个时间的计时长度，而是一个整数，我们称之为“时间片单位（quantum units）”。

缺省的情况下，Windows 2000/XP Professional线程运行2个时钟周期（6个时间片单位），Windows Server版线程运行12个时钟周期（36个时间片单位）。每次时钟中断，时钟中断程序从线程时间片中扣除一个固定的值3（1个时钟周期）。

Windows Server版设置了较长的缺省值是为了减少上下文转换。当有客户请求到来时，服务器应用程序被唤醒后，如果有较长的时间片，它就可以更好的完成这个请求，然后在时间片结束前返回等待状态。

如果线程时间片没有剩余，时间片结束处理进程就会被触发，然后另外一个线程可能被选择执行。当时钟中断发生时，如果系统正处于DPC/Dispatch级别或者更高，例如正在执行一个DPC或者一个中断服务程序，在这种情况下，就算当前的线程在整个时钟中断间隔都没有运行，它的时间片仍然会被减少。如果不是这样做，而设备中断或者DPC又总是刚好发生在时钟间隔中断前，线程的时间片可能因此总不减少。

不同的硬件平台，时钟间隔的长度是不同的。时钟中断的频率是由HAL（硬件层）负责，而不是内核负责。例如，大部分x86单处理器的时钟间隔是10毫秒，大部分x86多处理器的时钟间隔是15毫秒。

每个时钟滴答表示3个时间片单位，而不是一个时间片单位，这种表示方法是为了线程在等待完成的时候，其时间片可以被减少一部分。基本优先级少于14的线程执行了等待的函数，如WaitForSingleObject 或者 WaitForMultipleObjects后，它的时间片就减少1个单位；优先级是14或更高的线程等待后，其时间片会被重新设置。

线程的时间片可以部分被减少的原因是，当线程在时钟间隔计数器激发前进入等待状态，如果没有对其时间片进行调整，那么有可能这个线程的时间片就从不减少。例如：一个线程运行，然后进入等待状态，然后再运行，再进入等待状态。但当时钟间隔计数器激发时，却从来不是当前运行的线程，那么当它运行时其时间片就从不被记账，也就不会减少。

线程的调度方案

线程可以处于的不同的执行状态，图6-14显示了是Windows2000/XP中线程的状态的互相转变。

线程的状态有以下几种：

Windows在线程优先级上是以“谁将得到CPU”为基准的，但这个方法是实际上如何工作的呢？下面的部分将解释在线程的级别上，由优先级驱动的，抢占式的多任务的调度是如何工作的。注意到Windows在处理线程调度决策上，单处理器系统和多处理器系统是不同的，这将在后续部分解释。

（1）自愿切换

线程可能调用Win32的某些阻塞函数如WaitForSingleObject、 WaitForMultipleObjects来等待某个对象（如事件、信号量、I/O完成的端口、进程、线程、窗口信息等），从而进入等待状态，自动放弃对CPU的占用。该线程进入同优先级就绪队列的末尾，而CPU将上下文切换到就绪队列中的下一个线程并开始执行。

以下就餐的情景能很好的帮助你理解线程的自动切换：在餐厅，你点了一个尚未准备好的汉堡包，为了不阻碍其他的就餐者，你就文明地站到一边，让下一个食客点菜。这时候，你的汉堡包正在准备中。汉堡包准备好之前，你站到了其优先级的就绪队列的尾部。这样似乎有些不公平，因为你先点的，所以当汉堡包准备好了的时候，服务员一般会先给你端过来。

同样在操作系统中，为兼顾公平，大部分线程等待的对象受信后，一般会使用一个临时增强优先级，以让线程可以马上执行。

那么线程剩余的时间片又如何呢？当线程进入等待状态时，时间片的值并不重新设置。实际上，前面已经解释过，当线程的等待状态结束时，它的时间片被减少了1个时间量单位，相当于1/3个时钟间隔。而优先级等于或高于14的线程，等待状态结束后，它们的时间量会被重新设置。

（2）抢占式调度

这种调度情况是指一个低优先级的线程被一个较高优先级的线程强抢占。有2个原因会导致这种情况的发生：

l         较高优先级的线程的等待状态结束，也就是另外一个线程在等待的事件发生。

l         线程的优先级被提高或降低。

在上述的任何一个情况下，Windows都必须决定当前运行的线程是否仍然继续运行，还是被一个更高优先级的线程抢占运行。

注意：用户模式下的线程可以抢占内核模式下的线程。其实，线程运行在什么模式下并没有关系。线程的优先级才是决定因素。

当线程被抢占，它被放到了它运行的优先级的就绪队列的头。如果是实时优先级的线程，它的时间量会被重置成一个完整的时间片。如果是动态范围的优先级的线程，它再次运行时，就完成它上次剩余的时间片。

抢占就可以粗略地比喻你的汉堡包已经准备好时，突然总统走来要订一个汉堡包。当总统在拿他的午餐时，并不要求你去队尾，出于一种尊重，你只需站到一边。一旦总统离开，你可以马上获得汉堡包，立即享用。

（3）时间片用完

当一个运行的线程使用完它的时间量，Windows必须决定是否要降低线程的优先级，和是否让另外一个线程使用处理器。

如果线程的优先级被降低，Windows寻找一个更适合的线程进行调度。一个更适合的线程是指优先级比当前运行的线程的新的优先级更高的，在就绪队列中的线程。如果线程的优先级没有被降低，而且又有同样优先级的线程在就绪队列中，Windows将在队列中选择下一个线程，而将先前运行的线程放到了队列的尾部，并赋予它一个新的时间片值，将其状态从运行改为就绪。如果没有另外一个同样优先级的线程准备好运行，线程将继续执行它下一个时间片。

（4）终止

当线程调用了ExitThread从主函数中返回，或者被TerminateThread杀掉，它都结束运行，运行状态改为终止状态。如果该线程对象没有打开的句柄，就会从进程的线程队列中被删除，其相关的数据结构将会释放并重新被分配。

线程优先级的提升

在五种情况下，Windows会提升线程当前优先级的值：

• 完成I/O操作时；
• 等待执行体事件或者信号量受信后；
• 前台进程的线程完成等待操作后；
• 因为窗口行为，GUI线程被唤醒时；
• 当线程准备好运行，但却一直不能运行。（CPU饥饿）

这些调整的目的是为了提高系统整体的吞吐量和响应能力，同时也为了解决潜在的不公平的调度现象。正象任意的调度算法一样，这些调整并不是完美的，并不是所有的应用程序都会从中得到好处。Windows从不提升那些在实时范围内（16-31）的线程的优先级。因此，在谈到实时范围内的线程时，调度通常是可预知的。

说明：

本文摘自《Windows Internals》第6章《进程、线程和作业》6.5《线程调度》