Model konzistence - Consistency model

tento článek možná matoucí nebo nejasné čtenářům. Prosím, pomoz nám objasnit článek. O tom by mohla být diskuse diskusní stránka. (Ledna 2015) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v počítačová věda, modely konzistence jsou používány v distribuované systémy jako distribuovaná sdílená paměť systémy nebo distribuovaná úložiště dat (například a souborové systémy, databáze, optimistická replikace systémy nebo ukládání do mezipaměti webu ). Systém údajně podporuje daný model, pokud se operace v paměti řídí konkrétními pravidly. Model konzistence dat specifikuje smlouvu mezi programátorem a systémem, přičemž systém zaručuje, že pokud programátor bude dodržovat pravidla, paměť bude konzistentní a výsledky čtení, zápisu nebo aktualizace paměti budou předvídatelné. To se liší od koherence, ke které dochází v systémech, které jsou uloženo do mezipaměti nebo bez mezipaměti a je to konzistence dat s ohledem na všechny procesory. Koherence se zabývá udržováním globálního pořadí, ve kterém všechny procesory vidí zápisy do jednoho umístění nebo jedné proměnné. Konzistence se zabývá uspořádáním operací na více místech s ohledem na všechny procesory.

Jazyky na vysoké úrovni, jako C ++ a Jáva, částečně udržovat smlouvu převodem operací paměti na operace nízké úrovně způsobem, který zachovává sémantika paměti. Chcete-li dodržet smlouvu, kompilátoři mohou změnit pořadí některých paměťových pokynů a volání knihoven, jako je pthread_mutex_lock () zapouzdřit požadovanou synchronizaci.^[1]

Ověření sekvenční konzistence přes kontrola modelu je nerozhodnutelný obecně i pro konečný stav soudržnost mezipaměti protokoly.^[2]

Modely konzistence definují pravidla pro zjevné pořadí a viditelnost aktualizací a jsou na kontinuum s kompromisy.^[3]

Příklad

Předpokládejme, že nastane následující případ:^[3]

• Řádek X je replikován na uzlech M a N
• Klient A zapíše řádek X do uzlu M.
• Po určité době t načte klient B řádek X z uzlu N

Model konzistence musí určit, zda klient B vidí zápis prováděný klientem A nebo ne.

Typy

Existují dvě metody k definování a kategorizaci modelů konzistence; vydání a pohled.

Problém

Metoda vydání popisuje omezení, která definují, jak může proces vydávat operace.

Pohled

Metoda zobrazení, která definuje pořadí operací viditelných pro procesy.

Například model konzistence může definovat, že procesu není povoleno vydat operaci, dokud nebudou dokončeny všechny dříve vydané operace. Různé modely konzistence vynucují různé podmínky. Jeden model konzistence lze považovat za silnější než jiný, pokud vyžaduje všechny podmínky daného modelu a další. Jinými slovy, model s méně omezeními je považován za slabší model konzistence.

Tyto modely definují, jak je třeba rozvrhnout hardware a na vysoké úrovni, jak musí programátor kódovat. Vybraný model také ovlivňuje, jak může kompilátor přeuspořádat pokyny. Obecně platí, že pokud jsou objednány závislosti ovládání mezi pokyny a zápisy do stejného umístění, může kompilátor podle potřeby změnit pořadí. U modelů popsaných níže však některé mohou umožnit přeskupení zápisů před načtením, zatímco jiné nemusí.

Přísná konzistence

Přísná konzistence je nejsilnějším modelem konzistence. V rámci tohoto modelu musí být zápis do proměnné jakýmkoli procesorem okamžitě viditelný všemi procesory.

Striktní modelový diagram a nestriktní modelová schémata popisují časové omezení - okamžité. Lze to lépe pochopit, jako by existovaly globální hodiny, ve kterých by se každý zápis měl projevit ve všech mezipaměti procesoru do konce této doby. K další operaci musí dojít až v následující hodinové periodě.

Toto je nejpevnější model. V tomto modelu bude programátor očekávaný výsledek pokaždé. Je to deterministické. Jeho praktický význam je omezen na myšlenkový experiment a formalismus, protože okamžitá výměna zpráv je nemožná. Nepomůže při odpovědi na otázku řešení konfliktů při souběžných zápisech do stejné datové položky, protože předpokládá, že souběžné zápisy jsou nemožné.

Postupná konzistence

The sekvenční konzistence model navrhl Lamport (1979). Je to slabší paměťový model než přísný model konzistence. Zápis do proměnné nemusí být viděn okamžitě, zápisy do proměnných různými procesory však musí všechny procesory vidět ve stejném pořadí. Jak je definováno Lamportem (1979),^[4] postupná konzistence je splněna, pokud „je výsledek jakéhokoli spuštění stejný, jako kdyby byly operace všech procesorů provedeny v nějakém postupném pořadí a operace každého jednotlivého procesoru se objeví v tomto pořadí v pořadí určeném jeho programem.“

Pořadí programu v rámci každého procesoru a postupné řazení operací mezi procesory by mělo být zachováno. Aby bylo možné zachovat postupné pořadí provádění mezi procesory, musí se všechny operace zdát prováděny okamžitě nebo atomicky s ohledem na všechny ostatní procesory. Tyto operace je třeba pouze „objevit“, protože je fyzicky nemožné odeslat informace okamžitě. Například v systému využívajícím jednu globálně sdílenou sběrnici, jakmile je na sběrnici uvedena informace, je zaručeno, že všechny procesory uvidí informace ve stejném okamžiku. Takže předávání informací na sběrnici dokončí provádění s ohledem na všechny procesory a zdálo se, že bylo provedeno. Architektury bez mezipaměti nebo architektury v mezipaměti s propojovacími sítěmi, které nejsou okamžité, mohou obsahovat pomalou cestu mezi procesory a pamětí. Tyto pomalé cesty mohou vést k postupné nekonzistenci, protože některé paměti přijímají vysílaná data rychleji než jiné.

Sekvenční konzistence může přinést nedeterministické výsledky. Důvodem je, že posloupnost sekvenčních operací mezi procesory se může během různých běhů programu lišit. Všechny operace s pamětí musí probíhat v pořadí programu.

