Сравнить и поменять местами

В информатике , сравнение и замена ( CAS ) — это атомарная инструкция используемая в многопоточности для достижения синхронизации . Он сравнивает содержимое ячейки памяти с заданным значением и, только если они совпадают, изменяет содержимое этой ячейки памяти на новое заданное значение. Это делается как одна атомарная операция. Атомарность гарантирует, что новое значение рассчитывается на основе актуальной информации; если бы за это время значение было обновлено другим потоком, запись не удалась бы. Результат операции должен указывать, выполнила ли она подстановку; это можно сделать либо с помощью простого логического ответа (этот вариант часто называют «сравнить-и-установить »), либо путем возврата значения, прочитанного из ячейки памяти ( а не значения, записанного в нее).

Обзор

Операция сравнения и замены — это атомарная версия следующего псевдокода , где * обозначает доступ через указатель : ^[1]

function cas(p: pointer to int, old: int, new: int) is
    if *p ≠ old
        return false

    *p ← new

    return true

Эта операция используется для реализации примитивов синхронизации , таких как семафоры и мьютексы . ^[1] а также более сложные алгоритмы блокировки и ожидания . Морис Херлихи (1991) доказал, что CAS может реализовать больше этих алгоритмов, чем атомарное чтение, запись или выборка и добавление , и, предполагая довольно большую ^{[ нужны разъяснения ]} объем памяти, позволяющий реализовать все из них. ^[2] CAS эквивалентен load-link/store-conditional в том смысле, что постоянное количество вызовов любого примитива может использоваться для реализации другого без ожидания . ^[3]

Алгоритмы, построенные на основе CAS, обычно считывают некоторую ячейку ключевой памяти и запоминают старое значение. На основе этого старого значения они вычисляют новое значение. Затем они пытаются заменить новое значение с помощью CAS, где сравнение проверяет, соответствует ли местоположение старому значению. Если CAS указывает, что попытка не удалась, ее необходимо повторить с самого начала: местоположение пересчитывается, новое значение пересчитывается и CAS пробуется снова. Исследователи обнаружили, что вместо немедленной повторной попытки после сбоя операции CAS общая производительность системы может быть улучшена в многопроцессорных системах (где многие потоки постоянно обновляют какую-то конкретную общую переменную), если потоки, которые видят сбой своего CAS, используют экспоненциальную отсрочку - другими словами, ждут немного перед повторной попыткой CAS. ^[4]

Пример применения: атомный сумматор

В качестве примера использования сравнения и обмена приведен алгоритм атомарного увеличения или уменьшения целого числа . Это полезно во многих приложениях, использующих счетчики. Функция add выполняет действие *p ← *p + a , атомарно (опять обозначая косвенное обращение указателя * , как в C) и возвращает окончательное значение, хранящееся в счетчике. В отличие от cas , нет требования, чтобы любая последовательность операций была атомарной, за исключением Кас .

function add(p: pointer to int, a: int) returns int
    done ← false
    while not done
        value ← *p  // Even this operation doesn't need to be atomic.
        done ← cas(p, value, value + a)

    return value + a

В этом алгоритме, если значение *p изменяется после (или во время!) его выборки и до того, как CAS выполнит сохранение, CAS заметит и сообщит об этом факте, заставив алгоритм повторить попытку. ^[5]

проблема ABA

На некоторые алгоритмы на основе CAS влияет проблема ложноположительного совпадения или проблема ABA , и они должны ее решать . Возможно, что между моментом чтения старого значения и моментом попытки CAS некоторые другие процессоры или потоки изменят ячейку памяти два или более раз, так что она приобретет битовую комбинацию, соответствующую старому значению. Проблема возникает, если этот новый битовый шаблон, который выглядит точно так же, как старое значение, имеет другое значение: например, это может быть переработанный адрес или завернутый счетчик версий.

Общим решением этой проблемы является использование CAS двойной длины (DCAS). Например, в 32-битной системе можно использовать 64-битный CAS. Вторая половина используется для удержания стойки. Часть операции сравнения сравнивает ранее прочитанное значение указателя и счетчика с текущим указателем и счетчиком. Если они совпадают, происходит замена — записывается новое значение, — но новое значение имеет увеличенный счетчик. Это означает, что если произошел ABA, хотя значение указателя будет тем же самым, крайне маловероятно, что счетчик будет таким же (для 32-битного значения кратное 2). ³² должны были бы произойти операции, вызывающие перенос счетчика, и в этот момент значение указателя также случайно должно было бы быть тем же самым).

