Синхронизация без ожидания
Постановка задачи
Традиционный подход с использованием блокировки для поддержки целостности совместно используемых данных в параллельных программах имеет значительные недостатки, относящиеся к таким областям, как разработка программного обеспечения, надежность, эффективность и масштабируемость. В силу этого в последние несколько десятилетий усилия исследователей прилагались главным образом к неблокирующим механизмам синхронизации.
Основополагающая статья Мориса Херлихи «Синхронизация без ожидания» [12] была посвящена проблеме реализации параллельных структур данных без ожидания, таким образом, чтобы каждая операция на этой структуре данных завершалась за конечное количество шагов вызывающим ее потоком, независимо от того, насколько быстро или медленно выполняются другие потоки и даже от того, не происходит ли у некоторых или всех из них окончательной остановки. Реализации, основанные на блокировках, не являются вариантами без ожидания, поскольку в период, когда один поток удерживает блокировку, другие могут предпринять неограниченное количество шагов в ожидании блокировки. Требование реализации без ожидания позволяет потенциально избавиться от присущих блокировкам недостатков.
В первой части статьи Херлихи исследовалась сила различных примитивов синхронизации применительно к вычислениям без ожидания. Он определил число консенсуса для конкретного примитива как максимальное число потоков, для которого мы способны обеспечить консенсус без ожиданий при помощи этого примитива (наряду с использованием регистров типа чтение-запись). Задача достижения консенсуса требует, чтобы участвующие в ней потоки согласовали свои значения (например, «истина» или «ложь») на фоне других значений, содержащихся в потоках. Возможность решения этой задачи является ключевым индикатором силы примитива синхронизации, поскольку она является основным компонентом множества задач, естественно возникающих при параллельных вычислениях. Например, в системах с программной транзакционной памятью потоки должны согласиться с тем, что конкретная транзакция должна быть принята или отклонена.
Херлихи установил иерархию примитивов синхронизации в соответствии с их числом консенсуса. Он показал, что (1) число консенсуса регистров типа чтение-запись равно 1 (в силу чего задача консенсуса без ожидания не может быть решена даже для двух потоков), (2) число консенсуса для стеков и очередей FIFO равно 2, (3) существуют так называемые универсальные примитивы с числом консенсуса, равным [math]\displaystyle{ \infty }[/math]. Типичными примерами таких примитивов являются сравнение с обменом (compare-and-swap, CAS) и подход с «условной записью» (load-linked/store-conditional, LL/SC).
Иерархия Херлихи была более детально рассмотрена в нескольких статьях. В них было показано, что относительно небольшие изменения модели или семантики примитивов могут оказать неожиданно значимое влияние на результат. Большая часть этих публикаций представляет главным образом теоретический интерес. Основной практический аспект иерархии Херлихи заключается в том, что для поддержки эффективной синхронизации без ожидания в общем случае требуются универсальные примитивы. Признавая этот факт, все современные мультипроцессоры с разделяемой памятью предоставляют какие-либо универсальные примитивы.
Кроме того, Херлихи показал, что решение задачи о консенсусе может использоваться для реализации без ожидания любого совместно используемого объекта и, таким образом, для этой цели подойдет любой универсальный примитив. Он продемонстрировал свою идею при помощи так называемого универсального построения, которое принимает на вход последовательный код объекта и создает реализацию без ожидания для этого объекта, используя консенсус для разрешения состояния гонки между параллельными операциями. Несмотря на важные практические последствия этого результата, само по себе универсальное построение оказалось весьма непрактичным. Основная идея заключалась в построении списка операций, используя консенсус для определения порядка операций, и последующем итерационном выполнении потоков над списком, применяющих операции для определения текущего состоянии объекта. Построение требовало [math]\displaystyle{ O(N^3) \; }[/math] памяти, чтобы гарантировать достаточное количество сохраненных операций для определения текущего состояния. Оно также оказалось очень медленным, поскольку многим потокам приходилось заново вычислять одну и ту же информацию, что препятствовало распараллеливанию операций.
Впоследствии Херлихи [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] пояснили, что контроль конкуренции необходим для ускорения прогресса в свете ее наличия, поскольку в этом случае алгоритмы без препятствий не могут прямо гарантировать прогресс. Однако они не пояснили более конкретно, как именно использовать механизмы контроля конкуренции на практике.
Впоследствии Херлихи др. [16] представили динамическую STM-систему (см. следующий раздел), которая предоставляет интерфейс для модульного инструмента управления конкуренцией (менеджера конкуренции), позволяющий экспериментировать с альтернативными менеджерами. Шерер и Скотт [22] экспериментировали с несколькими такими альтернативными менеджерами и обнаружили, что выбор лучшего менеджера конкуренции зависит от рабочей нагрузки. Геррауи и др. [9] описали подход к реализации, поддерживающий замену менеджеров конкуренции «на лету» в ответ на изменение условий рабочей нагрузки.
Все менеджеры конкуренции, описанные в вышеупомянутых работах, являются ситуативными и работают на базе интуиции; не приводится каких-либо попыток анализа того, какие гарантии обеспечиваются менеджерами конкуренции и есть ли такие гарантии вообще. Геррауи и др. [10] сделали первый шаг по направлению к формальному анализу менеджеров конкуренции, показав, что их жадный менеджер конкуренции Greedy гарантирует, что каждая транзакция в конечном итоге завершается. Однако использование менеджера конкуренции Greedy приводит к тому, что алгоритм становится блокирующим, так что при доказательстве обязательно приходится предполагать, что потоки не потерпят неудачу при выполнении транзакций.
Фич и др. [7] показали, что любой алгоритм без препятствий может быть преобразован в алгоритм, который в любой реальной системе окажется практически алгоритмом без ожидания. Термин «практически» здесь применен по той причине, что гарантия прогресса в случае алгоритма без ожидания зависит от частичной синхронности, существующей в любой реальной системе, однако преобразованный алгоритм технически не является алгоритмом без ожидания, так как этот термин определен в контексте полностью асинхронной системы. Тем не менее, алгоритм, полученный в результате преобразования Фич и др. алгоритма без препятствий, гарантирует прогресс для удачных транзакций, даже если другие транзакции не достигли успеха.
Работа по встраиванию техник управления конкуренцией в алгоритмы без препятствий выполнялась главным образом в контексте STM-систем, так что менеджер конкуренции может быть вызван непосредственно из реализации STM. Таким образом, программисту, использующему реализацию STM, не приходится беспокоиться о том, как управление конкуренцией интегрировано в систему; однако это не относится к случаю интеграции механизма управления конкуренцией в непосредственные реализации структур данных без препятствий.
Одним из вариантов является встраивание программистом вызовов менеджера конкуренции вручную, однако этот подход довольно утомителен и приводит к появлению ошибок. Геррауи и др. [11] предложили версию подхода, в которой менеджер конкуренции рассматривается как абстрактный детектор ошибок. Авторы также исследовали вопрос о том, какие гарантии прогресса и какими детекторами ошибок могут быть обеспечены.
Аттия и др. [4], а также Агилера и др. [2] предложили изменить семантику операций над структурой данных таким образом, чтобы они могли в случае наличия конкуренции возвращать специальное значение, в результате чего управление конкуренцией можно было бы осуществлять за рамками структуры данных. Однако этот подход по-прежнему возлагает на программиста обязанность следить за тем, чтобы эти специальные значения всегда возвращались операцией, которая не может завершиться из-за наличия конкуренции, и чтобы возвращалось корректное специальное значение, соответствующее предписанной семантике.
Еще одним вариантом является использование поддержки системы, гарантирующей, что вызовы менеджера конкуренции выполняются достаточно часто для обеспечения прогресса. Эта поддержка может выражаться в форме скомпилированных вызовов, поддержки во время выполнения, сигналов, отправляемых по истечении установленного таймера, и других аналогичных способов. Однако все эти подходы имеют недостатки – такие как невозможность применения в универсальных средах, непереносимость и т. п.
Поскольку задача разработки и проверки непосредственных реализаций совместно используемых структур данных без препятствий по-прежнему остается актуальной, а различные подходы по встраиванию в них механизмов контроля конкуренции не лишены недостатков, использование таких инструментов, как STM со встроенными интерфейсами управления конкуренцией, оказывается самым удобным способом построения неблокирующих структур данных.
Применение
Подход «без препятствий» к созданию неблокирующих механизмов синхронизации предложили Херлихи и др. [15], использовавшие его для разработки двухсторонней очереди на базе широко распространенной команды CAS (сравнение с обменом). Всем предыдущим неблокирующим двухсторонним очередям либо требовались экзотические команды синхронизации, такие как двойное сравнение с обменом (DCAS), либо приходилось мириться с тем, что операции с противоположных концов очереди всегда конфликтовали друг с другом.
Херлихи и др. [16] предложили Dynamic STM (DSTM) – первый STM-алгоритм, являющийся динамическим в следующих смыслах: (1) новые объекты могут распределяться «на лету», и к ним могут впоследствии обращаться транзакции; (2) транзакциям нет необходимости заранее знать, к каким объектам они будут обращаться. Эти два свойства делают алгоритм DSTM намного более полезным, чем предыдущие версии STM для программирования динамических структур данных. В результате стали возможными неблокирующие реализации таких сложных структур совместно используемых данных, как сбалансированные деревья поиска, списки с пропусками, динамические хеш-таблицы и т. п.
Подход «без препятствий» сыграл ключевую роль в разработке обоих вышеупомянутых результатов: Херлихи и др. [16] могли сконцентрироваться на функциональности и корректности DSTM, не заботясь о том, как обеспечить более сильные гарантии прогресса – такие как отсутствие блокировок.
Появление DSTM и подхода «без препятствий» привели к разработке множества улучшений и вариаций различными исследовательскими группами, большая часть которых также предпочитала подход «без препятствий». С другой стороны, Харрис и Фрейзер [8] предложили динамическую версию STM под названием OSTM, обладавшую преимуществами DSTM, но при этом являвшуюся неблокирующей. Эксперименты, проведенные в Рочестерском университете [20], показали, что на некоторых рабочих нагрузках DSTM превосходит эффективностью OSTM на порядок величины, однако на других нагрузках OSTM вдвое превосходит DSTM. Эти различия, вероятно, связаны с разными проектными решениями, которые в большинстве случаев являются ортогональными к условию прогресса, поэтому не вполне понятно, какое заключение можно сделать в данном случае по поводу влияния выбранного условия прогресса на эффективность работы алгоритма.
Возможно, более непосредственное сравнение можно выполнить для другой пары алгоритмов, один из которых также является алгоритмом без препятствий от Херлихи и др. [14], а второй – аналогичным алгоритмом, но без блокировок, который представили Харрис и Фрейзер [8]. Эти алгоритмы, разработанные независимо друг от друга, реализуют инструкцию MCAS (CAS, обобщенную на случай обращения к M независимо выбранным областям памяти). Эти два алгоритма очень похожи; проведенное независимое сравнение обнаружило, что разница между ними связана лишь с желанием Харриса и Фрейзера разработать реализацию без блокировок. В результате их алгоритм стал несколько более сложным, к тому же ему требуется не менее 3M + 1 операций CAS, тогда как алгоритм Херлихи и др. [14] требует только 2M + 1 операций. Непосредственного сравнения эффективности этих двух алгоритмов не производилось, однако можно предполагать, что алгоритм без препятствий будет эффективнее алгоритма без блокировок – особенно в отсутствие конфликтующих операций MCAS.
Открытые вопросы
Поскольку исследования транзакционной памяти выросли из исследований неблокирующих структур данных, поддержка разработки таких структур данных долгое время считалась обязательной для реализаций STM. Однако недавно некоторые исследователи заметили, что по меньшей мере некоторые преимущества транзакционной памяти, связанные с разработкой ПО, могут быть получены и при помощи блокирующих STM. До сих пор продолжаются дискуссии о том, должны ли STM быть неблокирующими и какова цена за достижение этого состояния.
Конструирование блокирующих STM значительно проще, но, хотя во многих случаях они оказываются достаточными, это не всегда верно. Рассмотрим, например, обработчик прерываний, использующий данные совместно с прерванным потоком. Прерванный поток не запустится заново до того момента, как обработчик прерываний закончит работу, поэтому очень важно, чтобы прерванный поток не блокировал обработчика прерываний. Таким образом, если планируется использование STM для упрощения кода доступа к этим совместно используемым данным, то STM должна быть неблокирующей. Это стимулирует авторов к продолжению исследований, направленных на улучшение неблокирующих STM, и к пониманию фундаментального разрыва, если таковой существует, между блокирующими и неблокирующими STM.
Эффективность неблокирующих STM в общем случае планомерно растет [19], и нет причины полагать, что неблокирующие STM не могут успешно конкурировать с блокирующими в общем случае, т.е. до тех пор, пока система не решит, что одна транзакция не должна ждать другую, которая была задержана (такая функция недоступна у блокирующих STM).
Исследователи пришли к выводу, что наличие разрыва между блокирующими и неблокирующими STM можно доказать согласно некоторой метрике, однако в общем случае он не повлечет значительной разницы в эффективности. И в самом деле, Аттийя и др. [3] продемонстрировали разницу между алгоритмами без препятствий и блокирующими алгоритмами согласно метрике, учитывающей количество различных базовых объектов, к которым обращается реализация, плюс количество «остановок памяти», которые показывают, сколько раз реализация может столкнуться с конкуренцией за переменную из другого потока. Этот результат интересен сам по себе, однако неясно, окажется ли он полезным для решения вопроса о том, следует ли использовать блокирующие объекты или объекты без препятствий, поскольку сама по себе метрика не учитывает время, потраченное на ожидание при блокирующих реализациях, и потому ошибается в их пользу. На данный момент сохраняется оптимистичная надежда на то, что STM можно сделать неблокирующими, не жертвуя значительно эффективностью в общем случае.
Еще один любопытный вопрос, который пока, по-видимому, остается открытым, заключается в том, являются ли затраты на внедрение более сильных условий прогресса при неблокирующей реализации принципиально более высокими, чем в случае отсутствия препятствий. На данный момент общий консенсус заключается в том, что это скорее так. Известно, что существует фундаментальное различие между отсутствием препятствий и отсутствием блокировок в системах, поддерживающих только операции чтения и записи: в этой модели можно обеспечить консенсус в системах без препятствий, но нельзя – в системах без блокировок [15]. Это весьма любопытное наблюдение, к сожалению, почти неактуально с практической точки зрения, поскольку все современные мультипроцессоры с разделяемой памятью поддерживают более сильные примитивы синхронизации – такие как CAS – с помощью которых можно легко найти консенсус, и даже без ожидания. Таким образом, интересно было бы узнать, существует ли фундаментальное различие в эффективности реальных систем между случаями без блокировки и без препятствий.
Для того чтобы всерьез повлиять на направление разработок, подобные результаты должны рассматривать эффективность алгоритма в общем случае либо некоторые другие метрики (например, объем памяти), актуальные для повседневного использования. Многие результаты для нижних границ подчеркивают различие между сложностью в наихудшем случае, которое не обязательно должно напрямую влиять на решения о разработке, поскольку наихудшие случаи встречаются весьма редко. До сих пор все попытки определить различие при помощи потенциально полезных метрик лишь приводили к более сильным результатам, чем предполагались возможными. Лучанго, Мойр и Шавит [18] сделали попытку определить разницу в количестве инструкций CAS, необходимых для нахождения консенсуса в отсутствие конкуренции, однако обнаружили, что эта метрика является не особенно полезной, поскольку смогли найти реализацию без ожидания, не использующую инструкции CAS в отсутствие конкуренции. Вторая попытка [6] заключалась в определении различия согласно метрике сложности в шагах для алгоритма без препятствий, которая считает максимальное количество шагов, требующихся для выполнения операции в случае, если операция более не встретит конкуренции. Авторы знали о возможности реализации DCAS без препятствий с константной сложностью в шагах и попытались доказать невозможность этого для DCAS без блокировок, однако в результате получили алгоритм, выполняющий эту задачу. Их опыт доказывает, что помимо непосредственных преимуществ алгоритмов без препятствий они к тому же могут оказаться полезным плацдармом для перехода к алгоритмам с более сильными гарантиями прогресса.
Наконец, хотя множество менеджеров конкуренции оказались эффективными для различных рабочих нагрузок, остается открытым вопрос, можно ли адаптировать один менеджер конкуренции так, чтобы он работал наравне с лучшими при всех вариантах рабочей нагрузки, и насколько близко он может подойти к принятию оптимальных решений об управлении конкуренцией. Результаты, полученные на данный момент, позволяют предположить, что достичь этой цели будет очень непросто. Следовательно, для любой системы главным приоритетом должна быть возможность устранения конкуренции как таковой. К счастью, транзакционная память потенциально способна сделать эту задачу намного более простой, чем модели программирования на основе блокировок, поскольку ей свойственны преимущества мелкомодульной синхронизации без сложности, присущей программированию схем мелкомодульной блокировки.
См. также
Литература
1. Agarwal, A., Cherian, M.: Adaptive backoff synchronization techniques. In: Proceedings of the 16th Annual International Symposium on Computer Architecture, pp. 396-406. ACM Press, New York (1989)
2. Aguilera, M.K., Frolund, S., Hadzilacos, V., Horn, S.L., Toueg, S.: Brief announcement: Abortable and query-abortable objects. In: Proc. 20th Annual International Symposium on Distributed Computing, 2006
3. Attiya, H., Guerraoui, R., Hendler, D., Kouznetsov, P.: Synchronizing without locks is inherently expensive. In: PODC '06: Proceedings of the twenty-fifth Annual ACM Symposium on Principles of Distributed Computing, New York, USA, pp. 300-307. ACM Press (2006)
4. Attiya, H., Guerraoui, R., Kouznetsov, P.: Computing with reads and writes in the absence of step contention. In: Proc. 19th Annual International Symposium on Distributed Computing, 2005
5. Damron, P., Fedorova, A., Lev, Y., Luchangco, V., Moir, M., Nussbaum, D.: Hybrid transactional memory. In: Proc. 12th Symposium on Architectural Support for Programming Languages and Operating Systems, 2006
6. Fich, F., Luchangco, V., Moir, M., Shavit, N.: Brief announce ment: Obstruction-free step complexity: Lock-free DCAS as an example. In: Proc. 19th Annual International Symposium on Distributed Computing, 2005
7. Fich, F., Luchangco, V., Moir, M., Shavit, N.: Obstruction-free algorithms can be practically wait-free. In: Proc. 19th Annual International Symposium on Distributed Computing, 2005
8. Fraser, K., Harris, T.: Concurrent programming without locks. http://www.cl.cam.ac.uk/netos/papers/ 2004-cpwl-submission.pdf (2004)
9. Guerraoui, R., Herlihy, M., Pochon, B.: Polymorphic contention management. In: Proc. 19th Annual International Symposium on Distributed Computing, 2005
10. Guerraoui, R., Herlihy, M., Pochon, B.: Toward a theory of transactional contention managers. In: Proc. 24th Annual ACM Symposium on Principles of Distributed Computing, 2005, pp. 258-264
11. Guerraoui, R., Kapalka, M., Kouznetsov, P.: The weakest failure detector to boost obstruction freedom. In: Proc. 20th Annual International Symposium on Distributed Computing, 2006
12. Herlihy, M.: Wait-free synchronization. ACM Trans. Program. Lang. Syst. 13(1), 124-149 (1991)
13. Herlihy, M.: A methodology for implementing highly concurrent data objects. ACM Trans. Program. Lang. Syst. 15(5), 745-770(1993)
14. Herlihy, M., Luchangco, V., Moir, M.: Obstruction-free mechanism for atomic update of multiple non-contiguous locations in shared memory. US Patent Application 20040034673 (2002)
15. Herlihy, M., Luchangco, V., Moir, M.: Obstruction-free synchronization: Double-ended queues as an example. In: Proceedings of the 23rd International Conference on Distributed Computing Systems, 2003
16. Herlihy, M., Luchangco, V., Moir, M., Scherer III., W.: Software transactional memory for supporting dynamic-sized data structures. In: Proc. 22th Annual ACM Symposium on Principles of Distributed Computing, 2003, pp. 92-101
17. Herlihy, M., Moss, J.E.B.: Transactional memory: Architectural support for lock-free data structures. In: Proc. 20th Annual International Symposium on Computer Architecture, 1993, pp. 289-300
18. Luchangco, V., Moir, M., Shavit, N.: On the uncontended complexity of consensus. In: Proc. 17th Annual International Symposium on Distributed Computing, 2005
19. Marathe, V.J., Moir, M.: Toward high performance nonblocking software transactional memory. In: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming. pp. 227-236, ACM, New York, USA (2008)
20. Marathe, V., Scherer, W., Scott, M.: Adaptive software transactional memory. In: Proc. 19th Annual International Symposium on Distributed Computing, 2005
21. Michael, M., Scott, M.: Nonblocking algorithms and preemption-safe locking on multiprogrammed shared memory multiprocessors. J. Parall.Distrib. Comput. 51(1), 1-26(1998)
22. Scherer, W., Scott, M.: Advanced contention management for dynamic software transactional memory. In: Proc. 24th Annual ACM Symposium on Principles of Distributed Computing, 2005
23. Shavit, N., Touitou, D.: Software transactional memory. Distrib. Comput., Special Issue 10,99-116 (1997)
24. Treiber, R.: Systems programming: Coping with parallelism. Technical Report RJ5118, IBM Almaden Research Center (1986)