Fetch-and-add (FAA) — це процесорна атомарна інструкція, яка збільшує вміст комірки пам'яті на задане значення.
Тобто fetch-and-add виконує таку операцію: збільшує значення за адресою на , де — це комірка пам'яті, — деяке значення, і повертає початкове значення за адресою .
При цьому операція виконується таким чином, що якщо її виконує один процес у системі з паралельним виконанням, жоден інший процес ніколи не побачить проміжного результату.
Fetch-and-add може використовуватися для реалізації структур керування конкурентним доступом, таких як м'ютекси та семафори.
Мотивація Мотивація для існування атомарної операції fetch-and-add полягає в тому, що операції, які в мовах програмування записуються як , не є безпечними в конкурентній системі, де одночасно виконуються кілька процесів або потоків (або в багатопроцесорній системі, або в однопроцесорній системі з витискальним плануванням). Причина полягає в тому, що така операція насправді реалізується як кілька машинних інструкцій:
завантажити у регістр; додати до вмісту регістра; записати значення регістра назад у .
Коли один процес одночасно виконує , а інший — , виникає гонитва даних. Обидва процеси можуть зчитати значення , виконати над ним свої обчислення, а потім записати результати назад, унаслідок чого один результат перезапише інший. У підсумку збережене значення стане або , або , а не , як можна було б очікувати.
У однопроцесорних системах, які не підтримують витіснення ядра, достатньо вимкнути переривання перед входом до критичної секції. Однак у багатопроцесорних системах (навіть за вимкнених переривань) два або більше процесорів можуть одночасно намагатися отримати доступ до однієї й тієї самої ділянки пам'яті. Інструкція fetch-and-add дає змогу будь-якому процесору атомарно збільшити значення в пам'яті, запобігаючи таким конфліктам між процесорами.
Моріс Герлігі (1991) довів, що операція fetch-and-add має скінченне число консенсусу, на відміну від операції compare-and-swap. Операція fetch-and-add може розв'язати задачу безочікувального консенсусу не більш ніж для двох процесів, що виконуються одночасно.
Реалізація Інструкція 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);
Апаратна та програмна підтримка Атомарний метод для std::atomic<T> з'явився у стандарті C++11. Він також доступний як пропрієтарне розширення для C у специфікації ABI для Itanium, а також (із тим самим синтаксисом) у GCC.
Реалізація в x86 В архітектурі 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
Примітки