В информатике инструкция центрального процессора «выборка и добавление » ( FAA ) атомарно увеличивает содержимое ячейки памяти на указанное значение.
То есть, fetch-and-add выполняет следующую операцию: увеличивает значение по адресу x на a , где x — это ячейка памяти, а a — некоторое значение, и возвращает исходное значение по адресу x .
таким образом, что если эта операция выполняется одним процессом в параллельной системе, никакой другой процесс никогда не увидит промежуточного результата.
Извлечение и добавление можно использовать для реализации структур управления параллелизмом, таких как мьютексы и семафоры .
Мотивация наличия атомарной выборки и добавления заключается в том, что операции, которые в языках программирования выглядят как x = x + a, небезопасны в параллельной системе, где несколько процессов или потоков выполняются одновременно (либо в многопроцессорной системе, либо с упреждающим планированием на некоторых одноядерных системах). Причина в том, что такая операция фактически реализуется как несколько машинных инструкций:
Когда один процесс выполняет x = x + a , а другой выполняет x = x + b одновременно, возникает гонка данных . Они оба могут извлечь x old и обработать его, затем оба сохранить свои результаты с эффектом того, что один перезапишет другой, и сохраненное значение станет либо x old + a , либо x old + b , а не x old + a + b , как можно было бы ожидать.
В однопроцессорных системах без поддержки вытеснения ядра достаточно отключить прерывания перед доступом к критической секции . Однако в многопроцессорных системах (даже с отключенными прерываниями) два или более процессоров могут пытаться получить доступ к одной и той же памяти одновременно. Инструкция fetch-and-add позволяет любому процессору атомарно увеличивать значение в памяти, предотвращая такие множественные коллизии процессоров.
Морис Херлихи (1991) доказал, что выборка и добавление имеют конечное число консенсуса , в отличие от операции сравнения и обмена . Операция выборки и добавления может решить проблему консенсуса без ожидания не более чем для двух параллельных процессов. [1]
Инструкция fetch-and-add ведет себя как следующая функция. Важно то, что вся функция выполняется атомарно : никакой процесс не может прервать функцию во время выполнения и, следовательно, увидеть состояние, которое существует только во время выполнения функции. Этот код служит только для того, чтобы помочь объяснить поведение fetch-and-add; атомарность требует явной аппаратной поддержки и, следовательно, не может быть реализована как простая функция высокого уровня.
<< атомарный >> функция FetchAndAdd( адрес местоположение, int inc) { int значение := * местоположение *расположение := значение + вкл. возвращаемое значение}Для реализации взаимной блокировки исключения мы определяем операцию FetchAndIncrement, которая эквивалентна FetchAndAdd с inc=1. С помощью этой операции можно реализовать взаимную блокировку исключения, используя алгоритм блокировки тикета следующим образом:
запись locktype { int ticketnumber int turn}процедура LockInit( тип_блокировки * блокировка) { lock.ticketnumber := 0 блокировка.поворот := 0}procedure Lock( locktype * lock) { int myturn := FetchAndIncrement(&lock.ticketnumber) // должно быть атомарным, так как несколько потоков могут запросить блокировку одновременно, пока lock.turn ≠ myturn пропустить // цикл продолжается до тех пор, пока блокировка не будет получена }процедура UnLock( тип_блокировки * блокировка) { FetchAndIncrement(&lock.turn) // это не обязательно должно быть атомарным, так как только владелец блокировки выполнит это }Эти процедуры обеспечивают блокировку взаимного исключения при соблюдении следующих условий:
Атомарная функция fetch_add появляется в стандарте C++11 . [2] Она доступна как фирменное расширение для C в спецификации Itanium ABI , [3] и (с тем же синтаксисом) в GCC . [4]
В архитектуре x86 инструкция ADD с операндом назначения, указывающим ячейку памяти, является инструкцией выборки и добавления, которая существует со времен 8086 (тогда она просто так не называлась), а с префиксом LOCK является атомарной для нескольких процессоров. Однако она не могла вернуть исходное значение ячейки памяти (хотя и возвращала некоторые флаги), пока в 486 не появилась инструкция XADD.
Ниже представлена реализация компилятора GCC на языке C для 32- и 64-разрядных платформ Intel x86, основанная на расширенном синтаксисе asm:
static inline int fetch_and_add ( int * variable , int value ) { __asm__ volatile ( "lock; xaddl %0, %1" : "+r" ( value ), "+m" ( * variable ) // ввод + вывод : // Нет ввода - только : "memory" ); возвращаемое значение ; } Технология выборки и добавления была введена в проект Ultracomputer , в рамках которого также был создан мультипроцессор, поддерживающий выборку и добавление и содержащий специальные коммутаторы VLSI, способные объединять параллельные ссылки на память (включая выборку и добавление), чтобы предотвратить их сериализацию в модуле памяти, содержащем целевой операнд.