{"id":692,"date":"2018-03-30T10:28:53","date_gmt":"2018-03-30T10:28:53","guid":{"rendered":"http:\/\/cppdepend.com\/blog\/?p=692"},"modified":"2023-05-31T15:36:27","modified_gmt":"2023-05-31T15:36:27","slug":"microsoft-crt-deep-dive-into-task-scheduler","status":"publish","type":"post","link":"https:\/\/cppdepend.com\/blog\/microsoft-crt-deep-dive-into-task-scheduler\/","title":{"rendered":"Microsoft CRT: Deep Dive into Task Scheduler"},"content":{"rendered":"

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.<\/p>\n

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 of 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 more efficiently schedule work.<\/p>\n

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.<\/p>\n

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.<\/p>\n

The Concurrency Runtime uses cooperative scheduling together with the preemptive scheduler of the operating system to achieve maximum usage of processing resources.<\/p>\n

Scheduler Design<\/strong><\/p>\n

The concurrency runtime provides the interface\u00a0Scheduler\u00a0to implement a specific scheduler adapted to application needs.<\/p>\n

Let’s discover classes implementing this interface, for that we can execute the following CQL request:<\/p>\n

\"\"<\/a><\/div>\n

The concurrency runtime provides two implementations of scheduler,\u00a0ThreadScheduler\u00a0and\u00a0UMSThreadScheduler.<\/p>\n

The scheduler as shown by the following dependency graph, reference many abstrac classes to acheive its goal:<\/p>\n

\"\"<\/a><\/div>\n

 <\/p>\n

Let’s discover the role of each abstract class used by the scheduler, for that we will discuss its responsibilities.<\/p>\n

There are three major responsibilities assigned to the Task Scheduler:<\/p>\n

1) Getting Resources(Processors, Cores, Memory):<\/strong><\/p>\n

When the scheduler is created it ask for resources from runtime resource manager as explained in this\u00a0article<\/a>.<\/p>\n

The scheduler communicates with the resource manager using\u00a0IResourceManager,\u00a0ISchedulerProxy\u00a0and\u00a0IScheduler\u00a0interfaces.
\nWhen creating the scheduler we can specify its policy.<\/p>\n

The Concurrency::PolicyElementKey enumeration defines the policy keys that are associated with the Task Scheduler.<\/p>\n

\"\"<\/a><\/div>\n

Here’s an\u00a0article\u00a0<\/a>explaining the utility of each policy key, and the default value of each key.<\/p>\n

Here’s a dependency graph to show what happens when we create a scheduler:<\/p>\n

\"\"<\/a><\/p>\n

The concurrency runtime create a default scheduler if no scheduler exists by invocking GetDefaultScheduler method, and a default policy is used.
\nThe Task Scheduler enables applications to use one or more\u00a0scheduler instances<\/span>\u00a0to schedule work, and an application can invoke Scheduler::Create to add another scheduler that uses a specific policy.<\/p>\n

The following collaborations between the scheduler and resource manager shows the role of each interface concerned by the allocation.<\/p>\n

– Ask for resource allocation:<\/p>\n

\"\"<\/a><\/div>\n

– Getting resources from resource manager:
\n\"\"<\/a><\/p>\n

2) Manage the task queues:<\/strong><\/p>\n

When Schedeluer is created, tasks could be assigned to it to be executed, the Scheduler store tasks into queues.to enforce the cohesion of classes, the queues are not managed directly by the ThreadScheduler class but by ScheduleGroupBase class.<\/p>\n

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.<\/p>\n

As shown in the following graph, the runtime provides two kind of ScheduleGroup:\u00a0FairScheduleGroup\u00a0and\u00a0CacheLocalScheduleGroup, choosing between thoses two groups as it will be explained later impact the algorithm of choosing the next task to execute by the scheduler.<\/p>\n

\"\"<\/a><\/div>\n

