Какие архитектуры процессоров поддерживают Compare and Swap (CAS)?

Question

просто интересно узнать, какие архитектуры процессора поддерживают сравнение и замену атомных примитивов?

Answer 1

Sparc v9 имеет инструкцию по эксплуатации на корпусе. В SPARC v9 architecture manual обсуждается использование инструкции CAS в Приложении J, посмотрите конкретно на примеры J.11 и J.12.

Я считаю, что имя инструкции на самом деле является «casa», поскольку оно может получить доступ либо к текущему адресному пространству, либо к альтернативному. «cas» - это ассемблерный макрос, который обращается к текущему ASI.

Существует также статья о developers.sun.com, в которой обсуждаются различные атомарные инструкции, которые были реализованы на протяжении многих лет процессорами Sparc, включая cas.

Answer 2

х86 и Itanium имеют CMPXCHG (сравнение и обмен)

Answer 3

Intel x86 имеет такую ​​поддержку. IBM в это Solaris to Linux Porting Guide дает этот пример:

bool_t My_CompareAndSwap(IN int *ptr, IN int old, IN int new) 
{ 
     unsigned char ret; 

     /* Note that sete sets a 'byte' not the word */ 
     __asm__ __volatile__ (
       " lock\n" 
       " cmpxchgl %2,%1\n" 
       " sete %0\n" 
       : "=q" (ret), "=m" (*ptr) 
       : "r" (new), "m" (*ptr), "a" (old) 
       : "memory"); 

     return ret; 
} 

Answer 4

имеет более PowerPC мощные примитивы доступны: «lwarx» и «stwcx»

lwarx загружает значение из памяти, но запоминает расположение. Любой другой поток или процессор, который касается этого местоположения, приведет к сбою команды «stwcx», инструкции условного хранилища.

Так lwarx/stwcx комбо позволяет реализовать атомный инкремент/декремент, сравнение и замены, и более мощные атомные операции, такие как «атомных приращения индекс кольцевого буфера»

Answer 5

Начиная с архитектурой ARM ARMv6 имеют LDREX/STREX, которые могут использоваться для реализации операции атомного сравнения.

Answer 6

Для того, чтобы завершить список, MIPS имеет инструкции Load Linked (ll) и Store Conditional (sc), которые загружают значение из памяти и затем условно сохраняют, если другой ЦП не получил доступ к местоположению. Это правда, что вы можете использовать эти инструкции для выполнения операций свопинга, приращения и других операций. Однако недостатком является то, что при большом количестве процессоров, которые сильно запирают блокировки, вы попадаете в livelock: условное хранилище будет часто терпеть неудачу и потребует другого цикла, чтобы повторить попытку, что не удастся и т. Д.

Реализация программного обеспечения mutex_lock может стать очень сложная попытка реализовать экспоненциальную отсрочку, если эти ситуации считаются достаточно важными, чтобы волноваться. В одной системе я работал с 128 ядрами, они были.

Answer 7

Другой и более простой способ ответить на этот вопрос может состоять в перечислении многопроцессорных платформ, которые НЕ поддерживают сравнение и свопинг (или load-link/store-conditional, которые могут быть использованы для записи).

Единственный, о котором я знаю, это PARISC, который имеет только инструкцию с ясным атомом. Это можно использовать для построения мьютекса (при условии, что одно выравнивает слово на границе 16 байтов). В этом архетекторе нет CAS (в отличие от x86, ia64, ppc, sparc, mips, s390, ...)

Answer 8

Сравнение и своп был добавлен в мэйнфреймы IBM в 1973 году. Он (и сравнивает двойной и своп) по-прежнему на мэйнфреймах IBM (наряду с более поздними многопроцессорными функциями, такими как PLO - выполнять заблокированную работу).

Answer 9

Несколько человек прокомментировали/спросили, нужен ли префикс «блокировки» для x86/x64 для cmpxchg. Ответ да для многоядерных машин. Инструкция полностью атомная для одноядерных машин без блокировки.

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

Answer 10

