Windows內核安全之 線程調度

線程一個比較重要的概念是, CPU中永遠調度的是線程, 而不是進程, 而進程的切換完全是源於是否同一個CR3寄存器, 詳見SwapContext的實現

以下先列出KTHREAD對象
內核中對線程優先級(priority) 分別使用0~31表示
實時(Real-time)類別: 16~31
動態(Dynamic)類別: 1~15
系統(System)類別: 0

線程在內核的執行體層(Executable Layer)中 使用以下6種優先級
實時(Realtime)
高(High)
普通之上(Above normal)
普通(normal)
普通之下(Below normal)
低(Low)

執行體層透過一個數組PspPriorityTable 轉換成真正的表示 以下是他們的對應關係
實時(Realtime) 24
高(High) 13
普通之上(Above normal) 10
普通(normal) 8
普通之下(Below normal) 6
低(Low) 4



進程的對象EPROCESS結構中 BasePriority 指定一個進程中所有線程的預設優先級

可以通過KeSetPriorityAndQuantumProcess 或 KeSetBasePriorityThread 函數設置優先級

KTHREAD中的Priority域記錄一個線程當前實際優先級, 他一般是在BasePriority基礎上提升到某個增量

Priority不會超過0~15

內核通過調用KiComputeNewPriority計算並調整非實時的線程優先級

我們可以使用NtSetInformationProcess為進程的基礎優先級進行微調, 所以一條線程在執行體中的值並非數組中指定的值


優先級的提升:
-------------
由於每個線程優先級都有對應的鏈表維護著相同優先級的線程 方便調度
所以優先級的提升, 一定是在加入鏈表之前

內核中不小函數的參數使用KPRIORITY Increment進行提升
如:
KeInsertQueueApc
KePulseEvent
KeSetEvent
KeReleaseMutant
KeReleaseSemaphore
KeSetProcess
KeBoostPriorityThread
KeTerminateThread

線程狀態轉移:
--------------
KTHREAD中有一個成員State 是一個反映線程當前調度狀態的一個標誌
其結構如下:

typedef enum _KTHREAD_STATE{
  Initialized,    //初始化狀態, 說明一個線程內部狀態已被初始化,但尚未加到進程的線程鏈表,也沒有啟動
  Ready,          //就緒狀態,及等待被調度運行, 當線程調度器調度線程時,只考慮處於Ready狀態的線程,已加到某個CPU中的Ready線程鏈表
  Running,        //運行狀態, 線程正在運行, 他一直占有某個CPU, 直到時限或被更高優先級的線程搶占,或者主動放棄CPU/線程中止,或被掛起進入等待
  StandBy,        //備用線程, 每個CPU核心只能夠有一個備用線程,
  Terminated,     //結束狀態, 表示線程已結束,正等待回收
  Waiting,        //等待狀態,等到某條件,觸發線程立即運行或回到就緒狀態
  Transition,     //轉移狀態,已準備好運行, 但它的內核棧不在內存中,一旦它的內核棧被載入內存, 立即進入就緒狀態
  DeferredReady,  //延遲就緒狀態,還沒加到某個CPU中的Ready線程鏈表, 因而還沒能夠被調度, 等待有機會加入到某個核心中的Ready線程鏈表
  GateWait        //門等待狀態, 與等待狀態類似,不過觸發條件為門對象(Gate Object)
}KTHREAD_STATE;

一個線程會否被調度, 有一個十分重要的函數: KiReadyThread, 他是一個線程生命中的轉折點, 經過調用它後, 線程就會進入備用狀態,或就緒狀態
以下幾個為KiReadyThread調用的路徑:
1. 當一個線程被解除等待(即條件滿足時)
2. 內核隊列對象(KQUEUE)中有新的成員插入, 並且滿足條件時,也會使其隊列中等待線程被調用KiReadyThread函數
3. 線程被附載到一個新進程中, 如果目標進程在內存中, 則目標進程的就緒鏈表中的線程,被調用KiReadyThread函數
4. KeSetEventBoostPriority函數中
5. 處理換入進程鏈表時KiInSwapProcess函數會針對每個已換入進程中的就緒線程調用KiReadyThread.
6. 換出進程鏈表時KiOutSwapProcess
7. PspCreateThread創建線程時

延遲等待線程如何被執行:
----------------------------
一個延遲等待狀態的線程被一個鏈表(KiInsertDeferredReadyList)維護, 在KiReadyThread時加入
以後有機會當調度器有控制權時, 就會被逐個處理(KiProcessDeferredReadyList)遍歷所有延遲就緒線程
對每個線程調用KiDeferredReadyThread函數, 使他們有機會變成 就緒 或 備用狀態

