b***i
发帖数: 3043 | 1 看wiki，不懂，用lock怎么就不行了？
In 2005, Tim Harris, Simon Marlow, Simon Peyton Jones, and Maurice Herlihy
described an STM system built on Concurrent Haskell that enables arbitrary
atomic operations to be composed into larger atomic operations, a useful
concept impossible with lock-based programming. To quote the authors:
Perhaps the most fundamental objection [...] is that lock-based programs do
not compose: correct fragments may fail when combined. For example, consider
a hash table with thread-safe insert and delete operations. Now suppose
that we want to delete one item A from table t1, and insert it into table t2
; but the intermediate state (in which neither table contains the item) must
not be visible to other threads. Unless the implementor of the hash table
anticipates this need, there is simply no way to satisfy this requirement. [
...] In short, operations that are individually correct (insert, delete)
cannot be composed into larger correct operations.
—Tim Harris et al., "Composable Memory Transactions", Section 2: Background
, pg.2 |
t****t
发帖数: 6806 | 2 i didn't read the whole thing, but i guess you need to lock *both* hash-
table. usually that's not desirable, and if the lock order is incorrect, you
may get a dead-lock.
do
consider
t2
must
【在 b***i 的大作中提到】
: 看wiki，不懂，用lock怎么就不行了？
: In 2005, Tim Harris, Simon Marlow, Simon Peyton Jones, and Maurice Herlihy
: described an STM system built on Concurrent Haskell that enables arbitrary
: atomic operations to be composed into larger atomic operations, a useful
: concept impossible with lock-based programming. To quote the authors:
: Perhaps the most fundamental objection [...] is that lock-based programs do
: not compose: correct fragments may fail when combined. For example, consider
: a hash table with thread-safe insert and delete operations. Now suppose
: that we want to delete one item A from table t1, and insert it into table t2
: ; but the intermediate state (in which neither table contains the item) must
|
p*****2
发帖数: 21240 | |
a*****e
发帖数: 1700 | 4 这个例子简单说就是，如果使用 lock 机制提供了 atomic delete 和 atomic insert
两个操作，还是不足以保证两者的组合使用时 (e.g. delete x from A then insert
into B) 的正确性，必须暴露底层 delete 和 insert 的实现中所用到的 lock。也就
是说，使用 lock 是无法实现一个 clean composition 的，当 delete 和 insert 本
身的实现被修改时，原先正确的组合可能就变得不正确了。使用 STM 则有效的解决了
这个问题，而且可以引入灵活的组合方式。
do
consider
t2
must
【在 b***i 的大作中提到】
: 看wiki，不懂，用lock怎么就不行了？
: In 2005, Tim Harris, Simon Marlow, Simon Peyton Jones, and Maurice Herlihy
: described an STM system built on Concurrent Haskell that enables arbitrary
: atomic operations to be composed into larger atomic operations, a useful
: concept impossible with lock-based programming. To quote the authors:
: Perhaps the most fundamental objection [...] is that lock-based programs do
: not compose: correct fragments may fail when combined. For example, consider
: a hash table with thread-safe insert and delete operations. Now suppose
: that we want to delete one item A from table t1, and insert it into table t2
: ; but the intermediate state (in which neither table contains the item) must
|
f**********3
发帖数: 295 | 5 大牛再详细讲讲，如果
A.lock()
B.lock()
A.remove(x)
B.add(x)
B.unlock()
A.unlock()
会有问题吗？这和
atomic {
A.remove(x)
B.add(x)
}
效果是一样的吧？ 而且stm底下用的是Lock吗？
insert
【在 a*****e 的大作中提到】
: 这个例子简单说就是，如果使用 lock 机制提供了 atomic delete 和 atomic insert
: 两个操作，还是不足以保证两者的组合使用时 (e.g. delete x from A then insert
: into B) 的正确性，必须暴露底层 delete 和 insert 的实现中所用到的 lock。也就
: 是说，使用 lock 是无法实现一个 clean composition 的，当 delete 和 insert 本
: 身的实现被修改时，原先正确的组合可能就变得不正确了。使用 STM 则有效的解决了
: 这个问题，而且可以引入灵活的组合方式。
:
: do
: consider
: t2
|
p*****2
发帖数: 21240 | 6
用STM不需要用lock，所以可以大幅提高concurrency
【在 f**********3 的大作中提到】
: 大牛再详细讲讲，如果
: A.lock()
: B.lock()
: A.remove(x)
: B.add(x)
: B.unlock()
: A.unlock()
: 会有问题吗？这和
: atomic {
: A.remove(x)
|
a*****e
发帖数: 1700 | 7 你这段 psuedo code 正好说明 lock 机制不适合从小部件拼装组合大部件。比如这段
封装起来成一个函数 extract(x, A, B)，看似没问题吧？结果用户在不同的两个线程里
用到了 extract(x, a, b) 和 extract(y, b, a)，你就死锁啦！
而且 delete 和 insert 的具体实现也不一定非要 whole table lock 不可。
后面那个 atomic 的写法显然需要 global lock，正确性是有了，但是没效率。
【在 f**********3 的大作中提到】
: 大牛再详细讲讲，如果
: A.lock()
: B.lock()
: A.remove(x)
: B.add(x)
: B.unlock()
: A.unlock()
: 会有问题吗？这和
: atomic {
: A.remove(x)
|
a*****e
发帖数: 1700 | 8 STM 也有自己的问题，但是 composability 上绝对是强过 lock
【在 p*****2 的大作中提到】
:
: 用STM不需要用lock，所以可以大幅提高concurrency
|
m******t
发帖数: 635 | 9 最近打算用STM作点东西，能详细说说STM的问题吗？
【在 a*****e 的大作中提到】
: STM 也有自己的问题，但是 composability 上绝对是强过 lock
|
b***i
发帖数: 3043 | 10 感觉底层还是用了lock。那么，用STM，就不允许lock后单独修改数据了，必须都
atomic。否则，有的atomic,有的不用atomic,肯定不行，是不是？
就是在语法上简化了。
【在 a*****e 的大作中提到】
: STM 也有自己的问题，但是 composability 上绝对是强过 lock
|
a*****e
发帖数: 1700 | 11 语义上就限制了在 transaction 内部的 side effect 必须是 reversible，比如发个
packet出去就不行，只能 buffer 起来到 transaction 结束之后再做。
另外 When performance sucks, you don't know why.
Tuning STM programs for performance 比起 lock tuning 可能还要困难一些，当然
我没有什么第一手经验，道听途说的吧。
【在 m******t 的大作中提到】
: 最近打算用STM作点东西，能详细说说STM的问题吗？
|
a*****e
发帖数: 1700 | 12 底层用不用 lock 另说，但一定要支持 rollback。
和 lock 混用估计也是可以做到的，不过在 Haskell 里面，直接 STM monad 在类型上
就限制了 side effect 的种类，也不允许在 transaction 内部使用 lock。脱离开了
STM Monad，你在 transaction 外部使用什么都可以。
【在 b***i 的大作中提到】
: 感觉底层还是用了lock。那么，用STM，就不允许lock后单独修改数据了，必须都
: atomic。否则，有的atomic,有的不用atomic,肯定不行，是不是？
: 就是在语法上简化了。
|
b***i
发帖数: 3043 | 13 我的意思是,如果atomic里面进行对两个map的修改，然后我另一个thread不在atomic里
面对map修改，那肯定不行吧。所以atomic里面肯定还是使用了lock，才能保证atomic
。所谓rollback，就是说改完了一个map，发现无法获得第二个map的锁，所以rollback
，等下次再试。我猜是这样的。
了
【在 a*****e 的大作中提到】
: 底层用不用 lock 另说，但一定要支持 rollback。
: 和 lock 混用估计也是可以做到的，不过在 Haskell 里面，直接 STM monad 在类型上
: 就限制了 side effect 的种类，也不允许在 transaction 内部使用 lock。脱离开了
: STM Monad，你在 transaction 外部使用什么都可以。
|
p*****2
发帖数: 21240 | 14
atomic
rollback
应该是MVCC吧？
【在 b***i 的大作中提到】
: 我的意思是,如果atomic里面进行对两个map的修改，然后我另一个thread不在atomic里
: 面对map修改，那肯定不行吧。所以atomic里面肯定还是使用了lock，才能保证atomic
: 。所谓rollback，就是说改完了一个map，发现无法获得第二个map的锁，所以rollback
: ，等下次再试。我猜是这样的。
:
: 了
|
