Ссылка загрузки / магазин-условная - Load-link/store-conditional

В информатике , привязанная к загрузке / условная запись ( LL / SC ), иногда известная как зарезервированная загрузка / условная запись ( LR / SC ), представляет собой пару инструкций, используемых в многопоточности для достижения синхронизации . Load-link возвращает текущее значение ячейки памяти, в то время как последующее условие сохранения в той же ячейке памяти сохранит новое значение только в том случае, если с момента загрузки ссылки не произошло никаких обновлений в этой ячейке. Вместе это реализует атомарную операцию чтения-изменения-записи без блокировки .

"Load-сшитый" также известен как нагрузки линии связи , нагрузки защищены и нагрузки с блокировкой .

LL / SC был первоначально предложен Дженсеном, Хагенсеном и Бротоном для мультипроцессора S-1 AAP в Ливерморской национальной лаборатории Лоуренса .

Сравнение LL / SC и сравнение и замена

Если произошли какие-либо обновления, store-conditional гарантированно завершится ошибкой, даже если значение, прочитанное с помощью load-link, с тех пор было восстановлено. Таким образом, пара LL / SC сильнее, чем чтение с последующим сравнением и заменой (CAS), которое не обнаружит обновления, если было восстановлено старое значение (см. Проблему ABA ).

Реальные реализации LL / SC не всегда успешны, даже если нет одновременных обновлений в рассматриваемой области памяти. Любые исключительные события между двумя операциями, такие как переключение контекста , другая ссылка загрузки или даже (на многих платформах) другая операция загрузки или сохранения, вызовут ложный сбой условия сохранения. Старые реализации потерпят неудачу, если по шине памяти будут транслироваться какие-либо обновления. Исследователи называют это слабым LL / SC, поскольку он нарушает многие теоретические алгоритмы LL / SC. Слабость относительна, и для некоторых алгоритмов можно использовать некоторые слабые реализации.

LL / SC сложнее эмулировать, чем CAS. Кроме того, остановка выполнения кода между парными инструкциями LL / SC, например, при пошаговом прохождении кода, может предотвратить продвижение вперед, что затрудняет отладку.

Тем не менее, LL / SC эквивалентен CAS в том смысле, что любой примитив может быть реализован в терминах другого, в O (1) и без ожидания .

Реализации

Инструкции LL / SC поддерживаются:

  • Альфа : ldl_l / stl_c и ldq_l / stq_c
  • PowerPC / Power ISA : lwarx / stwcx и ldarx / stdcx
  • MIPS : ll / sc
  • ARM : ldrex / strex (ARMv6 и v7) и ldxr / stxr (версия ARM 8)
  • RISC-V : lr / sc
  • ARC : LLOCK / SCOND

Некоторые ЦП требуют, чтобы адрес, к которому осуществляется доступ, был настроен исключительно в режиме сквозной записи.

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

Все эти платформы обеспечивают слабый LL / SC. Реализация PowerPC позволяет паре LL / SC переносить загрузки и даже сохранять в другие строки кэша (хотя этот подход уязвим для ложного совместного использования строк кэша). Это позволяет реализовать, например, подсчет ссылок без блокировок при изменении графов объектов с произвольным повторным использованием счетчиков (что в противном случае требует двойного сравнения и замены , DCAS). RISC-V обеспечивает архитектурную гарантию возможного прогресса для последовательностей LL / SC ограниченной длины.

Некоторые реализации ARM определяют блоки, зависящие от платформы, в диапазоне от 8 байтов до 2048 байтов, и попытка LL / SC в любом заданном блоке завершается ошибкой, если между LL и SC имеется нормальный доступ к памяти внутри одного и того же блока. Другие реализации ARM терпят неудачу, если есть модификация где-нибудь во всем адресном пространстве. Первая реализация более надежна и практична.

LL / SC имеет два преимущества перед CAS при проектировании архитектуры загрузки-сохранения : чтение и запись - это отдельные инструкции, как того требует философия проектирования (и конвейерная архитектура ); и обе инструкции могут быть выполнены с использованием только двух регистров (адреса и значения), естественно вписываясь в общие ISA с двумя операндами . CAS, с другой стороны, требует трех регистров (адрес, старое значение, новое значение) и зависимости между прочитанным значением и записанным значением. x86 , будучи архитектурой CISC , не имеет этого ограничения; хотя современные микросхемы вполне могут внутренне переводить инструкцию CAS в отдельные микрооперации LL / SC .

Расширения

Аппаратные реализации LL / SC обычно не допускают вложения пар LL / SC. Механизм вложенности LL / SC может использоваться для обеспечения примитива MCAS (многословный CAS, где слова могут быть разбросаны). В 2013 году Тревор Браун, Фейт Эллен и Эрик Рупперт реализовали в программном обеспечении многоадресное расширение LL / SC (которое они называют LLX / SCX), основанное на автоматической генерации кода; они использовали его для реализации одного из наиболее эффективных параллельных двоичных деревьев поиска (на самом деле хроматического дерева ), немного превосходящего реализацию списка пропусков на основе JDK CAS .

Смотрите также

использованная литература