V počítačové technologii je softwarová transakční paměť ( STM ) mechanismem souběžného řízení podobným mechanismu databázových transakcí pro řízení přístupu ke sdílené paměti v paralelním počítání . Je to alternativa pro synchronizaci založenou na zámku . Transakce je v tomto kontextu kus kódu, který čte ze sdílené (sdílené) paměti a zapisuje do ní. Čtení a zápis logicky probíhají v jediném okamžiku a mezistavy jsou pro ostatní (výsledné) transakce neviditelné. Myšlenka poskytování transakcí s hardwarovou podporou vznikla v roce 1986 v díle a patentu Toma Knighta . [1] Nápad zveřejnili Maurice Herlihy a Eliot Moss . [2] V roce 1995 Nir Shavit a Dan Toytu rozšířili tuto myšlenku na softwarovou transakční paměť (STM). STM je stále v centru intenzivního výzkumu; jeho podpora praktických implementací se zvyšuje.
Na rozdíl od metod blokování používaných ve většině moderních vícevláknových aplikací je STM velmi optimistický: vlákno dokončuje změny sdílené paměti bez ohledu na to, co dělají ostatní vlákna, a zaznamenává všechna čtení a zápisy do protokolu. Namísto použití zapisovače ke kontrole, zda to má negativní vliv na další probíhající operace, je odpovědnost přenesena na čtečku, která po dokončení transakce zkontroluje, zda jiná vlákna neprovedla souběžné změny v paměti, ke které se přistupovalo v minulost.. Tato poslední operace, která kontroluje změny transakce a která, pokud kontrola uspěje, zůstane nezměněna, se nazývá potvrzení. Transakci lze kdykoli ukončit, v důsledku čehož budou zrušeny všechny poslední změny. Pokud transakce nemůže být potvrzena kvůli konfliktům změn, bude přerušena a bude opakována od začátku, dokud nebude úspěšně dokončena.
Výhoda tohoto optimistického přístupu je umocněna paralelismem: žádné vlákno nemusí čekat na přístup ke zdroji a různá vlákna mohou současně a bezpečně upravovat nesouvislé části datové struktury, které by byly chráněny stejným zámkem.
V praxi však systémy STM ztrácejí na výkonu oproti jemnozrnným systémům založeným na zámcích na malém počtu procesorů (od 1 do 4 v závislosti na aplikaci). To je způsobeno především režií údržby protokolu a časem stráveným transakcemi. Ale i v tomto případě se výkon neliší více než 2krát. [3] Zastánci STM věří, že takové ztráty jsou ospravedlněny koncepčními výhodami STM.
Teoreticky je časová a prostorová složitost běhu n paralelních transakcí v nejhorším případě O (n) . Skutečná cena závisí na implementaci (transakci můžete předčasně zrušit, abyste se vyhnuli režii), ale vždy budou existovat případy, i když vzácné, kdy budou mít zamykací algoritmy lepší časovou složitost než softwarová transakční paměť.
Kromě výkonnostních výhod STM výrazně zjednodušuje koncepční pochopení vícevláknových programů a pomáhá při jejich udržovatelnosti bezproblémovou prací s existujícími abstrakcemi na vysoké úrovni, jako jsou objekty a moduly.
Programování zámků obsahuje řadu známých problémů, které se v praxi často objevují:
Naopak koncept transakční paměti je mnohem jednodušší, protože každou transakci lze posuzovat individuálně, jako jednovláknový výpočet. Zablokování je buď zcela zabráněno, nebo je řeší externí správce transakcí; o to se programátor nemusí starat. Inverze priority může být stále problémem, ale transakce s vysokou prioritou mohou zrušit konfliktní transakce s nízkou prioritou, které ještě nebyly potvrzeny.
Na druhou stranu nutnost přerušit neúspěšné transakce také ukládá omezení jejich chování: nemohou provádět žádnou operaci, kterou nelze vrátit zpět, včetně většiny I/O. Taková omezení jsou v praxi obvykle překonána vytvořením vyrovnávacích pamětí, které řadí nevratné operace do fronty a provádějí je o nějaký čas později mimo jakoukoli transakci. V Haskellu je toto omezení vynuceno systémem typů v době kompilace.
V roce 2005 Tim Harris, Simon Marlow, Simon Peyton-Jones a Maurice Herlihy popsali systém STM postavený v Haskellu , který implementuje paralelismus. Tento systém umožňuje kombinovat libovolné atomické operace do větších atomových operací, což je užitečný koncept, který není možný s programováním zámků. Podle autorů:
„Možná nejzásadnější nevýhodou je, že zámkové programy se nemohou propojit: správné fragmenty nemusí při propojení fungovat. Zvažte například hašovací tabulku s vkládáním a mazáním bezpečným pro vlákna. Nyní předpokládejme, že chceme odstranit jeden prvek z tabulky t1 a vložit jej do tabulky t2, ale mezistav (ve kterém žádná tabulka tento prvek neobsahuje) by neměl být viditelný pro ostatní vlákna. Dokud návrhář hashovacích tabulek nestanoví tuto potřebu, neexistuje žádný způsob, jak tento požadavek uspokojit. Obecně platí, že každou správnou operaci (vložení, vymazání) nelze spojovat do větších správných operací.
— (Tim Harris a kol., „Operace přístupu ke složitelné paměti“, oddíl 2. Pozadí, str. 2)S STM je tento problém vyřešen jednoduše: prostým spojením dvou operací v jedné transakci se ze sestavitelné operace stane atomická. Jediným kamenem úrazu je, že volajícímu, který nezná detaily implementace metod propojení, není jasné, kdy by se měl pokusit transakci opakovat, pokud k ní nedojde. V reakci na to autoři navrhli příkaz opakovat, který používá protokol transakcí (soubor protokolu) generovaný neúspěšnou transakcí k určení části paměti, kterou čte. Poté automaticky zahájí transakci znovu, když se jedno z těchto paměťových míst změní. To je založeno na logice, že transakce se nebude chovat jinak, dokud se nezmění alespoň jedna taková hodnota.
Autoři také navrhli mechanismus pro konstrukci alternativ (funkce orElse). Zahájí jednu transakci a pokud se transakce zopakuje, spustí druhou. Pokud se totéž stane druhému, mechanismus spustí oba znovu, dokud nenastane výrazná změna. Tato funkce, srovnatelná s funkcí select() standardu sítě POSIX, umožňuje volajícímu čekat na kteroukoli z mnoha událostí současně. Také zjednodušuje programování rozhraní, například tím, že poskytuje jednoduchý převodní mechanismus mezi blokujícími a neblokujícími operacemi.
Toto schéma bylo implementováno v Haskell kompilátoru GHC .
Koncepční jednoduchost systémů STM umožňuje programátorovi s nimi snadno pracovat pomocí relativně jednoduché syntaxe jazyka. Tim Harris a Keir Fraser ve své knize An Auxiliary Language for Lightweight Transactions navrhli myšlenku použití klasické podmíněné kritické oblasti (CCR) k reprezentaci transakcí. Ve své nejjednodušší podobě je to jen „atomový blok“, kus kódu, který je postupně spouštěn v jediném okamžiku:
// Atomicky vložit uzel do dvojitě propojeného seznamu atomový { newNode->prev = uzel; novyUzel->dalsi = uzel->dalsi; uzel->dalsi->prev = novyUzel; uzel->dalsi = novyUzel; }Po dosažení konce bloku je transakce pokud možno potvrzena, jinak je ukončena a opakována. Podmíněné kritické oblasti také umožňují podmínku perzistence, která umožňuje transakci čekat, dokud se její úloha neprovede.
atomic (velikost fronty > 0) { odstranit položku z fronty a použít ji }Pokud podmínka selže, správce transakcí počká, dokud nenastane další, která ovlivní podmínku, než to zkusí znovu. Tato volná komunikace mezi výrobci a spotřebiteli zlepšuje modularitu oproti jasné signalizaci mezi vlákny. Composable Memory Access jde dále pomocí příkazu opakování (viz výše), který může transakci kdykoli zrušit a před opakováním počkat, dokud nedojde k nějaké změně v hodnotě dříve načtené operací. Příklad:
atomový { if (velikost fronty > 0) { odstranit položku z fronty a použít ji } jinak { zkusit znovu } }Tato možnost dynamického opakování na konci transakce zjednodušuje programovací model a otevírá nové možnosti.
Jedním z problémů je chování výjimek, když se šíří mimo transakce. V "A Composable Memory Access Operation" se autoři rozhodli, že by to mělo zrušit transakci, protože výjimky obvykle naznačují neočekávané chyby v Haskellu (se souběžným zpracováním), ale že tato výjimka může ukládat poskytnuté informace a číst je během transakce pro účely diagnostiky. Zdůrazňují, že další konstrukční rozhodnutí jsou rozumná i za jiných parametrů.
STM lze implementovat jako bezuzamykatelný a uzamykatelný algoritmus. Existují dva typy blokování.
Schéma provádění transakcí nazvané „Transactional Locking-2“ a implementované společnostmi Dice, Shalev a Shavit využívá globální čas. Každá transakce začíná načtením aktuální časové hodnoty a uloží ji pro čtení. Poté se při každém čtení a zápisu porovnává verze zadané oblasti paměti s verzí pro čtení, a pokud je větší, transakce se zruší. Tím je zajištěno, že se kód spustí na příslušné kopii paměti. Během potvrzení jsou všechny oblasti čtení uzamčeny a hodnoty dané verze všech oblastí paměti pro zápis a čtení jsou znovu zkontrolovány. Nakonec se zvýší globální čas, nové hodnoty záznamu protokolu se zapíší zpět do paměti s novou verzí času.
Stále populárnější metodou pro správu transakčních konfliktů v transakční paměti , zejména v STM, je pořadí, ve kterém(CO). Používá se k dosažení bezuzamykatelného řazení (tj. žádné uzamčení konfliktních transakcí a pouze uzamčení potvrzení transakce) přeskupováním transakcí (např. Ramadan et al. 2009 a Zhang et al. 2006). Objednávání je základem pro správný stav transakční paměti (při paralelních transakcích). O STM pomocí „exekučního řádu“ již byly publikovány desítky prací a patentů.
"Zhang et al., 2006" je americký patent s názvem "Software pro objednávky transakcí a řízení konfliktů" (který odkazuje na Order Order US Patent 5,701,480). Zde jsou úryvky:
„Vyvíjejí se různé technologie a metody pro uplatnění pořadí provádění v softwarovém transakčním paměťovém systému. Systém transakční paměti programu je vybaven funkcí, na kterou lze aplikovat předem definované pořadí provádění mnoho operací. Předdefinované pořadí odevzdání se za běhu používá k určení pořadí, ve kterém provádět transakce v softwarovém transakčním paměťovém systému. Proces řízení konfliktů je vyvolán, když konflikt mezi první a druhou transakcí. Předdefinované pořadí odevzdání se používá v procesu řízení konfliktů, určit, která transakce by měla konflikt vyhrát a mít povolení pokračovat."S pořadím odevzdání je požadované vlastnosti uspořádání dosaženo potvrzením transakcí pouze v chronologickém pořadí v souladu s pořadím priority (určené chronologickým pořadím operací v konfliktech)
SRTM byl implementován (různé kvality a stability) v různých programovacích jazycích. Jako: