Haskell: come funziona TVar?

Question

Come funziona TVar? Da quello che ho letto tenta di eseguire tutte le transazioni immediatamente dopo averle ricevute, tuttavia, una transazione che completa invalida altre transazioni attualmente in esecuzione, che devono quindi essere riavviate. È così che funziona TVar?

In questo caso, se ci fossero transazioni lunghe 1 ms che si verificano ogni 100 ms, ciò significherebbe che una transazione che richiede 200 ms per l'elaborazione non verrebbe mai completata?

Answer 1

Fintantoché due transazioni accedono allo TVars distinte, possono essere eseguite contemporaneamente senza invalidare l'un l'altro.

Giusto per mettere in chiaro quando una transazione è invalidato, consideriamo il seguente scenario:

1. Supponiamo che t :: TVar Int è inizializzato a 0 e viene letto tramite readTVar t all'inizio di una transazione A.
2. Nel frattempo, in un'altra discussione, viene avviata la transazione B in cui viene eseguito un writeTVar t 1. Si supponga che B si impegna prima dello A. Il sistema STM verificherà l'eventuale presenza di incongruenze e concluderà che è sicuro che B esegua il commit a questo punto, quindi ora writeTVar t 1 diventa effettivo.
3. Ciò causa tuttavia l'annullamento della transazione A poiché il vecchio valore 0 di t è stato letto all'inizio di A. (Se A è stato permesso di commettere, otterremmo una violazione della atomicità.)

Il documento originale [1] sul sistema STM di Haskell (vedi cap 6.5) risponde alla tua domanda:

"Starvation Ad esempio, una transazione che viene eseguita per un periodo di tempo molto lungo può essere ripetutamente in conflitto con transazioni più brevi Pensiamo che in pratica non si verificherà la fame, ma noi non possiamo dirlo senza ulteriore esperienza " .

[1] Tim Harris, Simon Marlow, Simon Peyton Jones e Maurice Herlihy. Conferenza ACM su principi e pratica della programmazione parallela 2005 (PPoPP'05).

Answer 2

Se ci fossero transazioni lunghe 1 ms che si verificano ogni 100 ms, ciò significherebbe che una transazione che richiede 200 ms per elaborare non verrebbe mai completata? solo

transazioni conflitto se toccano gli stessi TVar s, quindi se alcune delle operazioni di 1ms evitato tutte le variabili interessate dalle operazioni di 200ms, quindi l'200ms si potrebbe essere in grado di completare. Inoltre, dal momento che la monade STM è piuttosto rigida su cosa è permesso all'interno (solo accessi di memoria e calcoli puri!) È molto insolito avere una tale disparità tra la lunghezza delle transazioni; di solito, saranno solo poche memorie di lettura/scrittura e tutti gli IO e altri calcoli verranno eseguiti al di fuori della transazione.Inoltre, se una determinata transazione è mai bloccata per sempre da altre transazioni è un po 'un problema di programmazione; Non sono sicuro al 100% quale sia l'attuale scheduler di GHC, ma sembra plausibile che preferisca le transazioni più vecchie (o più alte).

Detto questo, il livelock è un problema molto reale con STM ed è quasi insidioso e difficile da ragionare come un deadlock nelle implementazioni di concomitanza con blocchi più tradizionali.

Come funziona TVar?

Probabilmente godrai di this paper.