Регулирование параллельной обработки в ThreadPool в CLR 4.0

В ThreadPool в новейшем выпуске CLR (версии 4.0) было внесено несколько серьезных изменений по сравнению с CLR 2.0. Недавние крупные перемены в технологиях — вроде широкого распространения многоядерных архитектур процессоров и естественного появления потребности в распараллеливании существующих приложений или написания нового параллельного кода — стали одной из весомых причин для совершенствования CLR ThreadPool.

В статье «Управление потоками в CLR» (msdn.microsoft.com/magazine/dd252943) под рубрикой «CLR с изнанки» в номере «MSDN Magazine» за январь 2009 г. я обсуждала некоторые из этих причин и сопутствующие вопросы, в том числе управление параллельной обработкой. Теперь я опишу, как мы решили эти задачи в ThreadPool в CLR 4.0, какой выбор был у нас в реализации и как он мог повлиять на поведение общеязыковой исполняющей среды (CLR). Я уделю внимание подходу, принятому для автоматизации управления параллельной обработкой в текущей версии ThreadPool для CLR 4.0 (далее для краткости просто ThreadPool). Кроме того, я дам краткий обзор архитектуры ThreadPool. Моя статья охватывает и детали реализации, подлежащие изменению в будущих версиях. Все это может оказаться полезным для понимания и использования преимуществ поведения текущей версии ThreadPool не только тем, кто проектирует и пишет новые параллельные приложения, но и тем, кто заинтересован в улучшении старых приложений за счет распараллеливания, а также в использовании технологий ASP.NET или Parallel Extension (в контексте CLR 4.0).

Обзор ThreadPool

Пул потоков (thread pool) обеспечивает ключевые сервисы, в частности управление потоками, абстракции различных типов параллельной обработки и регулирование (throttling) параллельных операций. Эти сервисы снимают часть бремени ручной работы с программистов. Для неопытных программистов очень удобно, что не требуется изучать и иметь дело со сложными деталями внутреннего устройства многопоточной среды. Более опытные программисты, располагая надежной системой потоков, могут сосредоточиться на улучшении различных аспектов своих приложений. ThreadPool предоставляет эти сервисы управляемым приложениям и поддерживает перенос между платформами, позволяя выполнять определенные приложения Microsoft .NET Framework, например, в Mac OS.

К разным частям системы могут относиться разные типы параллельной обработки. Наиболее релевантные: процессорный параллелизм, параллелизм ввода-вывода, таймеры и синхронизация, балансировка нагрузки и использование ресурсов. Я кратко обрисую архитектуру ThreadPool в терминах различных аспектов параллельной обработки (подробнее об архитектуре ThreadPool и применении соответствующих API см.«The CLR’s Thread Pool» по ссылке msdn.microsoft.com/magazine/cc164139). Особо стоит отметить, что существует две независимые реализации ThreadPool: одна из них имеет дело с процессорным параллелизмом и называется пулом рабочих потоков (worker ThreadPool), а другая — с параллелизмом ввода-вывода и может быть названа пулом потоков ввода-вывода. В следующем разделе мы сосредоточимся на процессорном параллелизме и соответствующей реализации в ThreadPool, в частности поговорим о стратегиях регулирования параллельной обработки.

Пул рабочих потоков Он предоставляет сервисы на уровне процессорного параллелизма и использует преимущества многоядерных архитектур. В отношении процессорного параллелизма нужно учитывать два важнейших фактора: быстрая и оптимальная диспетчеризация работы и регулирование степени параллелизма. В первом случае реализация ThreadPool использует такие стратегии, как очереди, свободные от блокировок (lock-free queues), чтобы избежать конкуренции и «кражи» работы при балансировке нагрузки; однако эти области выходят за рамки нашего обсуждения (подробно эта тематика освещается по ссылке msdn.microsoft.com/magazine/cc163340). А во втором случае — регулировании степени параллелизма — реализация ThreadPool обеспечивает управление параллельной обработкой, чтобы предотвратить конкуренцию за ресурсы и последующее уменьшение общей пропускной способности.

