Fetch-and-add

Fetch-and-add (FAA) — це процесорна атомарна інструкція, яка збільшує вміст комірки пам'яті на задане значення.

Тобто fetch-and-add виконує таку операцію: збільшує значення за адресою x на a, де x — це комірка пам'яті, a — деяке значення, і повертає початкове значення за адресою x.

При цьому операція виконується таким чином, що якщо її виконує один процес у системі з паралельним виконанням, жоден інший процес ніколи не побачить проміжного результату.

Fetch-and-add може використовуватися для реалізації структур керування конкурентним доступом, таких як м'ютекси та семафори.

Мотивація для існування атомарної операції fetch-and-add полягає в тому, що операції, які в мовах програмування записуються як x = x + a, не є безпечними в конкурентній системі, де одночасно виконуються кілька процесів або потоків (або в багатопроцесорній системі, або в однопроцесорній системі з витискальним плануванням). Причина полягає в тому, що така операція насправді реалізується як кілька машинних інструкцій:

1. завантажити x у регістр;
2. додати a до вмісту регістра;
3. записати значення регістра назад у x.

Коли один процес одночасно виконує x = x + a, а інший — x = x + b, виникає гонитва даних. Обидва процеси можуть зчитати значення x_old, виконати над ним свої обчислення, а потім записати результати назад, унаслідок чого один результат перезапише інший. У підсумку збережене значення стане або x_old + a, або x_old + b, а не x_old + a + b, як можна було б очікувати.

У однопроцесорних системах, які не підтримують витіснення ядра, достатньо вимкнути переривання перед входом до критичної секції. Однак у багатопроцесорних системах (навіть за вимкнених переривань) два або більше процесорів можуть одночасно намагатися отримати доступ до однієї й тієї самої ділянки пам'яті. Інструкція fetch-and-add дає змогу будь-якому процесору атомарно збільшити значення в пам'яті, запобігаючи таким конфліктам між процесорами.

Моріс Герлігі (1991) довів, що операція fetch-and-add має скінченне число консенсусу, на відміну від операції compare-and-swap. Операція fetch-and-add може розв'язати задачу безочікувального консенсусу не більш ніж для двох процесів, що виконуються одночасно.^[1]

Інструкція fetch-and-add поводиться так само, як наведена нижче функція. Важливо, що вся функція виконується атомарно: жоден процес не може перервати її під час виконання й, відповідно, побачити стан, який існує лише в процесі виконання цієї функції. Наведений код слугує лише для пояснення принципу роботи fetch-and-add; забезпечення атомарності потребує явної апаратної підтримки, тому її не можна реалізувати як звичайну функцію високого рівня.

using std::atomic;

int fetchAndAdd(atomic<int>* location, int inc) {
    return location->fetch_add(inc);
}

Взаємовиключене блокування можна реалізувати за допомогою алгоритму блокування за квитками таким чином:

import std;

using std::atomic;
using std::memory_order;

class Lock {
private:
    atomic<int> ticketNumber{0};
    atomic<int> turn{0};
public:
    void lock() {
        // Must be atomic, since many threads may ask for a lock simultaneously
        int myTurn = ticketNumber.fetch_add(1, memory_order::relaxed):
        while (turn.load(memory_order::acquire) != myTurn) {
            // Spin until lock is acquired
        }
    }

    void unlock() {
        // This need not be atomic, as only the possessor of the lock will execute this
        turn.fetch_add(1, memory_order::release);
    }
};

Атомарний метод fetch_add() для std::atomic<T> з'явився у стандарті C++11.^[2] Він також доступний як пропрієтарне розширення для C у специфікації ABI для Itanium,^[3] а також (із тим самим синтаксисом) у GCC.^[4]

В архітектурі x86 інструкція ADD, у якій операнд призначення вказує на комірку пам'яті, є інструкцією fetch-and-add і існує ще з часів 8086 (хоча тоді вона так не називалася). Разом із префіксом LOCK вона виконується атомарно навіть у багатопроцесорних системах. Проте до появи інструкції XADD у 486 вона не могла повертати початкове значення комірки пам'яті (хоча повертала значення деяких прапорців).

Нижче наведено реалізацію мовою C для компілятора GCC на 32- і 64-бітних платформах Intel x86, яка використовує розширений синтаксис asm:

inline int fetchAndAdd(int* variable, int value) {
    asm volatile(
        "lock; xaddl %0, %1"
        : "+r" (value), "+m" (*variable) // input + output
        : // No input-only
        : "memory"
    );
    return value;
}

Операцію fetch-and-add було вперше запропоновано в межах проєкту Ultracomputer, у рамках якого також було створено багатопроцесорну систему з підтримкою fetch-and-add і спеціалізованими НВІС-комутаторами, здатними об'єднувати одночасні звернення до пам'яті (зокрема операції fetch-and-add), щоб запобігти їх послідовному виконанню в модулі пам'яті, який містить операнд призначення.

• Compare-and-swap
• Load-link/store-conditional
• Read–modify–write
• Test-and-set
• Test and test-and-set