Linearizovatelnost (také známý jako atomová konzistence) lze definovat jako sekvenční konzistenci s omezením v reálném čase.

Kauzální konzistence

Kauzální konzistence je oslabující model postupné konzistence kategorizováním událostí na ty, které kauzálně souvisejí a ty, které nejsou. Definuje, že pouze operace zápisu, které kauzálně souvisejí, musí být viděny ve stejném pořadí všemi procesy.

Tento model uvolňuje sekvenční konzistenci při souběžných zápisech procesorem a při zápisech, které nesouvisí kauzálně. Dva zápisy se mohou stát kauzálně související, pokud jeden zápis do proměnné závisí na předchozím zápisu do jakékoli proměnné, pokud procesor provádějící druhý zápis právě přečetl první zápis. Tyto dva zápisy mohly být provedeny stejným procesorem nebo různými procesory.

Stejně jako v postupné konzistenci nemusí čtení odrážet změny okamžitě, ale musí odrážet všechny změny proměnné postupně.

Ž₁ nesouvisí kauzálně s W₂. R1 by byla postupně nekonzistentní ale je kauzálně konzistentní.^{[je zapotřebí objasnění ][5]}

W (x) 1 a W (x) 2 jsou kauzálně příbuzné kvůli čtení provedenému P2 na x před W (x) 2.^[5]

Konzistence procesoru

Aby byla zachována konzistence dat a bylo možné dosáhnout škálovatelných procesorových systémů, kde má každý procesor svou vlastní paměť, konzistence procesoru byl odvozen model.^[5] Všechny procesory musí být konzistentní v pořadí, v jakém vidí zápisy provedené jedním procesorem a způsobem, jakým vidí zápisy různých procesorů do stejného umístění (soudržnost je zachována). Nemusí však být konzistentní, pokud jsou zápisy prováděny různými procesory do různých umístění.

Každá operace zápisu může být rozdělena do několika dílčích zápisů do všech pamětí. Ke čtení z jedné takové paměti může dojít před dokončením zápisu do této paměti. Čtená data proto mohou být zastaralá. Procesor pod PC tedy může provést mladší zátěž, když je třeba zastavit starší úložiště. Čtení před zápisem, čtení po čtení a zápis před zápisem je v tomto modelu stále zachováno.

Model konzistence procesoru^[6] je podobný Konzistence PRAM model se silnější podmínkou, která definuje všechny zápisy do stejného umístění paměti, musí být viděn ve stejném pořadí všemi ostatními procesy. Konzistence procesoru je slabší než sekvenční konzistence, ale silnější než model konzistence PRAM.

The Stanfordský multiprocesorový systém DASH implementuje variaci konzistence procesoru, která je nesrovnatelná (ani slabší, ani silnější) s Goodmanovými definicemi.^[7] Všechny procesory musí být konzistentní v pořadí, v jakém vidí zápisy od jednoho procesoru, a ve způsobu, jakým vidí zápisy různých procesorů do stejného umístění. Nemusí však být konzistentní, pokud jsou zápisy prováděny různými procesory do různých umístění.

Zřetězená konzistence RAM nebo konzistence FIFO

Zřetězená konzistence RAM (Konzistence PRAM) představili Lipton a Sandberg v roce 1988^[8] jako jeden z prvních popsaných modelů konzistence. Díky své neformální definici existují ve skutečnosti alespoň dvě nenápadně odlišné implementace,^[7] jeden od Ahamad et al. a jeden od Mosbergera.

V konzistenci PRAM všechny procesy zobrazují operace jednoho procesu ve stejném pořadí, v jakém byly vydány daným procesem, zatímco operace vydané různými procesy lze zobrazit v jiném pořadí od různých procesů. Konzistence PRAM je slabší než konzistence procesoru. PRAM uvolňuje potřebu udržovat soudržnost s umístěním napříč všemi svými procesory. Zde lze provést čtení do jakékoli proměnné před zápisem do procesoru. Čtení před zápisem, čtení po čtení a zápis před zápisem je v tomto modelu stále zachováno.

Konzistence mezipaměti

Konzistence mezipaměti^[6][9] vyžaduje, aby všechny operace zápisu do stejného umístění paměti byly prováděny v určitém pořadí. Konzistence mezipaměti je slabší než konzistence procesu a neporovnatelná s konzistencí PRAM.

Pomalá konzistence

Pomalá paměť

V pomalé konzistenci^[9] pokud proces načte hodnotu dříve zapsanou do paměťového umístění, nemůže z tohoto umístění následně přečíst žádnou dřívější hodnotu. Zápisy provedené procesem jsou pro tento proces okamžitě viditelné. Pomalá konzistence je slabší model než konzistence PRAM a mezipaměti.

Příklad:Diagram pomalé paměti zobrazuje příklad pomalé konzistence. První proces zapisuje 1 do paměťového umístění X a poté zapisuje 1 do paměťového umístění Y. Druhý proces čte 1 z Y a poté čte 0 z X, přestože X bylo zapsáno před Y.

Hutto, Phillip W. a Mustaque Ahamad (1990)^[10] ilustrují, že vhodným programováním může být pomalá paměť (konzistence) expresivní a efektivní. Zmínili, že pomalá paměť má dvě cenné vlastnosti; lokalita a podpora redukce z atomové paměti. Navrhují dva algoritmy, které představují expresivitu pomalé paměti.

Následující modely vyžadují specifickou synchronizaci programátory.

Slabé objednávání

Pořadí programu a atomicita je udržována pouze u skupiny operací a ne u všech čtení a zápisů. To bylo odvozeno z pochopení, že určité operace paměti - například ty, které jsou prováděny v kritické sekci - nemusí být viditelné všemi procesory - dokud nebudou například dokončeny všechny operace v kritické sekci. Rovněž využívá skutečnosti, že programy zapsané k provedení na víceprocesorovém systému obsahují požadovanou synchronizaci, aby se zajistilo, že nedojde k datovým rasám a výsledky SC budou vytvořeny vždy. Ve slabém pořadí lze tedy operace jiné než synchronizační operace klasifikovat jako data operace.^[11]

