Come si implementa la memoria transazionale del software?

Question

In termini di effettive istruzioni atomiche di basso livello e recinti di memoria (suppongo siano utilizzati), come si implementa STM?

La parte che è misteriosa per me è che dato un po 'di codice arbitrario, hai bisogno di un modo per tornare indietro e determinare se i valori utilizzati in ogni passaggio erano validi. Come lo fai e come lo fai in modo efficiente? Ciò sembra anche suggerire che, proprio come qualsiasi altra soluzione di "blocco", si desidera mantenere le sezioni critiche più piccole possibili (per ridurre la probabilità di un conflitto), ho ragione?

Inoltre, STM può semplicemente rilevare " un altro thread è entrato in quest'area mentre il calcolo era in esecuzione, quindi il calcolo non è valido " o può effettivamente rilevare se sono stati usati valori ostruiti (e quindi per fortuna a volte due thread possono eseguire la stessa sezione critica contemporaneamente senza necessità di rollback)?

Answer 1

La risposta più semplice è " dipende " ;. Ci sono tonnellate di implementazioni radicalmente diverse che funzionano praticamente in qualsiasi modo immaginabile.

  

La parte che è misteriosa per me è che dato un po 'di codice arbitrario, hai bisogno di un modo per tornare indietro e determinare se i valori utilizzati in ogni passaggio erano validi. Come lo fai e come lo fai in modo efficiente?

