Atomová sémantika - Atomic semantics
Atomová sémantika je druh záruky poskytované a datový registr sdílí několik procesory v paralelní stroj nebo v síti počítačů spolupracujících. Atomová sémantika je velmi silná. Atomový registr poskytuje silné záruky, i když existuje souběžnost a selhání.
Registr pro čtení / zápis R ukládá hodnotu a je přístupný dvěma základními operacemi: čtení a zápis (v). Čtení vrátí hodnotu uloženou v R a write (v) změní hodnotu uloženou v R na v. Registr se nazývá atomický, pokud splňuje dvě následující vlastnosti:
1) Každá operace vyvolání operace čtení nebo zápisu:
• Musí se objevit, jako by byl proveden v jednom bodě τ (op) v čase.
• τ (op) funguje následovně: τb (op) ≤ τ (op) ≤ τe (op): kde τb (op) a τe (op) označují čas, kdy operace op začíná a končí.
• Pokud op1 ≠ op2, pak τ (op1) ≠ τ (op2)
2) Každá operace čtení vrací hodnotu zapsanou poslední operací zápisu před čtením v pořadí, ve kterém jsou všechny operace seřazeny podle jejich hodnot τ.
Atomový / linearizovatelný registr:
Ukončení: když je uzel správný, dříve nebo později bude každá operace čtení a zápisu dokončena.
Bezpečnostní majetek (Linearizační body pro čtení a zápis a neúspěšné operace):
Operace čtení: Vypadá to, jako by se to stalo na všech uzlech někdy mezi vyvoláním a dobou odezvy.
Operace zápisu: Podobně jako operace čtení se zdá, jako by se to stalo na všech uzlech někdy mezi vyvoláním a dobou odezvy.
Neúspěšná operace (atomový termín pochází z tohoto pojmu): Vypadá to, jako by byl dokončen v každém jednotlivém uzlu nebo se to nikdy nestalo v žádném uzlu.
Příklad: Víme, že atomový registr je takový, který je linearizovatelný na sekvenční bezpečný registr.
Následující obrázek ukazuje, kam bychom měli umístit linearizační bod pro každou operaci:
Atomový registr lze definovat pro proměnnou s jedním zapisovačem, ale s více čtečkami (SWMR), s jedním zapisovačem / s jedním čtečkem (SWSR) nebo s více zapisovačem / více čtečkami (MWMR). Zde je příklad atomového registru s více čtečkami a více zapisovači, ke kterému přistupují tři procesy (P1, P2, P3). Všimněte si, že R. read () → v znamená, že odpovídající operace čtení vrátí v, což je hodnota registru. Následující provedení registru R by tedy mohlo splňovat definici atomových registrů: R.write (1), R.read () → 1, R.write (3), R.write (2), R.read () → 2, R. číst () → 2.
Viz také
Reference
- Atomová sémantika je formálně definována v Lamportově „On Interprocess Communication“ Distributed Computing 1, 2 (1986), 77-101. (Také se objevila jako SRC Research Report 8).