Načíst a přidat - Fetch-and-add
v počítačová věda, načíst a přidat procesor instrukce (FAA) atomicky zvýší obsah paměťového místa o zadanou hodnotu.
To znamená, že načtení a přidání provede operaci
- zvýší hodnotu na adrese X podle A, kde X je místo v paměti a A je nějaká hodnota a vrátí původní hodnotu na X
takovým způsobem, že pokud je tato operace provedena jedním procesem v a souběžně systému, žádný jiný proces nikdy neuvidí přechodný výsledek.
Fetch-and-add lze použít k implementaci řízení souběžnosti struktury jako zámky mutex a semafory.
Přehled
Motivací pro atomové načítání a přidávání jsou operace, které se v programovacích jazycích zobrazují jako
- x = x + a
nejsou bezpečné v souběžném systému, kde je více procesy nebo vlákna běží současně (buď v více procesorů systém, nebo preventivně naplánováno na některé jednojádrové systémy). Důvodem je, že taková operace je ve skutečnosti implementována jako více strojových instrukcí:
- Načtěte hodnotu na místě X, řekněme Xstarý, do rejstříku;
- přidat A na Xstarý v rejstříku;
- uložit novou hodnotu registru zpět do X.
Když jeden proces dělá x = x + a a další dělá x = x + b současně existuje stav závodu. Mohli by přinést oba Xstarý a pracovat na tom, pak oba uložit své výsledky s účinkem, že jeden přepíše druhý a uložená hodnota se stane buď Xstarý + A nebo Xstarý + b, ne Xstarý + A + b jak by se dalo očekávat.
v jednoprocesor systémy bez č předpoklad jádra podporováno, stačí deaktivovat přerušení před přístupem k kritická sekce V systémech s více procesory (i když jsou deaktivována přerušení) se však dva nebo více procesorů mohlo pokoušet získat přístup ke stejné paměti současně. Instrukce načtení 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ázali, že načítání a přidávání má konečnou hodnotu shoda číslo, na rozdíl od porovnat a vyměnit úkon. Operace načtení a přidání může vyřešit problém konsensu bez čekání pro ne více než dva souběžné procesy.[1]
Implementace
Instrukce načtení a přidání se chová jako následující funkce. Klíčové je, že je provedena celá funkce atomicky: žádný proces nemůže přerušit funkci uprostřed provádění, a tedy vidět stav, který existuje pouze během provádění funkce. Tento kód slouží pouze k objasnění chování načítání a přidávání; atomicita vyžaduje výslovnou hardwarovou podporu, a proto ji nelze implementovat jako jednoduchou funkci na vysoké úrovni.
<< atomic >>funkce FetchAndAdd (adresa umístění, int inc) { int value: = * location * location: = value + inc vrátit se hodnota}
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í zámek lístku algoritmus jako:
záznam typ zámku { int číslo lístku int otáčet se}postup LockInit (typ zámku* zámek) {lock.ticketnumber: = 0 lock.turn: = 0}postup Zámek(typ zámku* zámek) { int myturn: = FetchAndIncrement (& lock.ticketnumber) // musí být atomové, protože mnoho vláken může požádat o zámek současně zatímco lock.turn ≠ myturn přeskočit // otáčejte, dokud nezískáte zámek }postup Odemknout(typ zámku* zámek) {FetchAndIncrement (& lock.turn) // toto nemusí být atomové, protože to provede pouze vlastník zámku}
Tyto rutiny poskytují zámek vzájemného vyloučení, pokud jsou splněny následující podmínky:
- Struktura dat typu Locktype je před použitím inicializována funkcí LockInit
- Počet úkolů čekajících na zámek kdykoli nepřekročí INT_MAX
- Celočíselný datový typ použitý v hodnotách zámku se může „zalomit“, když se neustále zvyšuje
Hardwarová a softwarová podpora
Atomový načíst_add funkce se objeví v C ++ 11 Standard.[2] Je k dispozici jako proprietární rozšíření pro C v Itanium ABI Specifikace,[3] a (se stejnou syntaxí) v GCC.[4]
implementace x86
V architektuře x86 je instrukce ADD s cílovým operandem určujícím umístění paměti instrukcí načtení a přidání, která tam byla od 8086 (to se tehdy tak nenazvalo) a s předponou LOCK je atomová napříč více procesory. Nemohlo však vrátit původní hodnotu umístění paměti (i když vrátilo některé příznaky), dokud 486 představil instrukci XADD.
Toto je a C implementace pro GCC překladač pro 32 i 64bitové platformy x86 Intel, založený na rozšířené syntaxi asm:
statický v souladu int načíst_a_přidat(int* proměnná, int hodnota){ __asm__ nestálý("zámek; xaddl% 0,% 1" : „+ r“ (hodnota), „+ m“ (*proměnná) // vstup + výstup : // Žádný pouze vstup : "Paměť" ); vrátit se hodnota;}
Dějiny
Fetch-and-add představil Ultrapočítač project, který také vytvořil multiprocesor podporující fetch-and-add a obsahující vlastní přepínače VLSI, které byly schopny kombinovat souběžné odkazy na paměť (včetně fetch-and-adds), aby jim zabránily v serializaci na paměťovém modulu obsahujícím cílový operand.
Viz také
Reference
- ^ Herlihy, Maurice (leden 1991). „Synchronizace bez čekání“ (PDF). ACM Trans. Program. Lang. Syst. 13 (1): 124–149. CiteSeerX 10.1.1.56.5659. doi:10.1145/114005.102808. Citováno 2007-05-20.
- ^ "std :: atomic :: fetch_add". cppreference.com. Citováno 1. června 2015.
- ^ „Intel Itanium Processor-specific Application Binary Interface (ABI)“ (PDF). Intel Corporation. 2001.
- ^ „Atomic Builtins“. Používání GNU Compiler Collection (GCC). Free Software Foundation. 2005.
Tento operační systém související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to. |