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

Сделанное Херлихи и др. [15] наблюдение, заключающееся в том, что более слабые условия прогресса позволяют создавать более простые и практичные алгоритмы, позволило Херлихи определить еще более слабое условие: ''алгоритм без препятствий'' не гарантирует, что операция завершится, за исключением случаев, если она не встречает препятствий от других операций. По сравнению с алгоритмами без блокировки алгоритмы без препятствий проще в разработке, проще по структуре и быстрее работают в условиях общего случая без конкуренции. Обратной стороной этих преимуществ алгоритмов без препятствий является потенциальная возможность динамической взаимоблокировки (livelock), при которой две или несколько операций постоянно вмешиваются в работу друг друга в бесконечном цикле. Эта проблема имеет не только теоретическую значимость; она встречалась и на практике [16]. К счастью, можно довольно легко устранить возможность взаимоблокировки при помощи механизмов контроля конкуренции, способных вмешиваться в процесс выполнения операций во избежание взаимного вмешательства.

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

Серьезные трудности, сопряженные с разработкой и проверкой корректности неблокирующих структур данных, мотивировали исследователей к изучению инструментов для их построения, вместо того чтобы самим заниматься непосредственной разработкой таких структур. В частности, многообещающим направлением оказалась транзакционная память ([5, 17, 23]). Транзакционная память позволяет программистам выделять сегменты кода, которые могут быть исполнены автоматически, а система с транзакционной памятью (реализованная в аппаратной или программной форме либо в виде их сочетания) ответственна за управление взаимодействием между одновременными транзакциями, обеспечивающим атомарность. Далее будут рассматриваться системы с программной транзакционной памятью (software transactional memory, STM).

Гарантия прогресса для параллельной структуры данных, реализованной при помощи STM, зависит от реализации конкретной STM. Можно охарактеризовать условия прогресса реализации транзакционной памяти в терминах системы потоков, в которой каждая операция на совместно используемой структуре данных выполняется путем последовательных попыток применения транзакции вплоть до успешного завершения. В этом контексте можно говорить, что реализация транзакционной памяти является реализацией без препятствий, если она гарантирует, что в случае, если поток последовательно выполняет транзакции и в конечном итоге больше не встречает помех со стороны других потоков, то он в конечном итоге успешно завершает транзакцию.