前言
Windows 線程調度器的實現分散在內核各處，并且與許多組件都有關聯，很難進行系統地學習，所以我打算寫幾篇文章來記錄下自己學習過程中的思考和分析，同時也方便日后查閱，此文可以看作是《Windows內核原理與實現》中線程調度部分的讀書筆記和簡單總結。
正文
一. 線程當前狀態
在對調度器函數進行分析學習之前，首先要明確一個概念：調度器只由內核層進行負責實現，不涉及執行體層。因此線程相關的數據結構只有 KTHREAD，其中調度相關的最重要的成員是 State，它標識了線程的當前狀態，取值由名為 KTHREAD_STATE 的枚舉類型定義：
typedef enum _KTHREAD_STATE {Initialized,Ready,Running,Standby,Terminated,Waiting,Transition,DeferredReady,GateWait
} KTHREAD_STATE;已初始化 (Initialized)：線程創建過程中的內部狀態，此時線程不參與調度。
就緒 (Ready)：線程已經準備好運行，等待被調度。
運行中 (Running)：線程正在某一處理器上運行。
待命 (Standby)：線程被選為某一處理器上下一個將要被執行的線程。
已終止 (Terminated)：線程已終止，正在進行資源回收。
等待中 (Waiting)：線程正在等待某個條件滿足，比如事件對象被觸發。
轉移 (Transition)：線程已經準備好運行但內核棧不在內存中。
延遲就緒 (DeferredReady)：線程尚未被確定在哪個處理器上運行，此狀態對于單處理器系統沒有意義。
門等待 (GateWait)：線程正在等待一個門對象。
其中就緒和延遲就緒狀態的主要區別是：延遲就緒線程尚未確定被分配到哪個處理器上運行，而就緒線程已經被分配到了某個處理器上。
對于線程各個狀態間的轉移規則，可以參考線程狀態轉移圖（引自潘愛民老師的《Windows內核原理與實現》）：
二. 進程的當前狀態
進程在內核層所對應的 KPROCESS 結構中，也有一個用來標識當前狀態的 State 成員，它的取值由名為 KPROCESS_STATE 的枚舉類型定義：
typedef enum _KPROCESS_STATE {ProcessInMemory,ProcessOutOfMemory,ProcessInTransition,ProcessOutTransition,ProcessInSwap,ProcessOutSwap
} KPROCESS_STATE;ProcessInMemory：表示進程的虛擬地址空間內容在物理內存中。
ProcessOutOfMemory：表示進程的虛擬地址空間內容已被換出物理內存。
ProcessInTransition：表示進程的虛擬地址空間內容不在物理內存中，但已請求換入。
ProcessOutTransition：表示進程的虛擬地址空間內容存在于物理內存中，但已請求換出。
ProcessInSwap：表示正在將進程的虛擬地址空間內容換入物理內存，換入完成后，狀態將變更為 ProcessInMemory。
ProcessOutSwap：表示正在將進程的虛擬地址空間內容換出物理內存，換出完成后，狀態將變更為 ProcessOutOfMemory。
換入或換出進程的虛擬地址空間會導致進程狀態的切換，此工作是由名為 平衡集管理器 (Balance Set Manager) 的內核組件負責的，在內核第一階段初始化接近結束時，MmInitSystem 函數創建了兩個平衡集管理器線程，其對應例程分別是 KeBalanceSetManager 和 KeSwapProcessOrStack 函數。
KeBalanceSetManager 線程循環等待一個每秒觸發一次的定時器對象和一個工作集管理器事件對象，當等待成功后，它觸發名為 KiSwapEvent 的事件對象來通知交換線程，以嘗試對滿足條件的線程的內核棧執行換出操作。KeSwapProcessOrStack 即為交換線程，它循環等待上述的 KiSwapEvent 對象，一旦等待成功，會根據情況執行進程和線程內核棧的換入換出工作。
一個進程的換出操作發生在進程的 StackCount 為 0 時，StackCount 記錄了該進程中有多少個線程的內核棧位于內存中，當該進程的所有線程的內核棧都被換出內存時，KiOutSwapKernelStacks 會將進程插入到待換出鏈表中，并觸發 KiSwapEvent 對象，交換線程會在下次循環中調用 KiOutSwapProcesses 函數將該進程換出內存。
平衡集管理器實質上是內存管理器組件，有關它更多更詳細的內容將在之后的文章中更新。
三. 調度器主要函數實現
1. KiReadyThread：
KiReadyThread 從名字上來看是將一個線程轉為就緒狀態，而實際上這個函數根據三種不同情況來進行處理：
void __fastcall KiReadyThread(IN PKTHREAD Thread) {PKPROCESS Process;Process = Thread->ApcState.Process;if (Process->State != ProcessInMemory) {Thread->State = Ready;Thread->ProcessReadyQueue = TRUE;InsertTailList(&Process->ReadyListHead, &Thread->WaitListEntry);if (Process->State == ProcessOutOfMemory) {Process->State = ProcessInTransition;InterlockedPushEntrySingleList(&KiProcessInSwapListHead, &Process->SwapListEntry);KiSetInternalEvent(&KiSwapEvent, KiSwappingThread);}return;} else if (Thread->KernelStackResident == FALSE) {ASSERT(Process->StackCount != MAXULONG_PTR);Process->StackCount += 1;ASSERT(Thread->State != Transition);Thread->State = Transition;InterlockedPushEntrySingleList(&KiStackInSwapListHead, &Thread->SwapListEntry);KiSetInternalEvent(&KiSwapEvent, KiSwappingThread);return;} else {KiInsertDeferredReadyList(Thread);return;}
}分支一：
首先，此函數根據上文提到的 KPROCESS 的 State 成員，來判斷目標線程所屬進程當前是否處于 ProcessInMemory 狀態，即進程虛擬地址空間是否在物理內存中，若不是則將目標線程設置為就緒狀態，并將線程的 ProcessReadyQueue 標志設置為 TRUE，然后將線程插入到所屬進程的就緒鏈表 (ReadyListHead) 中，ProcessReadyQueue 用來標識線程是否在其所屬進程的就緒鏈表中。而后進一步判斷進程是否處于 ProcessOutOfMemory 狀態，若是則將該進程設置為 ProcessInTransition 狀態，并插入到待換入進程鏈表中，最后觸發 KiSwapEvent 對象通知交換線程執行進程換入操作。由此可以看出，ProcessInTransition 是一種中間狀態，他標識了進程將要但還沒有被執行換入操作，此狀態介于 ProcessInMemory 和 ProcessInSwap 之間。
當進程當前處于 ProcessOutOfMemory 狀態時，其后續操作是：平衡集管理器的交換線程成功等待到 KiSwapEvent，進而調用 KiInSwapProcesses 函數將之前插入到待換入進程鏈表中的進程換入內存（通過 MmInSwapProcess 函數），之后將進程狀態修改為 ProcessInMemory。此時進程虛擬地址空間已在物理內存中，可以對進程中所有的就緒線程進行調度，所以 KiInSwapProcesses 函數遍歷該進程的就緒鏈表，對其中的所有線程再次調用 KiReadyThread，而后將線程從鏈表中移除。由于這一次進程已存在于內存中，所以此次 KiReadyThread 函數不會再執行到此分支。
而對于 ProcessInTransition 和 ProcessInSwap 這兩種狀態，則不需要通知交換線程將進程換入內存，因為此時交換線程已經或將要執行 KiInSwapProcesses 函數，如上所述，此函數會在將進程換入內存后，對該進程就緒鏈表中的所有線程再次調用 KiReadyThread。
最后，若進程處于 ProcessOutTransition 或 ProcessOutSwap 狀態（進程因其所有線程的內核棧都被換出內存而導致自身也被換出內存，在換出的過程中，如果有屬于該進程的新線程被創建，或某一現有線程掛靠到該進程上，則 KiReadyThread 被調用，此時進程可能處于這兩種狀態），那么剩下的工作將由交換線程通過調用 KiOutSwapProcesses 函數來完成，此函數負責將待換出進程鏈表中的進程換出內存，它在兩個階段分別檢查待換出進程的就緒鏈表：若進程尚未換出內存，則取消換出操作并將進程狀態修改為 ProcessInMemory，然后對該進程就緒鏈表中的所有線程再次調用 KiReadyThread；若進程已換出內存，則修改進程狀態為 ProcessInTransition 并觸發 KiSwapEvent 對象，交換線程會在下次循環中調用 KiInSwapProcesses 執行后續操作。
綜上所述，只有當進程處于 ProcessOutOfMemory 狀態時，此函數才通知交換線程將進程換入內存，其余情況平衡集管理器會進行判斷和處理，而無論哪種一情況，進程最后都會變為 ProcessInMemory 狀態，進而交由其他分支處理，所謂異途同歸。
分支二：
如果進程當前處于 ProcessInMemory 狀態（經分支一處理后，進程必然處于此狀態），則繼續判斷目標線程的內核棧是否在物理內存中（由 KernelStackResident 標志指示）。上文提到，線程棧的換入和換出操作也是由平衡集管理器負責的，當一個線程處于等待狀態超過一定時間之后，交換線程調用 KiOutSwapKernelStacks 函數將其內核棧換出物理內存。因此若線程的內核棧已被換出物理內存，則要先通知交換線程將內核棧其換入內存，交換線程通過調用 KiInSwapKernelStacks 函數將線程內核棧換入物理內存，而后直接調用 KiInsertDeferredReadyList 函數將線程插入到延遲就緒鏈表中，關于 KiInsertDeferredReadyList 函數，見分支三。
另外上文還提到，進程 KPROCESS 對象中的 StackCount 成員記錄了該進程中有多少個線程的內核棧位于內存中，對于一個將要被換入內存的線程，自然要將其所屬進程的 StackCount 加一（由于線程終止或掛靠到其他進程時也會引起 StackCount 的變動，所以此成員不由平衡集管理器維護）。
分支三：
進入到分支三就表示線程已滿足執行條件（內核棧和所屬進程都已在物理內存中），因此調用 KiInsertDeferredReadyList 函數執行下一步操作：
PKPRCB Prcb;
Prcb = KeGetCurrentPrcb();
Thread->State = DeferredReady;
Thread->DeferredProcessor = Prcb->Number;
PushEntryList(&Prcb->DeferredReadyListHead, &Thread->SwapListEntry);此函數邏輯十分簡單，所做的僅僅是將線程設置為延遲就緒狀態，并將其插入到當前處理器 PRCB 結構中的延遲就緒鏈表中，以后當調度器獲得控制權時，KiProcessDeferredReadyList 函數將遍歷此鏈表，并對每個線程調用 KiDeferredReadyThread 函數，使其有機會變為就緒或待命狀態。注：此處所說的就緒狀態是真正的就緒，區別于上文所說進程就緒鏈表中的線程，后者不滿足執行條件（需要等待其所屬進程被換入內存）。
至此 KiReadyThread 函數已分析完畢，可以看出，經過此函數處理后的任何線程都會變為延遲就緒狀態，這對線程來說是一個重要轉折點，意味著它將有機會獲得執行權，而在此之前，該線程不會被考慮執行。
![[SceneKit專題]11-Reference-Nodes引用節點](http://pic.xiahunao.cn/[SceneKit專題]11-Reference-Nodes引用節點)
