I databehandling er STM ( Transactional Memory ) en samtidighetskontrollmekanisme som er analog med databasetransaksjoner for å kontrollere tilgang til delt minne i samtidig programmering . Den fungerer som et alternativ til låsebasert synkronisering , og implementeres vanligvis uten låser. I denne sammenhengen er en transaksjon et stykke kode som utfører en serie leser og skriver til delt minne. Disse lesingene og skrivingene foregår praktisk talt udelelig, mellomstatene er ikke synlige for andre vellykkede transaksjoner.
I 1993 kom Maurice Herlihy og Moss på ideen om å gi maskinvarestøtte for transaksjoner. I 1995 tilpasset Nir Shavit og Dan Touitou denne ideen ved å fjerne behovet for spesifikk maskinvare, derav navnet programvaretransaksjonsminne. STM var nylig Objektet med intens forskning og konkrete implementeringer multipliserer.
I motsetning til låsingsteknikkene som brukes i flertrådede applikasjoner , er STM optimistisk : hver tråd gjør endringer i delt minne uavhengig av hva andre tråder gjør, og logger hver av sine leser og skriver. I stedet for å gi ansvaret til de trådene som skriver i minnet for å være sikker på at de ikke unødig påvirker pågående operasjoner, er dette ansvaret gitt til leseren tråder , som etter å ha fullført en komplett transaksjon, sjekk at de andre trådene gjorde ikke samtidig endringer i minnet. Den endelige operasjonen kalles en forpliktelse , der endringer i en transaksjon blir begått og, hvis forpliktelsen er vellykket, blir de gjort permanente. En transaksjon kan også mislykkes når som helst. Alle endringer som gjelder det blir " tilbakekalt " eller kansellert. Hvis en handel ikke kan begås på grunn av motstridende endringer, blir den vanligvis avbrutt og utført på nytt fra begynnelsen til den lykkes.
Fordelen med en optimistisk tilnærming er økt samtidighet: ingen tråder må vente på å få tilgang til en ressurs, og forskjellige tråder kan trygt og samtidig endre usammenhengende deler av datastrukturer som normalt vil være beskyttet under samme lås. Til tross for merkostnadene ved å prøve på nytt mislykkede transaksjoner, er konflikter i de fleste realistiske programmer sjeldne nok til at det er en enorm ytelsesgevinst over låsebaserte protokoller på et stort antall prosessorer.
Men i praksis lider STM av lavere ytelse sammenlignet med finkornede systemer med et lite antall prosessorer (1 til 4 avhengig av applikasjon). Dette er hovedsakelig på grunn av overhead forbundet med å opprettholde loggen og tiden det tar når du begår flere transaksjoner. Men selv da, typisk. ytelsen er bare halvparten så god, STM-advokater mener at STMs konseptuelle fordeler oppveier denne straffen.
Teoretisk sett, i verste fall, når det er n samtidige transaksjoner samtidig, kan det kreve 0 (n) minne og CPU-forbruk. Faktiske krav avhenger av implementeringsdetaljer. For eksempel kan en transaksjon gjøres for å mislykkes tidlig nok til å minimere overhead. Men det vil alltid være tilfeller, riktignok sjeldne, der låsebaserte algoritmer har en teoretisk bedre tid enn programvaretransaksjonsminne.
I tillegg til ytelsesfordeler, forenkler STM forståelsen av flertrådede programmer og hjelper derfor å gjøre programmene mer vedlikeholdbare fordi de fungerer i harmoni med abstraksjoner på høyt nivå som objekter og moduler. Låsebasert programmering har en rekke kjente problemer som ofte oppstår i praksis:
I motsetning til dette er konseptet med en minnetransaksjon mye enklere fordi hver transaksjon kan sees isolert i en enkeltlinjeberegning. Låsere og livelocks unngås enten helt, eller administreres av en ekstern transaksjonsleder. Programmereren trenger aldri å bekymre seg for det. Prioritering kan fortsatt være et problem, men transaksjoner med høy prioritet kan avbryte transaksjoner med lavere prioritet som ikke er begått.
På den annen side begrenser behovet for å avbryte mislykkede transaksjoner den mulige oppførselen til transaksjoner: de kan ikke utføre handlinger som ikke kan angres, som de fleste I / O. I praksis kan man vanligvis overvinne slike begrensninger ved å lage buffere som akkumulerer irreversible operasjoner og utføre dem senere utenfor en transaksjon.
I 2005 beskrev Tim Harris, Simon Marlow, Simon Peyton Jones og Maurice Herlihy et system bygget for STM Concurrent Haskell (in) . Det gjør at atomoperasjoner kan komponeres i større atomoperasjoner, et nyttig konsept som ikke er mulig med låsebasert programmering. La oss sitere forfatterne:
"Den kanskje mest grunnleggende innvendingen ... er at låsebaserte programmer ikke består : riktige fragmenter kan mislykkes når de kombineres. Tenk for eksempel på en hash-tabell med trådsikker innsettings- og slettingsoperasjoner . Anta at vi vil slette element A fra tabell t1, og sette det inn i tabell t2. Men mellomtilstanden (der ingen tabell inneholder elementet) må ikke være synlig for andre tråder . Med mindre hashbord-implantereren forventer dette behovet, er det ingen enkel måte å tilfredsstille dette kravet på. [...]. Kort sagt, operasjoner som er individuelt korrekte (sett inn, slett) kan ikke sammensettes til større og fortsatt korrekte operasjoner. "
- Tim Harris et al., "Composable Memory Transactions", Avsnitt 2: Bakgrunn, s.2
Med STM er det enkelt å løse problemet: innpakningsoperasjoner i en transaksjon gjør kombinasjonen deres atomær. Det eneste delikate punktet er at det ikke er klart for den som ringer, som ikke kjenner til detaljene for implementeringen av komponentmetodene når de skal prøve å kjøre transaksjonen på nytt hvis den mislykkes. Som svar på dette problemet foreslo forfatterne en prøvekommando på nytt som bruker loggen til den mislykkede transaksjonen for å bestemme hvilken minnecelle som blir lest, og for å prøve transaksjonen på nytt når en av disse cellene blir modifisert. Logikken er at transaksjonen ikke vil oppføre seg annerledes før ingen av disse verdiene er endret. Forfatterne foreslo også en mekanisme for å komponere alternativer , nøkkelordet orElse . Den utfører en transaksjon, og hvis den transaksjonen prøver på nytt , utfører den en annen. Hvis begge prøver på nytt, prøver den begge to igjen så snart en passende endring er gjort. Denne tjenesten, som kan sammenlignes med POSIX-nettverksfunksjonaliteten til select () systemanropet , lar den som ringer velge å vente på flere hendelser samtidig. Det forenkler også programmatiske grensesnitt, for eksempel ved å tilby en enkel mekanisme for å konvertere mellom blokkering og ikke-blokkering operasjoner.
Den konseptuelle enkelheten til STM gjør det mulig å eksponere denne mekanismen for programmereren med en relativt enkel syntaks. Språkstøtte for lette transaksjoner (støttet av språket for små transaksjoner) Tim Harris og Keir Fraser foreslår å bruke konseptet betinget kritisk region (" Conditional Critical Region ") for å representere transaksjonene. I sin enkleste form er det ganske enkelt en "atomblokk", det vil si en kodeblokk som bare kan utføres fullt ut eller ikke i det hele tatt:
// Insère, de manière atomique, un nœud dans une liste doublement chaînée atomic { newNode->prev = node; newNode->next = node->next; node->next->prev = newNode; node->next = newNode; }Når slutten av blokken er nådd, blir transaksjonen begått hvis mulig, ellers blir den avbrutt og prøvd på nytt.
Betingede kritiske regioner muliggjør også varetektsforhold , som gjør at en transaksjon kan vente til den har arbeid å gjøre:
atomic (queueSize > 0) { // Retire un élément de la file d'attente avant de l'utiliser }Hvis vilkåret ikke er oppfylt, vil transaksjonssjefen vente før han prøver transaksjonen på nytt for en annen transaksjon å utføre etter endring av vilkåret. Denne løse koblingen mellom produsenter og forbrukere gjør koden mer modulær enn å bruke eksplisitte signaler mellom tråder .
De composable minne transaksjoner ( " composable Memory Transaksjoner ") tillate oss å gå enda lenger med kommandoen retry (se ovenfor) som kan, når som helst å avbryte transaksjonen og vente før retry, at 'noen verdi lese før transaksjonen er endret. For eksempel :
atomic { if (queueSize > 0) { // Retire un élément de la file d'attente avant de l'utiliser } else { retry } }Denne evnen til å prøve transaksjonen dynamisk senere forenkler programmeringsmodellen og åpner for andre muligheter.
Et av problemene er hvordan et unntak som forplantes utenfor en transaksjon, samhandler med transaksjonen. I komponerbare minnetransaksjoner valgte Tim Harris og Keir Fraser å avbryte transaksjonen når et unntak blir kastet, siden et unntak i Concurrent Haskell vanligvis indikerer en uventet feil, men de bestemte seg også for at unntak for diagnostiske formål kan beholde informasjon som er tildelt og lest under transaksjonen. Imidlertid insisterer Tim Harris og Keir Fraser på at dette valget ikke er det eneste mulige, og at andre implementeringer kan ta andre rimelige valg.
Et problem med implementering av programvaretransaksjonsminne er at det er mulig for en transaksjon å lese inkonsekvent tilstand, det vil si å lese en blanding av gamle og nye verdier skrevet av en annen. En slik transaksjon er dømt til å avbrytes hvis den forsøker å begå, men det er mulig at en inkonsekvent tilstand får en transaksjon til å utløse en eksepsjonell dødelig tilstand som en segmenteringsfeil eller til og med gå inn i en endeløs løkke, som i det følgende kunstige eksemplet i figur 4 av “Språkstøtte for lette transaksjoner”:
|
atomic {
if (x != y)
while (true) { }
}
Transaksjon A |
atomic {
x++;
y++;
}
Transaksjon B |
Hvis i utgangspunktet x = y , vil ingen av de ovennevnte to transaksjonene endre den uendelige, men det er mulig at transaksjon A leser x før transaksjon B endrer den, noe som fører til en uendelig løkke. Den vanlige strategien for å håndtere dette er å fange dødelige unntak og med jevne mellomrom sjekke om hver transaksjon er gyldig. Ellers kan vi indusere hennes umiddelbare abort, siden hun vil mislykkes uansett hva.
Mange STM-implementeringer er utgitt (med store variasjoner i kvalitet og stabilitet), mange under gratis lisenser: