Uvolněte konzistenci - Release consistency

Uvolněte konzistenci je jedním ze synchronizačních systémů modely konzistence použito v souběžné programování (např. v distribuovaná sdílená paměť, distribuované transakce atd.).

Úvod[1]

V moderních paralelních výpočetních systémech konzistence paměti musí být zachována, aby se zabránilo nežádoucím výsledkům. Přísné modely konzistence jako sekvenční konzistence jsou intuitivně sestaveny, ale mohou být docela omezující z hlediska výkonu, protože by se deaktivovaly paralelismus na úrovni výuky který je široce používán v sekvenčním programování. K dosažení lepšího výkonu jsou zkoumány některé uvolněné modely a konzistence vydání je agresivním pokusem o uvolnění.

Uvolnění konzistence vs. sekvenční konzistence

Struktura hardwaru a úsilí na úrovni programu

Sekvenční konzistence lze dosáhnout jednoduše implementací hardwaru, zatímco konzistence vydání je také založena na pozorování, že většina paralelních programů je správně synchronizována. Na úrovni programování se synchronizace používá k jasnému naplánování určitého přístupu k paměti v jednom vlákně, který se má vyskytnout za druhým. Při přístupu k synchronizované proměnné by hardware zajistil, že všechny místní zápisy do procesoru byly přeneseny do všech ostatních procesorů a všechny zápisy z jiných procesorů budou viditelné a shromážděné. V modelu konzistence vydání je akce vstupu a výstupu a kritická sekce jsou klasifikovány jako získat a uvolnění a pro oba případy by měl být do programu vložen explicitní kód ukazující, kdy tyto operace provést.

Podmínky pro postupný konzistentní výsledek

Obecně platí, že distribuovaná sdílená paměť je konzistentní s vydáním, pokud se řídí následujícími pravidly:[2]

1. Před provedením přístupu ke sdílené proměnné musí být dokončeny všechny předchozí akvizice tímto procesorem.

2. Před provedením vydání musí být dokončena všechna předchozí čtení a zápisy tímto procesem.

3. Přístupy pro získání a vydání musí být konzistentní s procesorem.

Pokud jsou splněny výše uvedené podmínky a program je správně synchronizován (tj. Procesory implementují správně získání a vydání), výsledky jakéhokoli spuštění budou přesně stejné, jako by byly provedeny po postupné konzistenci. Ve skutečnosti jsou přístupy ke sdíleným proměnným rozděleny na atomové provozní bloky pomocí získat a uvolnění primitivy, takže bude zabráněno rasám a prokládání mezi bloky.

Implementace[3]

Uvolnění zámku

Příklad konzistence vydání implementovaný operací uvolnění zámku.

Uvolnění zámku lze považovat za typ synchronizace vydání. Předpokládejme, že se operace smyčky provádí pomocí kódu zobrazeného vpravo. Dvě vlákna mají v úmyslu vstoupit do kritické sekce a přečíst nejnovější hodnotu A, poté ukončete kritickou část. Kód ukazuje, že vlákno 0 nejprve získá zámek a vstoupí do kritické sekce. Aby bylo možné provést správně, P1 musí číst nejnovější hodnotu A napsal P0. V takovém případě může být v kritické sekci najednou pouze jedno vlákno. Proto samotná synchronizace zajistila, že k úspěšnému získání zámku na P1 dojde po uvolnění zámku P0. Kromě toho musí být zajištěno uspořádání S2 -> S3, protože P0 musí šířit novou hodnotu A na P1. Ze stejného důvodu musí S5 nastat po S4.

Je patrné, že správnost není ovlivněna, pokud paměť přistupuje po problému s odemknutím před dokončením odemknutí nebo přístup do paměti před problémem se zámkem po získání zámku. Kód v kritické sekci však nelze vydat před dokončením získání zámku, protože nemusí být zaručeno vzájemné vyloučení.

Po čekání

Příklad konzistence vydání implementovaný synchronizací po čekání.

Synchronizace po čekání je další implementační forma konzistence vydání. Jak je znázorněno v kódu vpravo, správnost lze zajistit, pokud dojde k následným operacím až po dokončení veškerého přístupu do paměti, zejména při uložení do „a“. Kromě toho by operace čtení neměla být prováděna, dokud není operace čekání dokončena. S2 funguje jako synchronizace vydání a S3 jako synchronizace získání. Proto musí S2 zabránit tomu, aby po něm došlo k předchozímu spuštění, a S3 musí zabránit tomu, aby před ním došlo k jakémukoli pozdějšímu spuštění. S2 nemusí bránit tomu, aby před ním došlo k pozdějšímu provedení, Stejně tak S3 nemusí zabránit tomu, aby po něm došlo k jakémukoli předchozímu provedení.

Líná konzistence uvolňování[4]

Propagace zápisu v modelu konzistence vydání

Líná konzistence vydání je další optimalizací konzistence vydání. Předpokládá, že vlákno provádějící získání přístupu nepotřebuje hodnoty zapsané jinými vlákny, dokud nebude získaný přístup dokončen. Veškeré chování koherence tedy může být zpožděno a může být vylepšeno načasování šíření zápisu.

Příklad

Zvažte scénáře popsané na obrázku vpravo. Tento případ ukazuje, kdy se šíření zápisu provádí v koherentním systému mezipaměti na základě modelu konzistence vydání. Proměnná datum je zcela rozšířen před šířením datumIsReady. Ale hodnota datum není potřeba až po získání synchronizačního přístupu v P1 a lze jej šířit spolu s datumIsReady aniž by došlo k poškození výsledku programu.

Propagace zápisu v modelu konzistence líného vydání

Druhý obrázek zobrazuje, co se stane, když se použije konzistence líného vydání. Vzhledem k tomuto scénáři jsou všechny hodnoty zapsané před synchronizací vydání zpožděny a šířeny společně s šířením samotného přístupu k vydání. Proto, datum a datumIsReady se šíří společně v bodě uvolnění.

„TreadMarks“[5] je skutečná aplikace konzistence líného uvolňování.

Zlepšení výkonu oproti konzistenci vydání

Líná konzistence vydání může v určitých případech překonat konzistenci vydání. Pokud existuje systém s malou šířkou pásma mezi procesory, nebo špatně trpí vyššími režijními náklady kvůli častému šíření malého bloku dat versus zřídka velkému šíření datových bloků, může LRC skutečně pomoci výkonu.

Zvažte, že systém využívá spíše softwarovou abstrakci sdílené paměti než skutečnou hardwarovou implementaci. V tomto systému se šíření zápisu provádí s granularitou stránky, což extrémně prodlužuje šíření celé stránky, když je upraven pouze jeden blok na této stránce. Šíření zápisu je proto zpožděno, dokud není dosažen bod synchronizace vydání a v tuto chvíli bude upravena celá stránka a bude šířena celá stránka.

Nevýhoda

LRC vyžaduje hromadné provádění šíření zápisu v bodě uvolnění synchronizace. Propagace tak velkého počtu zápisů dohromady zpomalí přístup k vydání a následné získání přístupu. Proto může jen těžko zlepšit výkon systému koherence hardwarové mezipaměti.

Uvolněte konzistenci vs. jiné uvolněné modely konzistence[6]

Slabé objednávání (Slabá konzistence )

Konzistence vydání vyžaduje od programátorů více ve srovnání se slabým uspořádáním. Musí označovat synchronizační přístupy jako získání nebo vydání, nejen jako synchronizační přístupy. Podobně jako slabé řazení, konzistence vydání umožňuje kompilátoru volně měnit pořadí načítání a ukládání, kromě toho, že nemohou migrovat nahoru za synchronizaci získání a nemohou migrovat dolů za synchronizaci vydání. Flexibilita a výkonnostní výhoda konzistence vydání však přichází na úkor vyžadování toho, aby byly synchronizační přístupy správně identifikovány a identifikovány jako akvizice a vydání. Na rozdíl od slabého řazení nelze synchronizační přístupy snadno identifikovat pouhými operačními kódy. Proto je na břemenu programátorů, aby správně identifikovali přístupy k získání a uvolnění synchronizace.[3]

Konzistence procesoru

Kvůli konzistenci procesoru všechny procesy viz zápisy od každého procesoru v pořadí, v jakém byly zahájeny. Zápisy od různých procesorů nemusí být vidět ve stejném pořadí, kromě toho, že zápisy do stejného umístění budou všude vidět ve stejném pořadí. Ve srovnání s konzistencí procesoru je konzistence vydání uvolněnější, protože nevynucuje řazení mezi obchody, ke kterému dochází v konzistenci procesoru. Nesleduje intuici programátorů, protože je relativně méně omezující na optimalizaci kompilátoru.

Viz také

Reference

  1. ^ Konzistence paměti a řazení událostí ve škálovatelných multiprocesorech sdílené paměti autorů: Kourosh Gharachorloo, Daniel Lenoski, James Laudon, Phillip Gibbons, Anoop Gupta a John Hennessy publikovaných v ISCA '90 Proceedings of the 17. každoroční mezinárodní sympozium o počítačové architektuře
  2. ^ Tanenbaum, Andrew (1995). Distribuované operační systémy. Pearson Education. 327–330. ISBN  9788177581799.
  3. ^ A b Solihin, Yan (2015). Základy paralelní vícejádrové architektury. Chapman & Hall / CRC Computational Science. 315–320. ISBN  9781482211184.
  4. ^ Líná konzistence vydání pro softwarově distribuovanou sdílenou paměť Pete Keleher, Alan L. Cox a Willy Zwaenepoel publikované v Proceeding ISCA '92 Proceedings of the 19. každoroční mezinárodní symposium o počítačové architektuře
  5. ^ TreadMarks: distribuovaná sdílená paměť na standardních pracovních stanicích a operačních systémech autor: Pete Keleher, Alan L. Cox, Sandhya Dwarkadas a Willy Zwaenepoel publikovali ve sborníku WTEC'94 z technické konference USENIX zima 1994 o technické konferenci USENIX zima 1994
  6. ^ Culler, David; Gupta, Anoop; Singh, Jaswinder (1997). Paralelní počítačová architektura: Hardwarový / softwarový přístup. Morgan Kaufmann Publishers Inc., str. 620–626. ISBN  1558603433.