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

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

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

4 ответа

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


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

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


Здесь пример Clojure:

Предположим, у вас есть вектор банковских счетов (в реальной жизни вектор может быть несколько длиннее....):

(def accounts 
 [(ref 0) 
 (ref 10) 
 (ref 20) 
 (ref 30)])
(map deref accounts)
=> (0 10 20 30)

И функция "transfer", которая безопасно передает сумму между двумя учетными записями в одной транзакции:

(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)

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

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


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

(defn- transact [f account amount]
 .... )
(def debit (partial transact -))
(def credit (partial transact +))

licensed under cc by-sa 3.0 with attribution.