8

IORefs、MVars、およびTVars を使用して、同時コンテキストで共有変数をラップできます。私はしばらくの間並行ハスケルを研究してきましたが、今ではいくつかの質問に遭遇しました。stackoverflow を検索して関連する質問を読んだ後、私の質問は完全には解決されていません。

  1. IORef ドキュメント「Extending the atomity to multiple IORefs is problem」によると、単一の IORefIORefが安全であるのに複数IORefの s が問題である理由を誰かが説明してくれますか?
  2. modifyMVar「例外セーフですが、このMVarの他のプロデューサーがない場合にのみアトミックです」。MVarのドキュメントを参照してください。ソース コードは、 andmodifyMVarのみを順次に構成することを示しており、別のプロデューサーが存在する場合にスレッド セーフではないことを示しています。しかし、プロデューサーがなく、すべてのスレッドが " then " のように動作する場合、単純に を使用するのはスレッドセーフですか?getMVarputMVartakeMVarputMVarmodifyMVar

具体的な状況を示すために、実際の問題を示します。空にならない共有変数がいくつかあり、それらを変更可能な状態にして、一部のスレッドがこれらの変数を同時に変更できるようにします。

OK、TVarすべてが明確に解決されたようです。しかし、私はそれに満足しておらず、上記の質問への回答を熱望しています. どんな助けでも大歓迎です。

-------------- re: @GabrielGonzalez BFS インターフェイス コード ------------------

以下のコードは、状態モナドを使用した私の BFS インターフェイスです。

{-# 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)
4

1 に答える 1

5

  1. 最新のプロセッサは、単一のポインターをアトミックに変更するコンペア アンド スワップ命令を提供します。十分に深く追跡すれば、この命令が実装に使用される命令であることがわかると思いますatomicModifyIORef。したがって、単一のポインターへのアトミック アクセスを提供するのは簡単です。ただし、複数のポインターに対するハードウェア サポートがないため、必要なことはすべてソフトウェアで行う必要があります。これには通常、すべてのスレッドでプロトコルを考案して手動で適用する必要がありますが、これは複雑でエラーが発生しやすいものです。

  2. はい、すべてのスレッドが「単一のtakeMVar後に単一が続くputMVar」動作のみを使用することに同意する場合、modifyMVar安全です。

于 2013-04-07T01:37:55.713 に答える