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

Важный практический аспект использования алгоритмов без препятствий заключается в том, каким образом выполняется управление конкуренцией при ее возникновении. Представляя принцип вычисления без препятствий, Херлихи и др. [15] пояснили, что контроль конкуренции необходим для ускорения прогресса в свете ее наличия, поскольку в этом случае алгоритмы без препятствий не могут прямо гарантировать прогресс. Однако они не пояснили более конкретно, как использовать механизмы контроля конкуренции на практике.

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

Все менеджеры конкуренции, описанные в вышеупомянутых работах, являются ситуативными и работают на базе интуиции; не приводится каких-либо попыток анализа того, какие гарантии обеспечиваются менеджерами конкуренции и есть ли такие гарантии вообще. Геррауи и др. [10] сделали первый шаг по направлению к формальному анализу менеджеров конкуренции, показав, что их жадный менеджер конкуренции гарантирует, что каждая транзакция в конечном итоге завершается. Однако использование жадного менеджера конкуренции приводит к тому, что алгоритм становится блокирующим, так что при доказательстве обязательно приходится предполагать, что потоки не потерпят неудачу при выполнении транзакций.

Фич и др. [7] показали, что любой алгоритм без препятствий может быть преобразован в алгоритм, который в любой реальной системе окажется практичным алгоритмом без ожидания. «Практичность» здесь используется по той причине, что гарантия прогресса в случае алгоритма без ожидания зависит от частичной синхронности, существующей в любой реальной системе, однако преобразованный алгоритм технически не является алгоритмом без ожидания, так как этот термин определен в контексте полностью асинхронной системы. Тем не менее, алгоритм, полученный в результате преобразования Фич и др. К алгоритму без препятствий, гарантирует прогресс для удачных транзакций, даже если другие транзакции не достигли успеха.

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

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

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