X = 1;plot xready = 1;

plotwhile (! xready) {}; plot y = 2;

Synchronizační operace signalizují procesoru, aby se ujistil, že dokončil a viděl všechny předchozí operace provedené všemi procesory. Aby bylo možné udržovat slabé řazení, musí být operace zápisu před operací synchronizace globálně provedeny před operací synchronizace. Operace přítomné po synchronizační operaci by měly být také prováděny až po dokončení synchronizační operace. Proto je přístup k synchronizačním proměnným sekvenčně konzistentní a jakékoli čtení nebo zápis by se mělo provádět až po dokončení předchozích synchronizačních operací. Soudržnost není v tomto modelu uvolněná. Jakmile jsou tyto požadavky splněny, lze změnit pořadí všech ostatních „datových“ operací.

V programu existuje velká závislost na explicitní synchronizaci. U modelů se slabým uspořádáním musí programátor použít pokyny pro atomové uzamčení, jako je test-and-set, fetch-and-op, uložení podmíněného, ​​propojeného se zátěží nebo musí označit proměnné synchronizace nebo použít ploty.

Uvolněte konzistenci

The konzistence uvolnění model uvolňuje model slabé konzistence rozlišením operace synchronizace vstupu od operace synchronizace výstupu. Při slabém uspořádání, když je třeba vidět synchronizační operaci, musí být všechny operace ve všech procesorech viditelné, než je synchronizační operace provedena a procesor pokračuje. V rámci modelu konzistence vydání však během vstupu do kritické sekce, nazývané „získat“, je nutné dokončit všechny operace týkající se proměnných místní paměti. Během ukončení, označovaného jako „vydání“, by měly být všechny změny provedené místním procesorem přeneseny na všechny ostatní procesory. Soudržnost je stále zachována.

Operace získání je načítání / čtení, které se provádí pro přístup do kritické sekce. Operace vydání je ukládání / zápis prováděný, aby umožnil ostatním procesorům používat sdílené proměnné.

Mezi synchronizačními proměnnými lze zachovat sekvenční konzistenci nebo konzistenci procesoru. Pomocí SC by měly být všechny konkurenční synchronizační proměnné zpracovány v pořadí. U PC však dvojice konkurenčních proměnných musí dodržovat pouze toto pořadí. Mladším akvizicím může být umožněno, aby se uskutečnily před staršími verzemi.^[12]

Vstupní konzistence

Toto je varianta modelu konzistence vydání. Vyžaduje také použití získat a uvolnění pokyny k výslovnému uvedení vstupu nebo výstupu do kritické sekce. V rámci konzistence vstupu je však každé sdílené proměnné přiřazena synchronizační proměnná, která je pro ni specifická. Tímto způsobem, pouze když je získání proměnné x, je nutné dokončit všechny operace související s x s ohledem na tento procesor. To umožňuje souběžné operace různých kritických sekcí různých sdílených proměnných. Souběžnost nelze zobrazit pro kritické operace na stejné sdílené proměnné. Takový model konzistence bude užitečný, když lze současně zpracovat různé prvky matice.

Obecná konzistence

Obecně konzistence,^[13] všechny kopie paměťového místa jsou nakonec identické po dokončení zápisů všech procesů.

Místní konzistence

V místní konzistenci^[9] každý proces provádí své vlastní operace v pořadí definovaném jeho programem. Pořadí, ve kterém se operace zápisu u jiných procesů zdají být prováděny, není nijak omezeno. Místní konzistence je nejslabší model konzistence v systémech sdílené paměti.

Další modely konzistence

Některé další modely konzistence jsou následující:

• Kauzální + konzistence^[14][15]
• Delta konzistence
• Případná konzistence
• Konzistence vidlice
• Serializovatelnost jedné kopie
• Serializovatelnost
• Konzistence vektorového pole
• Slabá konzistence
• Silná konzistence

Bylo navrženo několik dalších modelů konzistence, které vyjadřují omezení s ohledem na objednávání nebo viditelnost operací nebo se zabývají konkrétními předpoklady chyb.^[16]

Uvolněné modely konzistence paměti

Některé různé modely konzistence lze definovat uvolněním jednoho nebo více požadavků v sekvenční konzistence tzv. modely uvolněné konzistence.^[17] Tyto modely konzistence neposkytují konzistenci paměti na úrovni hardwaru. Ve skutečnosti jsou programátoři zodpovědní za implementaci konzistence paměti pomocí synchronizačních technik. Výše uvedené modely jsou klasifikovány na základě čtyř kritérií a jsou dále podrobně popsány.

Uvolněná konzistence definuje čtyři srovnání:

Relaxace

Jedním ze způsobů, jak kategorizovat uvolněnou konzistenci, je definovat, které požadavky na sekvenční konzistenci jsou uvolněné. Můžeme mít méně přísné modely uvolněním požadavků na programové pořadí nebo zápisu atomicity definovaných Adve a Gharachorloo, 1996.^[18] Pořadí programu zaručuje, že každý proces vydá požadavek na paměť nařízený jeho programem a atomicita zápisu definuje, že požadavky na paměť jsou obsluhovány na základě pořadí jedné fronty FIFO. V relaxačním pořadí programu lze uvolnit libovolné nebo všechny uspořádání provozních párů, zápisu po zápisu, čtení po zápisu nebo čtení / zápisu po čtení. V modelu uvolněnosti atomicity zápisu může proces zobrazit své vlastní zápisy před jinými procesory.

Synchronizace vs. nesynchronizace

Synchronizační model lze definovat rozdělením přístupů do paměti do dvou skupin a přiřazením různých omezení konzistence každé skupině vzhledem k tomu, že jedna skupina může mít slabý model konzistence, zatímco druhá potřebuje restriktivnější model konzistence. Naproti tomu nesynchronizující model přiřadí stejný model konzistence typům přístupu do paměti.

Problém vs. pohled

^[9] Metoda vydání poskytuje simulaci postupné konzistence definováním omezení procesů pro vydávání operací paměti. Vzhledem k tomu, metoda zobrazení popisuje omezení viditelnosti v pořadí událostí pro procesy.

