Load-linked/store-conditional (LL/SC), іноді також відомі як load-reserved/store-conditional (LR/SC), — це пара інструкцій, що використовуються в багатопотоковому виконанні для забезпечення синхронізації. Інструкція load-linked повертає поточне значення комірки пам'яті, тоді як наступна інструкція store-conditional для тієї самої комірки пам'яті записує нове значення лише в тому разі, якщо після виконання load-linked ця комірка не була змінена. Разом ці інструкції реалізують неблокувальну, атомарну операцію типу читання-модифікація-запис.
Інструкцію «load-linked» також називають load-link, load-reserved, або load-locked.
Механізм LL/SC був уперше запропонований Єнсеном, Гагенсеном і Бротоном для багатопроцесорної системи S-1 AAP у Ліверморській національній лабораторії Лоуренса.
Порівняння 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. Поняття «слабкості» є відносним, і деякі слабкі реалізації придатні для використання в окремих алгоритмах.
LL/SC складніше емулювати, ніж CAS. Крім того, зупинка виконання коду між парними інструкціями LL/SC, наприклад під час покрокового виконання програми, може перешкоджати її подальшому просуванню, що ускладнює налагодження.
Проте LL/SC еквівалентна CAS у тому сенсі, що будь-який із цих примітивів можна реалізувати через інший за O(1) і в безочікувальний спосіб.
Реалізації Інструкції LL/SC підтримуються такими архітектурами:
Alpha: ldl_l/stl_c і ldq_l/stq_c PowerPC/Power ISA: lwarx/stwcx і ldarx/stdcx MIPS: ll/sc і lld/scd ARM: ldrex/strex (ARMv6, v7 і v8-M), а також ldxr/stxr (ARMv8-A) RISC-V: lr/sc ARC: LLOCK/SCOND
Деякі процесори вимагають, щоб адреса, до якої здійснюється ексклюзивний доступ, була налаштована в режимі наскрізного запису (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. Механізм вкладених LL/SC може використовуватися для реалізації примітива MCAS (багатослівний CAS, у якому слова можуть бути розташовані в різних місцях пам'яті). У 2013 році Тревор Браун, Фейт Еллен і Ерік Рупперт реалізували програмне розширення LL/SC для кількох адрес (яке вони назвали LLX/SCX), що ґрунтується на автоматичному генеруванні коду. Вони використали його для реалізації однієї з найпродуктивніших конкурентних структур даних типу двійкове дерево пошуку (точніше, хроматичне дерево), яка за продуктивністю дещо перевершила реалізацію списку з пропусками на основі CAS у JDK.
Див. також Неблокуючий алгоритм Читання-модифікація-запис Транзакційна пам'ять
Примітки