L'STM fornisce un blocco a grana fine per le strutture dati esistenti?

Question

Reading Bartosz del fantastico blog post Milewski su STM, ero entusiasta di leggere quanto segue:

Ma prendere in considerazione un fatto importante: STM è molto a grana fine. Per l'istanza , quando si inserisce un elemento in un albero, la transazione STM bloccherà solo i nodi che si stanno effettivamente modificando. STM batterà facilmente una soluzione che utilizza un blocco globale per l'intero albero .

Tuttavia, a quanto ho capito, questo comportamento non è automatico, vero? Se utilizzo uno TVar (Map k a), non agirà come un unico blocco globale sull'intera mappa? E per ottenere il vantaggio di questo comportamento a grana fine, io (o qualcuno) dovrei implementare una sostituzione di mappa (TMap, ad esempio) che contenga internamente TVars, corretto?

Questa potrebbe sembrare una domanda ovvia, ma leggendo su implementazione STM sono stato confuso tra le letture di TVar se letture di posizioni di memoria. Voglio solo assicurarmi di averlo bene!

Bartosz va oltre a dire:

Per-nodo bloccaggio manuale è difficile da implementare correttamente perché del rischio di deadlock.

La differenza con STM, come mi risulta, è che mentre l'attuazione STM in effetto usa blocca il modo in cui una soluzione manualmente bloccato potrebbe, l'acquiry e rilascio di serrature effettivo è gestita dal runtime, non il programmatore - corretto?

Answer 1

A TVar è una cella mutabile. Con strutture immutabili, due thread non possono trasmettere modifiche avanti e indietro, quindi abbiamo bisogno di qualche nozione di cellula mutabile per causare l'effetto. In particolare, abbiamo

writeTVar :: TVar a -> a -> STM() 

che crea un SMT azione sostituendo il valore all'interno della cella mutevole. Possiamo sequenziare alcune di queste operazioni insieme, costruendo una STM un'azione più grande e più complessa, e quindi chiamare

atomically :: STM a -> IO a 

commettere atomicamente tutta STM azione contemporaneamente. Questa è la parte "transazionale" della memoria transazionale del software: altri thread con i propri riferimenti a queste celle mutabili saranno sempre e solo testimoni dell'intera azione STM -performata STM, non di sottoparti. Per ottenere questo Haskell potrebbe utilizzare il blocco, o qualcosa di più intelligente, è un semplice dettaglio di implementazione. L'unica cosa che STM ti chiede è che le azioni all'interno del tuo blocco STM possono essere eseguite ripetutamente come necessario, e quindi gli effetti collaterali al di fuori della modifica di alcune celle di memoria condivisa sono proibiti.

Quindi, come possiamo ottenere una concorrenza a grana fine? Facilmente: forniamo semplicemente più celle mutabili per i vari thread su cui sincronizzare. Ad esempio, possiamo leggere almeno 3 diversi tipi di Map.

TVar (Map k v) 
Map k (TVar v) 
TVar (Map k (TVar v)) 

La prima permetterà thread concorrenti di apportare modifiche a tutta Map tutto in una volta tale che non cambi parziali sono visibili. Il secondo, consente modifiche a qualsiasi valore memorizzato, ma sostiene che la struttura della mappa stessa - la scelta delle chiavi e la selezione dei valori memorizzati - è immutabile e le modifiche non possono essere facilmente propagate ad altri thread.

La scelta finale, TVar (Map k (TVar v)) è la più flessibile. Possiamo apportare modifiche all'ingrosso allo Map sincronizzandoci sull'esterno TVar e possiamo apportare modifiche ai valori memorizzati nella mappa leggendo fino al valore TVar s e sincronizzandoci sulle azioni al loro interno. L'insieme completo di semantica possibile disponibile per un tale albero è una miriade che consente sia il "blocco intero Map" che il "blocco del valore individuale" che avvengono insieme.