Рецепты на языке C#

Рецепты на языке C#

© CSharpCooking 2024

Тёмный режим

Планировщик задач
27/02/2022
Руслан Гибадуллин

Планировщик задач распределяет задачи по потокам и представлен абстрактным классом TaskScheduler. В .NET Framework предлагаются две конкретные реализации: стандартный планировщик, который работает в тандеме с пулом потоков CLR, и планировщик контекста синхронизации. Последний предназначен для содействия в работе с потоковой моделью WPF и Windows Forms, которая требует, чтобы доступ к элементам управления пользовательского интерфейса осуществлялся только из создавшего их потока. В данном посте представлен механизм работы стандартного планировщика.

Основные принципы

Планировщик задач играет связующую роль между задачами (рабочими элементами) и потоками. Множество задач приложения выполняется одними и теми же рабочими потоками, число которых динамически оптимизируется планировщиком с учетом возможностей вычислительной системы, фактической загруженности системы и прогрессом выполнения задач. В процессы работы планировщика задач включены очереди задач (одна глобальная и множество локальных очередей), стратегии распределения задач и рабочие потоки, которые фактически выполняют задачи.


Рис. 1. Составляющие элементы процесса работы планировщика задач

Всякий раз, когда запускается поток, несколько сотен микросекунд тратится на организацию таких элементов, как новый стек локальных переменных. Снизить эти накладные расходы позволяет пул потоков, предлагая накопитель заранее созданных многократно применяемых потоков. Организация пула потоков жизненно важна для эффективного параллельного программирования и реализации мелкомодульного параллелизма; пул потоков позволяет запускать короткие операции без накладных расходов, связанных с начальной настройкой потока.

Таким образом, приложение состоит из основного потока, в котором могут запускаться новые пользовательские потоки, и набора рабочих потоков. Рабочие потоки существуют на протяжении всей жизни приложения; изначально находятся в “спящем” состоянии, но могут быть задействованы для обработки пользовательских задач. Рабочие потоки включаются в обработку, если в коде программы есть работа с объектами библиотеки Task Parallel Library (Task, Parallel, PLINQ) или непосредственная работа с пулом потоков ThreadPool.

using System;
using System.Threading;
using System.Threading.Tasks;

namespace CSharpCooking
{
  class Program
  {
    static void Main()
    {
      Action IsPool = () =>
      {
        Console.WriteLine(Thread.CurrentThread.IsThreadPoolThread);
      };
      Console.WriteLine("Parallel.Invoke");
      Parallel.Invoke(IsPool, IsPool, IsPool, IsPool, IsPool);
      Console.WriteLine("Parallel.For");
      Parallel.For(0, 5, i => IsPool());
      Console.WriteLine("Task");
      Task.Factory.StartNew(IsPool).Wait();
      Console.WriteLine("Thread");
      new Thread(() => IsPool()).Start();
    }
  }
}

Итак, получаем, что задача Task выполняется в пуле, методы Parallel.Invoke, Parallel.For неявно создают задачи, которые тоже выполняются в пуле. Главный поток, выполняющий метод Main, и пользовательский поток не являются рабочими потоками пула. Часть работы, определяемой в методах Parallel.Invoke, Parallel.For, может выполнять в основном потоке.

Отметим, метод Parallel.Invoke будет работать эффективно, даже если ему передать массив из миллиона делегатов. Причина в том, что он разбивает большое количество элементов на пакеты, которые назначает небольшому числу существующих объектов Task, а не создает отдельный объект Task для каждого делегата. То же самое касается метода Parallel.For, ему можно передавать большое количество элементов работы, и они будут эффективно распределены по нескольким задачам.

Пул потоков состоит из глобальной очереди, организованной по принципу FIFO, и множества локальных очередей, организованных по принципу LIFO. Дисциплина очереди FIFO (first-in, first-out) предполагает, что первый добавленный элемент первым поступит на обработку. Рабочие потоки обращаются к глобальной очереди и получают задачу на обработку. Доступ нескольких потоков к одному ресурсу – очереди задач – требует применения синхронизации для избегания проблемы гонки данных. Синхронизированный доступ потоков снижает быстродействие обработки. Чем меньше “вычислительная нагрузка” задач, тем чаще потоки соревнуются за доступ к очереди.

Для уменьшения накладных расходов, связанных с необходимостью синхронизации доступа потоков к глобальной очереди, в структуру пула потоков введены локальные очереди. Каждая локальная очередь соответствует одному рабочему потоку.

