Inden for computerteknologi er softwaretransaktionshukommelse ( STM ) en samtidighedskontrolmekanisme, der ligner databasetransaktionsmekanismen til at kontrollere adgangen til delt hukommelse i parallel computing . Det er et alternativ til låsebaseret synkronisering . En transaktion er i denne sammenhæng et stykke kode, der læser fra og skriver til delt (delt) hukommelse. Læsning og skrivning sker logisk på et enkelt tidspunkt, og mellemtilstande er usynlige for andre (resulterende) transaktioner. Ideen om at give transaktioner med hardwaresupport opstod i 1986 i Tom Knights arbejde og patent . [1] Ideen blev offentliggjort af Maurice Herlihy og Eliot Moss . [2] I 1995 udvidede Nir Shavit og Dan Toytu denne idé til softwaretransaktionshukommelse (STM). STM er stadig i centrum for intens forskning; dens støtte til praktiske implementeringer er stigende.
I modsætning til de blokeringsmetoder , der bruges i de fleste moderne multitrådede applikationer, er STM meget optimistisk: en tråd fuldfører ændringer til delt hukommelse uden hensyntagen til, hvad andre tråde gør, og logger enhver læsning og skrivning til loggen. I stedet for at bruge skribenten til at kontrollere, om det har en negativ effekt på andre igangværende operationer, overføres ansvaret til læseren, som efter at have gennemført en komplet transaktion kontrollerer, om andre tråde samtidig har foretaget ændringer i den hukommelse, der blev tilgået i fortid.. Denne sidste operation, som kontrollerer for transaktionsændringer, og som, hvis kontrollen lykkes, forbliver uændret, kaldes en commit. Transaktionen kan til enhver tid opsiges, som følge heraf vil alle seneste ændringer blive annulleret. Hvis en transaktion ikke kan udføres på grund af ændringskonflikter, afbrydes den og forsøges igen fra begyndelsen, indtil den er fuldført.
Fordelen ved denne optimistiske tilgang forstærkes af parallelitet: ingen tråd behøver at vente på adgang til en ressource, og forskellige tråde kan samtidigt og sikkert ændre usammenhængende dele af datastrukturen, der ville være beskyttet af den samme lås.
Men i praksis taber STM-systemer i ydeevne til finkornede systemer baseret på låse på et lille antal processorer (fra 1 til 4 afhængigt af applikationen). Dette skyldes primært overhead ved at vedligeholde loggen og den tid, der bruges på transaktioner. Men selv i dette tilfælde afviger ydeevnen ikke mere end 2 gange. [3] Tilhængere af STM mener, at sådanne tab er begrundet i de konceptuelle fordele ved STM.
Teoretisk set er tids- og rumkompleksiteten ved at køre n parallelle transaktioner O (n) i værste fald . De faktiske omkostninger afhænger af implementeringen (du kan annullere transaktionen tidligt for at undgå overhead), men der vil altid være tilfælde, omend sjældne, hvor låsealgoritmer vil have bedre tidskompleksitet end softwaretransaktionshukommelse.
Ud over ydelsesfordelene forenkler STM i høj grad den konceptuelle forståelse af multitrådede programmer og hjælper med at vedligeholde dem ved at arbejde problemfrit med eksisterende abstraktioner på højt niveau såsom objekter og moduler.
Låseprogrammering indeholder en række kendte problemer, som ofte opstår i praksis:
Tværtimod er begrebet transaktionshukommelse meget enklere, fordi hver transaktion kan betragtes individuelt, som en enkelt-trådet beregning. Deadlocks er enten forhindret helt eller løst af en ekstern transaktionsadministrator; programmøren behøver næppe at bekymre sig om dette. Prioritetsinvertering kan stadig være et problem, men højprioritetstransaktioner kan afbryde modstridende lavprioritetstransaktioner, som endnu ikke er blevet begået.
På den anden side pålægger behovet for at afbryde mislykkede transaktioner også begrænsninger for deres adfærd: de kan ikke udføre nogen handling, der ikke kan fortrydes, inklusive de fleste I/O. Sådanne begrænsninger overvindes normalt i praksis ved at skabe buffere, der sætter irreversible operationer i kø og udfører dem nogen tid senere uden for enhver transaktion. I Haskell håndhæves denne begrænsning af typesystemet på kompileringstidspunktet.
I 2005 beskrev Tim Harris, Simon Marlow, Simon Peyton-Jones og Maurice Herlihy et STM-system bygget i Haskell , der implementerer parallelisme. Dette system gør det muligt at kombinere vilkårlige atomoperationer til større atomoperationer, et nyttigt koncept, der ikke er muligt med låseprogrammering. Ifølge forfatterne:
"Den måske mest fundamentale ulempe er, at låseprogrammer ikke kan linke: korrekte fragmenter fungerer muligvis ikke, når de er linket. Overvej for eksempel en hash-tabel med trådsikre indsættelser og sletninger. Antag nu, at vi vil fjerne et element fra tabel t1 og indsætte det i tabel t2, men den mellemliggende tilstand (hvor ingen tabel indeholder det element) bør ikke være synlig for andre tråde. Indtil hash-tabeldesigneren bestemmer dette behov, er der simpelthen ingen måde at opfylde dette krav på. Generelt kan hver korrekt operation (indsættelser, sletninger) ikke kombineres til større korrekte operationer.
— (Tim Harris et al., "Composable Memory Access Operation", afsnit 2. Baggrund, s.2)Med STM løses dette problem ganske enkelt: blot at kombinere to operationer i en transaktion forvandler en komponerbar operation til en atomær operation. Den eneste anstødssten er, at det ikke er klart for den, der ringer, som ikke kender implementeringsdetaljerne for linkmetoderne, hvornår de skal forsøge at prøve transaktionen igen, hvis den ikke sker. Som svar på dette har forfatterne foreslået en genforsøgskommando, der bruger transaktionsloggen (logfilen) genereret af den mislykkede transaktion til at bestemme det stykke hukommelse, den læser. Den starter derefter automatisk transaktionen igen, når en af disse hukommelsesplaceringer ændres. Dette er baseret på logikken om, at en transaktion ikke vil opføre sig anderledes, før mindst én sådan værdi er ændret.
Forfatterne foreslog også en mekanisme til at konstruere alternativer (ellerElse-funktionen). Den starter en transaktion, og hvis transaktionen forsøger igen, starter den en anden. Hvis det samme sker med den anden, starter mekanismen dem begge igen, indtil der sker en væsentlig ændring. Denne funktion, der kan sammenlignes med POSIX-netværksstandard select()-funktionen, giver den, der ringer, mulighed for at vente på en hvilken som helst af et antal hændelser på samme tid. Det forenkler også grænsefladeprogrammering, for eksempel ved at tilvejebringe en simpel konverteringsmekanisme mellem blokerende og ikke-blokerende operationer.
Denne ordning blev implementeret i Haskell- kompileren GHC .
Den konceptuelle enkelhed af STM-systemer gør det muligt for programmøren nemt at arbejde med dem ved hjælp af en relativt simpel syntaks af sproget. I deres bog An Auxiliary Language for Lightweight Transactions foreslog Tim Harris og Keir Fraser ideen om at bruge den klassiske Conditional Critical Region (CCR) til at repræsentere transaktioner. I sin enkleste form er dette blot en "atomblok", et stykke kode, der udføres sekventielt på et enkelt tidspunkt:
// Atomisk indsætte en node i en dobbelt linket liste atomare { newNode->prev = node; newNode->next = node->next; node->next->prev = nyNode; node->next = nyNode; }Når slutningen af blokeringen er nået, er transaktionen forpligtet, hvis det er muligt, ellers afsluttes den og gentages. Betingede kritiske områder tillader også en persistenstilstand, som gør det muligt for en transaktion at vente, indtil dens opgave er i kraft.
atomic (køstørrelse > 0) { fjern varen fra køen og brug den }Hvis betingelsen mislykkes, vil transaktionsadministratoren vente, indtil der opstår en anden, som vil påvirke tilstanden, før han prøver igen. Denne løse kommunikation mellem producenter og forbrugere forbedrer modulariteten i forhold til tydelig signalering mellem tråde. Composable Memory Access går videre med sin genforsøgskommando (se ovenfor), som kan afbryde transaktionen til enhver tid og vente, indtil der er en ændring i den værdi, som tidligere blev læst af operationen, før du prøver igen. Eksempel:
atomare { if (køstørrelse > 0) { fjern varen fra køen og brug den } andet { prøve igen } }Denne evne til dynamisk at prøve igen i slutningen af en transaktion forenkler programmeringsmodellen og åbner op for nye muligheder.
Et problem er adfærden hos undtagelser, når de udbreder sig uden for transaktioner. I "A Composable Memory Access Operation" besluttede forfatterne, at dette skulle afbryde transaktionen, da undtagelser normalt angiver uventede fejl i Haskell (med samtidighed), men at denne undtagelse kan gemme den angivne information og læse den under transaktionen til formålet. af diagnostik. De understreger, at andre designbeslutninger også er rimelige under andre parametre.
STM kan implementeres som en låsefri og låsbar algoritme. Der er to typer blokering.
Transaktionsudførelsesskemaet, kaldet "Transactional Locking-2" og implementeret af Dice, Shalev og Shavit, bruger global tid. Hver transaktion starter med at læse den aktuelle tidsværdi og gemmer den til læsning. Derefter, ved hver læsning og skrivning, sammenlignes versionen af det specificerede hukommelsesområde med versionen til læsning, og hvis den er større, annulleres transaktionen. Dette sikrer, at koden udføres på den passende kopi af hukommelsen. Under commit låses alle læseområder, og værdierne for den givne version af alle skrive- og læsehukommelsesområder kontrolleres igen. Til sidst øges den globale tid, de nye værdier for logindgangen skrives tilbage til hukommelsen med den nye version af tiden.
En stadig mere populær metode til at håndtere transaktionskonflikter i transaktionshukommelsen , især i STM'er, er den rækkefølge, hvori(CO). Det bruges til at opnå låsefri bestilling (dvs. ingen låsning på modstridende transaktioner og kun låsning på transaktionsbekræftelse) ved at genbestille transaktioner (f.eks. Ramadan et al. 2009 og Zhang et al. 2006). Bestilling er grundlaget for den korrekte tilstand af transaktionshukommelsen (når parallelle transaktioner udføres). Dusinvis af papirer og patenter er allerede blevet offentliggjort om STM ved hjælp af "udførelsesordren".
"Zhang et al., 2006" er et amerikansk patent med titlen "Transaction Order Software and Conflict Management" (som henviser til Order Order US Patent 5.701.480). Her er uddrag:
"Forskellige teknologier og metoder er ved at blive udviklet til at anvende rækkefølge for udførelse i et softwaretransaktionshukommelsessystem. Programtransaktionshukommelsessystemet er udstyret med en funktion, så en foruddefineret udførelsesrækkefølge er gældende for mange operationer. Den foruddefinerede commit-rækkefølge bruges under kørsel til at etablere den rækkefølge, hvori foretage transaktioner i softwarens transaktionshukommelsessystem. Konflikthåndteringsprocessen påberåbes, når konflikt mellem den første og anden transaktion. Den foruddefinerede rækkefølge af forpligtelse bruges i konflikthåndteringsprocessen, at afgøre, hvilken transaktion der skal vinde konflikten og få lov til at fortsætte."Med commit-rækkefølge opnås den ønskede egenskab for bestilling ved kun at begå transaktioner i kronologisk rækkefølge i overensstemmelse med rækkefølgen (som bestemt af den kronologiske rækkefølge af operationer i konflikter)
SRTM er implementeret (af varierende kvalitet og stabilitet) i forskellige programmeringssprog. Såsom: