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

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

Эффективность неблокирующих STM в общем случае планомерно растет [ ], и нет причины полагать, что неблокирующие STM не могут успешно конкурировать с блокирующими в общем случае, т.е. до тех пор, пока система не решит, что одна транзакция не должна ждать другую, которая была задержана (такая функция недоступна у блокирующих STM).

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

Еще один любопытный вопрос, который пока, по-видимому, остается открытым, заключается в том, являются ли затраты на внедрение более сильных условий прогрессf при неблокирующей реализации принципиально более высокими, чем в случае отсутствия препятствий. На данный момент общий консенсус заключается в том, что это скорее так. Известно, что существует фундаментальное различие между отсутствием препятствий и отсутствием блокировок в системах, поддерживающих только операции чтения и записи: в этой модели можно обеспечить консенсус в системах без препятствий, но нельзя – в системах без блокировок [ ]. Это весьма любопытное наблюдение, к сожалению, почти неактуально с практической точки зрения, поскольку все современные мультипроцессоры с разделяемой памятью поддерживают более сильные примитивы синхронизации – такие как CAS – с помощью которых можно легко найти консенсус, и даже без ожидания. Таким образом, интересно было бы узнать, существует ли фундаментальное различие в эффективности реальных систем между случаями без блокировки и без препятствий.

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