Relativní pevnost modelu

Některé modely konzistence jsou přísnější než jiné. Jinými slovy, přísné modely konzistence vynucují více omezení jako požadavky na konzistenci. Síla modelu může být definována pořadím programu nebo uvolněním atomicity a sílu modelů lze také porovnat. Některé modely přímo souvisejí, pokud používají stejnou relaxaci nebo více. Na druhou stranu modely, které uvolňují různé požadavky, přímo nesouvisí.

Sekvenční konzistence má dva požadavky, pořadí programu a atomicitu zápisu. Uvolněním těchto požadavků lze získat různé modely uvolněné konzistence. To se děje tak, že spolu s uvolněnými omezeními se zvyšuje výkon, ale programátor je zodpovědný za implementaci konzistence paměti pomocí synchronizačních technik a musí dobře rozumět hardwaru.

Potenciální relaxace:

• Napište pro čtení pořadí programu
• Napište a napište objednávku programu
• Čtení pro čtení a čtení pro zápis programových objednávek

Relaxační modely

Následující modely jsou některé modely uvolněné konzistence:

Uvolněné psaní ke čtení

Přístup ke zlepšení výkonu na hardwarové úrovni spočívá v uvolnění PO při zápisu a následném čtení, které účinně skrývá latenci operací zápisu. Optimalizace, na kterou tento typ relaxace spoléhá, ​​spočívá v tom, že umožňuje, aby následná čtení byla v uvolněném pořadí s ohledem na předchozí zápisy z procesoru. Kvůli této relaxaci některé programy jako XXX nemusí kvůli této relaxaci poskytovat výsledky SC. Zatímco od programů jako YYY se stále očekává, že budou poskytovat konzistentní výsledky kvůli prosazování zbývajících omezení objednávek programů.

Do této kategorie spadají tři modely. Model IBM 370 je nejpřísnějším modelem. Čtení může být dokončeno před dřívějším zápisem na jinou adresu, ale je zakázáno vracet hodnotu zápisu, pokud zápis neviděli všechny procesory. Model SPARC V8 total store ordering model (TSO) částečně uvolňuje model IBM 370, umožňuje čtení vrátit hodnotu zápisu vlastního procesoru vzhledem k ostatním zápisům do stejného umístění, tj. Vrátí hodnotu vlastního zápisu před ostatní to vidí. Podobně jako v předchozím modelu to nemůže vrátit hodnotu zápisu, pokud všechny procesory neviděly zápis. Model konzistence procesoru (PC) je nejvíce uvolněný ze tří modelů a uvolňuje obě omezení tak, že čtení může být dokončeno před dřívějším zápisem ještě předtím, než bude viditelný pro ostatní procesory.

V příkladu A je výsledek možný pouze v IBM 370, protože čtení (A) není vydáno, dokud není dokončen zápis (A) v daném procesoru. Na druhou stranu je tento výsledek možný v TSO a PC, protože umožňují čtení příznaků před zápisem příznaků v jediném procesoru.

V příkladu B je výsledek možný pouze s PC, protože umožňuje P2 vrátit hodnotu zápisu ještě předtím, než je viditelná pro P3. U dalších dvou modelů to nebude možné.

K zajištění postupné konzistence ve výše uvedených modelech se k ručnímu vynucení omezení používají bezpečnostní sítě nebo ploty. Model IBM370 má některé specializované pokyny k serializaci které jsou ručně umístěny mezi operacemi. Tyto pokyny se mohou skládat z paměťových instrukcí nebo nepaměťových instrukcí, jako jsou větve. Na druhou stranu modely TSO a PC neposkytují bezpečnostní sítě, ale programátoři mohou stále používat operace čtení, úpravy a zápisu, aby to vypadalo, že pořadí programu je stále udržováno mezi zápisem a následujícím čtením. V případě provozovatele přenosové soustavy se zdá, že PO je zachována, pokud je R nebo W, která je již součástí R-modify-W, nahrazena R-modify-W, vyžaduje to W v R-modify-W je 'dummy', která vrací přečtenou hodnotu. Podobně pro PC se PO zdá zachována, pokud je čtení nahrazeno zápisem nebo je již součástí R-modify-W.

Optimalizace kompilátoru však nelze provést po provedení této relaxace samostatně. Optimalizace kompilátoru vyžadují plnou flexibilitu změny pořadí libovolných dvou operací v objednávce, takže schopnost změnit pořadí zápisu s ohledem na čtení není v tomto případě dostatečně užitečná.

Uvolněné psaní pro čtení a psaní pro psaní

Některé modely ještě více uvolňují pořadí programů tím, že uvolňují dokonce omezení objednávání mezi zápisy na různá místa. Jediným příkladem takového modelu je model SPARC V8 s částečným objednáním úložiště (PSO). Schopnost pipeline a překrývající se zápisy do různých umístění ze stejného procesoru je klíčová optimalizace hardwaru povolená PSO. PSO je podobný TSO, pokud jde o požadavky na atomičnost, v tom, že umožňuje procesoru číst hodnotu jeho vlastního zápisu a brání ostatním procesorům číst zápis jiného procesoru, než je zápis viditelný pro všechny ostatní procesory. Pořadí programu mezi dvěma zápisy udržuje PSO pomocí explicitní instrukce STBAR. STBAR je vložen do vyrovnávací paměti pro zápis v implementacích s vyrovnávací pamětí pro zápis FIFO. Čítač se používá k určení, kdy byly dokončeny všechny zápisy před dokončením instrukce STBAR, což spustí zápis do paměťového systému a zvýší čítač. Potvrzení zápisu sníží počitadlo a když se počitadlo stane 0, znamená to, že jsou dokončeny všechny předchozí zápisy.

V příkladech A a B umožňuje PSO oba tyto nesekvenčně konzistentní výsledky. Bezpečnostní síť, kterou PSO poskytuje, je podobná jako u TSO, ukládá programové pořadí od zápisu ke čtení a vynucuje atomicitu zápisu.