KiDeferredReadyThread主要實現:
-------------------------------
1. 判斷各種情況調整處理線程的優先級
2. 選擇CPU某一核心
3. 如果可以找到一個空閒的cpu,滿足線程親和性(指定CPU號)要求就可以設置為備用狀態, 就會在該CPU下一次調度時執行 ->返回
4. 否則, 試圖搶占這個cpu的控制權, 如果確實能夠搶占(優先級比備用線程高),則搶占,讓被搶占線程回復延遲等待狀態
5. 新的線程則會為該CPU上成為下一個執行的線程 ->返回
6. 如果CPU下一個要執行的線程還沒有選出(即以上條件都不符合), 則嘗試搶占CPU當前線程, 如能搶占(優先級比當前線程高),則搶占
7. 如以上步驟都不能, 搶占,則把線程設置為就緒狀態, 並且將其線程插入到 對應親和性的CPU中的就緒鏈表中

一個就緒狀態或備用狀態的線程 如何被執行:
-----------------------------------
每個處理器在內核中有一個結構體維護(KPRCB)
結構如下:

typedef struct _KPRCB
{
     WORD MinorVersion;
     WORD MajorVersion;
     PKTHREAD CurrentThread;   //當前線程(運行狀態)
     PKTHREAD NextThread;      //下一個會被執行的線程(備用狀態)
     PKTHREAD IdleThread;      //空閒線程(完成初始化後)
     UCHAR Number;
     UCHAR NestingLevel;
     WORD BuildType;
     ULONG SetMember;
     CHAR CpuType;
     CHAR CpuID;
     union
     {
          WORD CpuStep;
          struct
          {
               UCHAR CpuStepping;
               UCHAR CpuModel;
          };
     };
     KPROCESSOR_STATE ProcessorState;
     ULONG KernelReserved[16];
     ULONG HalReserved[16];
     ULONG CFlushSize;
     UCHAR PrcbPad0[88];
     KSPIN_LOCK_QUEUE LockQueue[33];
     PKTHREAD NpxThread;
     ULONG InterruptCount;
     ULONG KernelTime;
     ULONG UserTime;
     ULONG DpcTime;
     ULONG DpcTimeCount;
     ULONG InterruptTime;
     ULONG AdjustDpcThreshold;
     ULONG PageColor;
     UCHAR SkipTick;
     UCHAR DebuggerSavedIRQL;
     UCHAR NodeColor;
     UCHAR PollSlot;
     ULONG NodeShiftedColor;
     PKNODE ParentNode;
     ULONG MultiThreadProcessorSet;
     PKPRCB MultiThreadSetMaster;
     ULONG SecondaryColorMask;
     ULONG DpcTimeLimit;
     ULONG CcFastReadNoWait;
     ULONG CcFastReadWait;
     ULONG CcFastReadNotPossible;
     ULONG CcCopyReadNoWait;
     ULONG CcCopyReadWait;
     ULONG CcCopyReadNoWaitMiss;
     LONG MmSpinLockOrdering;
     LONG IoReadOperationCount;
     LONG IoWriteOperationCount;
     LONG IoOtherOperationCount;
     LARGE_INTEGER IoReadTransferCount;
     LARGE_INTEGER IoWriteTransferCount;
     LARGE_INTEGER IoOtherTransferCount;
     ULONG CcFastMdlReadNoWait;
     ULONG CcFastMdlReadWait;
     ULONG CcFastMdlReadNotPossible;
     ULONG CcMapDataNoWait;
     ULONG CcMapDataWait;
     ULONG CcPinMappedDataCount;
     ULONG CcPinReadNoWait;
     ULONG CcPinReadWait;
     ULONG CcMdlReadNoWait;
     ULONG CcMdlReadWait;
     ULONG CcLazyWriteHotSpots;
     ULONG CcLazyWriteIos;
     ULONG CcLazyWritePages;
     ULONG CcDataFlushes;
     ULONG CcDataPages;
     ULONG CcLostDelayedWrites;
     ULONG CcFastReadResourceMiss;
     ULONG CcCopyReadWaitMiss;
     ULONG CcFastMdlReadResourceMiss;
     ULONG CcMapDataNoWaitMiss;
     ULONG CcMapDataWaitMiss;
     ULONG CcPinReadNoWaitMiss;
     ULONG CcPinReadWaitMiss;
     ULONG CcMdlReadNoWaitMiss;
     ULONG CcMdlReadWaitMiss;
     ULONG CcReadAheadIos;
     ULONG KeAlignmentFixupCount;
     ULONG KeExceptionDispatchCount;
     ULONG KeSystemCalls;
     ULONG PrcbPad1[3];
     PP_LOOKASIDE_LIST PPLookasideList[16];
     GENERAL_LOOKASIDE_POOL PPNPagedLookasideList[32];
     GENERAL_LOOKASIDE_POOL PPPagedLookasideList[32];
     ULONG PacketBarrier;
     LONG ReverseStall;
     PVOID IpiFrame;
     UCHAR PrcbPad2[52];
     VOID * CurrentPacket[3];
     ULONG TargetSet;
     PVOID WorkerRoutine;
     ULONG IpiFrozen;
     UCHAR PrcbPad3[40];
     ULONG RequestSummary;
     PKPRCB SignalDone;
     UCHAR PrcbPad4[56];
     KDPC_DATA DpcData[2];
     PVOID DpcStack;
     LONG MaximumDpcQueueDepth;
     ULONG DpcRequestRate;
     ULONG MinimumDpcRate;
     UCHAR DpcInterruptRequested;
     UCHAR DpcThreadRequested;
     UCHAR DpcRoutineActive;
     UCHAR DpcThreadActive;
     ULONG PrcbLock;
     ULONG DpcLastCount;
     ULONG TimerHand;
     ULONG TimerRequest;
     PVOID PrcbPad41;
     KEVENT DpcEvent;
     UCHAR ThreadDpcEnable;
     UCHAR QuantumEnd;
     UCHAR PrcbPad50;
     UCHAR IdleSchedule;
     LONG DpcSetEventRequest;
     LONG Sleeping;
     ULONG PeriodicCount;
     ULONG PeriodicBias;
     UCHAR PrcbPad5[6];
     LONG TickOffset;
     KDPC CallDpc;
     LONG ClockKeepAlive;
     UCHAR ClockCheckSlot;
     UCHAR ClockPollCycle;
     UCHAR PrcbPad6[2];
     LONG DpcWatchdogPeriod;
     LONG DpcWatchdogCount;
     LONG ThreadWatchdogPeriod;
     LONG ThreadWatchdogCount;
     ULONG PrcbPad70[2];
     LIST_ENTRY WaitListHead;
     ULONG WaitLock;
     ULONG ReadySummary;                      //記錄DispatcherReadyListHead中哪些優先級的鏈表為非NULL
     ULONG QueueIndex;
     SINGLE_LIST_ENTRY DeferredReadyListHead; //維護所有延遲就緒狀態的線程
     UINT64 StartCycles;
     UINT64 CycleTime;
     UINT64 PrcbPad71[3];
     LIST_ENTRY DispatcherReadyListHead[32]; //維護所有就緒線程, 就緒線程的index為該優先級
     PVOID ChainedInterruptList;
     LONG LookasideIrpFloat;
     LONG MmPageFaultCount;
     LONG MmCopyOnWriteCount;
     LONG MmTransitionCount;
     LONG MmCacheTransitionCount;
     LONG MmDemandZeroCount;
     LONG MmPageReadCount;
     LONG MmPageReadIoCount;
     LONG MmCacheReadCount;
     LONG MmCacheIoCount;
     LONG MmDirtyPagesWriteCount;
     LONG MmDirtyWriteIoCount;
     LONG MmMappedPagesWriteCount;
     LONG MmMappedWriteIoCount;
     ULONG CachedCommit;
     ULONG CachedResidentAvailable;
     PVOID HyperPte;
     UCHAR CpuVendor;
     UCHAR PrcbPad9[3];
     UCHAR VendorString[13];
     UCHAR InitialApicId;
     UCHAR CoresPerPhysicalProcessor;
     UCHAR LogicalProcessorsPerPhysicalProcessor;
     ULONG MHz;
     ULONG FeatureBits;
     LARGE_INTEGER UpdateSignature;
     UINT64 IsrTime;
     UINT64 SpareField1;
     FX_SAVE_AREA NpxSaveArea;
     PROCESSOR_POWER_STATE PowerState;
     KDPC DpcWatchdogDpc;
     KTIMER DpcWatchdogTimer;
     PVOID WheaInfo;
     PVOID EtwSupport;
     SLIST_HEADER InterruptObjectPool;
     LARGE_INTEGER HypercallPagePhysical;
     PVOID HypercallPageVirtual;
     PVOID RateControl;
     CACHE_DESCRIPTOR Cache[5];
     ULONG CacheCount;
     ULONG CacheProcessorMask[5];
     UCHAR LogicalProcessorsPerCore;
     UCHAR PrcbPad8[3];
     ULONG PackageProcessorSet;
     ULONG CoreProcessorSet;
} KPRCB, *PKPRCB;