Процессорный параллелизм может представлять особую проблему, потому что на него влияет множество параметров, скажем, определение того, сколько рабочих элементов можно выполнять одновременно в любой конкретный момент. Другая проблема — количество ядер и как оптимизировать распределение различных типов рабочих нагрузок. Например, в теории оптимальным считается один поток на процессор, но, если рабочая нагрузка постоянно блокируется, процессорное время тратится впустую, и можно было бы использовать большее число потоков для выполнения большего объема работы. Размер и тип рабочей нагрузки на самом деле являются еще одним параметром. Так, в случае блокирующихся рабочих нагрузок крайне трудно определить число потоков, обеспечивающих оптимальную пропускную способность, поскольку сложно вычислить, когда будет завершена обработка запроса (или даже насколько часто будут появляться запросы — это тесно связано с блокировкой ввода-вывода). Соответствующий API в этом ThreadPool — QueueUserWorkItem, который помещает метод (рабочий элемент) в очередь для выполнения (msdn.microsoft.com/library/system.threading.threadpool.queueuserworkitem). Он рекомендуется для использования в приложениях, где есть работа, которую потенциально можно выполнять параллельно (с другими задачами). Эта работа передается ThreadPool, который автоматически «выясняет», когда запускать ее выполнение. Этот механизм снимает с программиста заботу о том, как и когда создавать потоки; но, увы, это не самое эффективное решение на все случаи жизни.

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

Параллельная обработка в ThreadPool

Параллельная обработка — задача трудна, но необходимая, так как она прямо влияет на общую производительность системы. Как система регулирует параллельную обработку, сказывается и на других задачах вроде синхронизации, использовании ресурсов и балансировке нагрузки (и наоборот).

Концепция управления параллельной обработкой (concurrency control), или точнее регулирования параллельной обработки (throttling concurrency), относится к тому, сколько потоков разрешается запускать для выполнения работы в конкретное время в ThreadPool; это политика, определяющая, сколько потоков может выполняться одновременно без вреда для производительности. В этой статье управление параллельной обработкой рассматривается лишь применительно к пулу рабочих потоков. Как бы то ни противоречило термину, суть управления параллельной обработкой заключается в регулировании и уменьшении количества рабочих элементов, которые могут выполняться параллельно, с целью увеличения пропускной способности пула рабочих потоков (т. е. управление степенью параллелизма предотвращает выполнение некой части работы).

Алгоритм управления параллельной обработкой в ThreadPool автоматически выбирает уровень параллелизма; он решает за программиста, сколько потоков нужно для поддержания общей производительности на оптимальном уровне. Реализация этого алгоритма — одна из сложнейших и интересных частей ThreadPool. Существуют различные подходы к оптимизации производительности ThreadPool в контексте уровня параллелизма (другими словами, к определению «правильного» количества потоков, выполняемых одновременно). В следующем разделе я опишу некоторые из этих подходов, которые рассматривались или применялись в CLR.

Эволюция управления параллельной обработкой в ThreadPool

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

Другой идеей было просто оставить за ОС все заботы об уровне параллелизма. По сути, именно это и делает пул потоков ввода-вывода, но пул рабочих потоков требовал более высокого уровня абстракции, чтобы обеспечить большие портируемость и эффективность управления ресурсами. Этот подход мог бы сработать в некоторых ситуациях, но программисту все равно нужно было бы знать, как осуществляется регулировка во избежание перенасыщения ресурсов (например, если созданы тысячи потоков, конкуренция за ресурсы может стать проблемой, а увеличение числа потоков только ухудшит ситуацию). Более того, это подразумевало, что программист должен был бы самостоятельно заботиться о параллельной обработке, что противоречит смыслу пула потоков.

Более новый подход включал концепцию пропускной способности, измеряемой в количестве завершенных рабочих элементов в единицу времени; этот показатель использовался для оптимизации производительности. В этом случае, когда нагрузка на процессор низка, потоки добавляются и одновременно проверяется, повысилась ли пропускная способность. Если да, добавляются еще потоки; не помогает — потоки удаляются. Такой подход более разумен, чем предыдущие, потому что он учитывает, сколько работы было выполнено, а не просто как используются ресурсы. К сожалению, на пропускную способность влияет много факторов — не только количество активных потоков (скажем, размер рабочих элементов), а это сильно затрудняет оптимизацию.

Теория управления для регулирования параллельной обработки

