Fetch And Add in computer science , odkazuje na instrukci procesoru Fetch-And-Add (FAA), která atomicky zvyšuje obsah paměťového místa o zadanou hodnotu.
To znamená, že instrukce extrahovat a přidat provede operaci zvyšující hodnotu na adrese x o a (kde x je adresa paměti a a je libovolná hodnota), a poté vrátí původní hodnotu. Adresa x, takže pokud je tato operace provedena jeden proces v souběžném systému , žádný jiný proces nikdy neuvidí přechodný výsledek.
Instrukci extrahovat a přidat lze použít k implementaci struktur řízení souběžnosti, jako jsou zámky vzájemného vyloučení a semafory .
Motivací pro získání atomového výpisu a prohlášení je, že operace, které se objevují v programovacích jazycích jako x = x + a, nejsou bezpečné v souběžném systému, kde běží současně více procesů nebo vláken (buď v systému s více procesory, nebo plánované preventivně na některých jednojádrových systémech). Důvodem je, že taková operace je ve skutečnosti implementována jako více strojových instrukcí:
Když jeden proces probíhá x = x + a a další dělá x = x + b současně, nastává situace závodu . Mohou oba chytit x staré a pracovat na tom, pak oba ukládají své výsledky s efektem, že jeden přepíše druhý a uložená hodnota se stane buď x old + a nebo x old + b , ne x old + a + b jak by mohlo být očekávaný.
V jednoprocesorových systémech bez podpory předvolby jádra stačí před přístupem do kritické sekce deaktivovat přerušení .
Nicméně, v víceprocesorových systémů (dokonce i při přerušení se zdravotním postižením), dva nebo více procesorů se může pokusit o přístup stejnou paměť současně. Instrukce pro extrahování a přidání umožňuje kterémukoli procesoru atomicky zvýšit hodnotu v paměti a zabránit tak kolizím více procesorů.
Maurice Herlihy (1991) prokázal, že instrukce pro extrakci a přidání má na rozdíl od operace porovnání a výměny konečné číslo konsensu . Operace extrakce a přidání může vyřešit problém konsensu bez čekání na více než dva současné procesy.
Instrukce pro extrakci a přidání se chová jako následující funkce. V zásadě se celá funkce provádí atomicky : žádný proces nemůže přerušit spuštěnou funkci, a proto vidí stav, který existuje pouze za běhu funkce. Následující kód slouží pouze k vysvětlení chování instrukce; atomicity vyžaduje explicitní podporu hardwaru a nemůže být proveden jako jednoduchá funkce vysoké úrovni.
<< atomique >> function FetchAndAdd(address location, int inc) { int value := *location *location := value + inc return value }Chcete-li implementovat zámek vzájemného vyloučení , definujeme operaci FetchAndIncrement, která je ekvivalentní FetchAndAdd s inc = 1.
S touto operací lze zámek vzájemného vyloučení implementovat pomocí algoritmu uzamčení lístku , jako je:
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 }Tyto rutiny poskytují zámek vzájemného vyloučení, když jsou splněny následující podmínky:
Atomová funkce fetch_add se objeví ve standardu C ++ 11 . Je k dispozici jako proprietární rozšíření C ve specifikaci Itanium ABI a (se stejnou syntaxí) v GCC .
V architektuře x86 je instrukce ADD s cílovým operandem určujícím místo v paměti instrukcí pro extrakci a přidání, která existuje již od 8086 (v té době se tomu tak říkalo) a s předponou LOCK je atomová na více procesorech. Nemohlo však vrátit původní hodnotu umístění v paměti (ačkoli vrátilo některé příznaky), dokud 486 nevstoupila do instrukce XADD.
Zde je implementace C pro kompilátor GCC pro 32bitové a 64bitové platformy Intel x86 na základě rozšířené syntaxe 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; }Instrukci pro extrakci a přidání představil projekt Ultracomputer , který také vytvořil multiprocesor podporující tuto instrukci a obsahující vlastní přepínače VLSI schopné kombinovat simultánní odkazy na paměť (včetně načtení a přidání instrukce d), aby se zabránilo jejich serializaci do paměťového modulu obsahující cílový operand.