Linearizovatelnost - Linearizability

Šedě lineární dílčí historie, procesy začínající na b nemají linearizovatelnou historii, protože b0 nebo b1 se mohou dokončit v jakémkoli pořadí, než dojde k b2.

V souběžném programování je operace (nebo sada operací) linearizovatelná, pokud se skládá z uspořádaného seznamu událostí vyvolání a odezvy ( zpětných volání ), které lze rozšířit přidáním událostí odezvy tak, že:

1. Rozšířený seznam lze znovu vyjádřit jako sekvenční historii (lze serializovat ).
2. Tato sekvenční historie je podmnožinou původního nerozbaleného seznamu.

Neformálně to znamená, že neupravený seznam událostí je linearizovatelný právě tehdy, pokud jeho vyvolání byla serializovatelná , ale některé odpovědi sériového plánu se ještě musí vrátit.

V souběžném systému mohou procesy přistupovat ke sdílenému objektu současně. Protože k jednomu objektu přistupuje více procesů, může nastat situace, ve které zatímco jeden proces přistupuje k objektu, jiný proces mění jeho obsah. Tento příklad ukazuje potřebu linearizovatelnosti. V linearizovatelném systému, i když se operace na sdíleném objektu překrývají, se zdá, že každá operace probíhá okamžitě. Linearizovatelnost je podmínka silné správnosti, která omezuje, jaké výstupy jsou možné, když je k objektu přistupováno více procesy současně. Jedná se o bezpečnostní vlastnost, která zajišťuje, že operace se nedokončí neočekávaným nebo nepředvídatelným způsobem. Pokud je systém linearizovatelný, umožňuje programátorovi uvažovat o systému.

Historie linearizovatelnosti

Atomicita byl nejprve zaveden jako modelu konzistence podle Herlihy a křídlo v roce 1987. To zahrnovalo více omezující definice atomová, jako je například „atomická operace je takový, který nemůže být (nebo ne) přerušena paralelních operací“, které jsou obvykle nejasné když se má za to, že operace začíná a končí.

Atomový objekt lze chápat okamžitě a úplně z jeho postupné definice, jako soubor operací probíhajících paralelně, které se vždy objevují jeden po druhém; nemusí se objevit žádné nesrovnalosti. Linearizovatelnost konkrétně zaručuje, že invarianty systému budou dodrženy a zachovány všemi operacemi: pokud všechny operace jednotlivě zachovají invariant, bude to systém jako celek.

Definice linearizovatelnosti

Souběžný systém se skládá z kolekce procesů komunikujících prostřednictvím sdílených datových struktur nebo objektů. Linearizovatelnost je důležitá v těchto souběžných systémech, kde k objektům lze přistupovat více procesy současně a programátor musí být schopen uvažovat o očekávaných výsledcích. Provedení souběžného systému má za následek historii , uspořádanou sekvenci dokončených operací.

Historie je sekvence vyvolání a odpovědí z objektu sadou nití nebo procesy. Vyvolání lze považovat za začátek operace a odezvou je signalizovaný konec této operace. Každé vyvolání funkce bude mít následnou odpověď. To lze použít k modelování jakéhokoli použití objektu. Předpokládejme například, že dvě vlákna, A a B, se obě pokusí uchopit zámek a ustoupí, pokud je již obsazen. To by bylo modelováno jako oba podprocesy vyvolávající operaci zámku, poté oba podprocesy obdrží odpověď, jeden úspěšný, druhý ne.

Sekvenční historie je taková, ve které jsou všechny vyvolání mít okamžité reakce; to znamená, že vyvolání a reakce se považují za uskutečněné okamžitě. Sekvenční historie by měla být triviální, protože nemá skutečnou souběžnost; předchozí příklad nebyl sekvenční, a proto je těžké o něm uvažovat. To je místo, kde přichází linearizovatelnost.

Historie je linearizovatelná, pokud existuje lineární pořadí dokončených operací tak, že: ${\ displaystyle \ sigma}$

1. Pro každou dokončenou operaci v vrátí operace stejný výsledek v provedení, jako by se operace vrátila, pokud by byla každá operace dokončena jeden po druhém v pořadí .${\ displaystyle \ sigma}$${\ displaystyle \ sigma}$
2. Pokud je operace op ₁ dokončena (dostane odpověď) před začátkem op ₂ (vyvolá), pak op ₁ předchází op ₂ in .${\ displaystyle \ sigma}$

