În tehnologia computerelor , memoria tranzacțională software ( STM ) este un mecanism de control al concurenței similar cu mecanismul tranzacției bazei de date pentru controlul accesului la memoria partajată în calculul paralel . Este o alternativă pentru sincronizarea bazată pe blocare . O tranzacție în acest context este o bucată de cod care citește și scrie în memoria partajată (partajată). Citirea și scrierea apar în mod logic la un singur moment în timp, iar stările intermediare sunt invizibile pentru alte tranzacții (rezultate). Ideea de a oferi tranzacții cu suport hardware a luat naștere în 1986 în lucrarea și brevetul lui Tom Knight . [1] Ideea a fost mediatizată de Maurice Herlihy și Eliot Moss . [2] În 1995, Nir Shavit și Dan Toytu au extins această idee la memoria tranzacțională software (STM). STM este încă în centrul cercetării intense; sprijinul său pentru implementări practice este în creștere.
Spre deosebire de metodele de blocare utilizate în majoritatea aplicațiilor moderne cu mai multe fire, STM este foarte optimist: un fir de execuție completează modificările aduse memoriei partajate fără a ține cont de ceea ce fac alte fire și înregistrează orice citire și scriere în jurnal. În loc să se folosească scriitorul pentru a verifica dacă are un efect negativ asupra altor operațiuni în desfășurare, responsabilitatea este transferată către cititor, care, după finalizarea unei tranzacții complete, verifică dacă alte fire de execuție au făcut modificări concomitente în memoria care a fost accesată în trecut.. Această ultimă operație, care verifică modificările tranzacției și care, dacă verificarea reușește, rămâne neschimbată, se numește commit. Tranzacția poate fi oprită în orice moment, drept urmare toate modificările recente vor fi anulate. Dacă o tranzacție nu poate fi efectuată din cauza unor conflicte de modificare, aceasta este anulată și reîncercată de la început până când se finalizează cu succes.
Avantajul acestei abordări optimiste este sporit de paralelism: niciun fir nu trebuie să aștepte accesul la o resursă, iar firele diferite pot modifica simultan și în siguranță părți disjunctive ale structurii de date care ar fi protejate de aceeași blocare.
Cu toate acestea, în practică, sistemele STM pierd în performanță în fața sistemelor cu granulație fină bazate pe blocări pe un număr mic de procesoare (de la 1 la 4 în funcție de aplicație). Acest lucru se datorează în primul rând costurilor generale de menținere a jurnalului și timpului petrecut cu tranzacții. Dar chiar și în acest caz, performanța diferă de cel mult de 2 ori. [3] Susținătorii STM consideră că astfel de pierderi sunt justificate de avantajele conceptuale ale STM.
Teoretic, complexitatea de timp și spațiu a rulării n tranzacții paralele este O (n) în cel mai rău caz . Costul real depinde de implementare (puteți anula tranzacția mai devreme pentru a evita cheltuielile generale), dar vor exista întotdeauna cazuri, deși rare, în care algoritmii de blocare vor avea o complexitate de timp mai bună decât memoria tranzacțională software.
Pe lângă beneficiile de performanță, STM simplifică foarte mult înțelegerea conceptuală a programelor multithreaded și ajută la menținerea acestora, lucrând fără probleme cu abstracțiile existente la nivel înalt, cum ar fi obiectele și modulele.
Programarea blocării conține o serie de probleme cunoscute care apar adesea în practică:
Dimpotrivă, conceptul de memorie tranzacțională este mult mai simplu, deoarece fiecare tranzacție poate fi considerată individual, ca un calcul cu un singur thread. Blocajele sunt fie prevenite în întregime, fie rezolvate de un manager de tranzacții extern; programatorul nu trebuie să-și facă griji pentru asta. Inversarea priorității poate fi în continuare o problemă, dar tranzacțiile cu prioritate ridicată pot anula tranzacțiile conflictuale cu prioritate scăzută care nu au fost încă comise.
Pe de altă parte, necesitatea de a anula tranzacțiile eșuate impune și restricții asupra comportamentului lor: nu pot efectua nicio operațiune care nu poate fi anulată, inclusiv majoritatea I/O. Astfel de limitări sunt de obicei depășite în practică prin crearea de buffer-uri care pun în coadă operațiunile ireversibile și le execută ceva timp mai târziu în afara oricărei tranzacții. În Haskell, această restricție este impusă de sistemul de tip în timpul compilării.
În 2005, Tim Harris, Simon Marlow, Simon Peyton-Jones și Maurice Herlihy au descris un sistem STM construit în Haskell care implementează paralelismul. Acest sistem permite combinarea operațiunilor atomice arbitrare în operațiuni atomice mai mari, un concept util care nu este posibil cu programarea blocării. Potrivit autorilor:
„Poate cel mai fundamental dezavantaj este că programele de blocare nu pot lega: fragmentele corecte pot să nu funcționeze atunci când sunt legate. Luați în considerare, de exemplu, un tabel hash cu inserări și ștergeri sigure pentru fire. Acum să presupunem că vrem să eliminăm un element din tabelul t1 și să-l inserăm în tabelul t2, dar starea intermediară (în care niciun tabel nu conține acel element) nu ar trebui să fie vizibilă pentru alte fire. Până când proiectantul tabelului hash nu determină această nevoie, pur și simplu nu există nicio modalitate de a satisface această cerință. În general, fiecare operație corectă (inserții, ștergeri) nu poate fi combinată în operații corecte mai mari.
— (Tim Harris și colab., „Operațiunea de acces la memorie compusă”, Secțiunea 2. Context, p.2)Cu STM, această problemă se rezolvă simplu: simpla combinare a două operații într-o singură tranzacție transformă o operație componabilă într-una atomică. Singura piatră de poticnire este că nu este clar pentru apelant, care nu cunoaște detaliile de implementare a metodelor de legătură, când ar trebui să încerce să reîncerce tranzacția dacă aceasta nu are loc. Ca răspuns la aceasta, autorii au propus o comandă de reîncercare care utilizează jurnalul de tranzacții (fișierul jurnal) generat de tranzacția eșuată pentru a determina fragmentul de memorie pe care o citește. Apoi începe automat tranzacția din nou când una dintre aceste locații de memorie se schimbă. Aceasta se bazează pe logica că o tranzacție nu se va comporta diferit până când cel puțin o astfel de valoare nu se va schimba.
Autorii au propus, de asemenea, un mecanism de construire a alternativelor (funcția orElse). Începe o tranzacție și dacă tranzacția reîncearcă, începe o a doua. Dacă la fel se întâmplă și cu al doilea, mecanismul le pornește din nou pe amândouă până când apare o schimbare semnificativă. Această funcție, comparabilă cu funcția standard select() de rețea POSIX, permite apelantului să aștepte oricare dintre mai multe evenimente în același timp. De asemenea, simplifică programarea interfeței, de exemplu prin furnizarea unui mecanism simplu de conversie între operațiunile de blocare și neblocare.
Această schemă a fost implementată în compilatorul Haskell GHC .
Simplitatea conceptuală a sistemelor STM permite programatorului să lucreze cu ușurință cu ele folosind o sintaxă relativ simplă a limbajului. În cartea lor An Auxiliary Language for Lightweight Transactions, Tim Harris și Keir Fraser au propus ideea de a utiliza Regiunea Critică Condițională (CCR) clasică pentru a reprezenta tranzacțiile. În forma sa cea mai simplă, acesta este doar un „bloc atomic”, o bucată de cod care este executată secvenţial la un singur moment în timp:
// Inserați atomic un nod într-o listă dublu legată atomic { newNode->prev = nod; newNode->next = nod->next; nod->next->prev = newNode; nod->next = newNode; }Când se ajunge la sfârșitul blocului, tranzacția este comisă, dacă este posibil, în caz contrar se încheie și se repetă. Regiunile critice condiționate permit, de asemenea, o condiție de persistență, care permite unei tranzacții să aștepte până când munca sa este în vigoare.
atomic (queueSize > 0) { eliminați elementul din coadă și utilizați-l }Dacă condiția eșuează, managerul de tranzacții va aștepta până când apare o alta care va afecta condiția înainte de a încerca din nou. Această comunicare liberă între producători și consumatori îmbunătățește modularitatea față de semnalizarea clară între fire. Composable Memory Access merge mai departe cu comanda sa de reîncercare (vezi mai sus), care poate anula tranzacția în orice moment și poate aștepta până când există o modificare a valorii citite anterior de operație înainte de a reîncerca. Exemplu:
atomic { if (QueueSize > 0) { eliminați elementul din coadă și utilizați-l } altfel { reîncercați } }Această capacitate de a reîncerca în mod dinamic la sfârșitul unei tranzacții simplifică modelul de programare și deschide noi posibilități.
O problemă este comportamentul excepțiilor atunci când se propagă în afara tranzacțiilor. În „A Composable Memory Access Operation”, autorii au decis că aceasta ar trebui să anuleze tranzacția, deoarece excepțiile indică, de obicei, erori neașteptate în Haskell (cu concurență), dar că această excepție poate stoca informațiile furnizate și le poate citi în timpul tranzacției în acest scop. de diagnosticare. Ei subliniază că alte decizii de proiectare sunt, de asemenea, rezonabile în raport cu alți parametri.
STM poate fi implementat ca un algoritm fără blocare și blocabil. Există două tipuri de blocare.
Schema de execuție a tranzacțiilor, numită „Transactional Locking-2” și implementată de Dice, Shalev și Shavit, folosește ora globală. Fiecare tranzacție începe prin citirea valorii curente a timpului și o stochează pentru citire. Apoi, la fiecare citire și scriere, versiunea zonei de memorie specificată este comparată cu versiunea pentru citire, iar dacă este mai mare, tranzacția este anulată. Acest lucru asigură că codul se execută pe copia corespunzătoare a memoriei. În timpul comiterii, toate regiunile de citire sunt blocate, iar valorile versiunii date a tuturor regiunilor de memorie de scriere și citire sunt verificate din nou. În cele din urmă, ora globală este incrementată, noile valori ale intrării de jurnal sunt scrise înapoi în memorie cu noua versiune a timpului.
O metodă din ce în ce mai populară pentru gestionarea conflictelor tranzacționale în memoria tranzacțională , în special în STM-uri, este ordinea în care(CO). Este utilizat pentru a obține o comandă fără blocare (adică fără blocare pentru tranzacțiile conflictuale și blocarea doar pentru comiterea tranzacțiilor) prin reordonarea tranzacțiilor (de exemplu, Ramadan și colab. 2009 și Zhang și colab. 2006). Comandarea este baza pentru starea corectă a memoriei tranzacționale (când se efectuează tranzacții paralele). Zeci de lucrări și brevete au fost deja publicate despre STM folosind „ordinul de executare”.
„Zhang şi colab., 2006” este un brevet american intitulat „Software de comandă de tranzacţii şi managementul conflictelor” (care se referă la brevetul US 5.701.480 de ordine de comandă). Iată fragmente:
„Sunt dezvoltate diverse tehnologii și metode pentru a aplica ordinea de execuție într-un sistem de memorie tranzacțională software. Sistemul de memorie tranzacțională a programului este echipat cu o funcție, astfel încât să se aplice o ordine predefinită de execuție multe operatii. Ordinea de comitere predefinită este utilizată în timpul execuției pentru a stabili ordinea în care efectuați tranzacții în sistemul de memorie tranzacțională software. Procesul de management al conflictului este invocat atunci când conflict între prima și a doua tranzacție. Ordinea predefinită de comitere este utilizată în procesul de gestionare a conflictului, pentru a determina ce tranzacție ar trebui să câștige conflictul și să i se permită să continue”.Cu ordinea de comitere, proprietatea dorită de ordonare este realizată prin efectuarea tranzacțiilor numai în ordine cronologică compatibilă cu ordinea de prioritate (după cum este determinată de ordinea cronologică a operațiunilor în conflicte)
SRTM a fost implementat (de diferite calități și stabilitate) în diferite limbaje de programare. Ca: