Haskell的读者-作家锁
我正在实现一个web应用程序，它在内存中保存一些数据。一些请求读取这些数据以进行处理，而一些请求则更新这些数据。
在这种情况下，多个读取器可以同时对数据进行操作，但写入器需要对内存中的数据进行独占访问。我想实现一个读写器锁来解决这个问题。我还希望在锁上的服务生按照FIFO顺序处理公平性属性，以避免读写饥饿。
Haskell标准库似乎没有提供这样的功能。我发现concurrency-extra提供了这个功能，但是这个库似乎没有被维护(并且在LTS 3.22之后被从堆栈中删除)，而且它的公平性属性对我来说并不清楚。
我觉得有点奇怪，在标准的haskell库和堆栈中没有读写器锁库，这不是许多软件中常见的读写器模式吗？或者，在Haskell中，是否有一种完全不同(可能是无锁)的方法是可取的？
编辑：更准确地说，在公平性属性上，当写入器被阻止等待获取锁时，只有在写入器获得和释放写锁之后才允许后续的读锁请求--类似于MVar的公平性属性- S具有FIFO属性。
回答 3
Stack Overflow用户
发布于 2016-05-20 11:14:17
最好的解决方案取决于读者/作者之间的关系，但我认为您只能使用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当4 WRITER working begin下一次请求等待时，读取器1、2和3同时运行，但1、2和3可以终止。
(输入FIFO的输出和进程顺序在此示例中不准确，但读取或确定的项数显示了实际顺序)
Stack Overflow用户
发布于 2016-05-19 09:25:11
读写器锁很容易在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的基础上实现一个类似的库，尽管这会更复杂，特别是如果我们想要保证公平性。
我会倾向于避免使用MVar，而是使用信号量，而使用QSem，这可以保证FIFO语义。使用这些，我们可以用Dijkstra风格实现读者/作者。
Stack Overflow用户
发布于 2016-05-19 15:24:14
的确，concurrent-extra 不提供公平。
正如chi所写的那样，没有办法保证STM的公平性。但是我们可以在IO中使用STM。其想法是将其他状态添加到chi的LockState中，该状态指示读取器无法获取锁：
data LockState = Writing | Reading Int | Waiting然后，作者应该首先将状态设置为Waiting，然后等待所有读取器释放锁。注意，等待应该在单独的STM事务中执行，这就是为什么我们不能保证STM中的公平性。
这里是一个示例实现:它不是在Hackage上，但是您可以提供它(is是BSD许可的)。
对实现进行了优化，以尽量减少唤醒。对于单个TVar，当锁处于Waiting状态时，每个读取器释放不必要的唤醒所有等待获得锁的读取器。所以我有两个TVar，一个用于锁状态，另一个用于读取器的数量。
补充说：这里是我与IRC用户就读写锁实现的缺陷进行的一次有趣的(也是相当长的)讨论。
https://stackoverflow.com/questions/37318611
复制相似问题
腾讯云开发者