Every\u00a0Scheduler<\/strong>\u00a0has 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.<\/p>\n

As shown in the following dependency graph , The schedulingRing is responsable of managing Scheduler Groups, it contains a list of groups and create them.<\/p>\n

\"\"<\/a><\/p>\n

The Schedule group contains three kind of queues:<\/p>\n

1) FIFO Queue<\/strong><\/p>\n

This queue contains lightweight tasks, a lightweight task resembles the function that you provide to the Windows API\u00a0CreateThread\u00a0function. Therefore, lightweight tasks are useful when you adapt existing code to use the scheduling functionality of the Concurrency Runtime.<\/p>\n

A lighweight task is represented by\u00a0RealizedChore\u00a0class, and the FIFO queue of the schedule group is represented by the field m_realizedChores.<\/p>\n

Let’s search for methods using directly this queue:<\/p>\n

\"\"<\/a><\/div>\n

So we can add a lightweight task to the group by invoking ScheduleGroupBase::ScheduleTask or Scheduler::ScheduleTask.<\/p>\n

\"\"<\/a><\/p>\n

Here’s an interesting\u00a0article<\/a>\u00a0talking about lighweight tasks.<\/p>\n

2)Work Stealing queue:<\/strong><\/p>\n

There’s only one FIFO queue associated to the schedule group, but the schedule group reference a list of work sealing queues, for each worker thread there’s a local queue associated with it.<\/p>\n

A thread that is attached to a scheduler is known as an\u00a0execution context<\/span>, or just\u00a0context<\/span>, so actually this local queue is associated to\u00a0Context\u00a0class.<\/p>\n

The\u00a0Context\u00a0class provides a programming abstraction for an execution context and offer the ability to cooperatively block, unblock, and yield the current context.<\/p>\n

And to be sure that only\u00a0the Context create this kind of queue, let’s search of the methods accessing directly to m_workQueues field.<\/p>\n

\"\"<\/a><\/div>\n

 <\/p>\n

The context is responsable of creating this queue, and for each context there’s a local work stealing queue associated to it.<\/p>\n

To illustrate the behavior of the work-stealing algorithm, let’s supposethat we have two worker thread allocated to the scheduler.<\/p>\n

As explained before for each worker thread there’s a local queue associated with it.<\/p>\n

\"\"<\/a><\/div>\n

Three tasks in the queue Worker Thread 1, tasks 3 and 4 are waiting to be executed while the 5 is running.<\/span><\/span><\/p>\n

\"\"<\/a><\/div>\n

The Dispatch method finds that there is nothing in the queue, so the task 3 is moved, or “stolen” from its original queue, to be distributed\u00a0the worker thread available.<\/span><\/span><\/p>\n

\"\"<\/a><\/div>\n

How we can create a task managed by work stealing queue? for that let’s search for methods indirectly invocking the CreateWorkQueue method.<\/p>\n

As shown in this dependency graph, this kind of task could be created by using task_group class.<\/p>\n

\"\"<\/a><\/p>\n

Using task_group to add new task is more better than using Sheduler::ScheduleTask to create a lighweight task, indeed the work stealing algorithm optimize better the using of virtual processors allocated to the scheduler.<\/p>\n

However, ScheduleTask could be better to migrate easilly from the existing code using CreateThread API.<\/p>\n

3)Unblocqued Context queue:<\/p>\n

The\u00a0Context<\/strong>\u00a0class 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.
\nThe 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.<\/p>\n

When a context is unblocked and it’s available to be executed , it’s add to runnable context queue, this queue is represented by the field m_runnableContexts.<\/p>\n

Here’s a dependency graph showing some cases where the context is added to runnable queue:<\/p>\n

\"\"<\/a><\/div>\n

So the context is added to the queue when it’s unblocked or a virtual processor is retired from the scheduler.
\n3)Dispatching Tasks:<\/strong><\/p>\n

The scheduler try to search for work to execute, a work could be:<\/p>\n