39

我最近问了一些关于 的问题TVar，但我仍然对活锁感到担忧。

于是我想到了这个结构：

  1. 每个事务都有一个唯一的优先级（可能按创建顺序分配）。
  2. 事务尝试获取它们访问的数据的读/写锁。自然，同时读取是可以的，但是一个写入锁会排除所有其他锁（读取和写入）。
  3. 假设事务 A 比事务 B 具有更高的优先级。如果 A 持有锁，B 等待，但如果 B 持有锁并且 A 想要它，则 B 从锁中启动，A 获得它，然后事务 B 重新启动（如 with TVar）。然而，B 保持其当前的重试优先级。
  4. 当一个锁被释放并且有事务在等待时，它会转到最高优先级的事务，其余的继续等待。

我相信这个系统可以防止死锁，但也可以防止饥饿（不像TVar）。我想知道是否有人实施了这样的系统，因为它似乎相当明显，我不想重新发明轮子。

当然，这种方法可以很容易地扩展为允许用户指定优先级。

Priority 可以是 pair (user_supplied_prio, auto_increment)，具有user_supplied_prio优先权，但同等优先级的任务按 FIFO 顺序解决。

评论/解决方案：

实际上，当我想到它时，我所描述的已经存在于 Haskell 中，只需使用一个IORef包裹所有数据的方法，并且仅使用atomicModifyIORef. 这atomicModifyIORef将确保按顺序应用事务。然而，有人可能会认为这意味着数据结构是顺序的（即实际上仅限于一个线程），但由于惰性，它实际上是并行的。

为了解释这一点，考虑一个昂贵的函数f。我们将把它应用到Data.Map键为“foo”的数据上。

这替换(foo -> x)为(foo -> future(f x)). 该线程将继续解决(f x)实际情况，但同时我们可以将 g 应用于“bar”。由于将g应用于“bar”不需要“foo”的结果，我们可以同时解决这个问题。

没有死锁，没有饥饿，最终所有事务都将被处理（大致按照它们被接收的顺序）。

4

1 回答 1

1

您可以设置一个工作线程以确定性方式处理所有请求，因此没有人会挨饿。这种策略将相当有效并且不受活锁的影响。 

-- yes, this is a horrible name
createManagerFactory :: a -> IO ((IO a), IO (((a -> a) -> IO a)))

IO a 是一种使用只读 STM 动作安全快速地查询值的动作。(a -> a) 是一个修改值的纯函数，因此 ((a -> a) -> IO a) 是一个接受修饰函数，安全地修改值并返回新值的动作。

运行一次以初始化工厂。 

(query, modifierFactory) <- createManagerVactory initValue

然后为每个线程运行它以生成一个新的修饰符。

myModify <- modifierFactory

createManagerFactory 将执行以下操作：

  • 创建一个包含 initValue 的 TVar（称之为 valueTVar）。
  • 创建一个包含一个空的 TVar 集合的 TVar (Either a (a -> a)) (称之为 modifyTVarCollection)
  • 返回（原子地 $ readTVar valueTVar）作为“查询”结果
  • 返回一个知道 modifyTVarCollection 的 modifierFactory

modifierFactory 会这样做：

  • 创建一个新的 TVar (Either a (a -> a)) (称之为 modifyTVar)，用 valueTVar 的当前值将其初始化为 (Left a)，并将其添加到 modifyTVarCollection
  • 返回一个修改器操作，在一个 STM 操作中将 (Right (a -> a)) 加载到 modifyTVar 中，然后在另一个 STM 操作中重试，直到 modifyTVar 包含 (Left a) 结果值，然后返回该值。

工作线程将运行此循环：

  • 在一个操作中，从 modifyTVarCollection 中获取所有查询 TVar，并检查它们的值。如果它们都包含 (Left a) 值，则重试（这将阻塞，直到某个其他线程使用修改器函数加载它们的 modifyTVar，或者修改器工厂创建了一个新的修改器TVar 并将其添加到集合中）。返回包含 Right (a -> a) 的所有 modifyTVars 的列表
  • 遍历所有返回的 modifyTVars。对于每个 TVar，执行读取修改函数的操作，安全地执行修改，并将结果作为 a（左 a）放回 modifyTVar
于 2012-09-06T04:22:01.717 回答