Podobně jako u předchozích modelů nejsou uvolnění povolená funkcí PSO dostatečně flexibilní, aby byla užitečná pro optimalizaci kompilátoru, což vyžaduje mnohem flexibilnější optimalizaci.

Relaxační čtení a čtení pro psaní programových objednávek

V některých modelech jsou všechny operace do různých míst uvolněné. Čtení nebo zápis lze změnit pořadí s ohledem na jiné čtení nebo zápis na jiném místě. The slabé objednávání mohou být zařazeny do této kategorie a do tohoto modelu spadají také dva typy modelů konzistence vydání (RCsc a RCpc). V rámci této kategorie relaxace jsou také navrženy tři komerční architektury: Digital Alpha, SPARC V9 relaxed memory order (RMO) a IBM PowerPC models. Všechny tyto modely umožňují přeuspořádání čtení na stejné místo, kromě Digital Alpha. Tyto modely porušují sekvenční pořadí v příkladech A a B. Další relaxace povolená v těchto modelech, která chybí v předchozích modelech, spočívá v tom, že operace paměti následující po operaci čtení lze překrývat a měnit pořadí vzhledem ke čtení. Všechny tyto modely, očekávejte RCpc a PowerPC, umožňují čtení vrátit hodnotu časného zápisu jiného procesoru. Z pohledu programátora musí všechny tyto modely udržovat iluzi atomicity zápisu, i když umožňují procesoru číst vlastní zápis brzy.

Tyto modely lze rozdělit do dvou kategorií podle typu poskytované bezpečnostní sítě. Zde je vidět potřeba pečlivě napsaných programů. Povaha synchronizace pomáhá kategorizovat mezi modely slabého řazení, RCsc a RCpc. Modely Alpha, RMO a PowerPC poskytují plotové instrukce, aby bylo možné uložit pořadí programů mezi různými operacemi paměti.

Slabé objednávání

Příkladem modelu, který uvolňuje většinu výše uvedených omezení (kromě předčasného čtení zápisů ostatních), je slabé uspořádání. Klasifikuje operace s pamětí do dvou kategorií: datové operace a synchronizační operace. Pro vynucení pořadí programu musí programátor najít v programu alespoň jednu synchronizační operaci. Předpoklad, podle kterého to funguje, je ten, že změna pořadí operací paměti do datových oblastí mezi operacemi synchronizace nemá vliv na výsledek programu. Chovají se jen jako záchranná síť pro vynucování programového řádu. Funguje to tak, že čítač sleduje počet datových operací a dokud se tento čítač nestane nulovým, synchronizační operace se nevydá. Kromě toho nebudou vydány žádné další datové operace, dokud nebudou dokončeny všechny předchozí synchronizace. Paměťové operace mezi dvěma synchronizačními proměnnými lze překrývat a měnit jejich pořadí, aniž by to ovlivnilo správnost programu. Tento model zajišťuje, že atomicita zápisu je vždy zachována, proto pro slabé řazení není nutná žádná další bezpečnostní síť.

Konzistence vydání: RCsc a RCpc

Existují dva typy konzistence vydání, konzistence vydání se sekvenční konzistencí (RCsc) a konzistence vydání s konzistencí procesoru (RCpc). Druhý typ označuje, který typ konzistence se použije na níže jmenované operace jako speciální.

Existují speciální (srov. Běžné) paměťové operace, které samy sestávají ze dvou tříd operací: synchronizace nebo nsync operace. Posledně uvedené jsou operace, které se nepoužívají k synchronizaci; první jsou a skládají se z získat a uvolnění operace. Získání je efektivně operace čtení paměti používaná k získání přístupu k určité sadě sdílených umístění. Release je na druhé straně operace zápisu, která se provádí pro udělení oprávnění pro přístup ke sdíleným umístěním.

Pro sekvenční konzistenci (RCsc) jsou omezení:

• získat → vše,
• vše → vydání,
• speciální → speciální.

Pro konzistenci procesoru (RCpc) je pořadí zápisu a čtení programu uvolněné, má omezení:

• získat → vše,
• vše → vydání,
• speciální → speciální (očekávejte, že po speciálním zápisu následuje speciální čtení).

Poznámka: výše uvedený zápis A → B znamená, že pokud operace A předchází B v pořadí programu, pak je vynuceno pořadí programu.

Alfa, RMO a PowerPC

Tyto tři komerční architektury vykazují jako bezpečnostní sítě výslovné pokyny k oplocení. Model Alpha poskytuje dva typy pokynů k oplocení, paměťová bariéra (MB) a napsat paměťovou bariéru (WMB). Operaci MB lze použít k udržení pořadí programu jakékoli operace paměti před MB s operací paměti po bariéře. Podobně WMB udržuje pořadí programů pouze mezi zápisy. Model SPARC V9 RMO poskytuje instrukci MEMBAR, kterou lze přizpůsobit tak, aby objednávala předchozí čtení a zápisy s ohledem na budoucí operace čtení a zápisu. K dosažení tohoto pořadí není nutné používat čtení, úpravy a zápisy, protože k objednání zápisu s ohledem na následující čtení lze použít instrukci MEMBAR. Model PowerPC používá jedinou plotovou instrukci nazvanou SYNC instrukce. Je to podobné jako s MB instrukcí, ale s malou výjimkou, že ke čtení může dojít mimo pořadí programu, i když je SYNC umístěn mezi dvěma čteními do stejného umístění. Tento model se také liší od Alpha a RMO z hlediska atomicity. Umožňuje vidět zápis dříve než dokončení čtení. K vytvoření iluze atomicity zápisu může být nutná kombinace operací čtení a zápisu.

Transakční paměťové modely

Transakční paměťový model^[17] je kombinace modelů koherence mezipaměti a konzistence paměti jako modelu komunikace pro systémy sdílené paměti podporované softwarem nebo hardwarem; model transakční paměti poskytuje jak konzistenci paměti, tak koherenci mezipaměti. Transakce je posloupnost operací prováděných procesem, který transformuje data z jednoho konzistentního stavu do jiného. Transakce se buď zaváže, když nedojde ke konfliktu, nebo se přeruší. V revizích jsou všechny změny viditelné pro všechny ostatní procesy, když je transakce dokončena, zatímco zrušení zruší všechny změny. Ve srovnání s uvolněnými modely konzistence se transakční model snadněji používá a může poskytnout vyšší výkon než model sekvenční konzistence.