Локальные очереди предназначены для вложенных задач. Задачи, которые объявляются и запускаются из пользовательского потока, являются задачами верхнего уровня (top-most level tasks). Такие задачи помещаются в глобальную очередь и распределяются по рабочим потокам. При выполнении задачи верхнего уровня рабочий поток добавляет в свою локальную очередь все вложенные задачи.


Рис. 2. Глобальная и локальные очереди задач

Вложенные задачи помещаются в локальную очередь рабочего потока, в котором выполняется родительская задача. Локальные очереди организованы по принципу LIFO (last-in, first-out). Первой вложенной задачей, которая будет выполняться рабочим потоком, будет та задача, которая добавлена в очередь последней. Такой порядок объясняется возможной локальностью данных. Последняя добавленная вложенная задача использует общие данные в ближайшем окружении.

Task t = Task.Factory.StartNew(() =>
{
  // готовим данные для подзадачи 1
  data1 = f1(data);  
  // добавляем в очередь подзадачу 1
  Task t1 = Task.Factory.StartNew(() => { work(data1); });
  
  // готовим данные для подзадачи 2
  data2 = f2(data);
  // добавляем в очередь подзадачу 2
  Task t2 = Task.Factory.StartNew(() => { work(data2); });
  
  // готовим данные для подзадачи 3
  data3 = f3(data);
  // добавляем в очередь подзадачу 3
  Task t3 = Task.Factory.StartNew(() => { work(data3); });
  
  // ожидаем завершения подзадач
  Task.WaitAll(t1, t2, t3);
});

Благодаря стратегии планировщика Inlined Execution (см. ниже), не стоит опасаться блокировки потока, если последняя вложенная задача ссылается на предыдущую подзадачу (ожидает завершения или события из предыдущей задачи).

Опция PreferFairness

Если обратный порядок выполнения задач не желателен, то можно использовать опцию PreferFairness при создании задач. Такие задачи помещаются в глобальную очередь. Организация глобальной очереди по принципу FIFO позволяет надеяться, что вложенные задачи, созданные с опцией PreferFairness, будут выполняться в порядке добавления.

static void Main()
{
  Task tMain = Task.Factory.StartNew(() =>
  {
    var t1 = Task.Factory.StartNew(() => ...);
    var t2 = Task.Factory.StartNew(() => ...);
    var t3 = Task.Factory.StartNew(() => ...,
          TaskCreationOptions.PreferFairness);
    var t4 = Task.Factory.StartNew(() => ...,
          TaskCreationOptions.PreferFairness);
  });
}

В этом фрагменте – одна задача верхнего уровня, которая помещается в глобальную очередь. При обработке задачи tMain в одном из рабочих потоков вложенные задачи t1 и t2 помещаются в локальную очередь данного рабочего потока. Задачи t3 и t4 созданы с опцией PreferFairness, поэтому добавляются в глобальную очередь. Порядок обработки вложенных задач локальной очереди – обратный порядку добавления. Сначала будет обрабатываться задача t2, затем t1. Задачи t3 и t4 обрабатываются в порядке добавления, т.е. сначала t3, затем t4. В каком рабочем потоке фактически будет выполняться задачи t1, t2, t3 и t4 зависит от загруженности других рабочих потоков (см. стратегию Work Stealing). Но можно сказать, что для задач t1 и t2 созданы предпосылки последовательного выполнения в том же рабочем потоке, что и родительская задача tMain. Для задач t3 и t4 созданы предпосылки параллельного выполнения в других рабочих потоках пула. Следует не забывать, что выполнение вложенных задач в других рабочих потоках может быть сопряжено с накладными расходами при использовании данных родительской задачи.

Таким образом, опция PreferFairness применяется не для изменения порядка выполнения задач (для этого проще изменить порядок добавления вложенных задач в локальную очередь), а для обеспечения условий параллельного выполнения вложенных задач в разных рабочих потоках.

Стратегии планировщика

Оптимизация выполнения задач выполняется с помощью трех стратегий планировщика:

  • стратегия заимствования задач (Work Stealing),
  • стратегия Inlined Execution,
  • стратегия динамического изменения числа рабочих потоков (Thread Injection).

Стратегия Work Stealing

