A számítástechnikában a szoftvertranzakciós memória ( STM ) egy párhuzamos számítási folyamat során a megosztott memóriához való hozzáférés szabályozására szolgáló adatbázis - tranzakciós mechanizmushoz hasonló párhuzamosság-vezérlő mechanizmus . Ez egy alternatíva a zár alapú szinkronizáláshoz . A tranzakció ebben az összefüggésben egy olyan kódrészlet, amely a megosztott (megosztott) memóriából olvas és oda ír. Az olvasás és írás logikailag egyetlen időpontban történik, és a köztes állapotok láthatatlanok a többi (eredményes) tranzakció számára. A tranzakciók hardveres támogatással történő biztosításának ötlete 1986-ban Tom Knight munkájából és szabadalmából származik . [1] Az ötletet Maurice Herlihy és Eliot Moss tette közzé . [2] 1995-ben Nir Shavit és Dan Toytu kiterjesztette ezt az ötletet a szoftveres tranzakciós memóriára (STM). Az STM még mindig az intenzív kutatások középpontjában áll; a gyakorlati megvalósítások támogatottsága növekszik.
A legtöbb modern többszálú alkalmazásban használt blokkoló módszerekkel ellentétben az STM nagyon optimista: a szálak a megosztott memóriában végrehajtott változtatásokat anélkül hajtják végre, hogy a többi szál mit csinálnak, és minden olvasást és írást naplóz a naplóba. Ahelyett, hogy az írót használnák annak ellenőrzésére, hogy ez negatív hatással van-e más folyamatban lévő műveletekre, a felelősség az olvasóra száll át, amely a teljes tranzakció befejezése után ellenőrzi, hogy más szálak egyidejűleg módosítottak-e a memóriában, amelyhez a programban hozzáfértek. múlt. Ezt az utolsó műveletet, amely ellenőrzi a tranzakciós változásokat, és ha az ellenőrzés sikeres, változatlan marad, véglegesítésnek nevezzük. A tranzakció bármikor felmondható, melynek eredményeként az összes legutóbbi módosítás törlésre kerül. Ha egy tranzakciót nem lehet végrehajtani változási ütközések miatt, akkor megszakad, és az elejétől újra próbálkozik a sikeres befejezésig.
Ennek az optimista megközelítésnek az előnyét a párhuzamosság növeli: egyetlen szálnak sem kell megvárnia az erőforráshoz való hozzáférést, és a különböző szálak egyidejűleg és biztonságosan módosíthatják az adatstruktúra olyan diszjunkt részeit, amelyeket ugyanaz a zár védene.
A gyakorlatban azonban az STM-rendszerek teljesítményüket veszítik a kis számú (alkalmazástól függően 1-től 4-ig terjedő) processzoron alapuló, finomszemcsés rendszerekhez képest. Ennek oka elsősorban a naplóvezetés többletköltsége és a tranzakciókra fordított idő. De még ebben az esetben is a teljesítmény legfeljebb 2-szer tér el. [3] Az STM támogatói úgy vélik, hogy az ilyen veszteségeket az STM koncepcionális előnyei indokolják.
Elméletileg n párhuzamos tranzakció futtatásának időbeli és térbeli összetettsége a legrosszabb esetben O (n) . A tényleges költség a megvalósítástól függ (a többletköltség elkerülése érdekében a tranzakciót korán törölheti), de mindig lesznek olyan esetek, bár ritkák, amikor a zárolási algoritmusok időben bonyolultabbak, mint a szoftveres tranzakciós memória.
A teljesítménybeli előnyök mellett az STM nagyban leegyszerűsíti a többszálú programok fogalmi megértését, és segíti karbantarthatóságukat azáltal, hogy zökkenőmentesen dolgozik a meglévő magas szintű absztrakciókkal, például objektumokkal és modulokkal.
A zárprogramozás számos ismert problémát tartalmaz, amelyek gyakran előfordulnak a gyakorlatban:
Ellenkezőleg, a tranzakciós memória fogalma sokkal egyszerűbb, mivel minden tranzakció külön-külön, egyszálú számításnak tekinthető. A holtpontokat vagy teljesen megakadályozza, vagy egy külső tranzakciókezelő feloldja; a programozónak aligha kell emiatt aggódnia. A prioritás inverziója továbbra is problémát jelenthet, de a magas prioritású tranzakciók megszakíthatják a még nem véglegesített, ütköző alacsony prioritású tranzakciókat.
Másrészt a sikertelen tranzakciók megszakítása is korlátozza a viselkedésüket: nem hajthatnak végre olyan műveleteket, amelyeket nem lehet visszavonni, beleértve a legtöbb I/O-t is. Az ilyen korlátokat a gyakorlatban rendszerint áthidalják pufferek létrehozásával, amelyek visszafordíthatatlan műveleteket sorba állítanak, és egy idő után végrehajtják azokat bármely tranzakción kívül. A Haskellben ezt a korlátozást a típusrendszer hajtja végre a fordításkor.
2005-ben Tim Harris, Simon Marlow, Simon Peyton-Jones és Maurice Herlihy egy Haskellben épített STM-rendszert írt le, amely párhuzamosságot valósít meg. Ez a rendszer lehetővé teszi tetszőleges atomi műveletek kombinálását nagyobb atomi műveletekké, ami a zárprogramozással nem lehetséges. A szerzők szerint:
„Talán a legalapvetőbb hátrány az, hogy a zárprogramok nem tudnak linkelni: előfordulhat, hogy a megfelelő töredékek nem működnek, ha összekapcsolják őket. Vegyünk például egy hash-táblázatot szálbiztos beszúrásokkal és törlésekkel. Most tegyük fel, hogy el akarunk távolítani egy elemet a t1 táblából, és beilleszteni a t2 táblába, de a köztes állapot (amikor egyetlen tábla sem tartalmazza ezt az elemet) ne legyen látható más szálak számára. Amíg a hash tábla tervezője nem határozza meg ezt az igényt, egyszerűen nincs mód ennek a követelménynek a kielégítésére. Általában minden helyes művelet (beszúrások, törlések) nem kombinálható nagyobb helyes műveletekké.
– (Tim Harris et al., "Composable Memory Access Operation", 2. rész. Háttér, 2. o.)Az STM-mel ez a probléma egyszerűen megoldható: ha két műveletet egyszerűen kombinálunk egy tranzakcióban, az összeállítható művelet atomi műveletté válik. Az egyetlen akadály az, hogy a hívó fél számára, aki nem ismeri a link metódusok megvalósítási részleteit, nem világos, hogy mikor kell újra próbálkoznia a tranzakcióval, ha az nem történik meg. Erre válaszul a szerzők egy újrapróbálkozási parancsot javasoltak, amely a sikertelen tranzakció által generált tranzakciós naplót (naplófájlt) használja az olvasott memóriarész meghatározására. Ezután automatikusan újraindítja a tranzakciót, ha a memóriahelyek egyike megváltozik. Ez azon a logikán alapul, hogy egy tranzakció addig nem fog másképp viselkedni, amíg legalább egy ilyen érték meg nem változik.
A szerzők alternatívák létrehozásának mechanizmusát is javasolták (az orElse függvényt). Elindít egy tranzakciót, és ha a tranzakció újra próbálkozik, elindít egy másodikat. Ha ugyanez történik a másodikkal is, a mechanizmus mindkettőt újra elindítja, amíg jelentős változás nem következik be. Ez a POSIX hálózati szabványos select() függvényhez hasonló funkció lehetővé teszi a hívó számára, hogy egyszerre több eseményre várjon. Az interfész programozását is leegyszerűsíti, például egyszerű konverziós mechanizmust biztosít a blokkoló és a nem blokkoló műveletek között.
Ezt a sémát a Haskell GHC fordítóprogramban valósították meg .
Az STM rendszerek fogalmi egyszerűsége lehetővé teszi a programozó számára, hogy könnyedén dolgozzon velük a nyelv viszonylag egyszerű szintaxisával. Tim Harris és Keir Fraser An Auxiliary Language for Lightweight Transactions című könyvében javasolta a klasszikus feltételes kritikus régió (CCR) használatát a tranzakciók ábrázolására. A legegyszerűbb formájában ez csak egy "atomi blokk", egy kódrészlet, amely szekvenciálisan végrehajtódik egyetlen időpontban:
// Csomópont atomi beszúrása egy duplán linkelt listába atom { newNode->prev = csomópont; newNode->next = csomópont->következő; csomópont->következő->előző = newNode; csomópont->következő = newNode; }A blokk végére érve a tranzakció lehetőség szerint véglegesítésre kerül, ellenkező esetben megszakad és megismétlődik. A feltételes kritikus régiók egy perzisztencia feltételt is lehetővé tesznek, ami lehetővé teszi, hogy a tranzakció várjon, amíg a feladata hatályba lép.
atomic (queueSize > 0) { távolítsa el az elemet a sorból, és használja }Ha a feltétel sikertelen, a tranzakciókezelő megvárja, amíg egy másik, a feltételt befolyásoló esemény bekövetkezik, mielőtt újra próbálkozna. Ez a laza kommunikáció a gyártók és a fogyasztók között javítja a modularitást a szálak közötti egyértelmű jelzéshez képest. A Composable Memory Access tovább megy az újrapróbálkozási paranccsal (lásd fent), amely bármikor megszakíthatja a tranzakciót, és megvárja, amíg a művelet által korábban beolvasott érték megváltozik, mielőtt újra próbálkozna. Példa:
atom { if (queueSize > 0) { távolítsa el az elemet a sorból, és használja } más { próbálja újra } }Ez a dinamikus újrapróbálkozás képessége a tranzakció végén leegyszerűsíti a programozási modellt és új lehetőségeket nyit meg.
Az egyik probléma a kivételek viselkedése, amikor a tranzakciókon kívül terjednek. Az "A Composable Memory Access Operation"-ban a szerzők úgy döntöttek, hogy ezzel meg kell szakítani a tranzakciót, mivel a kivételek általában a Haskell váratlan hibáit jelzik (egyidejűleg), de ez a kivétel tárolhatja a megadott információkat és elolvashatja a tranzakció során. a diagnosztikából. Hangsúlyozzák, hogy más tervezési döntések más paraméterek mellett is ésszerűek.
Az STM zárolás nélküli és zárható algoritmusként is megvalósítható. Kétféle blokkolás létezik.
A "Tranzakciós zárolás-2" nevű tranzakció-végrehajtási séma, amelyet a Dice, Shalev és Shavit valósított meg, globális időt használ. Minden tranzakció az aktuális időérték beolvasásával kezdődik, és eltárolja azt olvasásra. Ezután minden olvasáskor és íráskor összehasonlítják a megadott memóriaterület verzióját az olvasási verzióval, és ha nagyobb, akkor a tranzakció törlődik. Ez biztosítja, hogy a kód a memória megfelelő másolatán fut le. A véglegesítés során az összes olvasási régió zárolásra kerül, és az összes írási és olvasási memóriarégió adott verziójának értékei újraellenőrzésre kerülnek. Végül a globális idő növekszik, a naplóbejegyzés új értékei visszaíródnak a memóriába az idő új verziójával.
Egyre népszerűbb módszer a tranzakciós memóriában lévő tranzakciós konfliktusok kezelésére , különösen az STM-ekben, az a sorrend,(CO). A zárolás nélküli rendelés (vagyis az ütköző tranzakciók zárolásának és csak a tranzakció véglegesítésének zárolásának) elérésére szolgál a tranzakciók átrendezésével (pl. Ramadan et al. 2009 és Zhang et al. 2006). A rendezés az alapja a tranzakciós memória helyes állapotának (amikor párhuzamos tranzakciókat hajtanak végre). Az STM-ről már több tucat közlemény és szabadalom jelent meg a "végrehajtási sorrend" használatával.
A "Zhang et al., 2006" a "Tranzakciós rendelési szoftver és konfliktuskezelés" című amerikai egyesült államokbeli szabadalom (amely az 5 701 480 számú amerikai egyesült államokbeli Order Order-re hivatkozik). Íme a részletek:
„Különféle technológiák és módszerek fejlesztés alatt állnak a végrehajtási sorrend alkalmazására egy szoftveres tranzakciós memóriarendszerben. A program tranzakciós memóriarendszere olyan funkcióval van felszerelve, amelyre előre meghatározott végrehajtási sorrend alkalmazható sok művelet. A rendszer az előre meghatározott véglegesítési sorrendet használja futás közben annak megállapítására, hogy milyen sorrendben tranzakciókat hajt végre a szoftveres tranzakciós memóriarendszerben. A konfliktuskezelési folyamat akkor indul el, amikor konfliktus az első és a második tranzakció között. Az előre meghatározott commit sorrendet használják a konfliktuskezelési folyamatban, annak meghatározása, hogy melyik tranzakció nyerje meg a konfliktust, és hagyja azt folytatni."A véglegesítési megbízásnál a rendelés kívánt tulajdonsága úgy érhető el, hogy a tranzakciókat csak a prioritási sorrendnek megfelelő időrendi sorrendben hajtják végre (a műveletek időrendi sorrendje szerint ütközések esetén)
Az SRTM-et (változó minőségű és stabilitású) különféle programozási nyelveken implementálták. Úgymint: