В информатике , сравнение и замены ( CAS ) представляет собой атомная инструкция используется в многопоточном для достижения синхронизации . Он сравнивает содержимое ячейки памяти с заданным значением и, только если они совпадают, изменяет содержимое этой ячейки памяти на новое заданное значение. Это выполняется как одна атомарная операция. Атомарность гарантирует, что новое значение рассчитывается на основе актуальной информации; если за это время значение было обновлено другим потоком, запись завершится неудачно. Результат операции должен указывать, выполнялась ли подстановка; это можно сделать либо с помощью простого логическогоответ (этот вариант часто называют сравнением и установкой ) или возвращением значения, считанного из области памяти (а не записанного в нее значения).
Обзор
Операция сравнения и замены - это атомарная версия следующего псевдокода , где * обозначает доступ через указатель : [1]
функция cas (p: указатель на int, old: int, new: int) равна if * p ≠ old return false * p ← новое вернуть истину
Эта операция используется для реализации примитивов синхронизации, таких как семафоры и мьютексы , [1], а также более сложных алгоритмов без блокировки и без ожидания . Морис Херлихи (1991) доказал, что CAS может реализовать больше этих алгоритмов, чем атомарное чтение, запись или выборка и добавление , и, предполагая достаточно большой [ требуется пояснение ] объем памяти, он может реализовать все из них. [2] CAS эквивалентен load-link / store-conditional в том смысле, что постоянное количество вызовов одного из примитивов может использоваться для реализации другого без ожидания . [3]
Алгоритмы, построенные на основе CAS, обычно читают некоторые ключевые области памяти и запоминают старое значение. На основе этого старого значения они вычисляют новое значение. Затем они пытаются поменять местами новое значение с помощью CAS, где сравнение проверяет, соответствует ли местоположение старому значению. Если CAS указывает, что попытка не удалась, ее необходимо повторить с самого начала: местоположение перечитывается, новое значение повторно вычисляется, и CAS проверяется снова. Исследователи обнаружили, что вместо немедленной повторной попытки после сбоя операции CAS можно повысить общую производительность системы в многопроцессорных системах, где многие потоки постоянно обновляют некоторую конкретную общую переменную, если потоки, которые видят сбой своего CAS, используют экспоненциальный откат, другими словами, подождите немного перед повторной попыткой CAS. [4]
Пример приложения: атомный сумматор
В качестве примера использования функции сравнения и замены приведен алгоритм атомарного увеличения или уменьшения целого числа . Это полезно во множестве приложений, использующих счетчики. Функция add выполняет действие * p ← * p + a , атомарно (снова обозначает косвенный указатель * , как в C) и возвращает окончательное значение, сохраненное в счетчике. В отличие от cas pseudocode выше, не требуется, чтобы любая последовательность операций была атомарной, за исключением cas .
функция add (p: указатель на int, a: int) возвращает int сделано ← ложь пока не сделано value ← * p // Даже эта операция не обязательно должна быть атомарной. готово ← cas (p, value, value + a) возвращаемое значение + a
В этом алгоритме, если значение * p изменяется после (или во время!) его выборки и до того, как CAS выполнит сохранение, CAS заметит и сообщит об этом факте, заставляя алгоритм повторить попытку. [5]
Проблема ABA
Некоторые алгоритмы на основе CAS подвержены проблеме ложноположительного совпадения или проблеме ABA и должны решать эту проблему . Возможно, что между моментом чтения старого значения и моментом попытки CAS некоторые другие процессоры или потоки изменят местоположение памяти два или более раз, так что он получит битовый шаблон, который соответствует старому значению. Проблема возникает, если этот новый битовый шаблон, который выглядит точно так же, как старое значение, имеет другое значение: например, это может быть переработанный адрес или завернутый счетчик версий.
Общее решение - использовать CAS двойной длины (DCAS). Например, в 32-битной системе можно использовать 64-битный CAS. Вторая половина используется для удержания фишки. Часть операции сравнения сравнивает ранее прочитанное значение указателя и счетчика с текущим указателем и счетчиком. Если они совпадают, происходит обмен - записывается новое значение, но новое значение имеет увеличенный счетчик. Это означает, что если произошла ABA, хотя значение указателя будет таким же, счетчик вряд ли будет таким же (для 32-битного значения должно было произойти число, кратное 2 32 операциям, в результате чего счетчик wrap, и в этот момент значение указателя также должно быть случайно таким же).
Альтернативная форма этого (полезная для ЦП без DCAS) - это использование индекса в свободном списке, а не полного указателя, например, с 32-битным CAS использовать 16-битный индекс и 16-битный счетчик. Однако уменьшенная длина счетчиков делает ABA возможной на современных скоростях ЦП.
Один простой метод, который помогает решить эту проблему, - хранить счетчик ABA в каждом элементе структуры данных, а не использовать один счетчик ABA для всей структуры данных.
Более сложным, но более эффективным решением является реализация безопасного восстановления памяти (SMR). По сути, это сборка мусора без блокировки. Преимущество использования SMR заключается в гарантии того, что данный указатель будет существовать только один раз в любой момент времени в структуре данных, таким образом, проблема ABA полностью решена. (Без SMR будет использоваться что-то вроде freelist, чтобы гарантировать безопасный доступ ко всем элементам данных (без нарушений доступа к памяти), даже если они больше не присутствуют в структуре данных. структура данных будет доступна).
Затраты и преимущества
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
, [8], либо с некоторыми нестандартными расширениями C этого конкретного компилятора C [9], либо путем вызова функции, написанной непосредственно на языке ассемблера, с использованием функции compare-and -инструкция по замене.
Следующая функция C демонстрирует базовое поведение варианта сравнения и замены, который возвращает старое значение указанной области памяти; однако эта версия не обеспечивает решающих гарантий атомарности, которые могла бы быть при реальной операции сравнения и замены:
int compare_and_swap ( int * reg , int oldval , int newval ) { ATOMIC (); int old_reg_val = * reg ; если ( old_reg_val == oldval ) * reg = newval ; END_ATOMIC (); вернуть 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.
bool compare_and_swap ( int * аккумулятор , int * dest , int newval ) { если ( * аккумулятор == * dest ) { * dest = newval ; вернуть истину ; } Иначе { * Accum = * Dest ; вернуть ложь ; } }
Это логика в Руководстве по программному обеспечению Intel, том 2A.
Расширения
Поскольку 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]
- Одиночное сравнение, двойной обмен
- Сравнивает один указатель, но записывает два. Это реализует инструкция Itanium cmp8xchg16 [15], где два записанных указателя находятся рядом.
- Сравнение и замена нескольких слов
- Является обобщением нормального сравнения и обмена. Его можно использовать для атомарной замены произвольного количества произвольно расположенных ячеек памяти. Обычно сравнение и замена нескольких слов реализуется в программном обеспечении с использованием обычных операций сравнения и замены двойной ширины. [16] Недостатком этого подхода является отсутствие масштабируемости.
Смотрите также
- Условная установка и удаление
- Получить и добавить
- Ссылка загрузки / магазин-условно
- Неблокирующая синхронизация
- Тест и установка
- Транзакционная память
Рекомендации
- ^ a b Маллендер, Сапе; Кокс, Расс (2008). Семафоры в Plan 9 (PDF) . 3-й международный семинар по плану 9 .
- ^ Херлихи, Морис (январь 1991). «Синхронизация без ожидания» (PDF) . ACM Trans. Программа. Lang. Syst . 13 (1): 124–149. CiteSeerX 10.1.1.56.5659 . DOI : 10.1145 / 114005.102808 . Проверено 20 мая 2007 .
- ^ JH Андерсон и М. Мойр. «Универсальные конструкции для многообъектных операций». В Proc. 14-й ежегодный симпозиум ACM по принципам распределенных вычислений , страницы 184–193, 1995 г. См. Их таблицу 1, рисунки 1 и 2 и, в частности, раздел 2.
- ^ а б Дайс, Дэйв; Хендлер, Дэнни; Мирский, Илья (2013). «Упрощенное управление конфликтами для эффективных операций сравнения и обмена». arXiv : 1305.5800 [ cs.DC ].
- ^ Гетц, Брайан (23 ноября 2004 г.). "Теория и практика Java: атомарность" . IBM developerWorks .
- ^ Tudor Дэвид, Рашид Guerraoui и Vasileios Trigonakis. «Все, что вы всегда хотели знать о синхронизации, но боялись спросить». Труды Двадцать четвертого симпозиума ACM по принципам операционных систем . ACM, 2013, стр. 33-48. Подробно на стр. 34
- ^ Дэвид С. Миллер. «Семантика и поведение атомарных и битовых операций для разработчиков порта Linux». Архивировано 20 марта 2012 г. на Wayback Machine .
- ^ http://en.cppreference.com/w/c/atomic/atomic_compare_exchange
- ^ «Расширения GNU C к семейству языков C: встроенные функции для доступа к атомарной памяти»
- ^ Саймон Догерти и др., « DCAS - не серебряная пуля для разработки неблокирующего алгоритма ». 16-й ежегодный симпозиум ACM по параллелизму в алгоритмах и архитектурах, 2004 г., стр. 216–224. DOI : 10,1145 / 1007912,1007945
- ^ Кейр Фрейзер (2004), "Практическая свобода от замков" UCAM-CL-TR-579.pdf
- ↑ Дэйв Дайс, Йоси Лев, Марк Мойр, Дэн Нуссбаум и Марек Ольшевски. (2009) «Ранний опыт реализации коммерческой аппаратной транзакционной памяти». Технический отчет Sun Microsystems (60 стр.) SMLI TR-2009-180. Краткая версия появилась на ASPLOS'09 doi : 10.1145 / 1508244.1508263 . В полном объеме отчета обсуждается, как реализовать DCAS с использованием HTM, в разделе 5.
- ^ «Руководство разработчика программного обеспечения для архитектур Intel 64 и IA-32, том 2A: Справочник по набору команд, AM» (PDF) . Проверено 15 декабря 2007 .
- ^ http://www.pcworld.com/article/2058683/new-windows-8-1-requirements-strand-some-users-on-windows-8.html
- ^ «Руководство разработчика программного обеспечения с архитектурой Intel Itanium, том 3: Справочник по набору инструкций» (PDF) . Проверено 15 декабря 2007 .
- ^ «Практическая операция сравнения и замены нескольких слов» (PDF) . Проверено 8 августа 2009 .
Внешние ссылки
Базовые алгоритмы, реализованные с использованием CAS
- Сунделл, Хокан; Цигас, Филиппы. "Беспроблемные и практичные Deques с использованием сравнения и замены одного слова" (PDF) . Цитировать журнал требует
|journal=
( помощь ) - Валуа, Джон Д. "Свободные от блокировки связанные списки с использованием функции сравнения и обмена". CiteSeerX 10.1.1.41.9506 . Цитировать журнал требует
|journal=
( помощь ) - Пракаш, С .; Ли, Янн Ханг; Джонсон, Т. «Неблокирующий алгоритм для общих очередей с использованием функции сравнения и обмена» . Цитировать журнал требует
|journal=
( помощь ) - Обсуждение 2003 г. " Lock-Free с использованием cmpxchg8b ... " на Intel x86 с указателями на различные документы и исходный код
Реализации CAS
- AIX compare_and_swap Служба ядра
- Пакет Java
java.util.concurrent.atomic
реализует `compareAndSet` в различных классах - Методы класса .NET Interlocked :: CompareExchange
- Windows API InterlockedCompareExchange