Альтернативная форма этого (полезная для процессоров, в которых отсутствует DCAS) — использовать индекс в свободном списке, а не полный указатель, например, при 32-битном CAS используйте 16-битный индекс и 16-битный счетчик. Однако уменьшенная длина счетчиков делает возможным использование ABA на современных скоростях ЦП.

Один простой метод, который помогает решить эту проблему, — хранить счетчик ABA в каждом элементе структуры данных вместо использования одного счетчика ABA для всей структуры данных.

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

Затраты и выгоды

CAS и другие атомарные инструкции иногда считаются ненужными в однопроцессорных системах, поскольку атомарность любой последовательности инструкций может быть достигнута путем отключения прерываний во время ее выполнения. Однако отключение прерываний имеет множество недостатков. Например, коду, которому разрешено это делать, необходимо доверять, чтобы он не был вредоносным и не монополизировал ЦП, а также был корректным и не приводил случайно к бесконечному циклу или ошибке страницы. Кроме того, отключение прерываний часто считается слишком дорогим, чтобы быть практичным. Linux Таким образом, даже программы, предназначенные для запуска только на однопроцессорных машинах, получат выгоду от атомарных инструкций, как в случае с фьютексами .

В многопроцессорных системах обычно невозможно отключить прерывания на всех процессорах одновременно. Даже если бы это было возможно, два или более процессора могли бы одновременно пытаться получить доступ к памяти одного и того же семафора, и, таким образом, атомарность не была бы достигнута. Инструкция сравнения и замены позволяет любому процессору атомарно тестировать и изменять ячейку памяти, предотвращая такие конфликты между несколькими процессорами.

В многопроцессорных архитектурах серверного уровня 2010-х годов сравнение и замена обходятся дешевле по сравнению с простой загрузкой, которая не обслуживается из кэша. В документе 2013 года отмечается, что CAS всего в 1,15 раза дороже, чем некэшируемая нагрузка на Intel Xeon ( Westmere-EX ) и в 1,35 раза на AMD Opteron (Magny-Cours). ^[6]

Реализации

Функция сравнения и замены (и двойного сравнения и замены) была неотъемлемой частью архитектур IBM 370 (и всех последующих) с 1970 года. Операционные системы, работающие на этих архитектурах, широко используют эту инструкцию для облегчения процесса. (т. е. системных и пользовательских задач) и процессоров (т. е. центральных процессоров) параллелизма , одновременно устраняя, в максимально возможной степени, «отключенные спин-блокировки », которые использовались в более ранних операционных системах IBM. использование метода «тестируй и устанавливай» Аналогичным образом было исключено . В этих операционных системах новые единицы работы могут создаваться «глобально» в глобальном списке приоритетов служб или «локально» в списке приоритетов локальных служб путем выполнения одной инструкции сравнения и замены. Это существенно улучшило скорость реагирования этих операционных систем.

В архитектурах x86 (начиная с 80486 ) и Itanium это реализовано как инструкция сравнения и обмена ( CMPXCHG ) (на мультипроцессоре LOCK Необходимо использовать префикс ).

По состоянию на 2013 год большинство многопроцессорных архитектур поддерживают CAS на аппаратном уровне, а операция сравнения и замены является наиболее популярным примитивом синхронизации для реализации как блокирующих, так и неблокирующих параллельных структур данных . ^[4]

Операции атомарного счетчика и атомарной битовой маски в ядре Linux обычно используют в своей реализации инструкцию сравнения и замены. Архитектуры SPARC-V8 и PA-RISC — две из очень немногих современных архитектур, которые не поддерживают CAS аппаратно; порт Linux для этих архитектур использует спин-блокировку . ^[7]

Реализация на C

Многие компиляторы C поддерживают использование сравнения и замены либо с C11, либо с C11. <stdatomic.h> функции, ^[8] или какое-то нестандартное расширение C этого конкретного компилятора C, ^[9] или путем вызова функции, написанной непосредственно на языке ассемблера, с использованием инструкции сравнения и замены.