Извините за большое количество писем. :(

Практически все инструкции в ISA x86 (кроме так называемых строковых инструкций и, возможно, несколько других), включая CMPXCHG, являются атомарными в контексте Unicore CPU. Это связано с тем, что в соответствии с архитектурой x86 CPU проверяет после прерывания выполнения каждой команды и никогда не посередине. В результате запрос прерывания может быть обнаружен и его обработка будет запущена только на границе между выполнением двух последовательных инструкций. В связи с этим все ссылки на память, сделанные CPU во время выполнения одиночного инструкции изолированы и не могут чередоваться никакими другими действиями.Это поведение является обычным явлением для одноядерных и многоядерных процессоров. Но если в контексте Unicore CPU имеется только одна единица системы, которая выполняет доступ к памяти, в контексте многоядерного процессора имеется более одной единицы системы, которая выполняет доступ к t он память одновременно. Изоляции команд недостаточно для обеспечения согласованности в такой среде, так как обращения к памяти, производимые разными CPU одновременно, могут чередовать друг друга. Из-за этого дополнительный защитный слой должен применяться к протоколу изменения данных. Для x86 этот уровень является префиксом блокировки, который инициирует атомарную транзакцию на системной шине.

Резюме: Это безопасно и дешевле использовать для синхронизации инструкции, как CMPXCHG, XADD, БПС и т.д. без префикса блокировки, если вы уверены, что данные, доступ к этой инструкции могут быть доступны только по одному ядро. Если вы не уверены в этом, применяйте префикс блокировки для обеспечения безопасности, торгуя с производительности.

Есть два основных подхода к поддержке синхронизации аппаратных средств с помощью CPU:

1. Атомный транзакции на основе.
2. Протокол когерентности кэша.

Никто не является серебряной пулей. Оба подхода имеют свои преимущества и недостатки.

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

Подход, основанный на протоколе когерентности кеша, основан на том, что строка памяти может кэшироваться только в одном кэше L1 за один момент времени. Протокол доступа к памяти в системе когерентности кэш похож на следующую последовательность действий:

1. CPU A Храните строку памяти X в кеше L1. В то же время CPU B хочет получить доступ к строке памяти X. (X -> CPU A L1)
2. CPU B выдает строку памяти X транзакция доступа на шине. (X -> CPU A L1)
3. Все агенты шины (ядра ЦП) имеют так называемый отслеживающий агент, который прослушивает все транзакции на шине и проверяет, сохраняется ли доступ к линии памяти, к которой была запрошена транзакция, в своем собственном CPU L1. Таким образом, процессор Snooping Agent обнаруживает, что CPU A владеет линией памяти, запрошенной процессором B. (X -> CPU A L1)
4. CPU. Операция приостановки доступа к памяти, выдаваемая процессором B. (X -> CPU A L1)
5. CPU A Сбросьте строку памяти, запрошенную B из его кеша L1. (X -> память)
6. CPU Предыдущее ранее приостановленное действие. (X -> память)
7. CPU B извлекает строку памяти X из памяти. (X -> CPU B L1)

Благодаря этому протоколу ЦП ядра всегда обращается к фактическим данным в памяти, а обращения к памяти упорядочены в строгом порядке, один доступ во времени. Поддержка синхронизации на основе протокола когерентности основывается на том факте, что ЦП может легко обнаружить, что к конкретной линии памяти обращались между двумя точками времени. Во время первого доступа к памяти к строке X, которая должна открывать транзакцию, CPU может отметить, что строка памяти в кеше L1 должна контролироваться агентом отслеживания. В свою очередь, агент отслеживания может во время кэширования линии кэша выполнить проверку, чтобы идентифицировать, что линия отмечена для управления, и поднять внутренний флаг, если контролируемая линия сброшена. Как результат, если CPU проверит внутренний флаг во время доступа к памяти, который закроет транзакцию, он будет знать, что контролируемая линия памяти может быть изменена кем-то другим, и заключение заключается в том, что транзакция должна быть выполнена с успехом или должна считаться неудачной. Это способ реализации класса команд LL \ SC. Этот подход более прост, чем атомарная транзакция, и обеспечивает гораздо большую гибкость в синхронизации, поскольку на его основе может быть построено гораздо больше различных примитивов синхронизации по сравнению с методом атомных транзакций. Этот подход является более масштабируемым и эффективным, поскольку он не блокирует доступ к памяти для всех других частей системы. И, как вы видите, это решает проблему ABA, поскольку она основана на факте обнаружения доступа к области памяти, но не на значении обнаружения изменения области памяти. Любой доступ к области памяти, участвующей в текущей транзакции, будет считаться транзакцией. И это может быть хорошо и плохо в одно и то же время, потому что конкретный алгоритм может интересоваться только значением области памяти и не принимает в учетной записи, что это место было посещено кем-то посередине, пока этот доступ не изменит память , В этом случае чтение значения памяти в середине приведет к сбою ложной отрицательной транзакции. Кроме того, этот подход может привести к огромному снижению производительности контентов управляющих потоков на одной и той же линии памяти, поскольку они способны постоянно ставить линию памяти друг от друга, тем самым предотвращая успешное завершение транзакции завершения транзакции. Это действительно значительная проблема, потому что в терминальном случае она может превращать систему в livelock. Поддержка синхронизации на основе протокола когерентности, обычно используемая в CPU RISC, благодаря простоте и гибкости. Но следует отметить, что Intel решила поддержать такой подход для поддержки синхронизации в архитектуре x86. В прошлом году Intel анонсировала расширения Transactional Synchronization Extensions к архитектуре x86, которые будут реализованы в поколениях процессоров Intel для процессоров Haswell.В результате, похоже, что x86 будет иметь самую мощную поддержку синхронизации и позволит разработчикам системы использовать преимущества обоих подходов.