Программная транзакционная память - пример компоновки - PullRequest
Новая
       19

Программная транзакционная память - пример компоновки

17 голосов
/ 02 апреля 2011

Одним из основных преимуществ программной транзакционной памяти, которое всегда упоминается, является возможность компоновки и модульность.Различные фрагменты могут быть объединены для получения более крупных компонентов.В программах, основанных на блокировке, это часто не так.

Я ищу простой пример, иллюстрирующий это с помощью реального кода.Я бы предпочел пример в Clojure, но с Хаскеллом тоже все в порядке.Бонусные баллы, если в примере также показан код на основе блокировки, который не может быть легко составлен.

Ответы [ 4 ]

20 голосов
/ 02 апреля 2011

Пример, когда блокировки не составляются в 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

6 голосов
/ 02 апреля 2011

Перевод примера 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 Операция атомарная, повторные попытки будут происходить при столкновениях при фиксации, вы можете добавить валидаторы для согласованности и т. Д.

И, конечно, семантика такова, что они никогда не будут тупиковыми.

5 голосов
/ 07 апреля 2011

Вот пример 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)

Обратите внимание, что все множественные переводы происходили в одной комбинированной транзакции, т. е. было возможно "составить" меньшие транзакции.

Чтобы сделать это с блокировками, это очень быстро усложнилось бы: если учесть, что учетные записи должны быть индивидуально заблокированы, вам нужно будет сделать что-то вроде установления протокола порядка получения блокировок, чтобы избежать взаимных блокировок.Как справедливо отмечает Джон, в некоторых случаях вы можете сделать это, отсортировав все блокировки в системе, но в большинстве сложных систем это невозможно.Сделать ошибку, которую трудно обнаружить, очень легко.СТМ спасает вас от всей этой боли.

2 голосов
/ 02 апреля 2011

И чтобы сделать пример trprcolin еще более идиоматичным, я бы предложил изменить порядок параметров в функции transact и сделать определения дебет и кредит более компактными. 

(defn- transact [f account amount]
    ....  )

(def debit  (partial transact -))
(def credit (partial transact +))
...