Сравнить и обменять - Compare-and-swap

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

Обзор

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

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

    *p ← new

    return true

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

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

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

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

Проблема ABA

Основная статья: проблема 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).

Реализации

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

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

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

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

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

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

Следующая функция 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. 

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

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

Расширения

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

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

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

использованная литература

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

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

Реализации CAS