Windows: Dispatching and Scheduling (a short explanation)

Last week a student asked about the correct difference between Dispatching and Scheduling on Windows systems. Of course, this a long topic to talk and write, mainly when the time is very tight, but I will try to summarize the topic below.

Fundamentally, Dispatching is the the process (or action) of switching from a thread executing to another one, while Scheduling is the action of determining the next thread to be executed on the processor. Additionally, there are typical and main states for a thread such as Wait (blocked, waiting any related event occurs), Running (thread is active and running on CPU) and Ready (thread is eligible to run, but it needs to receive an authorization from OS for doing it). A thread can be in Waiting status because a system call (such as an execution of KeWaitSingleObject() by a device driver) and its state is controlled by KTHREAD structure (which is embedded inside the ETHREAD structure and holds information about thread stack, system calls, scheduling, priorities, and so on). A thread can be also in Running status that is determined by KPCR (Kernel Processor Control Region) structure (it can be accessed by functions such as KsGetCurrentThread() and PsGetCurrentProcess()) that holds information about the CPU (if the system has many CPUs, so there’re many KPCRs and each one holds CPU information that is shared by HAL and kernel). During a dispatching, the kernel saves the entire context from the current thread then it executes either the KiSwapThread() or KiSwitchToThread() for loading the context from the new thread.

How does the kernel choose the next thread to be activated and run? It uses the Scheduling feature to pick the next thread to run based on its priority given by Priority field (it can be changed by KeSetPriorityThread(), for example) from KPROCESS structure and respects the BasePriority attribute (the value can changed by using the KeSetBasePriorityThread()) that is the minimum value of Priority attribute. About priorities, there are two valid ranges such as “Dynamic Priority” (from 1 to 15) and “Real Time” (from 16 to 31), where the OS varies the thread’s priority of the former range, but it doesn’t vary the thread’s priority from the latter one. Therefore, real time thread can cause CPU starvation.

The Dynamic Priority value can be changed by operating system when events such as quantum exhaustion (the thread used its time slice), not running (not running threads gain a priority boots for having a chance to run), I/O completion (a driver has finished its I/O job and the current related thread needs of a chance to return to CPU) and KeSetEvent function that helps by bursting the the current thread’s priority to run on CPU.

Changing to a practical approach, examine the colors of the following WinDbg’s output:

lkd> !thread

THREAD fffff80002e58cc0 Cid 0000.0000 Teb: 0000000000000000 Win32Thread: 0000000000000000 RUNNING on processor 0
Not impersonating
DeviceMap fffff8a000008aa0
Owning Process fffff80002e59180 Image: Idle
Attached Process fffffa800a2e6b10 Image: System
Wait Start TickCount 430911 Ticks: 9 (0:00:00:00.140)
Context Switch Count 8568683
UserTime 00:00:00.000
KernelTime 01:45:09.008
Win32 Start Address nt!KiIdleLoop (0xfffff80002cc3570)
Stack Init fffff8000410adb0 Current fffff8000410ad40
Base fffff8000410b000 Limit fffff80004105000 Call 0
Priority 16 BasePriority 0 UnusualBoost 0 ForegroundBoost 0 IoPriority 0 PagePriority 0
Unable to get context for thread running on processor 0, HRESULT 0x80004001

lkd> !pcr

KPCR for Processor 0 at fffff80002e4ad00:

Major 1 Minor 1

    NtTib.ExceptionList: fffff80004103000
     NtTib.StackBase: fffff80004104080
     NtTib.StackLimit: 000000000020e448
     NtTib.SubSystemTib: fffff80002e4ad00
     NtTib.Version: 0000000002e4ae80
     NtTib.UserPointer: fffff80002e4b4f0
     NtTib.SelfTib: 000007fffff82000
     SelfPcr: 0000000000000000
     Prcb: fffff80002e4ae80
     Irql: 0000000000000000
     IRR: 0000000000000000
     IDR: 0000000000000000
     InterruptMode: 0000000000000000
     IDT: 0000000000000000
     GDT: 0000000000000000
     TSS: 0000000000000000
     CurrentThread: fffff80002e58cc0
     NextThread: 0000000000000000
     IdleThread: fffff80002e58cc0

lkd> !ready

Processor 0: No threads in READY state
Processor 1: No threads in READY state
Processor 2: No threads in READY state
Processor 3: No threads in READY state
Processor 4: No threads in READY state
Processor 5: No threads in READY state
Processor 6: No threads in READY state
Processor 7: No threads in READY state

My system is completely idle, but you are able to realize the Current Thread, NextThread (none) and the IdleThread values from the output above. Unfortunately, the WinDbg shows the partial contents of the PCR by using !pcr command.

I know that’s a basic explanation (without digging into excessive details) , but it can helps when you are studying and leaning the internal structures of Windows.

Have a nice day.

Alexandre Borges


Leave a Comment

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s