Konzistence a replikace

Tanenbaum a kol., 2007^[19] definuje dva hlavní důvody pro replikaci; spolehlivost a výkon. Spolehlivosti lze dosáhnout v replikovaném systému souborů přepnutím na jinou repliku v případě aktuálního selhání repliky. Replikace také chrání data před poškozením poskytnutím více kopií dat na různých replikách. Rovněž zlepšuje výkon dělením práce. Zatímco replikace může zlepšit výkon a spolehlivost, může způsobit problémy s konzistencí mezi více kopiemi dat. Více kopií je konzistentních, pokud operace čtení vrací stejnou hodnotu ze všech kopií a operace zápisu jako jedna atomická operace (transakce) aktualizuje všechny kopie dříve, než dojde k jakékoli jiné operaci. Tanenbaum, Andrew & Maarten Van Steen, 2007^[19] označte tento typ konzistence jako těsná konzistence poskytované synchronní replikací. Použití globální synchronizace, aby byly všechny kopie konzistentní, je však nákladné. Jedním ze způsobů, jak snížit náklady na globální synchronizaci a zlepšit výkon, může být oslabení omezení konzistence.

Modely konzistence zaměřené na data

Tanenbaum a kol., 2007^[19] definuje model konzistence jako smlouva mezi softwarem (procesy) a implementací paměti (úložiště dat). Tento model zaručuje, že pokud software dodržuje určitá pravidla, paměť funguje správně. Protože v systému bez globálních hodin je definování poslední operace mezi zápisy obtížné, lze na hodnoty, které lze vrátit operací čtení, použít některá omezení.

Důsledné objednávání operací

Některé modely konzistence, například sekvenční a také kauzální modely konzistence, se zabývají pořadím operací se sdílenými replikovanými daty, aby zajistily konzistenci. V těchto modelech musí všechny repliky souhlasit s konzistentním globálním uspořádáním aktualizací.

Postupná konzistence

Cílem modelů konzistence zaměřených na data je poskytnout konzistentní pohled na datové úložiště, kde procesy mohou provádět souběžné aktualizace. Jeden důležitý model konzistence zaměřený na data je sekvenční konzistence definovaný Lamportem (1979).^[4] Tanenbaum a kol., 2007^[19] definuje sekvenční konzistence za následující podmínky:

Výsledek libovolného provedení je stejný, jako kdyby byly operace (čtení a zápis) všemi procesy v úložišti dat provedeny v nějakém postupném pořadí a operace každého jednotlivého procesu se objevují v tomto pořadí v pořadí určeném jeho programem.^[19]

Adve a Gharachorloo, 1996^[18] definovat dva požadavky na implementaci postupné konzistence; programové pořadí a zápis atomicity.

• Pořadí programu: Pořadí programu zaručuje, že každý proces vydá požadavek na paměť objednaný jeho programem.
• Zápis atomicity: Zápis atomicity definuje, že požadavky na paměť jsou obsluhovány na základě pořadí jedné fronty FIFO.

V postupné konzistenci není pojem o čase ani o nejnovějších operacích zápisu. Existují některé operace prokládání, které jsou stejné pro všechny procesy. Proces může vidět operace zápisu všech procesů, ale může vidět pouze své vlastní operace čtení.

Linearizovatelnost^[20] (Atomová paměť)^[17] lze definovat jako sekvenční konzistenci s omezením v reálném čase zvážením počátečního a koncového času pro každou operaci. Provedení je linearizovatelné, pokud každá operace, která probíhá v linearizovatelném pořadí, umístěním bodu mezi jeho počáteční a koncový čas a zaručuje postupnou konzistenci.

Kauzální konzistence

The kauzální konzistence^[19] definované Huttem a Ahamadem, 1990^[10] je slabší model konzistence než sekvenční konzistence tím, že rozlišuje mezi kauzálně souvisejícími operacemi a těmi, které spolu nesouvisejí. Například pokud událost b vstoupí v platnost od dřívější události a, kauzální konzistence zaručuje, že všechny procesy vidí událost b po události a.

Tanenbaum a kol., 2007^[19] definuje, že úložiště dat je považováno za kauzální konzistentní za následující podmínky:

Zápisy, které jsou potenciálně kauzálně související, musí být viděny všemi procesy ve stejném pořadí. Souběžné zápisy lze na různých počítačích vidět v jiném pořadí.^[19]

Případná konzistence

An případná konzistence^[19] je slabý model konzistence v systému s nedostatkem současných aktualizací. Definuje, že pokud žádná aktualizace netrvá velmi dlouho, všechny repliky se nakonec stanou konzistentními.

Většina sdílených decentralizovaných databází má model případné konzistence, buď ZÁKLAD: v zásadě k dispozici; měkký stav; případně konzistentní nebo kombinace KYSELINA a ZÁKLAD někdy nazývaný SALT: sekvenční; souhlasil; ledgered; odolné proti neoprávněné manipulaci a také symetrické; bez administrátora; ledgered; a časově konsensuální.^[21][22][23]

Seskupování operací^[19]

V operaci seskupování jsou přístupy k synchronizačním proměnným postupně konzistentní. Proces má povolen přístup k synchronizační proměnné, že byly dokončeny všechny předchozí zápisy. Jinými slovy, přístupy k synchronizačním proměnným nejsou povoleny, dokud nejsou zcela provedeny všechny operace se synchronizačními proměnnými.

Kontinuální konzistence

Kontinuální konzistence je definována později v části protokolu konzistence.

Modely konzistence zaměřené na klienta^[19]

V distribuovaných systémech, údržba sekvenční konzistence pro řízení souběžných operací je zásadní. V některých speciálních úložištích dat bez současných aktualizací mohou modely konzistence zaměřené na klienta řešit nekonzistence méně nákladným způsobem. Následující modely jsou některé modely konzistence zaměřené na klienta:

Monotónní konzistence čtení

Tanenbaum a kol., 2007^[19] definuje monotónní konzistenci čtení takto:

"Pokud proces načte hodnotu datové položky x, každá následná operace čtení na x tímto procesem vždy vrátí stejnou hodnotu nebo novější hodnotu."^[19]

Monotónní konzistence čtení zaručuje, že poté, co proces načte hodnotu datové položky x v čase t, nikdy neuvidí starší hodnotu této datové položky.

Monotónní konzistence zápisu

Podmínku konzistence monotónního zápisu definují Tanenbaum et al., 2007^[19] jak následuje:

"Operace zápisu procesem na datové položce X je dokončena před jakoukoli následnou operací zápisu na X stejným procesem."^[19]

Konzistence čtení a zápisu

Hodnota zapsaná procesem na datové položce X bude vždy k dispozici pro následnou operaci čtení provedenou stejným procesem na datové položce X.^[19]

Konzistence zapisuje, sleduje a čte

V konzistenci zápisů, sledování a čtení se aktualizace šíří po provedení předchozích operací čtení. Tanenbaum a kol., 2007^[19] definuje následující podmínku pro konzistenci zápisů, následů a čtení:

"Operace zápisu procesem na datové položce x po předchozí operaci čtení na x stejným procesem je zaručena, že proběhne na stejné nebo novější hodnotě x, která byla přečtena."^[19]

Konzistentní protokoly

Implementace modelu konzistence je definována protokolem konzistence. Tanenbaum a kol., 2007^[19] ilustruje některé protokoly konzistence pro modely zaměřené na data.

Kontinuální konzistence

Kontinuální konzistence zavedená Yu a Vahdatem (2000).^[24] V tomto modelu je sémantika konzistence aplikace popsána pomocí conits v aplikaci. Protože požadavky na konzistenci se mohou lišit v závislosti na sémantice aplikace, Yu a Vahdat (2000)^[24] věří, že předem definovaný jednotný model konzistence nemusí být vhodným přístupem. Aplikace by měla specifikovat požadavky na konzistenci, které splňují sémantiku aplikace. V tomto modelu aplikace určuje každý požadavek na konzistenci jako conits (zkratka jednotek konzistence). Konit může mít fyzickou nebo logickou konzistenci a používá se k měření konzistence. Tanenbaum a kol., 2007^[19] popisuje pojem conit uvedením příkladu.

Existují tři nesrovnalosti, které mohou aplikace tolerovat.

Odchylka v číselných hodnotách

^[24] Numerická odchylka omezuje rozdíl mezi upravenou hodnotou a relativní hodnotou poslední aktualizace. K zápisům lze přiřadit váhu, která definuje důležitost zápisů v konkrétní aplikaci. Celkové váhy neviditelných zápisů pro podmínku lze v aplikaci definovat jako číselnou odchylku. Existují dva různé typy numerické odchylky; absolutní a relativní číselná odchylka.

Odchylka v objednávání

^[24] Objednávková odchylka je nesrovnalost mezi místním pořadím zápisů v replice a jejich relativním uspořádáním v případném konečném obrazu.

Odchylka v zatuchlosti mezi replikami

^[24] Odchylka stálosti definuje platnost nejstaršího zápisu ohraničením rozdílu mezi aktuálním časem a časem nejstaršího zápisu na místně neviditelném omezení. Každý server má místní frontu nejistého zápisu, která vyžaduje skutečné pořadí, které má být určeno a použito na konit. Maximální délka fronty nejistých zápisů je hranicí odchylky uspořádání. Když počet zápisů překročí limit, místo přijímání nových odeslaných zápisů se server pokusí provést nejisté zápisy tím, že bude komunikovat s jinými servery na základě pořadí, ve kterém by zápis měl být proveden.

Pokud jsou všechny tři hranice odchylek nastaveny na nulu, je model konzistentní konzistence silnou konzistencí.

Primární protokoly

Primární záložní protokol

Protokol primárního zálohování (místní zápis)

Primární protokoly^[19] lze považovat za třídu protokolů konzistence, jejichž implementace je jednodušší. Například sekvenční řazení je populární model konzistence, když se uvažuje o konzistentním řazení operací. Sekvenční řazení lze určit jako primární protokol. V těchto protokolech je pro každou datovou položku v datovém úložišti přidružený primární prostředek ke koordinaci operací zápisu na této datové položce.

Protokoly vzdáleného zápisu

V nejjednodušším primárním protokolu, který podporuje replikaci, známém také jako primární záložní protokol, jsou operace zápisu předávány na jeden server a operace čtení lze provádět lokálně.

Příklad: Tanenbaum a kol., 2007^[19] uvádí příklad protokolu primární zálohy. Schéma primárního záložního protokolu ukazuje příklad tohoto protokolu. Když klient požaduje zápis, požadavek na zápis je předán na primární server. Primární server odešle požadavek na zálohy k provedení aktualizace. Server poté obdrží potvrzení aktualizace ze všech záloh a odešle potvrzení o dokončení zápisů klientovi. Každý klient může číst poslední dostupnou aktualizaci místně. Kompromisem tohoto protokolu je, že klient, který odešle požadavek na aktualizaci, bude možná muset čekat tak dlouho, aby získal potvrzení, aby mohl pokračovat. Tento problém lze vyřešit lokálním provedením aktualizací a poté požádat ostatní zálohy o provedení aktualizací. Neblokující primární záložní protokol nezaručuje konzistenci aktualizace na všech záložních serverech. Zlepšuje však výkon. V protokolu primární zálohy uvidí všechny procesy stejné pořadí operací zápisu, protože tento protokol objednává všechny příchozí zápisy na základě globálně jedinečného času. Blokovací protokoly zaručují, že procesy zobrazují výsledek poslední operace zápisu.

Místní protokoly zápisu