Следующая функция C показывает базовое поведение варианта сравнения и замены, который возвращает старое значение указанной ячейки памяти; однако эта версия не обеспечивает решающих гарантий атомарности, которые могла бы обеспечить реальная операция сравнения и замены:

int compare_and_swap(int* reg, int oldval, int newval)
{
    ATOMIC();
    int old_reg_val = *reg;
    if (old_reg_val == oldval)
        *reg = newval;
    END_ATOMIC();
    return old_reg_val;
}

old_reg_val всегда возвращается, но его можно проверить после compare_and_swap операция, чтобы увидеть, соответствует ли она oldval, поскольку это может быть по-другому, означает, что другой процесс сумел добиться успеха в конкурирующем compare_and_swap чтобы изменить значение reg с oldval.

Например, протокол выборов можно реализовать таким образом, чтобы каждый процесс проверял результат compare_and_swap против своего собственного PID (= newval). Победный процесс находит compare_and_swap возврат исходного значения, отличного от PID (например, нуля). Проигравшим будет возвращен выигрышный PID.

Это логика в Руководстве по программному обеспечению Intel Vol 2A:

bool compare_and_swap(int *accum, int *dest, int newval)
{
    if (*accum == *dest) {
        *dest = newval;
        return true;
    } else {
        *accum = *dest;
        return false;
    }
}

Расширения

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

Двойное сравнение и замена (DCAS): Сравнивает две несвязанные ячейки памяти с двумя ожидаемыми значениями и, если они равны, присваивает обеим ячейкам новые значения. Обобщение DCAS на несколько (несмежных) слов называется MCAS или CASN. DCAS и MCAS представляют практический интерес для удобной (параллельной) реализации некоторых структур данных, таких как деки или двоичные деревья поиска . ^[10]^[11] Однако DCAS и MCAS могут быть реализованы с использованием более выразительной аппаратной транзакционной памяти. ^[12] присутствует в некоторых последних процессорах, таких как IBM POWER8 , или в процессорах Intel, поддерживающих расширения синхронизации транзакций (TSX).
Двойное сравнение и замена: Работает с двумя соседними ячейками размером с указатель (или, что то же самое, с одной ячейкой, в два раза превышающей указатель). На более поздних процессорах x86 инструкции CMPXCHG8B и CMPXCHG16B ^[13] выполнять эту роль, хотя ранние 64-битные процессоры AMD не поддерживали CMPXCHG16B (современные процессоры AMD поддерживают). Некоторые материнские платы Intel эпохи Core 2 также затрудняют его использование, хотя процессоры его поддерживают. Эти проблемы оказались в центре внимания при запуске Windows 8.1, поскольку для нее требовалась аппаратная поддержка CMPXCHG16B. ^[14]
Одиночное сравнение, двойной обмен: Сравнивает один указатель, но записывает два. Это реализуется в инструкции Itanium cmp8xchg16: ^[15] где два написанных указателя соседствуют.
Сравнение и замена нескольких слов: Это обобщение обычного сравнения и обмена. Его можно использовать для атомарной замены произвольного количества произвольно расположенных ячеек памяти. Обычно сравнение и замена нескольких слов реализуется в программном обеспечении с использованием обычных операций сравнения и замены двойной ширины. ^[16] Недостатком этого подхода является отсутствие масштабируемости.
Постоянное сравнение и замена: Представляет собой комбинацию операции сохранения и обычного сравнения и замены. Его можно использовать для атомарного сравнения и обмена значения, а затем сохранить его, чтобы не было разрыва между одновременной видимостью и видимостью сбоя. Расширение решает проблему чтения или непостоянной записи . ^[17]

См. также

Ссылки

