Ссылка загрузки / магазин-условная - 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 .
Смотрите также
использованная литература
- Дженсен, Эрик Х .; Хагенсен, Гэри У .; Бротон, Джеффри М. (ноябрь 1987 г.). Новый подход к эксклюзивному доступу к данным в мультипроцессорах с общей памятью (PDF) (Технический отчет). Ливерморская национальная лаборатория Лоуренса. UCRL-97663. Архивировано из оригинального (PDF) 02.02.2017 . Проверено 22 февраля 2012 .
- Брунер, Джон Д .; Хагенсен, Гэри У .; Дженсен, Эрик Х .; Паттин, Джей К.; Бротон, Джеффри М. (11 ноября 1987 г.). Cache Coherence на S-1 AAP (PDF) (Технический отчет). Ливерморская национальная лаборатория Лоуренса. UCRL-97646. Архивировано 2 февраля 2017 года из оригинального (PDF) . Проверено 10 ноября 2013 года .
- Detlefs, D .; Martin, P .; Moir, M .; Стил-младший, Гай Л. (2001). «Бесконтактный подсчет ссылок». PODC '01 Материалы двадцатого ежегодного симпозиума ACM по принципам распределенных вычислений . ACM. С. 190–9. CiteSeerX 10.1.1.92.8221 . DOI : 10.1145 / 383962.384016 . ISBN 1-58113-383-9.
- Рейнхольц, Кирк (декабрь 2004 г.). "Атомарные указатели подсчета ссылок" . Журнал пользователей C / C ++ .
- Сайты, Р.Л. (февраль 1993 г.). «Архитектура Alpha AXP». Comm. ACM . 36 (2): 33–44. DOI : 10.1145 / 151220.151226 .