Чтобы преодолеть некоторые ограничения предыдущих реализаций, в CLR 4.0 были заложены новые идеи. Первая методология, учтенная нами, была взята из области теории управления — алгоритм Hill Climbing (HC). Это подход с автоматической оптимизацией на основе петли обратной связи между входом и выходом (input-output feedback loop). Выход в системе наблюдается и измеряется через малые промежутки, чтобы увидеть влияние управляемого входа; эта информация передается обратно в алгоритм для дальнейшей настройки входа. Рассматривая вход и выход как переменные, мы моделируем систему как функцию зависимости от этих переменных. Цель — последующая оптимизация измеряемого выхода.

В контексте системы пула рабочих потоков входом является количество потоков, одновременно выполняющих работу (или уровень параллельной обработки), а выходом — пропускная способность (рис. 1).

Рисунок 1 Петля обратной связи в ThreadPool

Мы наблюдаем и измеряем изменения пропускной способности во времени как результат добавления или удаления потоков, а затем решаем, добавлять или удалять дополнительные потоки, исходя из наблюдаемого уменьшения или повышения пропускной способности. Рис. 2 иллюстрирует идею.

Рис. 2. Общая производительность как функция уровня одновременности выполнения

Представляя пропускную способность как (полиномиальную) функция уровня параллельной обработки, алгоритм добавляет потоки, пока не будет достигнут максимум функции (около 20 в этом примере). С этой точки начнется уменьшение пропускной способности, и алгоритм удалит потоки. Через каждый интервал берется выборка измерений пропускной способности и «усредняется». Затем на ее основе принимается решение для следующего интервала . Понятно, что, если в измерениях много шума, статистическая информация не отражает реальную ситуацию, если только она не была получена за большой промежуток времени. Иначе трудно сказать, было ли улучшение результатом изменения уровня параллелизма или причиной является другой фактор, например флуктуации в рабочей нагрузке.

Адаптивные подходы в реальных системах затруднены; в нашем случае их применение особенно проблематично из-за сложности обнаружения малых вариаций или выборки изменений из очень зашумленной среды за короткий промежуток. Первая проблема с таким подходом заключается в том, что смоделированная функция (см. черную кривую на рис. 2) не является статической на практике (см. серые точки на том же графике), поэтому измерить небольшие изменения трудно. Следующая и, возможно, более серьезная проблема в том, что шум (вариации в измерениях, вызванные системной средой, например определенными операциями ОС, сбором мусора и др.) фактически не позволяет понять, есть ли реальная связь между входом и выходом, т. е. с уверенностью сказать, что пропускная способность является лишь функцией от числа потоков. По сути, в ThreadPool пропускная способность составляет лишь малую часть того, что наблюдается на выходе в действительности — большая его часть является шумом. Например, возьмем приложение, использующее множество потоков для обработки своей рабочей нагрузки. Добавление еще нескольких потоков окажется незаметным на выходе: если в каком-то интервале вы заметите улучшение, не факт, что он связан с изменением в уровне параллельной обработки (эту проблему иллюстрирует рис. 3).

Рисунок 3 Пример шума в ThreadPool

На рис. 3 по оси x отложено время, а по оси y нанесены результаты измерений пропускной способности и уровня параллелизма. Верхний график иллюстрирует, что при некоторых рабочих нагрузках, даже если число потоков (прямая линия) сохраняется постоянным, могут наблюдаться колебания пропускной способности (ломаная кривая). В этом примере флуктуации являются шумом. Нижний график — другой пример, где даже в присутствие шума наблюдается, в целом, увеличение пропускной способности со временем. Но число потоков по-прежнему остается постоянным, поэтому увеличение пропускной способности вызвано каким-то другим фактором, действующим в системе.

В следующем разделе я рассмотрю подход к фильтрации шума.

Введение фильтрации сигнала

Фильтрация сигнала используется во многих областях техники для уменьшения шума в сигналах; идея в том, чтобы найти шаблон входного сигнала в выходном. Эта теория применима и в контексте ThreadPool, если мы интерпретируем вход (уровень параллелизма) и выход (пропускную способность) алгоритма управления параллельной обработкой как сигналы. Если мы вводим намеренно модифицированный уровень параллелизма как «волновой» с известными периодичностью и амплитудой и ищем исходный волновой шаблон на выходе, то можем различить, что является шумом, по реальному влиянию входа на выход. Эту идею иллюстрирует рис. 4.

Рисунок 4 Определение факторов, влияющих на выход ThreadPool

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