V primárních místních protokolech zápisu^[19] primární kopie se pohybuje mezi procesy ochotnými provést aktualizaci. Chcete-li aktualizovat datovou položku, proces ji nejprve přesune na své místo. Výsledkem je, že v tomto přístupu lze postupné operace zápisu provádět lokálně, zatímco každý proces může číst jejich místní kopii datových položek. Poté, co primární dokončí aktualizaci, aktualizace se předá dalším replikám a všichni provedou aktualizaci místně. Tento neblokující přístup může vést ke zlepšení. Schéma protokolu místního zápisu zobrazuje přístup místního zápisu v primárních protokolech. Proces požaduje operaci zápisu v datové položce x. Aktuální server je považován za nový primární pro datovou položku x. Provede se operace zápisu a po dokončení požadavku odešle primární požadavek na aktualizaci na další záložní servery. Každá záloha po dokončení operace aktualizace odešle potvrzení primárnímu.

Replikované protokoly zápisu

V protokolech replikovaného zápisu^[19] na rozdíl od primárního protokolu se všechny aktualizace provádějí ve všech replikách.

Aktivní replikace

V aktivní replikaci^[19] ke každé replice je přidružen proces k provedení operace zápisu. Jinými slovy, aktualizace jsou zasílány do každé repliky ve formě operace, aby mohly být provedeny. Všechny aktualizace je třeba provést ve stejném pořadí ve všech replikách. Ve výsledku je vyžadován zcela objednaný mechanismus vícesměrového vysílání. Při implementaci takového mechanismu vícesměrového vysílání ve velkých distribuovaných systémech existuje problém se škálovatelností. Existuje další přístup, při kterém se každá operace odesílá centrálnímu koordinátorovi (řadiči). Koordinátor nejprve přiřadí každé operaci pořadové číslo a poté předá operaci všem replikám. Druhý přístup také nemůže vyřešit problém škálovatelnosti.

Protokoly založené na kvoru^[19]

Hlasování může být dalším přístupem v protokolech replikovaného zápisu. V tomto přístupu klient požaduje a přijímá oprávnění z více serverů, aby mohl číst a zapisovat replikovaná data. Jako příklad předpokládejme, že v distribuovaném systému souborů je soubor replikován na N serverech. Chcete-li aktualizovat soubor, musí klient alespoň zaslat požadavek N / 2 + 1 za účelem souhlasu s provedením aktualizace. Po dohodě se na soubor použijí změny a aktualizovanému souboru se přidělí nové číslo verze. Podobně pro čtení replikovaného souboru odešle klient požadavek na N / 2 + 1 servery, aby z těchto serverů dostaly přidružené číslo verze. Operace čtení je dokončena, pokud jsou všechna přijatá čísla verzí nejnovější verzí.

Cache-coherence protocols

V replikovaném systému souborů je to protokol koherence mezipaměti^[19] poskytuje konzistenci mezipaměti, zatímco mezipaměti jsou obecně řízeny klienty. V mnoha přístupech je konzistence mezipaměti zajištěna základním hardwarem. Některé další přístupy v distribuovaných systémech založených na middlewaru používají softwarová řešení k zajištění konzistence mezipaměti.

Modely konzistence mezipaměti se mohou lišit v jejich strategiích detekce koherence, které definují, kdy dojde k nesrovnalostem. Existují dva přístupy k detekci nekonzistence; statická a dynamická řešení. Ve statickém řešení kompilátor určuje, které proměnné mohou způsobit nekonzistenci mezipaměti. Kompilátor tedy vynucuje instrukci, aby se vyhnul problému s nekonzistencí. V dynamickém řešení server kontroluje nekonzistence za běhu, aby kontroloval konzistenci dat uložených v mezipaměti, která se změnila po uložení do mezipaměti.

Strategie vynucování koherence je dalším protokolem koherence mezipaměti. Definuje to jak zajistit konzistenci v mezipaměti pomocí kopií umístěných na serveru. Jedním ze způsobů, jak zajistit konzistenci dat, je nikdy sdílená data neukládat do mezipaměti. Server může data uchovat a použít některý protokol konzistence, jako jsou primární protokoly, aby zajistil konzistenci sdílených dat. V tomto řešení mohou klienti ukládat do mezipaměti pouze soukromá data. V případě, že jsou sdílená data ukládána do mezipaměti, existují dva přístupy k vynucení soudržnosti mezipaměti.

V prvním přístupu, když se aktualizují sdílená data, server předá zneplatnění do všech mezipamětí. Ve druhém přístupu se aktualizace rozšíří. Většina systémů ukládání do mezipaměti používá tyto dva přístupy nebo si mezi nimi dynamicky vybírá.

Viz také

• Soudržnost mezipaměti
• Distribuovaná sdílená paměť
• Nejednotný přístup do paměti

Reference

Další čtení

• Paolo Viotti; Marko Vukolic (2016). "Konzistence v netransakčních distribuovaných úložných systémech". ACM Computing Surveys. 49 (1): 19:1–19:34. arXiv:1512.00168. doi:10.1145/2926965.
• Ali Sezgin (2004). „Formalizace a ověření sdílené paměti“ (PDF). Citovat deník vyžaduje | deník = (Pomoc) (obsahuje mnoho cenných odkazů)
• Kathy Yelick; Dan Bonachea; Chuck Wallace (2004). „Návrh modelu konzistence paměti UPC (v1.0)“ (PDF). Citovat deník vyžaduje | deník = (Pomoc)
• Mosberger, David (1993). „Modely konzistence paměti“. Recenze operačních systémů. 27 (1): 18–26. CiteSeerX  10.1.1.331.2924. doi:10.1145/160551.160553.
• Sarita V. Adve; Kourosh Gharachorloo (prosinec 1996). „Modely konzistence sdílené paměti: výuka“ (PDF). Počítač IEEE. 29 (12): 66–76. CiteSeerX  10.1.1.36.8566. doi:10.1109/2.546611. Citováno 2008-05-28.
• Steinke, Robert C .; Gary J. Nutt (2004). "Jednotná teorie konzistence sdílené paměti". Deník ACM. 51 (5): 800–849. arXiv:cs.DC / 0208027. doi:10.1145/1017460.1017464.

externí odkazy

• IETF snímky
• Řazení paměti v moderních mikroprocesorech, část I. a Část II, Paul E. McKenney (2005). Linux Journal