stringtranslate.com

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

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

Обзор

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

функция cas(p: указатель на int, old: int, new: int) —  если *p ≠ old, возвращает false *р ← новый вернуть истину

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

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

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

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

функция add(p: указатель на int, a: int) возвращает int сделано ← ложно пока не сделано значение ← *p // Даже эта операция не обязательно должна быть атомарной. сделано ← cas(p, значение, значение + a) возвращаемое значение + а

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

проблема АВА

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

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

Альтернативная форма этого (полезная для ЦП, не имеющих 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]

Реализации

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

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

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

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

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

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

Следующая функция 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, том 2A:

bool Compare_and_swap ( int * accum , int * dest , int newval ) { if ( * accum == * dest ) { * dest = newval ; вернуть истину ; } Еще { * аккум = * место ; вернуть ложь ; } }

Расширения

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

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

Смотрите также

Ссылки

  1. ^ ab Mullender, Sape; Cox, Russ (2008). Семафоры в Plan 9 (PDF) . 3-й международный семинар по Plan 9 .
  2. ^ Herlihy, Maurice (январь 1991 г.). «Wait-free synchronization» (PDF) . ACM Trans. Program. Lang. Syst . 13 (1): 124–149. CiteSeerX 10.1.1.56.5659 . doi :10.1145/114005.102808. S2CID  2181446 . Получено 2007-05-20 . 
  3. ^ JH Anderson и M. Moir. «Универсальные конструкции для многообъектных операций». В Proc. 14th Annual ACM Symposium on Principles of Distributed Computing , страницы 184–193, 1995. См. их Таблицу 1, Рисунки 1 и 2 и Раздел 2 в частности.
  4. ^ ab Дайс, Дэйв; Хендлер, Дэнни; ​​Мирский, Илья (2013). «Легкое управление конфликтами для эффективных операций сравнения и обмена». arXiv : 1305.5800 [cs.DC].
  5. ↑ Гетц, Брайан (23 ноября 2004 г.). «Теория и практика Java: переход к атомарности». IBM developerWorks .
  6. ^ Тудор Дэвид, Рашид Геррауи и Василиос Тригонакис. «Все, что вы всегда хотели знать о синхронизации, но боялись спросить». Труды Двадцать четвертого симпозиума ACM по принципам операционных систем . ACM, 2013, стр. 33-48. Подробности на стр. 34
  7. ^ Дэвид С. Миллер. «Семантика и поведение атомарных и битовых операций, для разработчиков портов Linux». Архивировано 20 марта 2012 г. на Wayback Machine .
  8. ^ "атомарный_сравнительный_обмен_слабый, атомарный_сравнительный_обмен_сильный, атомарный_сравнительный_обмен_слабый_явный, атомарный_сравнительный_обмен_сильный_явный". ru.cppreference.com .
  9. ^ «Расширения GNU C для семейства языков C: Встроенные функции для атомарного доступа к памяти»
  10. ^ Саймон Доэрти и др., «DCAS не является панацеей для разработки неблокируемых алгоритмов». 16-й ежегодный симпозиум ACM по параллелизму в алгоритмах и архитектурах, 2004, стр. 216–224. doi :10.1145/1007912.1007945
  11. ^ Кейр Фрейзер (2004), «Практическая свобода от блокировки» UCAM-CL-TR-579.pdf
  12. ^ Дэйв Дайс, Йосси Лев, Марк Мойр, Дэн Нуссбаум и Марек Ольшевски. (2009) «Ранний опыт коммерческой аппаратной реализации транзакционной памяти». Технический отчет Sun Microsystems (60 стр.) SMLI TR-2009-180. Краткая версия появилась на ASPLOS'09 doi :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 в тупик». PC World . Архивировано из оригинала 16 января 2024 г.
  15. ^ "Руководство разработчика программного обеспечения для архитектуры Intel Itanium, том 3: Справочник по набору инструкций" (PDF) . Получено 15 декабря 2007 г.
  16. ^ "Практическая операция сравнения и обмена нескольких слов" (PDF) . Получено 2009-08-08 .
  17. ^ Ван, Уильям; Дистельхорст, Стефан (17 июня 2019 г.). «Persistent Atomics для реализации прочных структур данных без блокировки для энергонезависимой памяти (краткое объявление)». 31-й симпозиум ACM по параллелизму в алгоритмах и архитектурах . Ассоциация вычислительной техники. стр. 309–311. doi :10.1145/3323165.3323166. ISBN 9781450361842. S2CID  195064876 – через цифровую библиотеку ACM.

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

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

Реализации CAS