Вместо подачи линейного постоянного входа мы вводим сигнал, а затем пытаемся найти его в зашумленном выходе. Этот эффект может быть достигнут использованием таких способов, как полосный фильтр (band pass filter) или фильтр совпадений (match filter), обычно применяемых для отделения одних волновых сигналов от других или поиска очень специфических сигналов на выходе. Это также означает, что за счет внесения изменений на входе алгоритм принимает решения в каждый момент, основываясь на последней небольшой порции входных данных.

В частности, алгоритм в ThreadPool использует дискретное преобразование Фурье — методологию, позволяющую получить такую информацию, как величина и фаза волны. Затем на основе этой информации можно понять, как влиял вход на выход и влиял ли вообще. График на рис. 5 показывает пример поведения ThreadPool при использовании этой методологии на рабочей нагрузке, выполняемой более 600 секунд.

Рисунок 5 Измерения влияния входа на выход

В примере на рис. 5 известный шаблон входной волны (фаза, частота и амплитуда) можно отследить и на выходе. График иллюстрирует поведение алгоритма параллельной обработки, использующего фильтрацию выборки рабочей нагрузки. Тренд светлого оттенка соответствует входу, а темного — выходу. Количество потоков с течением времени варьируется, но это не значит, что мы создаем или уничтожаем потоки; мы сохраняем примерно одинаковое их число.

Хотя масштаб количества потоков отличается от такового для пропускной способности, прекрасно видно, что можно сопоставить то, как вход влияет на выход. Число потоков постоянно меняется минимум на единицу за отрезок времени, но это не значит, что был создан или уничтожен какой-то поток. Вместо этого потоки остаются «жить» в пуле — просто они не выполняют никакой работы.

В противоположность первоначальном подходу с применением алгоритма Hill Climbing (HC), где цель заключалась в моделировании графика пропускной способности и принятии решения на основе этих вычислений, более совершенная методология просто определяет, поможет ли изменение на входе что-то улучшить на выходе. На интуитивном уровне растет уверенность в том, что изменения, которые мы искусственно вводим, оказывают различимое влияние на выходе (максимальное число потоков, вводившихся в сигнал до сих пор, равно 20, что вполне разумно — особенно в случаях с большим количеством потоков). Один из недостатков этого подхода, использующего фильтрацию сигнала, — из-за ввода искусственного волнового шаблона оптимальный уровень параллелизма всегда будет отличаться минимум на один поток в ту или другую сторону. Кроме того, регулирование уровня параллелизма происходит сравнительно медленно (более быстрые алгоритмы основываются на показателях использования процессора), так как сначала нужно собрать объем данных, достаточный для стабилизации модели. И скорость этого процесса будет зависеть от размера рабочих элементов.

Этот подход не совершенен; для одних нагрузок работает лучше, для других — хуже, но он значительно эффективнее предыдущих методологий. Лучше всего наш алгоритм действует, когда рабочие элементы выполняются за относительно небольшое время.Дело в том, что чем меньше рабочий элемент, тем быстрее адаптируется алгоритм. Например, он превосходно функционирует, когда длительность выполнения индивидуальных рабочих элементов меньше 250 мс, но становится еще эффективнее, если это время сокращается до значений меньше 10 мс.

Управление параллельной обработкой: мы делаем это за вас

В заключение отмечу, что ThreadPool предоставляет сервисы, помогающие программисту сосредоточиться на своей работе, а не на управлении параллельной обработкой. Чтобы обеспечить такую функциональность, в реализацию ThreadPool включены алгоритмы высочайшего технического уровня, способные автоматически принимать решения за пользователя. Один из примеров — алгоритм управления параллельной обработкой, который развивался с учетом технологий и потребностей из разных сценариев применения.

Задача алгоритма управления параллельной обработкой в CLR 4.0 — автоматически решать, сколько рабочих элементов можно выполнять одновременно без потерь в эффективности, соответственно оптимизируя пропускную способность ThreadPool. Этот алгоритм сложен в тонкой настройке из-за шумовых факторов и таких параметров, как тип рабочей нагрузки; он также опирается на предположение, что каждый рабочий элемент является полезной нагрузкой. На его текущую структуру и поведение сильно повлияли сценарии применения в ASP.NET и Parallel Framework, для которых он обеспечивает хорошую производительность. В целом, ThreadPool эффективно выполняет свою работу. Однако программист должен понимать, что при некоторых рабочих нагрузках или при одновременной работе нескольких пулов рабочих потоков поведение этого алгоритма может стать непредсказуемым.