软件事务内存 - 可组合性示例

Question

总是提到的软件事务存储器的主要优点之一是可组合性和模块性.可以组合不同的片段以产生更大的组分.在基于锁的程序中,通常情况并非如此.

我正在寻找一个用实际代码说明这一点的简单示例.我更喜欢Clojure中的一个例子,但Haskell也很好.如果该示例还展示了一些无法轻松编写的基于锁的代码,则会获得奖励积分.

Answer 1

锁在Java中不构成的示例:

class Account{
  float balance;
  synchronized void deposit(float amt){
    balance += amt;
  }
  synchronized void withdraw(float amt){
    if(balance < amt)
      throw new OutOfMoneyError();
    balance -= amt;
  }
  synchronized void transfer(Account other, float amt){
    other.withdraw(amt);
    this.deposit(amt);
  }
}

因此,存款是可以的,退出是可以的,但转移不合适:如果A开始转移到B,当B开始转移到A时,我们可能会遇到死锁情况.

现在在Haskell STM中:

withdraw :: TVar Int -> Int -> STM ()
withdraw acc n = do bal <- readTVar acc
                    if bal < n then retry
                    writeTVar acc (bal-n)

deposit :: TVar Int -> Int -> STM ()
deposit acc n = do bal <- readTVar acc
                   writeTVar acc (bal+n)

transfer :: TVar Int -> TVar Int -> Int -> STM ()
transfer from to n = do withdraw from n
                        deposit to n

因为没有明确的锁定,withdraw并deposit自然地构成transfer.语义仍然确保如果撤销失败,整个传输失败.它还确保撤销和存款将以原子方式完成,因为类型系统确保您不能在外部调用转移atomically.

atomically :: STM a -> IO a

这个例子来源于此: http://cseweb.ucsd.edu/classes/wi11/cse230/static/lec-stm-2x2.pdf 从本文改编,你可能需要阅读: http://research.microsoft.com /pubs/74063/beautiful.pdf

Answer 2

将Ptival的例子翻译成Clojure:

;; (def example-account (ref {:amount 100}))

(defn- transact [account f amount]
  (dosync (alter account update-in [:amount] f amount)))

(defn debit [account amount] (transact account - amount))
(defn credit [account amount] (transact account + amount))
(defn transfer [account-1 account-2 amount]
  (dosync
    (debit account-1 amount)
    (credit account-2 amount)))

因此,debit和credit的罚款对自己的呼叫,而像Haskell的版本,交易巢,因此整个transfer操作是原子,重试将发生在提交的碰撞,你可以添加的一致性验证等.

当然,语义是这样的,它们永远不会陷入僵局.

Answer 3

这是一个Clojure示例:

假设您有一个银行账户向量(在现实生活中,向量可能会更长一些......):

(def accounts 
 [(ref 0) 
  (ref 10) 
  (ref 20) 
  (ref 30)])

(map deref accounts)
=> (0 10 20 30)

还有一个"转移"功能,可以在一个交易中安全地转移两个账户之间的金额:

(defn transfer [src-account dest-account amount]
  (dosync
    (alter dest-account + amount)
    (alter src-account - amount)))

其工作原理如下:

(transfer (accounts 1) (accounts 0) 5)

(map deref accounts)
=> (5 5 20 30)

然后,您可以轻松地组合转移功能以创建更高级别的交易,例如从多个帐户转移:

(defn transfer-from-all [src-accounts dest-account amount]
  (dosync
    (doseq [src src-accounts] 
      (transfer src dest-account amount))))

(transfer-from-all 
  [(accounts 0) (accounts 1) (accounts 2)] 
  (accounts 3) 
  5)

(map deref accounts)
=> (0 0 15 45)

请注意,所有多次传输都发生在单个组合事务中,即可以"组合"较小的事务.

使用锁来执行此操作会很快变得复杂:假设需要单独锁定帐户,那么您需要执行诸如在锁获取顺序上建立协议以避免死锁的操作.正如Jon正确指出的那样,你可以在某些情况下通过对系统中的所有锁进行排序来实现这一点,但在大多数复杂系统中,这是不可行的.做出难以察觉的错误很容易.STM可以帮助您免受所有这些痛苦.