主页 / coding / 问题 / 79584702
Accepted
Enlico
Asked: 2025-04-21 21:12:35 +0800 CST

澄清在并发环境下 MVar 内部状态不变性的重要性

  • 772

在Simon Marlow 所著的《Haskell 中的并行和并发编程》第 133 和 134 页中显示了以下代码：

type Name        = String
type PhoneNumber = String
type PhoneBook   = Map Name PhoneNumber

newtype PhoneBookState = PhoneBookState (MVar PhoneBook)

lookup :: PhoneBookState -> Name -> IO (Maybe PhoneNumber)
lookup (PhoneBookState m) name = do
  book <- takeMVar m
  putMVar m book
  return (Map.lookup name book)

下一页有一些观察。不过，第二段的最后部分让我有点困惑。以下是该段的前半部分：

在可变包装器中使用不可变数据结构还有其他好处。需要注意的是，在lookup操作中，我们只是获取了状态的当前值，然后复杂的操作在/序列Map.lookup之外进行。这对于并发性来说非常有利，因为这意味着锁只会被持有很短的时间。takeMVarputMVar

这对我来说相当清楚，因为我理解 会takeMVar锁定，然后putMVar立即释放，这样后续对 的并发访问PhoneBookState就不会再受到任何阻碍。同时，我还发现 可能会发生进一步的变异，所以当 以 为返回值MVar时，该对可能已经从映射中移除（或者，如果返回，则可能已经将一些对添加到映射中）。lookupJust smth(name, smth)Nothing(name, smth)

然而，我不明白该段接下来的部分想要表达什么：

这之所以可能，是因为状态的值是不可变的。如果数据结构是可变的，那么我们在操作它时就必须持有锁。⁵

⁵. 另一种选择是使用无锁算法，但这非常复杂，很难做到正确。

这是什么意思？作者指的是将某些 API 暴露给 mutated 的情况Map吗？除非我们在 中，否则这根本不可能，IO对吧？或者他指的是对 的内容执行的修改（由释放锁m后的其他线程执行）会以某种方式影响 的内容？putMVarbook

haskell

2 个回答

  1. Marlow 将 Haskell 的不可变数据方法与允许所有数据结构发生变异的语言进行了对比。

    在 Java 或 JavaScript 这样的语言中，仅仅锁定保存 的变量是不够的Map，因为可能有另一个线程已经获取了Map并正在修改它。因此，您需要在访问整个结构时锁定它。

    在 Haskell 中，我们已经知道 是Map不可变的。任何想要获取Map并修改 的操作都必须创建一个新值。因此，我们只需要锁定MVar保存 的Map，而不是整个Map（尽管如果您打算将修改后的映射写回原始映射MVar，则确实需要为整个操作保持锁定）。

    关于“无锁”结构的部分在这篇维基百科文章中有更详细的解释。简而言之，创建一棵有序树，多个线程可以修改树的内容而不会出错，这几乎是可能的。但这种结构的定义和证明是深奥的魔法，在正常的开发过程中不应该尝试。

    • 2
  2. Best Answer

    这里有一个完整的示例，或许能说明这个问题。如果我不想写一整套可变映射表的实现来回答这个问题，相信您也能理解。但请考虑以下简化的可变映射表，它只能存储一个键值对。它支持“新建”、“查找”和“替换”操作。（我将其命名为“替换”而不是“插入”，是因为该映射表只能存储一个键值对，因此插入新键值对时，之前的条目会丢失。）

    data MMap k v = MMap (IORef k) (IORef v)

mmapNew :: k -> v -> IO (MMap k v)
mmapNew k v = MMap <$> newIORef k <*> newIORef v

mmapReplace :: k -> v -> MMap k v -> IO ()
mmapReplace k v (MMap k_ v_) = do
  writeIORef k_ k
  writeIORef v_ v

