The Task Scheduler schedules and coordinates tasks at run time. A task is a unit of work that performs a specific job. The Task Scheduler manages the details that are related to efficiently scheduling tasks on computers that have multiple computing resources.
Windows OS provides a preemptive kernel-mode scheduler: it’s a round-robin, priority-based mechanism that gives every task exclusive access to a computing resource for a given time period, and then switches to another task. Although this mechanism provides fairness (every thread makes forward progress), it comes at some cost in efficiency. For example, many computation-intensive algorithms do not require fairness; instead, it is important that related tasks finish in the least overall time. Cooperative scheduling enables an application to schedule work more efficiently.
Cooperative scheduling is a mechanism that gives every task exclusive access to a computing resource until the task finishes or until the task yields its access to the resource.
The user-mode cooperative scheduler enables application code to make its own scheduling decisions. Because cooperative scheduling enables many scheduling decisions to be made by the application, it reduces much of the overhead that is associated with kernel-mode synchronization.
The Concurrency Runtime uses cooperative scheduling together with the preemptive scheduler of the operating system to achieve maximum usage of processing resources.
Scheduler Design
The Concurrency Runtime provides the Scheduler interface to implement a specific scheduler adapted to application needs.
Let’s discover the classes implementing this interface; for that, we can execute the following CQL query:
The Concurrency Runtime provides two implementations of the scheduler: ThreadScheduler and UMSThreadScheduler.
As shown by the following dependency graph, the scheduler references many abstract classes to achieve its goal:
Let’s discover the role of each abstract class used by the scheduler; for that, we will discuss its responsibilities.
There are three major responsibilities assigned to the Task Scheduler:
1. Getting resources (processors, cores, memory):
When the scheduler is created, it asks for resources from the runtime resource manager, as explained in this article.
The scheduler communicates with the resource manager using the IResourceManager, ISchedulerProxy and IScheduler interfaces. When creating the scheduler we can specify its policy.
The Concurrency::PolicyElementKey enumeration defines the policy keys associated with the Task Scheduler.
Here’s an article explaining the purpose of each policy key and the default value of each one.
Here's a dependency graph to show what happens when we create a scheduler:
The Concurrency Runtime creates a default scheduler if no scheduler exists, by invoking the GetDefaultScheduler method, and a default policy is used. The Task Scheduler enables applications to use one or more scheduler instances to schedule work, and an application can invoke Scheduler::Create to add another scheduler that uses a specific policy.
The following collaborations between the scheduler and the resource manager show the role of each interface involved in the allocation.
- Ask for resource allocation:
- Getting resources from the resource manager:
2. Manage the task queues:
When the scheduler is created, tasks can be assigned to it to be executed; the scheduler stores tasks into queues. To enforce the cohesion of classes, the queues are not managed directly by the ThreadScheduler class but by the ScheduleGroupBase class.
A schedule group affinitizes, or groups, related tasks together. Every scheduler has one or more schedule groups. Use schedule groups when you require a high degree of locality among tasks, for example, when a group of related tasks benefit from executing on the same processor node.
As shown in the following graph, the runtime provides two kinds of ScheduleGroup: FairScheduleGroup and CacheLocalScheduleGroup. Choosing between these two groups, as will be explained later, impacts the algorithm used by the scheduler to choose the next task to execute.
Every scheduler has a default schedule group for every scheduling node. The runtime creates one scheduling node for every processor package or Non-Uniform Memory Architecture (NUMA) node. If you do not explicitly associate a task with a schedule group, the scheduler chooses which group to add the task to.
As shown in the following dependency graph, the SchedulingRing is responsible for managing schedule groups: it contains a list of groups and creates them.
The Schedule group contains three kind of queues:
1. FIFO Queue
This queue contains lightweight tasks, a lightweight task resembles the function that you provide to the Windows API CreateThread function. Therefore, lightweight tasks are useful when you adapt existing code to use the scheduling functionality of the Concurrency Runtime.
A lightweight task is represented by the RealizedChore class, and the FIFO queue of the schedule group is represented by the m_realizedChores field.
Let’s search for methods that directly use this queue:
So we can add a lightweight task to the group by invoking ScheduleGroupBase::ScheduleTask or Scheduler::ScheduleTask.
Here’s an interesting article about lightweight tasks.
2. Work Stealing queue:
There’s only one FIFO queue associated with the schedule group, but the schedule group references a list of work-stealing queues: for each worker thread there’s a local queue associated with it.
A thread that is attached to a scheduler is known as an execution context, or just context, so this local queue is actually associated with the Context class.
The Context class provides a programming abstraction for an execution context and offers the ability to cooperatively block, unblock, and yield the current context.
And to be sure that only the Context creates this kind of queue, let’s search for the methods that directly access the m_workQueues field.
The context is responsible for creating this queue, and for each context there’s a local work-stealing queue associated with it.
To illustrate the behavior of the work-stealing algorithm, let’s suppose that we have two worker threads allocated to the scheduler.
As explained before for each worker thread there's a local queue associated with it.
Three tasks are in the queue of worker thread 1: tasks 3 and 4 are waiting to be executed while task 5 is running.
The Dispatch method finds that there is nothing in the queue, so task 3 is moved, or “stolen”, from its original queue, to be distributed to the available worker thread.
How can we create a task managed by a work-stealing queue? For that, let’s search for methods that indirectly invoke the CreateWorkQueue method.
As shown in this dependency graph, this kind of task can be created by using the task_group class.
Using task_group to add a new task is better than using Scheduler::ScheduleTask to create a lightweight task; indeed, the work-stealing algorithm makes better use of the virtual processors allocated to the scheduler.
However, ScheduleTask can be better for easily migrating existing code that uses the CreateThread API.
3. Unblocked context queue
The Context class lets you block or yield the current execution context. Blocking or yielding is useful when the current context cannot continue because a resource is not available. The Context::Block method blocks the current context. A context that is blocked yields its processing resources so that the runtime can perform other tasks. The Context::Unblock method unblocks a blocked context.
When a context is unblocked and available to be executed, it’s added to the runnable context queue; this queue is represented by the m_runnableContexts field.
Here’s a dependency graph showing some cases where the context is added to the runnable queue:
So the context is added to the queue when it’s unblocked or when a virtual processor is retired from the scheduler.
3. Dispatching Tasks:
The scheduler tries to find work to execute; work can be:
- Unblocked context.
- Lightweight task.
- Task in work stealing queues.
And as explained before, all this work is stored in queues managed by schedule groups, and each group is managed by a scheduling ring.
When a virtual processor is allocated to the scheduler, a ThreadProxy class is created and associated with this processor, and after creation the Dispatch method of the ThreadProxy is invoked. As shown in the following dependency graph, and as explained before, the Concurrency Runtime uses abstract classes to enforce low coupling, and the actual dispatch invoked depends on the implementation chosen by the runtime; this choice is given by the scheduler policy.
The concrete implementation of Dispatch invokes the Dispatch method of the execution context.
Here’s a dependency graph showing the methods invoked by a concrete implementation of the Context::Dispatch method:
So the algorithm for finding the next work to execute is implemented by the WorkSearchContext class.
Let’s discover all the classes used directly by WorkSearchContext to fulfill its responsibility:
The responsibility of WorkSearchContext is to give us a WorkItem to execute; it could be InternalContextBase, RealizedChore or _UnrealizedChore.
To better understand the collaboration between these classes, let’s search for the methods used directly by WorkSearchContext:
So WorkSearchContext iterates over the SchedulingRing and ScheduleGroup classes using SchedulerBase methods.
And for each ScheduleBase we search for a RunnableContext, RealizedChore or UnrealizedChore.
The WorkSearchContext class is created by the VirtualProcessor class, and as shown in the following dependency graph, the algorithm used is specified when the VirtualProcessor is initialized; for that, it asks the scheduler for the SchedulingProtocol, which describes the scheduling algorithm that will be used by the scheduler.
WorkSearchContext is notified of the algorithm to use by being passed a value from the Algorithm enum.
So two algorithms are implemented by this class to find work:
- Cache Local algorithm:
This algorithm looks for runnable contexts within the current schedule group, then realized chores, then unrealized chores; if there’s no more work in the current schedule group, it looks in the next group in the same schedule ring, and when it has finished all the work in the current schedule ring, it looks in the next schedule ring.
So the scheduler prefers to continue to work on tasks within the current schedule group before moving to another schedule group.
This algorithm is implemented by the WorkSearchContext::SearchCacheLocal method, and as shown by this dependency graph, this method invokes other methods to search for runnable contexts, RealizedChore or _UnrealizedChore.
Another specificity of this algorithm is that the unblocked contexts are cached per virtual-processor and are typically scheduled in a last-in first-out (LIFO) fashion by the virtual processor which unblocked them.
And to verify this behavior, here’s a dependency graph of the methods invoked when searching for a runnable context:
This algorithm is the default one chosen by the scheduler if none is specified.
- Fair algorithm:
In this case, the scheduler prefers to round-robin through schedule groups after executing each task. Unblocked contexts are typically scheduled in a first-in-first-out (FIFO) fashion. Virtual processors do not cache unblocked contexts.
This algorithm is implemented by the WorkSearchContext::SearchFair method, and as shown by this dependency graph, this method invokes other methods to search for runnable contexts, RealizedChore or _UnrealizedChore.
