YaChudo

Load-link/store-conditional

Переглядів: 0. Оновлено 05.11.2026.

Load-linked/store-conditional[1] (LL/SC), іноді також відомі як load-reserved/store-conditional[2] (LR/SC), — це пара інструкцій, що використовуються в багатопотоковому виконанні для забезпечення синхронізації. Інструкція load-linked повертає поточне значення комірки пам'яті, тоді як наступна інструкція store-conditional для тієї самої комірки пам'яті записує нове значення лише в тому разі, якщо після виконання load-linked ця комірка не була змінена. Разом ці інструкції реалізують неблокувальну, атомарну операцію типу читання-модифікація-запис.

Інструкцію «load-linked» також називають load-link,[3] load-reserved,[2] або load-locked.

Механізм LL/SC був уперше[4] запропонований Єнсеном, Гагенсеном і Бротоном для багатопроцесорної системи S-1 AAP[1] у Ліверморській національній лабораторії Лоуренса.

Порівняння LL/SC та compare-and-swap

Якщо відбулися будь-які оновлення, інструкція store-conditional гарантовано завершиться невдачею, навіть якщо значення, прочитане інструкцією load-linked, згодом було відновлено. Таким чином, пара LL/SC є потужнішою за операцію читання з подальшим compare-and-swap (CAS), яка не виявляє оновлень, якщо старе значення було відновлено (див. проблема ABA).

Реальні реалізації LL/SC не завжди завершуються успішно навіть за відсутності одночасних оновлень відповідної комірки пам'яті. Будь-які виняткові події між двома операціями, такі як перемикання контексту, інша інструкція load-linked або навіть (на багатьох платформах) будь-яка інша операція завантаження чи запису, можуть призвести до хибної невдачі store-conditional. Старіші реалізації завершуються невдачею, якщо через шину пам'яті транслюються будь-які оновлення. Дослідники називають це слабкою реалізацією LL/SC, оскільки вона порушує роботу багатьох теоретичних алгоритмів LL/SC.[5] Поняття «слабкості» є відносним, і деякі слабкі реалізації придатні для використання в окремих алгоритмах.

LL/SC складніше емулювати, ніж CAS. Крім того, зупинка виконання коду між парними інструкціями LL/SC, наприклад під час покрокового виконання програми, може перешкоджати її подальшому просуванню, що ускладнює налагодження.[6]

Проте LL/SC еквівалентна CAS у тому сенсі, що будь-який із цих примітивів можна реалізувати через інший за O(1) і в безочікувальний спосіб.[7][8]

Реалізації

Інструкції LL/SC підтримуються такими архітектурами:

Деякі процесори вимагають, щоб адреса, до якої здійснюється ексклюзивний доступ, була налаштована в режимі наскрізного запису (write-through).

Зазвичай процесори відстежують адресу, завантажену інструкцією load-linked, на рівні рядка кеша або іншої одиниці гранулярності. Тому будь-яка модифікація будь-якої частини цього рядка кешу (незалежно від того, чи це store-conditional з іншого ядра, чи звичайна операція запису) є достатньою, щоб інструкція store-conditional завершилася невдачею.

Усі ці платформи надають слабку реалізацію LL/SC. Реалізація PowerPC дозволяє, щоб між інструкціями LL і SC виконувалися операції завантаження й навіть запису до інших рядків кеша (хоча такий підхід є вразливим до хибного спільного використання рядків кешу). Це дає змогу реалізувати, наприклад, неблокувальний підрахунок посилань за наявності змінюваних графів об'єктів із довільним повторним використанням лічильників (що в іншому разі потребувало б подвійний compare-and-swap (DCAS)). Архітектура RISC-V забезпечує на архітектурному рівні гарантію зрештою успішного завершення послідовностей LL/SC обмеженої довжини.

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

Під час проєктування архітектури load-store LL/SC має дві переваги над CAS: операції читання й запису є окремими інструкціями, як того вимагає філософія цієї архітектури (і конвеєрної архітектури); крім того, обидві інструкції використовують лише два регістри (адресу та значення), що природно відповідає поширеним архітектурі команд з двома операндами. Натомість CAS потребує трьох регістрів (адреси, старого значення й нового значення) і залежності між прочитаним та записуваним значеннями. Архітектура x86, будучи CISC-архітектурою, не має такого обмеження; хоча сучасні процесори можуть внутрішньо перетворювати інструкцію CAS на окремі мікрооперації LL/SC.

Розширення