^ Перейти обратно: ^а ^б Мюлендер, Сапе; Кокс, Расс (2008). Семафоры в Плане 9 (PDF) . 3-й международный семинар по Плану 9 .
^ Херлихи, Морис (январь 1991 г.). «Синхронизация без ожидания» (PDF) . АКМ Транс. Программа. Ланг. Сист . 13 (1): 124–149. CiteSeerX 10.1.1.56.5659 . дои : 10.1145/114005.102808 . S2CID 2181446 . Проверено 20 мая 2007 г.
^ Дж. Х. Андерсон и М. Мойр. «Универсальные конструкции для многообъектных операций». В Proc. 14-й ежегодный симпозиум ACM по принципам распределенных вычислений , стр. 184–193, 1995 г. См. Таблицу 1, рисунки 1 и 2 и, в частности, раздел 2.
^ Перейти обратно: ^а ^б Дайс, Дэйв; Хендлер, Дэнни; Мирский, Илья (2013). «Облегченное управление конфликтами для эффективных операций сравнения и замены». arXiv : 1305.5800 [ cs.DC ].
^ Гетц, Брайан (23 ноября 2004 г.). «Теория и практика Java: переход к атомарности» . IBM DeveloperWorks .
^ Тюдор Давид, Рашид Геррауи и Василиос Тригонакис. «Все, что вы всегда хотели знать о синхронизации, но боялись спросить». Материалы двадцать четвертого симпозиума ACM по принципам операционных систем . АКМ, 2013, стр. 33–48. Подробно на стр. 34
^ Дэвид С. Миллер. «Семантика и поведение атомарных операций и операций с битовой маской для сопровождающих портов Linux» . Архивировано 20 марта 2012 г. на Wayback Machine .
^ «atomic_compare_exchange_weak,atomic_compare_exchange_strong,atomic_compare_exchange_weak_explicit,atomic_compare_exchange_strong_explicit» . ru.cppreference.com .
^ «Расширения GNU C семейства языков C: встроенные функции для атомарного доступа к памяти»
^ Саймон Доэрти и др., « DCAS не является панацеей для разработки неблокирующих алгоритмов ». 16-й ежегодный симпозиум ACM по параллелизму в алгоритмах и архитектурах, 2004 г., стр. 216–224. дои : 10.1145/1007912.1007945
^ Кейр Фрейзер (2004), «Практическая свобода блокировки» UCAM-CL-TR-579.pdf
^ Дэйв Дайс, Йосси Лев, Марк Мойр, Дэн Нуссбаум и Марек Ольшевски. (2009) «Ранний опыт реализации транзакционной памяти на коммерческом оборудовании». Технический отчет Sun Microsystems (60 стр.) SMLI TR-2009-180. Краткая версия появилась на ASPLOS'09. дои : 10.1145/1508244.1508263 . В разделе 5 полного отчета обсуждается, как реализовать DCAS с использованием HTM.
^ «Руководство разработчика программного обеспечения для архитектур Intel 64 и IA-32, том 2A: Справочник по набору команд, AM» (PDF) . Проверено 15 декабря 2007 г.
^ Чакос, Брэд (29 октября 2013 г.). «Новые требования Windows 8.1 ставят в тупик некоторых пользователей Windows 8» . Мир ПК . Архивировано из оригинала 16 января 2024 года.
^ «Руководство разработчика программного обеспечения для архитектуры Intel Itanium, том 3: Справочник по набору команд» (PDF) . Проверено 15 декабря 2007 г.
^ «Практическая операция сравнения и замены нескольких слов» (PDF) . Проверено 8 августа 2009 г.
^ Ван, Уильям; Дистельхорст, Стефан (17 июня 2019 г.). «Постоянные атомы для реализации устойчивых структур данных без блокировки для энергонезависимой памяти (краткое объявление)» . 31-й симпозиум ACM по параллелизму в алгоритмах и архитектурах . Ассоциация вычислительной техники. стр. 309–311. дои : 10.1145/3323165.3323166 . ISBN 9781450361842 . S2CID 195064876 – через цифровую библиотеку ACM.

Внешние ссылки

Базовые алгоритмы, реализованные с помощью CAS

Санделл, Хокан; Цигас, Филипп. «Безблокировочные и практичные деки с использованием сравнения и замены отдельных слов» (PDF) .
Валуа, Джон Д. Связные списки без блокировок с использованием метода сравнения и замены . Материалы четырнадцатого ежегодного симпозиума ACM по принципам распределенных вычислений. CiteSeerX 10.1.1.41.9506 .
Пракаш, С.; Ли, Янн Ханг; Джонсон, Т. «Неблокирующий алгоритм для общих очередей с использованием сравнения и замены» . Транзакции IEEE на компьютерах .
Обсуждение 2003 г. «Lock-Free с использованием cmpxchg8b...» на Intel x86 со ссылками на различные документы и исходный код.

Реализации CAS