mmapLookup :: (Eq k) => k -> MMap k v -> IO (Maybe v)
mmapLookup k (MMap k'_ v_) = do
  k' <- readIORef k'_
  if k == k'
    then Just <$> readIORef v_
    else pure Nothing

    现在，假设我们要使用这个可变数据结构编写一个线程安全的并发电话簿接口。修改后的代码lookup与原始代码大致相同：

    type Name = String
type PhoneNumber = String
type PhoneBook = MMap Name PhoneNumber
newtype PhoneBookState = PhoneBookState (MVar PhoneBook)

lookup :: PhoneBookState -> Name -> IO (Maybe PhoneNumber)
lookup (PhoneBookState m) name = do
  book <- takeMVar m
  putMVar m book
  mmapLookup name book   -- no `return`, because this is an IO operation

    mmapLookup我们在解锁状态后执行实际操作。

    new和 的对应 API 代码replace大概是这样的：

    new :: Name -> PhoneNumber -> IO PhoneBookState
new name number = do
  book <- mmapNew name number
  PhoneBookState <$> newMVar book

replace :: PhoneBookState -> Name -> PhoneNumber -> IO ()
replace (PhoneBookState m) name number = do
  book <- takeMVar m
  mmapReplace name number book
  putMVar m book

    请注意，与 不同lookup，我们对 采取了保守的方法replace，在整个替换操作过程中保持锁定。

    lookup然而，这个实现对于/对存在竞争条件replace。为了明白原因，我们来给 添加一个延迟mmapLookup：

    mmapLookup :: (Eq k) => k -> MMap k v -> IO (Maybe v)
mmapLookup k (MMap k'_ v_) = do
  k' <- readIORef k'_
  threadDelay 2000000
  if k == k'
    then Just <$> readIORef v_
    else pure Nothing

    并考虑以下main函数，它为“Alice”的电话号码创建电话簿，然后启动两个线程 - 一个用于查找“Alice”，另一个用于用“Bob”的号码替换条目：

    main = do
  pbs <- new "Alice" "555-1234"
  forkIO $ do
    aliceno <- lookup pbs "Alice"
    putStrLn $ "Alice's number is " ++ show aliceno
  threadDelay 1000000
  forkIO $ replace pbs "Bob" "555-9876"
  threadDelay 5000000
  putStrLn "Done!"

    当此程序运行时，它会在查找 Alice 时错误地检索 Bob 的号码：

    Alice's number is Just "555-9876"
Done!

    显然，问题在于替换操作发生在键的比较和值的检索之间。

    如果您修改lookup为仅在查找完成后才释放锁：

    lookup :: PhoneBookState -> Name -> IO (Maybe PhoneNumber)
lookup (PhoneBookState m) name = do
  book <- takeMVar m
  number <- mmapLookup name book
  putMVar m book
  return number

    那么就不会出现竞争条件。无论你如何交错操作（也无论你如何精心设置延迟），你要么Just "555-1234"会从原始电话簿中检索到 Alice 的号码，要么无法检索到 Alice 的号码，并Nothing从修改后的电话簿中返回（其中 Alice 的号码已被 Bob 的号码替换）。

    因此，对于可变的MMap，我们必须持有操作的锁mmapLookup，以便安全地操作数据结构，而不允许任何其他线程在我们执行时修改数据结构lookup。

    相反，如果我们使用类似的不可变数据结构：

    data IMap k v = IMap k v

imapNew :: k -> v -> IMap k v
imapNew k v = IMap k v

imapReplace :: k -> v -> IMap k v -> IMap k v
imapReplace k v _ = IMap k v

imapLookup :: (Eq k) => k -> IMap k v -> Maybe v
imapLookup k (IMap k' v) | k == k' = Just v
                         | otherwise = Nothing


type Name = String
type PhoneNumber = String
type PhoneBook = IMap Name PhoneNumber
newtype PhoneBookState = PhoneBookState (MVar PhoneBook)

    new那么，，lookup和的相应实现replace将是：

    new :: Name -> PhoneNumber -> IO PhoneBookState
new name number = PhoneBookState <$> newMVar (imapNew name number)

lookup :: PhoneBookState -> Name -> IO (Maybe PhoneNumber)
lookup (PhoneBookState m) name = do
  book <- takeMVar m
  putMVar m book
  return $ imapLookup name book

replace :: PhoneBookState -> Name -> PhoneNumber -> IO ()
replace (PhoneBookState m) name number = do
  book <- takeMVar m
  let book' = imapReplace name number book
  putMVar m book'

    至关重要的是，当从 中取出replace时，它很可能与中的调用并发访问的相同，它不会改变自身，而是通过调用创建一个新的，而不会影响原始的。这就是不可变数据结构的本质，也是为什么操作可以安全地继续在未修改的 上运行，即使创建新的并将其写回到空的 中也是如此。bookMVarbookimapLookuplookupbookbook'imapReplacebookimapLookupbookreplacebook'MVar

    即使我们不遗余力地将其重写imapLookup为一个IO操作，也有足够的机会让另一个线程在键和值访问之间运行：

    imapLookup :: (Eq k) => k -> IMap k v -> IO (Maybe v)
imapLookup k m = do
  k' <- evaluate $ (\(IMap k v) -> k) m    -- force retrieval of the key
  threadDelay 1000000                      -- allow another thread to run
  v' <- evaluate $ (\(IMap k v) -> v) m    -- fetch the value
  pure $ if k == k' then Just v' else Nothing

    我们仍然不会触发竞争条件，因为book :: IMap k v被访问imapLookup name book是不可变的，无论它在其他线程中如何被访问。

    以下是使用可变结构说明竞争条件的完整示例MMap：

    import Prelude hiding (lookup)
import Data.IORef
import Control.Concurrent

data MMap k v = MMap (IORef k) (IORef v)

mmapNew :: k -> v -> IO (MMap k v)
mmapNew k v = MMap <$> newIORef k <*> newIORef v

mmapReplace :: k -> v -> MMap k v -> IO ()
mmapReplace k v (MMap k_ v_) = do
  writeIORef k_ k
  writeIORef v_ v

mmapLookup :: (Eq k) => k -> MMap k v -> IO (Maybe v)
mmapLookup k (MMap k'_ v_) = do
  k' <- readIORef k'_
  threadDelay 2000000  -- allow another thread to do mischief
  if k == k'
    then Just <$> readIORef v_
    else pure Nothing

type Name = String
type PhoneNumber = String
type PhoneBook = MMap Name PhoneNumber
newtype PhoneBookState = PhoneBookState (MVar PhoneBook)

new :: Name -> PhoneNumber -> IO PhoneBookState
new name number = do
  book <- mmapNew name number
  PhoneBookState <$> newMVar book

lookup :: PhoneBookState -> Name -> IO (Maybe PhoneNumber)
lookup (PhoneBookState m) name = do
  book <- takeMVar m
  putMVar m book
  mmapLookup name book

replace :: PhoneBookState -> Name -> PhoneNumber -> IO ()
replace (PhoneBookState m) name number = do
  book <- takeMVar m
  mmapReplace name number book
  putMVar m book

main = do
  pbs <- new "Alice" "555-1234"
  forkIO $ do
    aliceno <- lookup pbs "Alice"
    putStrLn $ "Alice's number is " ++ show aliceno
  threadDelay 1000000
  forkIO $ replace pbs "Bob" "555-9876"
  threadDelay 2000000  -- wait for children to finish
  putStrLn "Done!"

    以及没有竞争条件的不可变版本：

    module ImmutableMap where

import qualified Data.Map as Map
import Prelude hiding (lookup)
import Control.Concurrent
import Control.Exception

data IMap k v = IMap k v

imapNew :: k -> v -> IMap k v
imapNew k v = IMap k v

imapReplace :: k -> v -> IMap k v -> IMap k v
imapReplace k v _ = IMap k v

imapLookup :: (Eq k) => k -> IMap k v -> IO (Maybe v)
imapLookup k m = do
  k' <- evaluate $ (\(IMap k v) -> k) m    -- force retrieval of the key
  threadDelay 1000000                      -- allow another thread to run
  v' <- evaluate $ (\(IMap k v) -> v) m    -- fetch the value
  pure $ if k == k' then Just v' else Nothing

type Name = String
type PhoneNumber = String
type PhoneBook = IMap Name PhoneNumber
newtype PhoneBookState = PhoneBookState (MVar PhoneBook)

new :: Name -> PhoneNumber -> IO PhoneBookState
new name number = PhoneBookState <$> newMVar (imapNew name number)

lookup :: PhoneBookState -> Name -> IO (Maybe PhoneNumber)
lookup (PhoneBookState m) name = do
  book <- takeMVar m
  putMVar m book
  imapLookup name book

replace :: PhoneBookState -> Name -> PhoneNumber -> IO ()
replace (PhoneBookState m) name number = do
  book <- takeMVar m
  let book' = imapReplace name number book
  putMVar m book'

main = do
  pbs <- new "Alice" "555-1234"
  forkIO $ do
    aliceno <- lookup pbs "Alice"
    putStrLn $ "Alice's number is " ++ show aliceno
  threadDelay 1000000
  forkIO $ replace pbs "Bob" "555-9876"
  threadDelay 2000000  -- wait for children to finish
  putStrLn "Done!"
    • 2

相关问题