Синхронизация без ожидания
Постановка задачи
Традиционный подход с использованием блокировки для поддержки целостности совместно используемых данных в параллельных программах имеет значительные недостатки, относящиеся к таким областям, как разработка программного обеспечения, надежность, эффективность и масштабируемость. В силу этого в последние несколько десятилетий усилия исследователей прилагались главным образом к неблокирующим механизмам синхронизации.
Основополагающая статья Мориса Херлихи «Синхронизация без ожидания» [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. Можно охарактеризовать условия прогресса реализации транзакционной памяти в терминах системы потоков, в которой каждая операция на совместно используемой структуре данных выполняется путем последовательных попыток применения транзакции вплоть до успешного завершения. В этом контексте можно говорить, что реализация транзакционной памяти является реализацией без препятствий, если она гарантирует, что в случае, если поток последовательно выполняет транзакции и в конечном итоге больше не встречает помех со стороны других потоков, то он в конечном итоге успешно завершает транзакцию.