Синхронизация без ожидания
Постановка задачи
Традиционный подход с использованием блокировки для поддержки целостности совместно используемых данных в параллельных программах имеет значительные недостатки, относящиеся к таким областям, как разработка программного обеспечения, надежность, эффективность и масштабируемость. В силу этого в последние несколько десятилетий усилия исследователей прилагались главным образом к неблокирующим механизмам синхронизации.
Основополагающая статья Мориса Херлихи «Синхронизация без ожидания» [12] была посвящена проблеме реализации параллельных структур данных без ожидания, таким образом, чтобы каждая операция на этой структуре данных завершалась за конечное количество шагов вызывающим ее потоком, независимо от того, насколько быстро или медленно выполняются другие потоки и даже от того, не происходит ли у некоторых или всех из них окончательной остановки. Реализации, основанные на блокировках, не являются вариантами без ожидания, поскольку в период, когда один поток удерживает блокировку, другие могут предпринять неограниченное количество шагов в ожидании блокировки. Требование реализации без ожидания позволяет потенциально избавиться от присущих блокировкам недостатков.
В первой части статьи Херлихи исследовалась сила различных примитивов синхронизации применительно к вычислениям без ожидания. Он определил число консенсуса для конкретного примитива как максимальное число потоков, для которого мы способны обеспечить консенсус без ожиданий при помощи этого примитива (с использованием регистров типа чтение-запись). Задача достижения консенсуса требует, чтобы участвующие в ней потоки согласовали свои значения (например, «истина» или «ложь») на фоне других значений, содержащихся в потоках. Возможность решения этой задачи является ключевым индикатором силы примитива синхронизации, поскольку она является основным компонентом множества задач, естественно возникающих при параллельных вычислениях. Например, в системах с программной транзакционной памятью потоки должны согласиться с тем, что конкретная транзакция должна быть принята или отклонена.
Херлихи установил иерархию примитивов синхронизации в соответствии с их числом консенсуса. Он показал, что (1) число консенсуса регистров типа чтение-запись равно 1 (в силу чего задача консенсуса без ожидания не может быть решена даже для двух потоков), (2) число консенсуса для стеков и очередей FIFO равно 2, (3) существуют так называемые универсальные примитивы с числом консенсуса, равным 1. Типичными примерами таких примитивов являются сравнение с обменом (compare-and-swap, CAS) и подход с «условной записью» (load-linked/store-conditional, LL/SC).
Иерархия Херлихи была более детально рассмотрена в нескольких статьях. В них было показано, что относительно небольшие изменения модели или семантики примитивов могут оказать неожиданно значимое влияние на результат. Большая часть этих публикаций представляет главным образом теоретический интерес. Основной практический аспект иерархии Херлихи заключается в том, что для поддержки эффективной синхронизации без ожидания в общем случае требуются универсальные примитивы. Признавая этот факт, все современные мультипроцессоры с разделяемой памятью предоставляют какие-либо универсальные примитивы.
Кроме того, Херлихи показал, что решение задачи о консенсусе может использоваться для реализации без ожидания любого совместно используемого объекта и, таким образом, для этой цели подойдет любой универсальный примитив. Он продемонстрировал свою идею при помощи так называемого универсального построения, которое принимает на вход последовательный код объекта и создает реализацию без ожидания для этого объекта, используя консенсус для разрешения состоянии гонки между параллельными операциями. Несмотря на важные практические последствия этого результата, само по себе универсальное построение оказалось весьма непрактичным. Основная идея заключалась в построении списка операций, использовании консенсуса для определения порядка операций и последующем итерационном выполнении потоков над списком, применяющих операции для определения текущего состоянии объекта. Построение требовало O(N3) памяти, чтобы гарантировать достаточное количество сохраненных операций для определения текущего состояния. Оно также оказалось очень медленным, из-за чего многим потокам приходилось заново вычислять одну и ту же информацию, что препятствовало распараллеливанию операций.
Впоследствии Херлихи [13] представил более конкретное универсальное построение на основе пары инструкций LL/SC. Это построение требовало N + 1 копий объекта для N потоков и по-прежнему не допускало распараллеливания, в силу чего также было непрактичным. Несмотря на это, последующие работы, основанные на исследованиях Херлихи, сегодня дошли до той стадии, когда стало возможным поддерживать практические модели программирования с неблокирующими реализациями произвольных совместно используемых объектов. Далее будет рассмотрено современное состояние области неблокирующей синхронизации и попутно упомянуты некоторые факты из истории.
Более слабые условия прогресса для неблокирующих реализаций
Различные исследователи неоднократно добивались успеха в попытках преодоления недостатков построений Херлихи. Однако результаты оставались непрактичными из-за чрезмерных накладных расходов и слишком сложных алгоритмов. Фактически никакие нетривиальные совместно используемые объекты до сих пор не получили широкого практического распространения – как реализуемые непосредственно, так и использующие универсальные построения.
Самым значительным шагом в направлении практичности стало рассмотрение более слабых условий прогресса. Пока теоретики работали над реализациями без ожидания, более прагматичные исследователи искали неблокирующие реализации совместно используемых объектов. Неблокирующая реализация гарантирует, что после конечного количества шагов любой операции эта операция будет завершена. В отличие от алгоритмов без ожидания, в данном случае принципиально возможна ситуация, когда одна операция в структуре данных без блокировок будет постоянно «голодать» из-за поведения остальных. Однако на практике такая ситуация встречается редко, в частности, потому, что техники контроля над конкуренцией – такие как экспоненциальная задержка [1] – часто используются для подавления конкуренции при ее возникновении, что делает повторяющееся вмешательство еще менее вероятным. Таким образом, отсутствие сильной гарантии прогресса (такой как свобода от ожиданий) на практике нередко оказывается допустимым.
Сделанное Херлихи и др. [15] наблюдение, заключающееся в том, что более слабые условия прогресса условия прогресса позволяют создавать более простые и практичные алгоритмы, позволило Херлихи определить еще более слабое условие: алгоритм без препятствий не гарантирует, что операция завершится, за исключением случаев, если она не встречает препятствий от других операций. По сравнению с алгоритмами без блокировки алгоритмы без препятствий проще в разработке, проще по структуре и быстрее работают в условиях общего случая без конкуренции. Обратной стороной этих преимуществ алгоритмов без препятствий является потенциальная возможность динамической взаимоблокировки (livelock), при которой две или несколько операций постоянно вмешиваются в работу друг друга в бесконечном цикле. Эта проблема имеет не только теоретическую значимость; она встречалась и на практике [16]. К счастью, можно довольно легко устранить возможность взаимоблокировки при помощи механизмов контроля конкуренции, способных вмешиваться в процесс выполнения операций во избежание взаимного вмешательства.
Подход к синхронизации без препятствий позволяет разрабатывать простые и эффективные алгоритмы, удовлетворяющие самому слабому условию прогресса, и при необходимости интегрировать в него независимые механизмы контроля конкуренции для ускорения прогресса. Разделение сложных вопросов корректности и прогресса позволяет значительно упростить задачу разработки эффективных неблокирующих реализаций: алгоритмы не усложняются сильно связанными механизмами обеспечения свободы от блокировки, в то же время их можно легко изменять и экспериментировать с механизмами контроля конкуренции, поскольку они отдельны от алгоритма и не влияют на его корректность. Этот подход представляется весьма перспективным.
Транзакционная память
Серьезные трудности, сопряженные с разработкой и проверкой корректности неблокирующих структур данных, мотивировали исследователей к изучению инструментов для их построения, вместо того чтобы самим заниматься непосредственной разработкой таких структур. В частности, многообещающим направлением оказалась транзакционная память ([5, 17, 23]). Транзакционная память позволяет программистам выделять сегменты кода, которые могут быть исполнены автоматически, а система с транзакционной памятью (реализованная в аппаратной или программной форме либо в виде их сочетания) ответственна за управление взаимодействием между одновременными транзакциями, обеспечивающим атомарность. Далее будут рассматриваться системы с программной транзакционной памятью (software transactional memory, STM).
Гарантия прогресса для параллельной структуры данных, реализованной при помощи STM, зависит от реализации конкретной STM. Можно охарактеризовать условия прогресса реализации транзакционной памяти в терминах системы потоков, в которой каждая операция на совместно используемой структуре данных выполняется путем последовательных попыток применения транзакции вплоть до успешного завершения. В этом контексте можно говорить, что реализация транзакционной памяти является реализацией без препятствий, если она гарантирует, что в случае, если поток последовательно выполняет транзакции и в конечном итоге больше не встречает помех со стороны других потоков, то он в конечном итоге успешно завершает транзакцию.
Основные результаты
Далее будут вкратце рассмотрены наиболее важные результаты, относящиеся к неблокирующим механизмам синхронизации, и в частности, синхронизация без препятствий.
Несмотря на то, что в практическом плане был достигнут прогресс как в части неблокирующих реализаций совместно используемых объектов, так и в отношении неблокирующих STM-систем, этот прогресс был достаточно медленным из-за сложностей, связанных с одновременным обеспечением корректности и отсутствия блокировок. До введения понятия алгоритмов без препятствий STM-системы без блокировок отличались серьезными недостатками, такими как необходимость в заблаговременном объявлении и инициализации всей памяти, к которой впоследствии могли бы обращаться транзакции, необходимость заблаговременного знания транзакциями, к каким областям памяти они будут обращаться, неприемлемые ограничения на топологию этой памяти и т. п.
Помимо работы над такими инструментами, как STM-системы для построения неблокирующих структур данных, немалые усилия прилагались к работе над их непосредственной реализацией. Эта работа не привела к появлению практичных алгоритмов без ожидания, однако было получено несколько практичных реализаций без блокировки для простых структур данных, таких как очереди и стеки [21, 24]. В литературе было описано несколько более смелых реализаций, которые едва ли можно было назвать практичными, поскольку их алгоритмы были сложными и неочевидными, многие были неверными, и почти все не имели формальных доказательств. Находить доказательства для таких алгоритмов непросто, а после небольших модификаций их корректность приходится доказывать заново.
Далее будут рассмотрены некоторые результаты, полученные в результате применения подхода «без препятствий».
Важный практический довод за использование алгоритмов без препятствий заключается в том, каким образом выполняется управление конкуренцией при ее возникновении. Представляя принцип вычисления без препятствий, Херлихи и др. [15] пояснили, что контроль конкуренции необходим для ускорения прогресса в свете ее наличия, поскольку в этом случае алгоритмы без препятствий не могут прямо гарантировать прогресс. Однако они не пояснили более конкретно, как использовать механизмы контроля конкуренции на практике.
Впоследствии Херлихи др. [ ] представили динамическую STM-систему (см. следующий раздел), которая предоставляет интерфейс для модульного инструмента управления конкуренцией (менеджера конкуренции), позволяющий экспериментировать с альтернативными менеджерами. Шерер и Скотт [ ] экспериментировали с несколькими такими альтернативными менеджерами и обнаружили, что выбор лучшего менеджера конкуренции зависит от рабочей нагрузки. Геррауи и др. [9] описали подход к реализации, поддерживающий изменение менеджеров конкуренции «на лету» в ответ на изменение условий рабочей нагрузки.
Все менеджеры конкуренции, описанные в вышеупомянутых работах, являются ситуативными и работают на базе интуиции; не приводится каких-либо попыток анализа того, какие гарантии обеспечиваются менеджерами конкуренции и есть ли такие гарантии вообще. Геррауи и др. [10] сделали первый шаг по направлению к формальному анализу менеджеров конкуренции, показав, что их жадный менеджер конкуренции гарантирует, что каждая транзакция в конечном итоге завершается. Однако использование жадного менеджера конкуренции приводит к тому, что алгоритм становится блокирующим, так что при доказательстве обязательно приходится предполагать, что потоки не потерпят неудачу при выполнении транзакций.
Фич и др. [7] показали, что любой алгоритм без препятствий может быть преобразован в алгоритм, который в любой реальной системе окажется практичным алгоритмом без ожидания. «Практичность» здесь используется по той причине, что гарантия прогресса в случае алгоритма без ожидания зависит от частичной синхронности, существующей в любой реальной системе, однако преобразованный алгоритм технически не является алгоритмом без ожидания, так как этот термин определен в контексте полностью асинхронной системы. Тем не менее, алгоритм, полученный в результате преобразования Фич и др. К алгоритму без препятствий, гарантирует прогресс для удачных транзакций, даже если другие транзакции не достигли успеха.
Работа по встраиванию техник управления конкуренцией в алгоритмы без препятствий выполнялась главным образом в контексте STM-систем, так что менеджер конкуренции может быть вызван непосредственно из реализации STM. Таким образом, программисту, использующему реализацию STM, не приходится беспокоиться о том, как в систему интегрировано управление конкуренцией; однако это не относится к случаю интеграции механизма управления конкуренцией в непосредственные реализации структур данных без препятствий.
Одним из вариантов является встраивание программистом вызовов менеджера конкуренции вручную, однако этот подход довольно утомителен и приводит к появлению ошибок. Геррауи и др. [ ] предложили версию подхода, в которой менеджер конкуренции рассматривается как детектор ошибок. Авторы также исследовали вопрос о том, какие гарантии прогресса и какими детекторами ошибок могут быть обеспечены.