Синхронизация без ожидания: различия между версиями

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

Херлихи и др. [ ] предложили Dynamic STM (DSTM) – первый STM-алгоритм, являющийся динамическим в следующих смыслах: (1) новые объекты могут распределяться «на лету», и к ним могут впоследствии обращаться транзакции; (2) транзакциям нет необходимости заранее знать, к каким объектам они будут обращаться. Эти два свойства делают алгоритм DSTM намного более полезным, чем предыдущие версии STM для программирования динамических структур данных. В результате стали возможными неблокирующие реализации таких сложных структур совместно используемых данных, как сбалансированные деревья поиска, списки с пропусками, динамические хеш-таблицы и т. п.

Подход «без препятствий» сыграл ключевую роль в разработке обоих вышеупомянутых результатов: Херлихи и др. [ ] могли сконцентрироваться на функциональности и корректности DSTM, не заботясь о том, как обеспечить более сильные гарантии прогресса – такие как отсутствие блокировок.

Появление DSTM и подхода «без препятствий» привели к разработке множества улучшений и вариаций различными исследовательскими группами, большая часть которых также предпочитала подход «без препятствий». С другой стороны, Харрис и Фрейзер [ ] предложили динамическую версию STM под названием OSTM, обладавшую преимуществами DSTM, но при этом являвшуюся неблокирующей. Эксперименты, проведенные в Рочестерском университете [20], показали, что на некоторых рабочих нагрузках DSTM превосходит эффективностью OSTM на порядок величины, однако на других нагрузках OSTM вдвое превосходит DSTM. Эти различия, вероятно, связаны с разными проектными решениями, которые в большинстве случаев являются ортогональными к условию прогресса, поэтому не вполне понятно, какое заключение можно сделать в данном случае по поводу влияния выбранного условия прогресса на эффективность работы алгоритма.

Возможно, более непосредственное сравнение можно выполнить для другой пары алгоритмов, один из которых также является алгоритмом без препятствий от Херлихи и др. [ ], а второй – аналогичным алгоритмом, но без блокировок, который представили Харрис и Фрейзер [ ]. Эти алгоритмы, разработанные независимо друг от друга, реализуют инструкцию MCAS (CAS, обобщенную на случай обращения к M независимо выбранным областям памяти). Эти два алгоритма очень похожи; проведенное независимое сравнение обнаружило, что разница между ними связана лишь с желанием Харриса и Фрейзера разработать реализацию без блокировок. В результате их алгоритм стал несколько более сложным, к тому же ему требуется не менее 3M + 1 операций CAS, тогда как алгоритм Херлихи и др. [ ] требует только 2M + 1 операций. Непосредственного сравнения эффективности этих двух алгоритмов не производилось, однако можно предполагать, что алгоритм без препятствий будет эффективнее алгоритма без блокировок – особенно в отсутствие конфликтующих операций MCAS.

Конструирование блокирующих STM значительно проще, но, хотя во многих случаях они оказываются достаточными, это не всегда верно. Рассмотрим, например, обработчик прерываний, использующий данные совместно с прерванным потоком. Прерванный поток не запустится заново до того момента, как обработчик прерываний закончит работы, поэтому очень важно, чтобы прерванный поток не блокировал обработчика прерываний. Таким образом, если планируется использование STM для упрощения кода доступа к этим совместно используемым данным, то STM должна быть неблокирующей. Это стимулирует авторов к продолжению исследований, направленных на улучшение неблокирующих STM и на понимание фундаментального разрыва, если таковой существует, между блокирующими и неблокирующими STM.

Эффективность неблокирующих STM в общем случае планомерно растет [ ], и нет причины полагать, что неблокирующие STM не могут успешно конкурировать с блокирующими в общем случае, т.е. до тех пор, пока система не решит, что одна транзакция не должна ждать другую, которая была задержана (такая функция недоступна у блокирующих STM).

Исследователи пришли к выводу, что наличие разрыва между блокирующими и неблокирующими STM можно доказать согласно некоторой метрике, однако в общем случае он не повлечет значительной разницы в эффективности. И в самом деле, Аттийя и др. [ ] продемонстрировали разницу между алгоритмами без препятствий и блокирующими алгоритмами согласно метрике, учитывающей количеством различных базовых объектов, к которым обращается реализация, плюс количество «остановок памяти», которые измеряют, сколько раз реализация может столкнуться с конкуренцией за переменную из другого потока. Этот результат интересен сам по себе, однако неясно, окажется ли он полезным для решения вопроса о том, следует ли использовать блокирующие объекты или объекты без препятствий, сама по себе метрика не учитывает время, потраченное на ожидание при блокирующих реализациях, и потому ошибается в их пользу. На данный момент сохраняется оптимистичная надежда на то, что STM можно сделать неблокирующими, не жертвуя значительно эффективностью в общем случае.

Еще один любопытный вопрос, который пока, по-видимому, остается открытым, заключается в том, являются ли затраты на внедрение более сильных условий прогрессf при неблокирующей реализации принципиально более высокими, чем в случае отсутствия препятствий. На данный момент общий консенсус заключается в том, что это скорее так. Известно, что существует фундаментальное различие между отсутствием препятствий и отсутствием блокировок в системах, поддерживающих только операции чтения и записи: в этой модели можно обеспечить консенсус в системах без препятствий, но нельзя – в системах без блокировок [ ]. Это весьма любопытное наблюдение, к сожалению, почти неактуально с практической точки зрения, поскольку все современные мультипроцессоры с разделяемой памятью поддерживают более сильные примитивы синхронизации – такие как CAS – с помощью которых можно легко найти консенсус, и даже без ожидания. Таким образом, интересно было бы узнать, существует ли фундаментальное различие в эффективности реальных систем между случаями без блокировки и без препятствий.

Для того чтобы всерьез повлиять на направление разработок, подобные результаты должны рассматривать эффективность алгоритма в общем случае либо некоторые другие метрики (например, объем памяти), актуальные для повседневного использования. Многие результаты для нижних границ подчеркивают различие между сложностью в наихудшем случае, которое не обязательно должно напрямую влиять на решения о разработке, поскольку наихудшие случаи встречаются весьма редко. До сих пор все попытки определить различие при помощи потенциально полезных метрик лишь приводили к более сильным результатам, чем предполагались возможными. Лучанго, Мойр и Шавит [18] сделали попытку определить разницу в количестве инструкций CAS, необходимых для нахождения консенсуса в отсутствие конкуренции, однако обнаружили, что эта метрика является не особенно полезной, поскольку смогли найти реализацию без ожидания, не использующую инструкции CAS в отсутствие конкуренции. Вторая попытка [ ] заключалась в определении различия согласно метрике сложности в шагах для алгоритма без препятствий, которая считает количество шагов, требующихся для выполнения операции в случае, если операция более не встретит конкуренции. Авторы знали о возможности реализации DCAS без препятствий с константной сложностью в шагах и попытались доказать невозможность этого для DCAS без блокировок, однако в результате получили алгоритм, выполняющий эту задачу. Их опыт доказывает, что помимо непосредственных преимуществ алгоритмов без препятствий они к тому же могут оказаться полезным плацдармом для перехода к алгоритмам с более сильными гарантиями прогресса.

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