2

メモリにデータを保持する Web アプリを実装しています。一部のリクエストは処理のためにこのデータを読み取り、一部のリクエストはこのデータを更新します。

このシナリオでは、複数のリーダーが同時にデータを操作できますが、ライターはメモリ内のデータに排他的にアクセスする必要があります。この問題を解決するために、リーダー/ライター ロックを実装したいと考えています。また、読み取りと書き込みの枯渇を回避するために、ロックの待機者が FIFO の順序で処理されるという公平性のプロパティも必要です。

Haskell 標準ライブラリは、そのような機能を提供していないようです。この機能を提供することがわかりましconcurrency-extraたが、ライブラリは維持されていないようです (LTS 3.22 の後にスタックから削除されました)。また、その公平性のプロパティは明確ではありません。

標準の haskell ライブラリとスタックにリーダー/ライター ロック ライブラリがないことは少し驚くべきことです。リーダー/ライター パターンは多くのソフトウェアで一般的ではありませんか? それとも、Haskell で好まれるまったく異なる (おそらくロックフリーの) アプローチはありますか?

EDIT :より正確には、公平性プロパティについて、ライターがロックの取得を待機してブロックされている場合、後続の読み取りロック要求は、ライターが書き込みロックを取得して解放した後にのみ許可する必要がありMVarます - s 公平性プロパティと同様 - MVars には FIFO があります財産

4

3 に答える 3

3

リーダー/ライター ロックは、STM の上に簡単に実装できます。

data LockState = Writing | Reading Int
type Lock = TVar LockState

startReading :: Lock -> STM ()
startReading lock = do
   s <- readTVar lock
   case s of
      Writing -> retry
      Reading n -> writeTVar (Reading (succ n))


stopReading :: Lock -> STM ()
stopReading lock = do
   s <- readTVar lock
   case s of
      Writing -> error "stopReading: lock in writing state?!"
      Reading n -> writeTVar (Reading (pred n))


startWriting :: Lock -> STM ()
startWriting lock = do
   s <- readTVar lock
   case s of
      Reading 0 -> writeTVar Writing
      _         -> retry

stopWriting :: Lock -> STM ()
stopWriting lock = do
   s <- readTVar lock
   case s of
      Writing -> writeTVar lock (Reading 0)
      _       -> error "stopwriting: lock in non-writing state?!"

上記に関する私の主な懸念は、1) ちょっとやり過ぎに見えること、2) STM で公平性 (ライブ性) を保証する方法がまだないことです。

MVar特に公平性を保証したい場合は、より複雑になりますが、 s の上に同様のライブラリを実装できると思います。

FIFO セマンティクスを保証するMVars を避け、代わりにセマフォを使用したくなるでしょう。QSemそれらを使用して、ダイクストラ スタイルでリーダー/ライターを実装できます。

于 2016-05-19T09:25:11.080 に答える
1

最適な解決策はリーダー/ライターの関係に依存しますが、を使用するだけで問題を解決できると思いますMVar。

させて

import System.Clock
import Text.Printf
import Control.Monad
import Control.Concurrent
import Control.Concurrent.MVar

t__ :: Int -> String -> IO ()
t__ id msg = do
    TimeSpec s n <- getTime Realtime
    putStrLn $ printf "%3d.%-3d - %d %s" (s `mod` 1000) n id msg

reader :: MVar [Int] -> Int -> IO ()
reader mv id = do
    t__                            id $ "reader waiting"
    xs <- readMVar mv
    t__                            id $ "reader working begin"
    threadDelay (1 * 10^6)
    t__                            id $ "reader working ends, " ++ show (length xs) ++ " items"

writer :: MVar [Int] -> Int -> IO ()
writer mv id = do
    t__                            id $ "WRITER waiting"
    xs <- takeMVar mv
    t__                            id $ "WRITER working begin"
    threadDelay (3 * 10^6)
    t__                            id $ "WRITER working ends, " ++ show (1 + length xs) ++ " items"
    putMVar mv (id: xs)

main = do

    mv <- newMVar []
    forM_ (take 10 $ zipWith (\f id -> forkIO (f mv id)) (cycle [reader, reader, reader, writer]) [1..]) $ \p -> do
        threadDelay (10^5)
        p

    getLine

出力あり

c:\tmp>mvar.exe +RTS -N20
486.306991300 - 1 reader waiting
486.306991300 - 1 reader working begin
486.416036100 - 2 reader waiting
486.416036100 - 2 reader working begin
486.525191000 - 3 reader waiting
486.525191000 - 3 reader working begin
486.634286500 - 4 WRITER waiting
486.634286500 - 4 WRITER working begin
486.743378400 - 5 reader waiting
486.852406800 - 6 reader waiting
486.961564300 - 7 reader waiting
487.070645900 - 8 WRITER waiting
487.179673900 - 9 reader waiting
487.288845100 - 10 reader waiting
487.320003300 - 1 reader working ends, 0 items
487.429028600 - 2 reader working ends, 0 items
487.538202000 - 3 reader working ends, 0 items
489.642147400 - 10 reader working begin
489.642147400 - 4 WRITER working ends, 1 items
489.642147400 - 5 reader working begin
489.642147400 - 6 reader working begin
489.642147400 - 7 reader working begin
489.642147400 - 8 WRITER working begin
489.642147400 - 9 reader working begin
490.655157400 - 10 reader working ends, 1 items
490.670730800 - 6 reader working ends, 1 items
490.670730800 - 7 reader working ends, 1 items
490.670730800 - 9 reader working ends, 1 items
490.686247400 - 5 reader working ends, 1 items
492.681178800 - 8 WRITER working ends, 2 items

リーダー 1、2、および 3 は同時に実行され、4 WRITER working begin次の要求がそれを待機しますが、1、2、および 3 は終了する可能性があります。

(この例では、stdout の出力と FIFO に入るプロセスの順序は正確ではありませんが、読み取られた、または決済されたアイテムの数は実際の順序を示しています)

于 2016-05-20T11:14:17.043 に答える