2013-04-07 9 views
6

IORef s, MVar s e TVar s può essere utilizzato per avvolgere una variabile condivisa in un contesto concorrente. Ho studiato haskell concomitante per un po 'e ora ho riscontrato alcune domande. Dopo aver cercato su StackOverflow e aver letto alcune domande correlate, le mie domande non sono completamente risolte.Come utilizzare variabili condivise thread-safe in Haskell

  1. Secondo il IORefdocumentation, "Estrazione del atomicità a più IORefs è problematico", qualcuno può aiutare a spiegare il motivo per cui un singolo IORef è sicuro, ma più di un IORef s sono problematici?
  2. modifyMVar è "eccezionalmente sicuro, ma solo atomico se non ci sono altri produttori per questo MVar". Vedi MVar's documentation. Il codice sorgente mostra che modifyMVar compone solo un getMVar e putMVar in sequenza, a indicare che è nota la sicurezza del thread se c'è un altro produttore. Ma se non c'è nessun produttore e tutti i thread si comportano nel modo "takeMVar then putMVar", allora è thread-safe usare semplicemente modifyMVar?

Per dare una situazione concreta, mostrerò il problema reale. Ho alcune variabili condivise che non sono mai vuote e voglio che siano stati mutabili, quindi alcuni thread possono modificare contemporaneamente queste variabili.

OK, sembra che lo TVar risolva tutto chiaramente. Ma non sono soddisfatto e sono desideroso di risposte alle domande sopra. Qualsiasi aiuto è apprezzato.

-------------- Re: @GabrielGonzalez BFS codice di interfaccia ------------------

codice sotto è la mia interfaccia BFS usando la monade di stato.

{-# LANGUAGE TypeFamilies, FlexibleContexts #-} 

module Data.Graph.Par.Class where 

import Data.Ix 
import Data.Monoid 
import Control.Concurrent 
import Control.Concurrent.MVar 
import Control.Monad 
import Control.Monad.Trans.State 

class (Ix (Vertex g), Ord (Edge g), Ord (Path g)) => ParGraph g where 
    type Vertex g :: * 
    type Edge g :: * 
    -- type Path g :: *   -- useless 
    type VertexProperty g :: * 
    type EdgeProperty g :: * 
    edges :: g a -> IO [Edge g] 
    vertexes :: g a -> IO [Vertex g] 
    adjacencies :: g a -> Vertex g -> IO [Vertex g] 
    vertexProperty :: Vertex g -> g a -> IO (VertexProperty g) 
    edgeProperty :: Edge g -> g a -> IO (EdgeProperty g) 
    atomicModifyVertexProperty :: (VertexProperty g -> IO (VertexProperty g)) -> 
           Vertex g -> g a -> IO (g a) -- fixed 

spanForest :: ParGraph g => [Vertex g] -> StateT (g a) IO() 
spanForest roots = parallelise (map spanTree roots) -- parallel version 

spanForestSeq :: ParGraph g => [Vertex g] -> StateT (g a) IO() 
spanForestSeq roots = forM_ roots spanTree -- sequencial version 

spanTree :: ParGraph g => Vertex g -> StateT (g a) IO() 
spanTree root = spanTreeOneStep root >>= \res -> case res of 
    [] -> return() 
    adjs -> spanForestSeq adjs 

spanTreeOneStep :: ParGraph g => Vertex g -> StateT (g a) IO [Vertex g] 
spanTreeOneStep v = StateT $ \g -> adjacencies g v >>= \adjs -> return (adjs, g) 

parallelise :: (ParGraph g, Monoid b) => [StateT (g a) IO b] -> StateT (g a) IO b 
parallelise [] = return mempty 
parallelise ss = syncGraphOp $ map forkGraphOp ss 

forkGraphOp :: (ParGraph g, Monoid b) => StateT (g a) IO b -> StateT (g a) IO (MVar b) 
forkGraphOp t = do 
    s <- get 
    mv <- mapStateT (forkHelper s) t 
    return mv 
    where 
    forkHelper s x = do 
     mv <- newEmptyMVar 
     forkIO $ x >>= \(b, s) -> putMVar mv b 
     return (mv, s) 

syncGraphOp :: (ParGraph g, Monoid b) => [StateT (g a) IO (MVar b)] -> StateT (g a) IO b 
syncGraphOp [] = return mempty 
syncGraphOp ss = collectMVars ss >>= waitResults 
    where 
    collectMVars [] = return [] 
    collectMVars (x:xs) = do 
     mvx <- x 
     mvxs <- collectMVars xs 
     return (mvx:mvxs) 
    waitResults mvs = StateT $ \g -> forM mvs takeMVar >>= \res -> return ((mconcat res), g) 
+0

Perché non sei soddisfatto di 'TVar's? 'stm' è la soluzione elegante di Haskell per la concorrenza. Non ho mai incontrato un problema che non potessi risolvere utilizzando la memoria transazionale del software. –

+0

Non sono sicuro che "thread-safety" sia la parola appropriata nel parlare del comportamento di 'modifyMVar'; il tuo programma non segnerà o esploderà come in Python, ma otterrai solo eccezioni "bloccate indefinitamente" generate nei tuoi thread. – jberryman

+0

@GabrielGonzalez Immagino che l'implementazione di STM usando "log then commit" sia relativamente inefficiente e possa causare troppo overhead. Ma non ho paragonato l'efficienza quantitativa, però. – pysuxing

risposta

4
  1. processori moderni offrono un'istruzione compare-and-swap che modifica atomicamente un unico puntatore. Mi aspetto che se si rintraccia abbastanza in profondità, si scoprirà che questa istruzione è quella utilizzata per implementare atomicModifyIORef. È quindi semplice fornire l'accesso atomico a un singolo puntatore. Tuttavia, poiché non esiste un supporto hardware per più di un puntatore, tutto ciò che è necessario dovrà essere fatto nel software. Questo in genere comporta l'invenzione e l'applicazione manuale di un protocollo in tutti i thread, che è complicato e soggetto a errori.

  2. Sì, se tutti i thread accettano di utilizzare solo il comportamento "singolo takeMVar seguito da un singolo putMVar", quindi modifyMVar è sicuro.

+0

Grazie per la risposta! Non ho ancora rintracciato la tecnica di implementazione. Se l'atomicità è limitata dall'hardware, cosa succederà se uso più di uno 'IORef's e li condivido tra i thread? – pysuxing

+1

@pysuxing l'avvertenza "Estendere l'atomicità a più IORef è problematico" si riferisce alla difficoltà nel fare qualcosa come ad es. spostando atomicamente il totale da un contatore 'a :: IORef Int' a' b :: IORef Int' e impostando 'a' a zero. Non c'è modo (o nessun modo semplice?) Per assicurarsi che gli altri thread non vedano nessuno degli stati intermedi. – jberryman

+0

@jberryman Con l'esempio si intende che è impossibile comporre più di un'operazione 'IORef' in un'operazione atomica. Ma usare "IORef" mutiple nel contesto multi-threading senza comporre non causerà problemi, posso dirlo? – pysuxing