Апаратні реалізації LL/SC зазвичай не підтримують вкладення пар LL/SC.[18] Механізм вкладених LL/SC може використовуватися для реалізації примітива MCAS (багатослівний CAS, у якому слова можуть бути розташовані в різних місцях пам'яті).[19] У 2013 році Тревор Браун, Фейт Еллен і Ерік Рупперт реалізували програмне розширення LL/SC для кількох адрес (яке вони назвали LLX/SCX), що ґрунтується на автоматичному генеруванні коду.[20] Вони використали його для реалізації однієї з найпродуктивніших конкурентних структур даних типу двійкове дерево пошуку (точніше, хроматичне дерево), яка за продуктивністю дещо перевершила реалізацію списку з пропусками на основі CAS у JDK.[21]

Див. також

Примітки

  1. ↑ а б S-1 project. Stanford Computer Science wiki. 30 листопада 2018. Архів оригіналу за 24 листопада 2020. Процитовано 18 липня 2026.
  2. ↑ а б в Andrew Waterman; Krste Asanović, ред. (7 травня 2017). 7.2 Load-Reserved/Store-Conditional Instructions. The RISC-V Instruction Set Manual, Volume 1: User-Level ISA, Version 2.2 (PDF).
  3. ↑ US20030217115A1, Rowlands, Joseph, "Load-linked/store conditional mechanism in a CC-NUMA system", issued 2003-11-20 
  4. ↑ Herlihy, Maurice (1 листопада 1993). A methodology for implementing highly concurrent data objects. ACM Transactions on Programming Languages and Systems. 15 (5): 745—770. doi:10.1145/161468.161469. ISSN 0164-0925.
  5. ↑ Beckmann, Nathan. Synchronization (PDF). 15-740: Computer Architecture, Fall 2018. Carnegie Mellon University. Процитовано 23 квітня 2021.
  6. ↑ Keno Fischer (2 травня 2020). Julia 1.5 Feature Preview: Time Traveling (Linux) Bug Reporting. Процитовано 14 травня 2020.
  7. ↑ Anderson, James H.; Moir, Mark (20 серпня 1995). Universal constructions for multi-object operations. Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing - PODC '95. New York, NY, USA: Association for Computing Machinery. с. 184—193. doi:10.1145/224964.224985. ISBN 978-0-89791-710-0.
  8. ↑ James H. Anderson; Mark Moir (1995). Universal constructions for multi-object operations. PODC '95 Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing. ACM. с. 184—193. doi:10.1145/224964.224985. ISBN 0-89791-710-3. S2CID 8204331. See their Table 1, Figures 1 & 2 and Section 2 in particular.
  9. ↑ а б Alpha Architecture Reference Manual (PDF). с. 4–9~4–12. Процитовано 26 січня 2024.
  10. ↑ а б Alpha Architecture Reference Manual (PDF). с. 4–13~4–15. Процитовано 26 січня 2024.
  11. ↑ May, Cathy; Silha, Ed; Simpson, Eick; Warren, Hank (1993). The PowerPC architecture: A SPECIFICATION FOR A NEW FAMILY OF RISC PROCESSORS. Morgan Kaufmann PUblishers, Inc. с. 336—338, 465. ISBN 1-55860-316-6.
  12. ↑ Kacmarcik, Cary (1995). Optimizing PowerPC Code. Addison-Wesley Publishing Company. с. 71–72. ISBN 0-201-40839-2.
  13. ↑ APPLICATION NOTE MIPS R4000 Synchronization Primitives (PDF). с. 9. Архів оригіналу (PDF) за 27 грудня 2023. Процитовано 27 грудня 2023.
  14. ↑ APPLICATION NOTE MIPS R4000 Synchronization Primitives (PDF). с. 5. Архів оригіналу (PDF) за 27 грудня 2023. Процитовано 27 грудня 2023.
  15. ↑ ARM11 MPCore™ Processor Revision: r2p0 Technical Reference Manual. с. 301-302(8-7,8-8). Процитовано 14 грудня 2023.
  16. ↑ Arm®v8-M Architecture Reference Manual. с. 278. Процитовано 14 грудня 2023.
  17. ↑ ARMv8-A Synchronization primitives. с. 6. Процитовано 14 грудня 2023.
  18. ↑ James R. Larus; Ravi Rajwar (2007). Transactional Memory. Morgan & Claypool. с. 55. ISBN 978-1-59829-124-7.
  19. ↑ Keir Fraser (Лютий 2004). Practical lock-freedom (PDF) (Технічний звіт). University of Cambridge Computer Laboratory. с. 20. UCAM-CL-TR-579.
  20. ↑ Brown, Trevor; Ellen, Faith; Ruppert, Eric (2013). Pragmatic primitives for non-blocking data structures (PDF). PODC '13 Proceedings of the 2013 ACM symposium on Principles of distributed computing. ACM. с. 13—22. arXiv:1712.06688. doi:10.1145/2484239.2484273. ISBN 978-1-4503-2065-8. S2CID 6537417. See also slides
  21. ↑ Trevor Brown; Faith Ellen; Eric Ruppert (2014). A general technique for non-blocking trees (PDF). PPoPP '14 ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. ACM. с. 329—342. arXiv:1712.06687. doi:10.1145/2555243.2555267. ISBN 978-1-4503-2656-8. S2CID 9442380.

Джерело: стаття у Вікіпедії та історія редагувань (автори).