Haskell中的读写锁

Question

我正在实现一个Web应用程序，将一些数据存储在内存中。一些请求读取此数据进行处理，而另一些请求则更新此数据。

在这种情况下，多个读取器可以同时操作数据，但编写器需要独占内存中的数据。我想要实现读者-写者锁来解决这个问题。我还希望等待锁的进程以FIFO顺序进行处理，以避免读取和写入饥饿。

Haskell标准库似乎没有提供这样的功能。我发现concurrency-extra提供了这个功能，但该库似乎没有维护（在LTS 3.22之后从stackage中删除），并且它的公平性属性对我来说不太清楚。

我觉得有点奇怪，在标准的Haskell库和stackage中没有读者-写者锁库 - 难道读者-写者模式在许多软件中不常见吗？或者在Haskell中是否有完全不同（也许是无锁）的方法？ 编辑：更精确地说，在公平性方面，当一个写者被阻塞等待获取锁时，后续的读锁请求应该只在写者获取并释放写锁之后才被允许 - 类似于MVar的公平性属性 - MVar具有FIFO属性。

- donatello

---

为什么不使用 Control.Concurrent.MVar（使用 takeMVar）？ - josejuan

我猜由于现在有了STM和TVar，一些更简单的锁形式就不再需要了。你可以使用TVar和STM，或者在MVar之上实现你的锁定。（后者看起来并不容易） - chi

@donatello，“在内存中保存一些数据”的意思是您的“内存数据”是不可变的，那么MVar操作就是原子操作；这是错误的吗？ - josejuan

您能详细说明一下“公平性”属性吗？通常通过“写偏向”实现来避免饥饿，就像这个例子：https://github.com/Yuras/qase/blob/master/lib/RWLock.hs 但是您对公平性的要求对我来说似乎不同。 - Yuras

“没有其他线程可以访问这些数据”，但是如果需要，可以使用readMVar(原子操作)进行读取，并使用takeMVar进行写入锁定（下一个读者将等待最终的写入操作）。我认为您应该澄清读/写关系（例如，写者不能释放“已更新”的数据，直到所有先前的读者使用了已读状态），但我认为MVar与您的最后一次编辑完美匹配。 - josejuan

Answer 1

在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?!"

我的主要关注点在于，首先这看起来有点过度设计，其次我们仍然没有办法确保STM的公平性（活跃性）。

我猜可以在MVars之上实现类似的库，尽管这会更加复杂，特别是如果我们想保证公平性。

我倾向于避免使用MVars，改用信号量，使用QSem来保证FIFO语义。利用这些，我们可以按照Dijkstra-style实现读者/写者问题。

- chi

---

是的，这并没有公平保证，但感谢您的实现。我现在对TVar不那么陌生了。 - donatello

Answer 2

实际上，concurrent-extra并不能提供公平性。

正如chi所写，STM无法保证公平性。但是我们可以在IO中使用STM来实现。思路是在chi的LockState中添加其他状态，指示读者无法获取锁：

data LockState = Writing | Reading Int | Waiting

然后，编写者应首先将状态设置为Waiting，然后等待所有读取器释放锁。请注意，等待应在单独的STM事务中执行，这就是为什么我们无法保证在STM中公平性的原因。

这里有一个示例实现Here：它不在Hackage上，但您可以将其压缩（它是BSD许可）。

该实现经过优化以最小化唤醒。使用单个TVar时，当锁处于Waiting状态时，每个读取器释放都会不必要地唤醒所有等待获取锁的读取器。因此，我有两个TVar，一个用于锁状态，另一个用于读取器数量。

添加：Here 这是我与IRC用户Cale关于读写锁实现陷阱的有趣（而且相当长）讨论。

- Yuras

---

谢谢您的回答，但我会选择MVar解决方案。 - donatello

Answer 3

最佳解决方案取决于读者/写者关系，但我认为您可以仅使用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个写入器开始工作 后续请求等待它，但1、2和3可以终止。

（此示例中的stdout输出和进程顺序不准确，但已读取或安装的项目数量显示真实顺序）

- josejuan

---

谢谢！这就是我需要的答案！ - donatello