Does Windows have a "Scheduler"


The question came up on the NTDEV mailing list a while back about how the “Scheduler” works in Windows … specifically about what thread it ran on and how it got control.


   


The answer is that you should ignore this idea that there’s a “scheduler” as an independent entity.  It doesn’t exist like that in Windows.


   


In windows there are basically two functions for scheduling in the dispatcher.  The first selects the most appropriate thread to run on a processor at any given time based on a number of factors such as thread priority, thread affinity, ideal processor, etc… .  The second initiates a context switch between the current thread and the new one.


   


The Ke subsystem implements these functions and uses them to schedule threads in a distributed manner.  Basically any time a Ke function is called which changes the state of a thread (to block it, to wake it up, to change its priority, to mark it as having exceeded a quantum) that function will invoke these two other functions to see if a different thread should be running and, if so, to swap over to it.


   


So you’ve got some user-mode code on a processor.  That code will continue to run until it:


   



  • Calls WaitForSingleObject, which calls the NtWaitForSingleObject system call which transitions to kernel mode and (eventually) calls KeWaitForSingleObject.  KeWaitForSingleObject links the current thread onto the wait list for the object (say an event) then selects another thread which could be run and does a context switch

   




  • Gets a page fault.  This triggers the kernel trap handler, which calls the memory manager which will initiate a page-in then calls KeWaitForSingleObject to block the thread until the I/O completes.  KeWaitForSingleObject will select a new thread to run and switch to it.

       


  • Is interrupted by a timer interrupt.  The kernel’s timer interrupt handler will see if the current thread has run longer than its quota and, if so, will attempt to select a new thread to run.  If the current thread is the highest priority thread in the system then it will be left on the processor.  Otherwise the kernel code will get select a new one and switch to it.

   



  • Is interrupted by a device interrupt which completes an I/O request initiated by another process.  Often this involves boosting the priority of the other process by calling a Ke function.  This function sets the new priority, then calls the selection function to see what process should be running on the processor.  If there’s a better candidate after the priority boost then Ke will swap to the new thread

   


There are a number of other conditions which can cause a context switch, and I’ve dramatically oversimplified some of them, but hopefully this will help you get the idea.  The responsibility for scheduling in NT is distributed across all threads in the system, which eventually end up in a Ke routine.

Comments (5)

  1. Björn says:

    Interesting info, but the dark blue on the dark gray background is a tad hard to read :]

  2. Darius says:

    Indeed, GREAT info, but please tweak the colors 🙂

  3. jvert says:

    Well there is the balance set manager thread that runs and swaps processes out. Also does the priority boosting to prevent priority inversions.

  4. Mike Dimmick says:

    Is it too obvious to point to "Windows Internals, Fourth Edition" as the reference every driver developer should have (and probably many app developers like me)?

  5. PeterWie says:

    Sorry about the colors – that’s what i get for posting an email message straight to the blog.