Una soluzione è utilizzare il controllo delle versioni. Ogni volta che un oggetto viene modificato, il suo numero di versione viene aggiornato. Mentre la transazione è in esecuzione, si convalida la versione di ciascun oggetto a cui si accede e quando la transazione viene confermata, si verifica che gli oggetti siano ancora validi. Questa convalida può essere un semplice confronto di interi (se transaction_start_version > = object_version , l'oggetto è valido), quindi può essere fatto in modo abbastanza efficiente.

  

Ciò sembrerebbe anche suggerire che, proprio come qualsiasi altra soluzione di "blocco", si desidera ridurre al minimo le sezioni critiche (per ridurre la probabilità di un conflitto), ho ragione?

Molto probabilmente. Penso che alcune implementazioni abbiano intrapreso la strada dell'ipotesi / richiedere che tutto sia una transazione, ma sì, nella maggior parte delle implementazioni, le transazioni sono blocchi di codice appositamente contrassegnati e più a lungo viene eseguita una transazione, più grande è la possibilità di un conflitto che può causare il rollback delle transazioni.

  

Inoltre, STM può semplicemente rilevare " un altro thread è entrato in quest'area mentre il calcolo era in esecuzione, quindi il calcolo non è valido " o può effettivamente rilevare se sono stati usati valori ostruiti (e quindi per fortuna a volte due thread possono eseguire la stessa sezione critica contemporaneamente senza necessità di rollback)?

Quest'ultimo. Tieni presente che l'idea in TM è di proteggere dati , piuttosto che codice .

Percorsi di codice diversi possono accedere alla stessa variabile in transazioni diverse. Questo deve essere rilevato dal sistema TM. Non esiste alcuna nozione reale di "quest'area", poiché si riferisce al codice, piuttosto che ai dati. Al sistema TM non importa quale codice sta eseguendo, tiene traccia di quali dati vengono modificati. In tal modo, differisce completamente dalle sezioni critiche (che proteggono il codice, piuttosto che i dati)

Answer 2

Alcuni articoli possono essere davvero difficili da leggere, ma due che sono molto chiari e concisi sono:

Transactional Locking II, Dave Dice, Ori Shalev, Nir Shavit che descrive il "TL2" Algoritmo STM in termini di qualsiasi lingua.

Deuce: memoria transazionale software non invasiva in Java, Guy Korland, Nir Shavit, Pascal Felber che spiega un trasformatore di classi di tempo di caricamento che trasforma le normali classi java in classi in memoria che hanno un bytecode aggiuntivo per eseguire STM. Questo è rilevante per la domanda poiché l'articolo spiega come il codice senza STM possa essere trasformato meccanicamente in codice che sta eseguendo STM in qualsiasi linguaggio OO.

Il framework Deuce consente di plug-in l'algoritmo effettivo che si desidera utilizzare; incluso l'algoritmo TL2. Poiché il framework Deuce è Java, la seguente discussione utilizza la terminologia java ma presuppone solo che si stia scrivendo in un linguaggio OO.

Di seguito verrà illustrato l'approccio TL2. Gli articoli hanno collegamenti ad approcci alternativi ma studiare un algoritmo risponde a molte domande.

  

come si implementa STM? La parte che è misteriosa per me è che dato un po 'di codice arbitrario, hai bisogno di un modo per tornare indietro e determinare se i valori utilizzati in ogni passaggio erano validi.

Una breve risposta su come TL2 fa STM è "contabilità" e quindi utilizzando solo i blocchi di scrittura in fase di commit. Leggi la carta per i dettagli precisi, ma un contorno di pennello da tavolo è il seguente. Ogni proprietà che è possibile utilizzare nel codice originale avrebbe un getter e setter. Nel codice trasformato ci sarebbe anche un numero di versione della proprietà e un codice aggiuntivo aggiunto al getter e al setter. Devi registrare la versione di ogni attributo che leggi all'interno della transazione come transazione "read-set". Puoi farlo facendo in modo che ogni getter aggiunga la versione dell'attributo vista in una lista linkata locale. È inoltre necessario bufferizzare le scritture come " write-set " in un threadlocal fino al commit. Si noti che i metodi getter devono controllare e restituire un valore di set di scrittura threadlocal per un determinato campo se ne hai uno. In questo modo vedi le tue scritture senza commit nelle tue letture ma nessun altro thread le vedrà fino a quando non commetti.

Al momento del commit prendi i blocchi di scrittura su ogni attributo che stai per scrivere. Mentre hai i lucchetti ricontrolla che il tuo read-set sia ancora valido; che gli attributi letti nella transazione non sono stati aggiornati a una versione successiva da un'altra transazione. In tal caso, la tua logica aziendale potrebbe non essere valida in quanto potresti avere letture incoerenti, quindi è necessario eseguire il rollback dell'intera transazione. Se i controlli finali passano, allora esegui il commit svuotando il set di scrittura, esegui il bump delle versioni di tali attributi, rilascia i blocchi di scrittura e cancella gli elenchi threadlocal sia del set di scrittura che del set di lettura.

Il documento spiega che l'algoritmo può interrompersi in anticipo se rileva che un attributo in corso di lettura è stato scritto dall'inizio di tx. Il documento presenta alcuni trucchi per accelerare le transazioni di sola lettura. Ha anche un trucco per capire quali blocchi sono di sola lettura e quali sono di lettura-scrittura. Chiunque esprima interesse per tali cose dovrebbe davvero apprezzare i due documenti.

Il framework Deuce nel documento sopra mostra come cambiare tutti i getter e setter iniettando un nuovo bytecode java nelle tue classi al momento del caricamento. Altre lingue potrebbero avere un compilatore o un preprocessore speciale che eseguono la stessa trasformazione meccanica del codice normale in codice abilitato STM. In particolare con Deuce gli oggetti del codice sorgente possono avere semplici coppie di setter getter, ma le classi trasformate in fase di esecuzione hanno setter getter arricchiti che fanno il bookwork.

Trasformare il codice normale in codice STM (in particolare in fase di runtime) è interessante ma se è necessario scrivere effettivamente una struttura di dati abilitata per STM non è necessaria alcuna magia. Invece basta creare una classe Ref con un get () e un set (x) e creare ogni singola relazione tra gli oggetti della struttura dei dati di handle Ref . Nella get e set della tua classe Ref puoi fare i bookwork locali. Quindi puoi implementare una versione semplice di " TL2 " o qualsiasi altro algoritmo che funzioni bene per le strutture dei dati e la concorrenza tra lettura e scrittura.

  

Questo sembra anche suggerire che, proprio come qualsiasi altro 'blocco'   soluzione che desideri per ridurre al minimo le sezioni critiche   (per ridurre la probabilità di un conflitto), ho ragione?

TL2 ha un periodo critico nel trattenere i blocchi di scrittura e poi fare i controlli e le scritture finali che è facile da comprendere e ottimizzare senza alcuna comprensione della logica di business dell'applicazione. Se si assegna a ciascun numero una proprietà unica, è possibile evitare banalmente un deadlock prendendo i blocchi in ordine crescente. È importante notare che tutte le logiche aziendali vengono eseguite in modo speculativo supponendo che i controlli di commit verranno eseguiti. Non tieni i blocchi mentre esegui una logica di business lenta e arbitraria. Puoi eseguire più ricerche di servizi Web o rallentare le chiamate al database e non eseguirai alcun blocco fino al commit. Chiaramente i professionisti riusciranno a mettere a tacere la sezione critica generica.

Il documento chiarisce che l'algoritmo potrebbe interrompersi più spesso di quanto richiesto dalla specifica logica aziendale. L'algoritmo generico non sa se specifiche letture sporche non influirebbero sul risultato di scrittura effettivo. La logica scritta a mano che comprende la logica aziendale reale potrebbe conoscere casi speciali quando non è necessario un rollback per un determinato set di letture sporche. Se tuttavia hai un sacco di codice da scrivere e un'applicazione in cui la probabilità di rollback è molto bassa, un approccio STM meccanico generico può portare a meno bug e ad avere buone prestazioni.

  

Inoltre, STM può semplicemente rilevare " un altro thread è entrato in quest'area mentre   il calcolo era in esecuzione, pertanto il calcolo non è valido "   o può effettivamente rilevare se sono stati usati valori ostruiti (e quindi   per fortuna a volte due thread possono eseguire la stessa sezione critica   contemporaneamente senza necessità di rollback)?

L'approccio TL2 in quanto tutto sui dati letti o scritti non sul codice che lo fa. È ciò che ottieni e imposta e che conta; e se qualsiasi altro filo ha calpestato le dita dei piedi prima di cancellare tutte le scritture. Tutto ciò che è richiesto per il codice è che hai un begin () , commit () e rollback () nella logica di business per iniziare , terminare e interrompere la transazione. Anche quello può essere generato codice. Con Java puoi contrassegnare i tuoi metodi con l'annotazione transazionale sui metodi e quindi generare il codice che avvolge le invocazioni dei tuoi metodi in un try / catch / infine che inizia / commit / rollback come java idiomica. Deuce inietta tale logica al momento del caricamento della classe.

Ancora una volta non hai bisogno di tale salsa magica per iniziare / eseguire il commit / rollback nelle tue strutture dati abilitate STM. Puoi essere esplicito e inserire tutto ciò nel tuo codice logico della struttura dei dati per creare le tue classi esplicitamente abilitate STM in qualsiasi linguaggio OO.

Answer 3

L'implementazione STM di

?? GHC è descritta nella sezione sei di:

Transazioni di memoria componibile . Tim Harris, Simon Marlow, Simon Peyton Jones, Maurice Herlihy. PPoPP'05: ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Chicago, Illinois, June 2005

E la sezione cinque di:

Memoria transazionale con invarianti di dati . Tim Harris, Simon Peyton-Jones. Marzo 2006 TRANSACT '06

Answer 4

Ti suggerisco di guardare questa presentazione: http: // www. infoq.com/presentations/Value-Identity-State-Rich-Hickey

Nella seconda metà spiega come aggiornare i valori senza lasciarli in uno stato indefinito. Ad esempio, se si dispone di un albero che si desidera aggiornare in stile STM, non si modifica affatto la versione precedente. Diciamo che tree è un puntatore alla radice dell'albero. L'unica cosa che crei sono i nodi modificati (ma possono fare riferimento a nodi nell'istantanea originale dell'albero.

Quindi esegui un confronto e uno scambio sul puntatore tree . Se è riuscito, allora tutti vedranno il tuo nuovo albero e quello vecchio può essere raccolto. In caso contrario, ripeti il ??processo e l'albero che hai appena costruito viene raccolto.

La grande idea è che non è necessario rilevare se qualcun altro ha cambiato l'albero fino a quando non si scambiano effettivamente i valori vecchi e nuovi, quindi non ci sono "conflitti". o "quotazioni ostruite" dalla tipica programmazione multithread.

Answer 5

Se si utilizza .NET Framework,

Puoi dare un'occhiata a questo sperimentale

• .NET 4.0 STM.Net
  
• .NET rock podcast su STM.Net: Dana Groff e Yossi Levanoni Talk STM