Jinými slovy:

• jeho vyvolání a odpovědi lze změnit pořadí, aby se získala sekvenční historie;
• že sekvenční historie je správná podle postupné definice objektu;
• pokud odpověď předcházela vyvolání v původní historii, musí ji předcházet při postupném přeskupování.

(Všimněte si, že první dvě odrážky se zde shodují se serializovatelností : zdá se, že operace probíhají v určitém pořadí. Je to poslední bod, který je jedinečný pro linearizovatelnost, a je tedy hlavním příspěvkem Herlihy a Wing.)

Podívejme se na dva způsoby přeuspořádání výše uvedeného příkladu uzamčení.

Změna pořadí vyvolání B pod odpovědí A přináší sekvenční historii. To lze snadno zdůvodnit, protože všechny operace se nyní odehrávají ve zřejmém pořadí. Bohužel neodpovídá postupné definici objektu (neodpovídá sémantice programu): A by měl úspěšně získat zámek a B by měl být následně přerušen.

Toto je další správná sekvenční historie. Je to také linearizace! Všimněte si, že definice linearizovatelnosti vylučuje pouze pořadí reakcí, které předcházejí vyvolání; protože původní historie neměla před vyvoláním žádné odpovědi, můžeme si ji změnit podle libosti. Proto je původní historie skutečně linearizovatelná.

Objekt (na rozdíl od historie) je linearizovatelný, pokud lze linearizovat všechny platné historie jeho použití. Všimněte si, že se jedná o mnohem těžší tvrzení.

Linearizovatelnost versus serializovatelnost

Zvažte následující historii, opět dvou objektů interagujících se zámkem:

Tato historie není platná, protože existuje bod, ve kterém A i B drží zámek; navíc jej nelze přeuspořádat na platnou sekvenční historii bez porušení pravidla pro objednávání. Proto to není linearizovatelné. V rámci serializovatelnosti však může být operace odemčení B přesunuta před původní zámek A, což je platná historie (za předpokladu, že objekt začíná historii v uzamčeném stavu):

Toto přeuspořádání je rozumné, pokud neexistují žádné alternativní způsoby komunikace mezi A a B. Linearizovatelnost je lepší, když se jednotlivé objekty posuzují samostatně, protože omezení pro přeskupování zajišťují, že více linearizovatelných objektů je považováno za celek, stále linearizovatelných.

Linearizační body

Tato definice linearizovatelnosti je ekvivalentní následujícímu:

• Všechna volání funkcí mají v určitém okamžiku linearizační bod mezi jejich vyvoláním a odpovědí.
• Zdá se, že všechny funkce se vyskytují okamžitě v jejich linearizačním bodě a chovají se tak, jak je uvedeno v sekvenční definici.

Tato alternativa je obvykle mnohem snazší dokázat. Jako uživatel je také mnohem snazší uvažovat, a to především díky jeho intuitivnosti. Tato vlastnost okamžitého nebo nedělitelného výskytu vede k použití termínu atomový jako alternativy k delšímu „linearizovatelnému“.

V níže uvedených příkladech je linearizační bod čítače postaveného na porovnání a výměně bod linearizace první (a jediné) úspěšné aktualizace porovnání a výměny. Čítač vytvořený pomocí zamykání lze považovat za linearizaci kdykoli, když jsou zámky drženy, protože během tohoto období jsou vyloučeny všechny potenciálně konfliktní operace.

Primitivní atomové instrukce

Procesory mají pokyny, které lze použít k implementaci algoritmů zamykání a bez zamykání a bez čekání . Schopnost dočasně potlačit přerušení a zajistit, že aktuálně běžící proces nelze přepnout na kontext , také na jednoprocesoru postačuje . Tyto pokyny jsou používány přímo autory překladačů a operačních systémů, ale jsou také abstrahovány a vystaveny jako bytecodes a funkce knihovny v jazycích vyšší úrovně:

• atomové čtení a zápis;
• atomový swap (instrukce RDLK v některých sálových počítačích Burroughs a instrukce XCHG x86 );
• testovat a nastavit ;
• načíst a přidat ;
• porovnat a vyměnit ;
• load-link / store-conditional .

Většina procesorů zahrnuje operace úložiště, které nejsou atomické s ohledem na paměť. Patří mezi ně víceslovné obchody a řetězcové operace. Pokud dojde k přerušení s vysokou prioritou, když je část úložiště dokončena, operace musí být dokončena, když se vrátí úroveň přerušení. Rutina, která zpracovává přerušení, nesmí měnit měněnou paměť. Je důležité to vzít v úvahu při psaní přerušovacích rutin.

Pokud existuje více instrukcí, které musí být dokončeny bez přerušení, použije se instrukce CPU, která dočasně zakáže přerušení. To musí být dodrženo pouze na několik pokynů a přerušení musí být znovu povolena, aby se zabránilo nepřijatelné době odezvy na přerušení nebo dokonce ke ztrátě přerušení. Tento mechanismus není v prostředí s více procesory dostatečný, protože každý procesor může zasahovat do procesu bez ohledu na to, zda dojde k přerušení či nikoli. Dále, za přítomnosti potrubí instrukcí , nepřerušitelné operace představují bezpečnostní riziko, protože mohou být potenciálně zřetězeny v nekonečné smyčce, aby se vytvořil útok odmítnutí služby , jako v chybě kómatu Cyrix .

Standard C a SUSv3 umožňují sig_atomic_tjednoduchá atomická čtení a zápis; není zaručeno, že přírůstek nebo úbytek bude atomický. Složitější atomové operace jsou k dispozici v C11 , který poskytuje stdatomic.h. Překladatelé používají k implementaci operací hardwarové funkce nebo složitější metody; příkladem je libatomic GCC.

Sada instrukcí ARM poskytuje LDREXa STREXpokyny, které lze použít k implementaci přístupu k atomové paměti pomocí exkluzivních monitorů implementovaných v procesoru ke sledování přístupů do paměti pro konkrétní adresu. Nicméně, pokud přepnutí kontextu dojde mezi volání LDREXa STREXdokumentace konstatuje, že STREXselžou, označující provoz by měl být opakován.

Atomové operace na vysoké úrovni

Nejjednodušší způsob, jak dosáhnout linearizovatelnosti, je spuštění skupin primitivních operací v kritické sekci . Přísně lze nezávislým provozům opatrně povolit překrývání jejich kritických částí, pokud to neporuší linearizovatelnost. Takový přístup musí vyvážit náklady velkého počtu zámků na výhody zvýšené paralelnosti.

Dalším přístupem, který upřednostňují vědci (ale zatím se v softwarovém průmyslu příliš nepoužívá), je navrhnout linearizovatelný objekt pomocí nativních atomových primitiv poskytovaných hardwarem. To má potenciál maximalizovat dostupný paralelismus a minimalizovat náklady na synchronizaci, ale vyžaduje matematické důkazy, které ukazují, že se objekty chovají správně.

Slibným hybridem těchto dvou je poskytnutí abstrakce transakční paměti . Stejně jako u kritických sekcí uživatel označí sekvenční kód, který musí být spuštěn izolovaně od ostatních vláken. Implementace pak zajišťuje, že se kód spustí atomicky. Tento styl abstrakce je běžný při interakci s databázemi; například při použití Spring Framework anotace metody pomocí @Transactional zajistí, že všechny uzavřené databázové interakce nastanou v jedné databázové transakci . Transakční paměť jde o krok dále a zajišťuje, že všechny interakce paměti probíhají atomicky. Stejně jako u databázových transakcí vznikají problémy týkající se složení transakcí, zejména transakcí s databázemi a v paměti.

Běžným tématem při navrhování linearizovatelných objektů je poskytnout rozhraní typu „všechno nebo nic“: buď operace bude úspěšná úplně, nebo selže a nic nedělá. ( Databáze ACID označují tento princip jako atomicitu .) Pokud operace selže (obvykle kvůli souběžným operacím), musí se uživatel pokusit znovu a obvykle provést jinou operaci. Například:

• Porovnat a vyměnit zapíše novou hodnotu do umístění pouze v případě, že se jeho obsah shoduje s dodanou starou hodnotou. To se běžně používá v sekvenci pro čtení, úpravy a CAS: uživatel načte umístění, vypočítá novou hodnotu pro zápis a zapíše ji pomocí CAS (porovnat a vyměnit); pokud se hodnota změní současně, CAS selže a uživatel to zkusí znovu.
• Load-link / store-conditional kóduje tento vzor příměji: uživatel načte umístění pomocí load-link, vypočítá novou hodnotu pro zápis a zapíše jej pomocí store-conditional; pokud se hodnota změnila souběžně, SC (podmíněné uložením) selže a uživatel to zkusí znovu.
• Pokud v databázové transakci nelze transakci dokončit z důvodu souběžné operace (např. Zablokování ), transakce bude zrušena a uživatel se musí pokusit znovu.

Příklady linearizovatelnosti

Počítadla

Abychom demonstrovali sílu a nutnost linearizovatelnosti, vezmeme v úvahu jednoduchý čítač, který mohou různé procesy zvyšovat.

Chtěli bychom implementovat objekt čítače, ke kterému může přistupovat více procesů. Mnoho běžných systémů využívá čítače ke sledování počtu výskytů události.

K objektu čítače lze přistupovat více procesy a má dvě dostupné operace.

1. Přírůstek - přidá 1 k hodnotě uložené v počitadle, potvrzení o vrácení
2. Číst - vrátí aktuální hodnotu uloženou v počitadle bez změny.

Pokusíme se implementovat tento objekt čítače pomocí sdílených registrů

Náš první pokus, který uvidíme, je nelineární, má následující implementaci pomocí jednoho sdíleného registru mezi procesy.

Non-atomové

Naivní, ne-atomová implementace:

Přírůstek:

1. Odečtěte hodnotu v registru R.
2. Přidejte jednu k hodnotě
3. Zapíše novou hodnotu zpět do registru R.

Číst:

Přečíst registr R.

Tato jednoduchá implementace není linearizovatelná, jak ukazuje následující příklad.

Představte si, že běží dva procesy, které přistupují k inicializovanému objektu jednoho čítače, který má hodnotu 0:

1. První proces načte hodnotu v registru jako 0.
2. První proces přidá jeden k hodnotě, hodnota čítače by měla být 1, ale než dokončí zápis nové hodnoty zpět do registru, může být pozastaven, zatímco běží druhý proces:
3. Druhý proces čte hodnotu v registru, která je stále rovna 0;
4. Druhý proces přidává jeden k hodnotě;
5. druhý proces zapíše novou hodnotu do registru, registr má nyní hodnotu 1.

Druhý proces je spuštěn a první proces pokračuje v provozu tam, kde přestal:

1. První proces zapíše 1 do registru, aniž by věděl, že druhý proces již aktualizoval hodnotu v registru na 1.

Ve výše uvedeném příkladu dva procesy vyvolaly příkaz přírůstku, ale hodnota objektu se zvýšila pouze z 0 na 1, namísto 2, jak by měla mít. Jedna z operací přírůstku byla ztracena v důsledku toho, že systém nebyl linearizovatelný.

Výše uvedený příklad ukazuje potřebu pečlivě promyslet implementace datových struktur a to, jak může mít linearizovatelnost vliv na správnost systému.

Atomový

Abychom implementovali linearizovatelný nebo atomový čítač, upravíme naši předchozí implementaci tak, aby každý proces P i použil svůj vlastní registr R i

Každý proces se zvyšuje a čte podle následujícího algoritmu:

Přírůstek:

1. Načíst hodnotu v registru R i .
2. Přidejte jednu k hodnotě.
3. Napište novou hodnotu zpět do R i

Číst:

1. Přečíst registry R 1, R 2, ... R n .
2. Vrátí součet všech registrů.

Tato implementace řeší problém s naší původní implementací. V tomto systému jsou operace přírůstku linearizovány v kroku zápisu. Bod linearizace operace přírůstku je, když tato operace zapíše novou hodnotu do svého registru R i. Operace čtení jsou linearizovány do bodu v systému, když se hodnota vrácená čtením rovná součtu všech hodnot uložených v každém registru R i.

Toto je triviální příklad. Ve skutečném systému mohou být operace složitější a chyby zavedené extrémně jemné. Například čtení 64bitové hodnoty z paměti může být ve skutečnosti implementováno jako dvě postupná čtení dvou 32bitových paměťových míst. Pokud proces přečetl pouze prvních 32 bitů a než přečte druhých 32 bitů, změní se hodnota v paměti, nebude mít ani původní hodnotu, ani novou hodnotu, ale smíšenou hodnotu.

Kromě toho konkrétní pořadí, ve kterém procesy běží, může změnit výsledky, což ztěžuje detekci, reprodukci a ladění takové chyby .

Porovnat a vyměnit

