windows进程与线程学习——调度实现的学习

来学习一下 Windows 线程调度的实现

Windows中有一个函数SwapContext用来实现线程切换，我们先得了解一下什么情况下会引发线程切换。

线程切换途径

分主动切换和被动切换，很好理解，主动切换就是线程主动让出 CPU 执行，被动就是被打断而不得不让出 CPU。

在做实验的时候，多核真的是很困扰的一个问题，想了半天想不明白多核怎么工作的，为了好理解线程切换，建议虚拟机都换成单核的，线程大多数时候是主动切换的。

ida 找到 KeWaitForSingleObject 函数，交叉引用

可以看到大量的 API 都有调用这个函数，而该函数必定会引发线程的切换。

调用链如下：

KeWaitForSingleObject->KiSwapThread->KiSwapContext->SwapContext

所以只要线程调用了相关的一些 api，那么就会主动让出 CPU。

考虑这样一个情况：线程从不主动让出 CPU，而是死循环执行简单的指令，那么谁来打断它呢，此时 CPU 已经被线程独占了。之前有学过 CPU 中断执行的方法，一种是中断，一种是异常。异常是 CPU 主动触发的，所以能打断的方法似乎只有中断了。

绝大部分系统内核函数都会调用SwapContext函数，来实现线程的切换，那么这种切换是线程主动调用的。那如果当前的线程不去调用系统API，操作系统如何实现线程切换呢?那就靠时钟中断了，这个是被动切换。

我们可以通过中断和异常来实现中断一个正在执行的程序。其中，时钟中断也是一种中断，中断号0x30，Windows系列操作系统为10-20毫秒。如下示意图就是对时钟中断执行时的流程示意图以供了解：

也就是说，即使你试图独占 CPU，那么再占用最多 20ms 后也会被迫交还 CPU 的控制权，除非屏蔽了中断。

时钟中断会导致线程进行切换，但并不是说只要有时钟中断就一定会切换线程，时钟中断时，如下两种情况会导致线程切换：

加上线程主动调用 api 切换线程，Windows 总共就有三种切换线程的方式。

任务段寄存器，作为 Intel 被设计用于线程切换的结构，虽然 Intel 提供的线程切换方式没有被使用，但是实际操作系统切换的时候还是使用到了这个结构。

在 R0，它指向了 KPCR 结构，在 R3，它指向了 TEB。

线程优先级 0~31，其中 0~15 是用户线程可以达到的级别 16~31 是内核线程可以达到的级别。

调度会按照优先级来判断，但是每次都判断链表表头是否为空太浪费时间，因此，当一个优先级的链表中不存在线程，那就把一个变量的对应位赋值为 0，这个变量是 KPCR.PrcbData.ReadySummary。

在 windbg 当中，因为中断挂起了所有线程，所以调度链表中没有线程，该值为 0。

假设 ReadySummary=11，那么说明优先级为 0 1 3 的调度链表中存在线程，其余不存在，那么就可以快速地先调度优先级为 3 的线程而不用每次都从最高优先级的链表开始一个一个找到底有没有线程。

对于一个这样的 bitmap，是有算法可以快速找到这个最高优先级的线程的。

下面是我自己想的一些方法：

二分法：对于这样的数据，先判断是否大于等于 32768，如果是，那么最高优先级的非空调度链表至少为 15，否则低于15，同理可得做四次运算即可获得该值。
算术法：因为打过 acm，对一个算法有印象，就是获取最低有效位，int lowbit(x){return x&(-x)}，所以我想获取最高有效位应该也有一个合适的算法，只是我目前不知道，也没有去考究。

说这个是担心想到了我最开始的想法——按从大到小的顺序判断找到第一个满足 ((1<<i)&ReadySummary)!=0 的链表下标。事实上就算这样，它依然比一个一个搜链表快。因为这样循环 32 次，值都可以在寄存器计算得到，而搜链表则需要最多 32 次的访存。

在多 CPU 的系统中，可以指定线程绑定某个 CPU 执行，使用 API：SetThreadAffinityMask，Affinity 在介绍 ETHREAD 结构时讲解过这个字段。

如果没有就绪线程，CPU也不会闲下来，它会执行一个空线程即为IdleThread，在 KPCR 中可以找到这个成员。