以上提出一個鏈表DeferredReadyListHead,一個數組DispatcherReadyListHead
他們分別指定cpu中的延遲就緒線程鏈表 及 就緒鏈表

內核中使用KiSelectReadyThread 及 KiFindReadyThread 把他們轉移到NextThread/ CurrentThread

KiSelectReadyThread: 返回某一優先級之上,最優先的線程
KiFindReadyThread: 遍歷指定KPRCB的鏈表數組, 從最高優先級開始直到找到第一個可以在該處理器運行的線程

由此可見, 系統的線程調度器並不是以單一函數存在, 而是分工到不同的函數之中


調度點:
-----------------------------
- KiSwapThread函數, 先判斷是否有NextThread或調用KiSelectReadyThread及KiFindReadyThread尋找合適的線程,( 一個例外情況, 當如果找到的新線程不是當前CPU的空閒線程,也不是當前線程,並且新線程正在被切換口, 則將新找到的線程設置成當前處理器的備用線程, 而把空閒線程設置成當前線程,從而讓空閒線程負責切換到新線程,這樣做可以避免死鎖)
- 當前時限已夠, 發生在KiQuantumEnd中
- 線程主動放棄執行權, 發生在NtYieldExecution中
- 除了以上調度點, 還有我們更改線程優先級,親和性等的信息時, 而線程原來的狀態是 就緒/備用/運行, 而因我們的修改令到線程狀態改變的話, 他會回到延遲就緒狀態, 因而讓線程的影響減到最低

