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

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

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