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

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

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

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

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