等待狀態:
----------------------------
當一個線程執行到KeDelayExecution , KeWaitForSingleObject, KeWaitForMultipleObject就有機會進入等待狀態

時限管理:
----------------------------
如果一個線程在它的執行過程中, 在運行狀態時(假設沒有進入等待或被搶占), 他會有一個時限(quantum)當時限結束時, 線程調度器會介入, 按照公平性原則, 接下來的時限會分配給同等優先級或者更高的線程

每個線程對象KTHREAD都有兩個域 跟時限有關 Quantum記錄線程當前時限剩下多少時間
QuantumReset記錄線程的時限重置值 即完整時限的時間單位, 它來自進程對象 客戶系統為6 , 服務器系統為36

每一次的時鐘中斷發生時, 這個Quantum會減去3 , 直到減至 <= 0 就會觸發線程調度 Windows優先級調度算法總結: 1. 系統維護了一個數組,KiProcessBlock,其中每個元素指向一個cpu核心的KPRCB對象 2. 其次有一個全局KiIdleSummary 記錄了哪個CPU空閒, 意指正在執行空閒循環 3. 當一個cpu沒有找到合適的線程運行時, 會調用KiSetIdleSummary設置KiIdleSummary 4. 如果一個空閒CPU被分配到一個線程,則需要通過調用KiClearIdleSummary函數來清除KiIdleSummary中相應的位 當一個空閒cpu被分配延遲就緒的線程時,就會有這個動作 5. KiSwapThread函數中找到了接下來需要運行的線程,也會調用 6. 每個處理器結構KPRCB中, 都有一個單鏈表DeferredReadyListHead保存CPU有多少個線程在 延遲就緒狀態 7. 雙鏈表數組DispatcherReadyListHead 表示每一個優先級上 已經被分配到此cpu的就緒狀態的線程 8. 32位的ReadySummary反映了哪些優先級的就緒鏈表是非空的 9. KiSelectReadyThread和KiFindReadyThread利用鏈表數組,和ReadySummary能很快地找到滿足條件的線程 這實際上也是windows線程 優先級調度算法的核心 , 不同優先級的線程加到不同鏈表中, 調度器在選擇待執行的線程時, 高優先級的線程鏈表也會首先被掃描, 這是提升不小速度.. 以下提出一張全視圖



接下來要討論的是哪些線程需要切換, 什麼時侯切換, 和如何切換:
---------------------------------------------------
1: 線程主動放棄執行權, 那當前CPU的控制流就會轉移到線程調度器(dispatcher), 比如進入了等待狀態,而條件不能滿足
2: 被逼放棄執行權, 比如時限片已經用完

前者線程則會調用KiSwapThread, 後者發生中斷到了KiDispatchInterrupt,後來會調用KiSwapContext, 以後會有文章詳細解說KiSwapContext , 它的實現比較緊要, 他的可是 進程, 虛擬內存, 線程之間切換的一個必要函數, 沒了他 整個操作系統都沒法切換進程,線程了