Většina systémů poskytuje atomovou instrukci pro porovnání a výměnu, která čte z paměťového místa, porovnává hodnotu s „očekávanou“, kterou poskytuje uživatel, a vypíše „novou“ hodnotu, pokud se tyto dva shodují, přičemž vrací, zda byla aktualizace úspěšná . Můžeme to použít k opravě algoritmu bez atomového čítače následujícím způsobem:

1. Přečtěte si hodnotu v paměti;
2. přidat jednu k hodnotě;
3. použijte porovnat a vyměnit zapsat zvýšenou hodnotu zpět;
4. zkuste to znovu, pokud hodnota načtená porovnáním a výměnou neodpovídá hodnotě, kterou jsme původně načetli.

Vzhledem k tomu, že k porovnání a výměně dochází (nebo se zdá, že k němu dochází) okamžitě, pokud jiný proces aktualizuje umístění, zatímco právě pracujeme, je zaručeno, že selhání porovnání a výměny.

Načíst a zvýšit

Mnoho systémů poskytuje instrukci atomického načítání a zvyšování, která čte z paměťového místa, bezpodmínečně zapisuje novou hodnotu (stará hodnota plus jedna) a vrací starou hodnotu. Můžeme to použít k opravě algoritmu bez atomového čítače následujícím způsobem:

1. Použijte načtení a přírůstek ke čtení staré hodnoty a zápisu přírůstkové hodnoty zpět.

Použití načítání a přírůstku je vždy lepší (vyžaduje méně odkazů na paměť) pro některé algoritmy - jako je ten, který je zde zobrazen - než porovnání a výměna, i když Herlihy dříve prokázal, že porovnání a výměna je lepší pro některé další algoritmy, které nelze implementovat vůbec pomocí pouze načítání a přírůstku. Takže návrhy CPU s načtením a přírůstkem a porovnáním a výměnou (nebo ekvivalentními pokyny) mohou být lepší volbou než ty, které mají pouze jeden nebo druhý.

Zamykání

Dalším přístupem je přeměna naivního algoritmu na kritickou část a zabránění jiným vláknům v narušení pomocí zámku . Opět oprava algoritmu neatomového čítače:

1. Získejte zámek, s vyloučením toho, aby ostatní vlákna současně spouštěla ​​kritickou část (kroky 2-4);
2. přečíst hodnotu v paměťovém místě;
3. přidat jednu k hodnotě;
4. zapsat zvýšenou hodnotu zpět do paměťového umístění;
5. uvolněte zámek.

Tato strategie funguje podle očekávání; zámek brání jiným vláknům v aktualizaci hodnoty, dokud není uvolněna. Ve srovnání s přímým použitím atomových operací však může trpět značnou režií v důsledku sporu o zámek. Aby se zlepšil výkon programu, může být dobrým nápadem nahradit jednoduché kritické sekce atomickými operacemi pro neblokující synchronizaci (jak jsme právě udělali pro pult s porovnáním a výměnou a načtením a přírůstkem), namísto obráceně, ale bohužel není zaručeno významné zlepšení a bezzámkové algoritmy se mohou snadno stát příliš komplikovanými, aby to stálo za tu námahu.

Viz také

• Atomová transakce
• Model konzistence
• KYSELINA
• Aktualizace pro čtení a kopírování (RCU)
• Číst, upravovat a psát
• Čas kontroly do doby použití

Reference

Další čtení

• Herlihy, Maurice P .; Wing, Jeannette M. (1987). Axiomy pro souběžné objekty . Sborník 14. sympozia ACM SIGACT-SIGPLAN o zásadách programovacích jazyků, POPL '87 . p. 13. doi : 10,1145 / 41625,41627 . ISBN 978-0-89791-215-0. S2CID  16017451 .
• Herlihy, Maurice P. (1990). Metodika implementace vysoce souběžných datových struktur . Oznámení ACM SIGPLAN . 25 . 197–206. CiteSeerX  10.1.1.186.6400 . doi : 10,1145 / 99164,99185 . ISBN 978-0-89791-350-8.
• Herlihy, Maurice P .; Wing, Jeannette M. (1990). "Linearizovatelnost: Podmínka správnosti pro souběžné objekty". Transakce ACM v programovacích jazycích a systémech . 12 (3): 463–492. CiteSeerX  10.1.1.142.5315 . doi : 10,1145 / 78969,77972 . S2CID  228785 .
• Aphyr. "Silné modely konzistence" . aphyr.com . Aphyr . Citováno 13. dubna 2018 .