Стратегия Work Stealing заключается в том, что свободный рабочий поток при условии отсутствия ожидающих задач в глобальной очереди заимствует задачу у одного из загруженных рабочих потоков. Для решения проблемы синхронизации доступ к каждой локальной очереди осуществляется с помощью двух ключей: private key – указатель на последний добавленный элемент (задачу), который используется только одним рабочим потоком – держателем очереди; public key – указатель на первый добавленный элемент, который используется сторонними рабочими потоками для заимствования.


Рис. 3. Двухключевой доступ к локальной очереди

Синхронизация реализована только для открытого ключа, так как существует возможность обращения нескольких свободных рабочих потоков к локальной очереди занятого потока. Механизм заимствования задач вносит коррективы в обработку вложенных задач. Если заимствование задач не происходит, то вложенные задачи выполняются последовательно в одном рабочем потоке в порядке обратном добавлению. При заимствовании вложенные задачи могут выполняться параллельно в разных рабочих потоках.

Стратегия Inlined Execution

Стратегия Inlined Execution применяется в случае блокировки выполняющейся задачи. Если выполняющаяся задача блокируется вызовом ожидания завершения задачи, которая находится в локальной очереди этого же рабочего потока, то планировщик выполняет задачу из очереди. Такая стратегия позволяет избежать взаимоблокировки рабочего потока (dead-lock), которая может возникнуть при определенном порядке вложенных задач в локальной очереди. Стратегия Inlined Execution применяется только для задач в локальной очереди блокированного рабочего потока.

static void Main()
{
  Task tParent = Task.Factory.StartNew(() =>
  {
    var tChild1 = Task.Factory.StartNew(() => ...);
    var tChild2 = Task.Factory.StartNew(() => ...);
    tChild1.Wait();
  });
}

В задаче tParent поочередно добавляются в локальную очередь tChild1, tChild2. Предполагается, что сначала должна завершить свою работу родительская задача, затем управление будет передано задаче tChild2, и только после этого задаче tChild1. Но оператор ожидания Wait блокирует родительскую задачу. Без стратегии планировщика Inlined Execution текущий рабочий поток был бы заблокированным. Но в действительности планировщик (среда выполнения) фиксирует вызов Wait и передает управление ожидаемой задаче tChild1.

Стратегия Inlined Execution работает при вызовах Wait для конкретной задачи в локальной очереди и при вызове WaitAll для ожидания нескольких задач локальной очереди. Но что происходит в случае, если бы вместо Wait вызывался метод WaitAny, остается неясным. Если у Вас есть какая-либо информация об этом, то пишите в комментариях ниже.

Стратегия Thread Injection

Стратегия Thread Injection применяется для оптимизации числа рабочих потоков. Применяются два механизма динамического изменения числа рабочих потоков. Первый механизм применяется с целью избежать блокировки рабочих потоков: планировщик добавляет еще один рабочий поток, если не наблюдает прогресса при выполнении задачи. При этом планировщик не различает, находится ли поток действительно в заблокированном состоянии, ожидая какого-либо события, или поток загружен полезной длительной работой (long-running task). В случае выполнения “длинных” задач такая стратегия планировщика не улучшает, а даже ухудшает производительность. При росте числа потоков возникает конкуренция за физические ядра вычислительной системы, появляются накладные расходы на переключение контекстов. Чтобы избежать неправильных действий планировщика рекомендуется делать более “короткие” задачи, а длинные вычислительно-ёмкие задачи запускать с опцией LongRunning:

Task t = Task.Factory.StartNew(VeryLongComputing, TaskCreationOptions.LongRunning);

Эта опция вынуждает планировщик выделить для задачи собственный поток и не контролировать прогресс выполнения данной задачи. Поток “длинной” задачи не входит в группу рабочих потоков пула, поэтому планировщик не применяет стратегии оптимизации работы этого потока и не использует поток для выполнения других задач, ожидающих в пуле.

Второй механизм стратегии Thread Injection добавляет или удаляет рабочие потоки в зависимости от результатов выполнения предыдущих задач. Если увеличение числа потоков привело к росту производительности, то планировщик увеличивает число потоков. Если производительность не растет, то число потоков сокращается. Эвристический алгоритм стремится найти оптимальное число потоков при текущей загрузке вычислительной системы. Уменьшение объема задач также помогает планировщику найти оптимальный вариант. Второй механизм дополняет первый и позволяет избежать неограниченного добавления рабочих потоков без улучшения производительности.