Получить и добавить

В информатике выборки и добавления ( FAA ) ЦП инструкция атомарно увеличивает содержимое ячейки памяти на указанное значение.

То есть функция выборки и добавления выполняет следующую операцию: увеличивает значение по адресу $x$ на $a$ , где $x$ — это ячейка памяти, а $a$ — некоторое значение, и возвращает исходное значение по адресу $x$ .

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

Метод выборки и добавления можно использовать для реализации структур управления параллелизмом, таких как блокировки мьютексов и семафоры .

Обзор

Мотивация использования атомарной выборки и сложения заключается в том, что операции, которые появляются в языках программирования как x = x + a небезопасны в параллельной системе, где несколько процессов или потоков выполняются одновременно (либо в многопроцессорной системе, либо заранее запланированы на некоторые одноядерные системы). Причина в том, что такая операция фактически реализуется как несколько машинных инструкций:

загрузить $x$ в регистр;
добавить $для регистрации$ ;
сохранить значение регистра обратно в $x$ .

Когда один процесс выполняет x = x + a, а другой делает x = x + b одновременно происходит гонка данных . Они могут одновременно получить $x old$ и работать с ним, а затем оба сохранить свои результаты с эффектом, что один перезаписывает другой, и сохраненное значение становится либо $x old + a$ , либо $x old + b$ , а не $x old + a + b,$ как могло бы быть . ожидал.

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

Морис Херлихи (1991) доказал, что операция выборки и сложения имеет конечное консенсусное число, в отличие от операции сравнения и замены . Операция выборки и добавления может решить проблему консенсуса без ожидания не более чем для двух параллельных процессов. ^[1]

Выполнение

Инструкция выборки и добавления ведет себя как следующая функция. Важно отметить, что вся функция выполняется атомарно : ни один процесс не может прервать функцию в середине выполнения и, следовательно, увидеть состояние, которое существует только во время выполнения функции. Этот код служит только для пояснения поведения операции выборки и добавления; атомарность требует явной аппаратной поддержки и, следовательно, не может быть реализована как простая функция высокого уровня.

<< atomic >>
function FetchAndAdd(address location, int inc) {
    int value := *location
    *location := value + inc
    return value
}

Чтобы реализовать блокировку взаимного исключения, мы определяем операцию FetchAndIncrement, которая эквивалентна FetchAndAdd с inc=1. С помощью этой операции блокировку взаимного исключения можно реализовать с использованием алгоритма блокировки билетов следующим образом:

record locktype {
    int ticketnumber
    int turn
}

procedure LockInit(locktype* lock) {
    lock.ticketnumber := 0
    lock.turn := 0
}

procedure Lock(locktype* lock) {
    int myturn := FetchAndIncrement(&lock.ticketnumber) // must be atomic, since many threads might ask for a lock at the same time
    while lock.turn ≠ myturn
        skip // spin until lock is acquired
 }

procedure UnLock(locktype* lock) {
    FetchAndIncrement(&lock.turn) // this need not be atomic, since only the possessor of the lock will execute this
 }

Эти процедуры обеспечивают блокировку взаимного исключения при выполнении следующих условий:

Структура данных Locktype инициализируется с помощью функции LockInit перед использованием.
Количество задач, ожидающих блокировки, никогда не превышает INT_MAX.
Целочисленный тип данных, используемый в значениях блокировки, может «зацикливаться» при постоянном увеличении.

Аппаратная и программная поддержка

Атомный Функция fetch_add появляется в стандарте C++11 . ^[2] Он доступен как собственное расширение C в спецификации Itanium ABI . ^[3] и (с тем же синтаксисом) в GCC . ^[4]

реализация x86

В архитектуре x86 инструкция ADD с операндом назначения, указывающим местоположение памяти, представляет собой инструкцию выборки и добавления, которая существует со времен 8086 (просто тогда она так не называлась) и с префиксом LOCK является атомарной. на нескольких процессорах. Однако он не мог вернуть исходное значение ячейки памяти (хотя и возвращал некоторые флаги), пока 486 не представил инструкцию XADD.

Ниже представлена на языке C реализация компилятора GCC для 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) // input + output
      : // No input-only
      : "memory"
    );
    return value;
}

История

Технология выборки и добавления была представлена в проекте Ultracomputer , который также создал мультипроцессор, поддерживающий выборку и добавление и содержащий специальные переключатели VLSI, которые могли комбинировать одновременные обращения к памяти (включая выборку и добавление), чтобы предотвратить их сериализацию в модуль памяти, содержащий операнд назначения.

См. также

Ссылки

^ Херлихи, Морис (январь 1991 г.). «Синхронизация без ожидания» (PDF) . АКМ Транс. Программа. Ланг. Сист . 13 (1): 124–149. CiteSeerX 10.1.1.56.5659 . дои : 10.1145/114005.102808 . S2CID 2181446 . Проверено 20 мая 2007 г.
^ "std::atomic::fetch_add" . cppreference.com . Проверено 1 июня 2015 г.
^ «Двоичный интерфейс приложения (ABI) для конкретного процессора Intel Itanium» (PDF) . Корпорация Интел . 2001.
^ «Атомные встроенные элементы» . Использование коллекции компиляторов GNU (GCC) . Фонд свободного программного обеспечения. 2005.

[1] Херлихи, Морис (январь 1991 г.). «Синхронизация без ожидания» (PDF) . АКМ Транс. Программа. Ланг. Сист . 13 (1): 124–149. CiteSeerX 10.1.1.56.5659 . дои : 10.1145/114005.102808 . S2CID 2181446 . Проверено 20 мая 2007 г.

[2] "std::atomic::fetch_add" . cppreference.com . Проверено 1 июня 2015 г.

[3] «Двоичный интерфейс приложения (ABI) для конкретного процессора Intel Itanium» (PDF) . Корпорация Интел . 2001.

[4] «Атомные встроенные элементы» . Использование коллекции компиляторов GNU (GCC) . Фонд свободного программного обеспечения. 2005.

[1]

[2]

[3]

[4]