Служба ядра AIX Compare_and_swap
Java-пакет java.util.concurrent.atomic реализует «compareAndSet» в различных классах
Методы класса .NET Interlocked::CompareExchange
Windows API InterlockedCompareExchange

[plan9-1] Перейти обратно: ^а ^б Мюлендер, Сапе; Кокс, Расс (2008). Семафоры в Плане 9 (PDF) . 3-й международный семинар по Плану 9 .

[herlihy91-2] Херлихи, Морис (январь 1991 г.). «Синхронизация без ожидания» (PDF) . АКМ Транс. Программа. Ланг. Сист . 13 (1): 124–149. CiteSeerX 10.1.1.56.5659 . дои : 10.1145/114005.102808 . S2CID 2181446 . Проверено 20 мая 2007 г.

[3] Дж. Х. Андерсон и М. Мойр. «Универсальные конструкции для многообъектных операций». В Proc. 14-й ежегодный симпозиум ACM по принципам распределенных вычислений , стр. 184–193, 1995 г. См. Таблицу 1, рисунки 1 и 2 и, в частности, раздел 2.

[dice-4] Перейти обратно: ^а ^б Дайс, Дэйв; Хендлер, Дэнни; Мирский, Илья (2013). «Облегченное управление конфликтами для эффективных операций сравнения и замены». arXiv : 1305.5800 [ cs.DC ].

[5] Гетц, Брайан (23 ноября 2004 г.). «Теория и практика Java: переход к атомарности» . IBM DeveloperWorks .

[6] Тюдор Давид, Рашид Геррауи и Василиос Тригонакис. «Все, что вы всегда хотели знать о синхронизации, но боялись спросить». Материалы двадцать четвертого симпозиума ACM по принципам операционных систем . АКМ, 2013, стр. 33–48. Подробно на стр. 34

[7] Дэвид С. Миллер. «Семантика и поведение атомарных операций и операций с битовой маской для сопровождающих портов Linux» . Архивировано 20 марта 2012 г. на Wayback Machine .

[8] «atomic_compare_exchange_weak,atomic_compare_exchange_strong,atomic_compare_exchange_weak_explicit,atomic_compare_exchange_strong_explicit» . ru.cppreference.com .

[9] «Расширения GNU C семейства языков C: встроенные функции для атомарного доступа к памяти»

[10] Саймон Доэрти и др., « DCAS не является панацеей для разработки неблокирующих алгоритмов ». 16-й ежегодный симпозиум ACM по параллелизму в алгоритмах и архитектурах, 2004 г., стр. 216–224. дои : 10.1145/1007912.1007945

[Fraser2004-11] Кейр Фрейзер (2004), «Практическая свобода блокировки» UCAM-CL-TR-579.pdf

[12] Дэйв Дайс, Йосси Лев, Марк Мойр, Дэн Нуссбаум и Марек Ольшевски. (2009) «Ранний опыт реализации транзакционной памяти на коммерческом оборудовании». Технический отчет Sun Microsystems (60 стр.) SMLI TR-2009-180. Краткая версия появилась на ASPLOS'09. дои : 10.1145/1508244.1508263 . В разделе 5 полного отчета обсуждается, как реализовать DCAS с использованием HTM.

[13] «Руководство разработчика программного обеспечения для архитектур Intel 64 и IA-32, том 2A: Справочник по набору команд, AM» (PDF) . Проверено 15 декабря 2007 г.

[14] Чакос, Брэд (29 октября 2013 г.). «Новые требования Windows 8.1 ставят в тупик некоторых пользователей Windows 8» . Мир ПК . Архивировано из оригинала 16 января 2024 года.

[15] «Руководство разработчика программного обеспечения для архитектуры Intel Itanium, том 3: Справочник по набору команд» (PDF) . Проверено 15 декабря 2007 г.

[16] «Практическая операция сравнения и замены нескольких слов» (PDF) . Проверено 8 августа 2009 г.

[17] Ван, Уильям; Дистельхорст, Стефан (17 июня 2019 г.). «Постоянные атомы для реализации устойчивых структур данных без блокировки для энергонезависимой памяти (краткое объявление)» . 31-й симпозиум ACM по параллелизму в алгоритмах и архитектурах . Ассоциация вычислительной техники. стр. 309–311. дои : 10.1145/3323165.3323166 . ISBN 9781450361842 . S2CID 195064876 – через цифровую библиотеку ACM.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]