Пример без блокировки C ++ 11 с использованием Load-link / store-conditional для предотвращения ABA?
При написании кода без блокировки с использованием техники сравнения и замены (CAS) возникает проблема, называемая проблемой ABA:
http://en.wikipedia.org/wiki/ABA_problem
в результате чего сравнение только по значению «А» проблематично, потому что между двумя наблюдениями могла произойти запись. Я прочитал и нашел это решение:
http://en.wikipedia.org/wiki/LL/SC
В информатике, Load-Link и Store-Conditional (LL / SC) являются
пара инструкций, используемых в многопоточности для достижения
синхронизации. Load-link возвращает текущее значение памяти
местоположение, в то время как последующее хранение обусловлено той же памяти
location будет хранить новое значение, только если не было обновлений
это место с момента загрузки ссылки. Вместе это реализует
без блокировки атомарная операция чтения-изменения-записи.
Как изменить типичный метод CAS без блокировок CAS для использования вышеуказанного решения? Кто-нибудь сможет показать маленький пример?
Я не возражаю против того, специфична ли его C ++ 11 / x86, x86-64 для Linux (желательно без ответов Win32).
Решение
LL / SC — это инструкции, реализованные некоторыми архитектурами (например, SPARC) для формирования основы атомных операций более высокого уровня. В x86 у вас есть LOCK вместо этого префикс для достижения аналогичной цели.
Чтобы избежать проблемы ABA на x86 с LOCK Вы должны обеспечить свою собственную защиту от вторжения в магазины. Один из способов сделать это — сохранить номер поколения (просто увеличивающееся целое число) рядом с рассматриваемой памятью. Каждый модуль обновления выполняет атомное сравнение / обмен достаточно широко, чтобы охватить как данные, так и серийный номер. Обновление будет успешным только в том случае, если будет найдено правильные данные и правильный номер. В то же время он обновляет номер, чтобы другие потоки увидели изменение.
Вы заметите, что x86 всегда (?) Предлагал CMPXCHG инструкция, которая в два раза шире машинного слова (см. CMPXCHG8B и позже CMPXCGH16B), которые могут быть использованы для этой цели.
Другие решения