并发通用数据结构,没有死锁或资源不足

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 -> a)）（将其称为“modifyTVarCollection”）
• 返回 (atomically $ readTVar valueTVar) 作为“查询”结果
• 返回一个了解modifyTVarCollection的modifierFactory

ModifierFactory 会这样做：

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

工作线程将运行此循环：

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