В информатике , то выборка и добавления CPU инструкция (FAA) атомарно увеличивает содержимое ячейки памяти по указанному значению.
То есть fetch-and-add выполняет операцию
- увеличить значение по адресу x на a , где x - это ячейка памяти, а a - некоторое значение, и вернуть исходное значение в x
таким образом, что если эта операция выполняется одним процессом в параллельной системе, никакой другой процесс никогда не увидит промежуточный результат.
Выборка и добавление может использоваться для реализации структур управления параллелизмом, таких как блокировки мьютексов и семафоры .
Обзор
Мотивация для использования атомарной выборки и добавления заключается в том, что операции, которые отображаются в языках программирования как
- х = х + а
небезопасны в параллельной системе, где несколько процессов или потоков выполняются одновременно (либо в многопроцессорной системе, либо предварительно запланированы на некоторых одноядерных системах). Причина в том, что такая операция фактически реализована в виде нескольких машинных инструкций:
- Извлечь значение в ячейке x , скажем, x old , в регистр;
- добавить к й старому в реестре;
- сохранить новое значение регистра обратно в x .
Когда один процесс делает x = x + a, а другой делает x = x + b одновременно, существует состояние гонки . Они могут получить x старый и работать с ним, затем оба сохранят свои результаты с эффектом, что один перезаписывает другой, и сохраненное значение становится либо x old + a, либо x old + b , а не x old + a + b, как могло бы ожидал.
В однопроцессорных системах без поддержки приоритетного прерывания ядра достаточно отключить прерывания перед доступом к критическому разделу . Однако в многопроцессорных системах (даже с отключенными прерываниями) два или более процессора могут одновременно пытаться получить доступ к одной и той же памяти. Команда выборки и добавления позволяет любому процессору атомарно увеличивать значение в памяти, предотвращая такие множественные конфликты процессоров.
Морис Херлихи (1991) доказал, что выборка и добавление имеет конечное согласованное число, в отличие от операции сравнения и обмена . Операция выборки и добавления может решить проблему консенсуса без ожидания не более чем для двух параллельных процессов. [1]
Выполнение
Инструкция по извлечению и добавлению ведет себя как следующая функция. Важно отметить, что вся функция выполняется атомарно : ни один процесс не может прервать выполнение функции в середине выполнения и, следовательно, увидеть состояние, которое существует только во время выполнения функции. Этот код служит только для объяснения поведения функции "выборка и добавление"; атомарность требует явной аппаратной поддержки и, следовательно, не может быть реализована как простая функция высокого уровня.
<< атомарная >> функция FetchAndAdd ( расположение адреса , int inc) { значение int : = * расположение * расположение: = значение + вкл. возвращаемое значение}
Чтобы реализовать блокировку взаимного исключения, мы определяем операцию FetchAndIncrement, которая эквивалентна FetchAndAdd с inc = 1. С помощью этой операции блокировка взаимного исключения может быть реализована с использованием алгоритма блокировки билета как:
запись locktype { int ticketnumber int turn}процедура LockInit ( locktype * lock) { lock.ticketnumber: = 0 lock.turn: = 0}procedure Lock ( locktype * lock) { int myturn: = FetchAndIncrement (& lock.ticketnumber) // должно быть атомарным, так как многие потоки могут запрашивать блокировку одновременно с lock.turn ≠ myturn skip // вращаться до получения блокировки }процедура UnLock ( locktype * lock) { FetchAndIncrement (& lock.turn) // это не обязательно должно быть атомарным, так как только владелец блокировки выполнит это }
Эти процедуры обеспечивают блокировку взаимного исключения при выполнении следующих условий:
- Структура данных Locktype инициализируется функцией LockInit перед использованием
- Количество задач, ожидающих блокировки, не превышает INT_MAX в любое время
- Целочисленный тип данных, используемый в значениях блокировки, может `` оборачиваться '' при непрерывном увеличении
Аппаратная и программная поддержка
Атомный Функция fetch_add присутствует в стандарте C ++ 11 . [2] Он доступен как проприетарное расширение для C в спецификации Itanium ABI , [3] и (с тем же синтаксисом) в GCC . [4]
реализация x86
В архитектуре x86 инструкция ADD с операндом назначения, определяющим расположение памяти, является инструкцией выборки и добавления, которая существует с 8086 (тогда она просто не вызывалась), и с префиксом LOCK является атомарной. через несколько процессоров. Однако он не мог вернуть исходное значение ячейки памяти (хотя и возвращал некоторые флаги) до тех пор, пока 486 не представил инструкцию XADD.
Ниже приведена реализация компилятора GCC на языке C для 32- и 64-разрядных платформ Intel x86 на основе расширенного синтаксиса asm:
static inline int fetch_and_add ( int * переменная , значение int ) { __asm__ volatile ( "lock; xaddl% 0,% 1" : "+ r" ( значение ), "+ m" ( * переменная ) // ввод + вывод : / / Без ввода только : «память» ); возвращаемое значение ; }
История
Функция выборки и добавления была введена проектом Ультракомпьютера , который также произвел мультипроцессор, поддерживающий выборку и добавление и содержащий настраиваемые переключатели СБИС, которые могли комбинировать параллельные ссылки на память (включая выборку и добавление), чтобы предотвратить их сериализацию в модуль памяти, содержащий целевой операнд.
Смотрите также
Рекомендации
- ^ Herlihy, Морис (январь 1991). «Синхронизация без ожидания» (PDF) . ACM Trans. Программа. Lang. Syst . 13 (1): 124–149. CiteSeerX 10.1.1.56.5659 . DOI : 10.1145 / 114005.102808 . Проверено 20 мая 2007 .
- ^ "std :: atomic :: fetch_add" . cppreference.com . Дата обращения 1 июня 2015 .
- ^ «Двоичный интерфейс приложений (ABI) для конкретных процессоров Intel Itanium» (PDF) . Корпорация Intel . 2001 г.
- ^ «Атомные встроенные элементы» . Использование коллекции компиляторов GNU (GCC) . Фонд свободного программного обеспечения. 2005 г.