haskell - 并发通用数据结构，无死锁或资源匮乏

Question

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

所以我想到了这个结构:

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

我相信这个系统可以防止死锁，但也可以防止饥饿(与TVar不同)。我想知道是否有人实现了这样的系统，因为它看起来相当明显，而且我不想重新发明轮子。

当然，这种方法可以轻松扩展以允许用户指定优先级。

优先级可以是(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”的结果，因此我们可以同时解决这个问题。

没有死锁，没有饥饿，最终所有交易都将被处理(大致按照接收顺序)。

Answer 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 的空集合(可以是 (a-> a)) (将其称为“modifyTVarCollection”)
• 返回(原子$ readTVar valueTVar)作为“查询”结果
• 返回一个了解modifyTVarCollection的modifierFactory

modifierFactory 会这样做:

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

工作线程将运行此循环:

• 在一个操作中，从modifyTVarCollection 中获取所有查询TVar，并检查它们的值。如果它们都包含(左 a)值，则重试(这将阻塞，直到其他线程使用修饰符函数加载它们的modifyTVar，或者modifierFactory 创建一个新的modifierTVar 并将其添加到集合中)。返回包含Right (a -> a) 的所有modifyTVar 的列表
• 迭代所有返回的modifyTVar。对于每个 TVar，执行读取修改器函数的操作，安全地执行修改，并将结果作为(左 a)放回到修改TVar