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

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

Ответ 1

Powerpc имеет более мощные примитивы: "lwarx" и "stwcx"

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

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

Ответ 2

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

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

Ответ 3

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

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

Ответ 4

Intel x86 поддерживает эту поддержку. IBM в нем Руководство по переносу Solaris в Linux дает следующий пример:

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;
}

Ответ 5

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

Ответ 6

Извините за много писем.: (

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

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

Существует два основных подхода к поддержке аппаратной синхронизации CPU:

Атомная транзакция.
На основе протокола когерентности кэша.

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

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

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

CPU A сохранит строку памяти X в кеше L1. В то же время CPU B хочет получить доступ к строке памяти X. (X → CPU A L1)
CPU B выдает строку памяти X транзакции доступа на шине. (X → CPU A L1)
Все агенты шины (ядра ЦП) имеют так называемый агент отслеживания, который прослушивает все транзакции на шине и проверяет, сохраняется ли доступ к строке памяти, к которой была запрошена транзакция, в кэше владельца L1 владельца. Таким образом, процессор Snooping Agent обнаруживает, что CPU A владеет линией памяти, запрошенной процессором B. (X → CPU A L1)
CPU: приостановить транзакцию доступа к памяти, выданную процессором B. (X → CPU A L1)
CPU. Очистите строку памяти, запрошенную B, из своего кеша L1. (X → память)
CPU: возобновление ранее приостановленной транзакции. (X → память)
CPU B извлекает строку памяти X из памяти. (X → CPU B L1)

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

Ответ 7

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

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

Ответ 8

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

Ответ 9

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

Ответ 10

Sparc v9 имеет инструкцию cas. Руководство по архитектуре SPARC v9 обсуждает использование инструкции CAS в Приложении J, посмотрите конкретно на примерах J.11 и J.12.

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

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