Haskell:TVar是如何工作的？

Question

TVar如何运作？从我所看到的,它尝试在收到它们后立即运行所有事务,但是,事务完成使其他当前运行的事务无效,然后必须重新启动.这是TVar的工作原理吗？

如果是这种情况,如果每100ms发生1ms长的事务,这是否意味着需要200ms处理的事务永远不会完成？

Answer 1

只要两个事务访问不同TVars,它们都可以同时提交而不会相互失效.

只是要清楚,当一个交易是无效的,让我们考虑以下情形:

1. 假设它t :: TVar Int被初始化为0并readTVar t在事务开始时被读取A.
2. 同时,在另一个线程中,B开始writeTVar t 1执行a的事务.假设B之前提交A.STM系统将检查是否存在任何不一致,并断定B此时提交是安全的,因此现在writeTVar t 1变得有效.
3. 然而,这会导致交易A以来的旧值无效0的t在开始时被读取A.(如果A允许提交,我们会违反原子性.)

关于Haskell的STM系统的原始论文[1](见第6.5节)回答了你的问题:

"饥饿是可能的.例如,长时间运行的交易可能会反复与较短的交易发生冲突.我们认为在实践中不太可能发生饥饿,但如果没有进一步的经验我们就无法分辨."

[1] Tim Harris,Simon Marlow,Simon Peyton Jones和Maurice Herlihy.ACM 2005年并行编程原理与实践会议(PPoPP'05).

Answer 2

如果每100ms发生1ms长的事务,这是否意味着需要200ms处理的事务永远不会完成？

只有当触摸相同的TVars时,事务才会发生冲突,所以如果1ms事务中的某些事务避免了受200ms事务影响的所有变量,那么200ms就可以完成.此外,由于STMmonad对内部允许的内容(仅内存访问和纯计算!)非常严格,因此在事务长度之间存在这种差异是非常不寻常的.通常,它们只有几个内存读/写长,而且全部IO和其他计算将在交易之外完成.此外,特定事务是否永远被其他事务阻止是一个调度问题; 我不是100%确定GHC当前的调度程序是什么样的,但似乎有理由认为它优先考虑旧的(或更高的故障率)交易.

也就是说,livelock是一个非常真实的问题STM,并且在更传统的锁定并发实现中就像僵局一样难以理解为死锁.

TVar如何运作？

你可能会喜欢这篇论文.