[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
SlideShare a Scribd company logo

ClojureではじめるSTM入門

•
•
S
sohta
1 of 49
Downloaded 27 times
ClojureではじめるSTM入門 @athos0220 並列/並行基礎勉強会
自己紹介 @athos0220 趣味でClojure触ってます 正直STMとかまともに使ったことないわー 付け焼刃に勉強したので間違ってるところあ るかも(´・ω・`) →生温かくご指摘お願いします
What’s STM?
STMとは Software Transactional Memory ソフトウェアトランザクショナルメモリは、データベーストラン ザクションに似た並行性制御機構であり、並列計算を行う際の 共有メモリへのアクセス法である。 この機構はロックベースの同期を用いた並行性制御の代替手段と して機能し、ノンブロッキングな方法で実装される物もある。 Wikipediaより 楽観的： 他のスレッドを気にせずとりあえず実行してみる 変なことになったらリトライする 最近盛んに研究されている(らしい)
ロックの利点と欠点 利点 いつロックを取得し、解除するかを陽に制御できる 開発者にとって馴染みがある方法 多くのプログラミング言語でサポートされている 欠点 ロックのとる順序によってデッドロックが起こる 優先度逆転が起こる composableでない
STMの利点と欠点 利点 デッドロックや優先度逆転が起きない 楽観的なので並行性が向上する composableである(ネストできる) 欠点 リトライが頻発することでパフォーマンスが悪くなる 余分なオーバーヘッドがかかる トランザクション内では副作用を避ける必要がある
各言語での対応状況 言語(処理系)組込み Clojure, Haskell, Perl6(Pugs) ライブラリ C, C++, C#, Common Lisp, Java, OCaml, Python, Scala, Smalltalk どの入門書にもSTMの解説があるのはClojure だけ
How to use STM in Clojure
STMの基本構文・関数 (dosync <body>)：<body>をトランザクションで 実行 (ref <val>)：トランザクション内で変更が可能な 参照(Ref型)を生成 (deref <ref>)：Refにくるまれた値をデリファレ ンス。@<ref>は糖衣構文 (ref-set <ref> <val>)：Refの値を変更する。 dosyncの外で使うとエラーになる
STMを使ったコード (def counter (ref 42)) counter 42 Thread A Thread B (dosync (dosync (let [v @counter] (let [v @counter] (when (<= v 100) (when (<= v 100) (ref-set counter (ref-set counter (inc v))))) (inc v)))))
STMを使ったコード (def counter (ref 42)) counter 42 Thread A Thread B (dosync (dosync (let [v @counter] (let [v @counter] (when (<= v 100) (when (<= v 100) (ref-set counter (ref-set counter (inc v))))) (inc v)))))
STMを使ったコード (def counter (ref 42)) counter 42 Thread A Thread B (dosync (dosync (let [v @counter] (let [v @counter] (when (<= v 100) (when (<= v 100) (ref-set counter (ref-set counter (inc v))))) (inc v))))) 42
STMを使ったコード (def counter (ref 42)) counter 42 Thread A Thread B (dosync (dosync (let [v @counter] (let [v @counter] (when (<= v 100) (when (<= v 100) (ref-set counter (ref-set counter (inc v))))) (inc v))))) 42 42
STMを使ったコード (def counter (ref 42)) counter 42 Thread A Thread B (dosync (dosync (let [v @counter] (let [v @counter] (when (<= v 100) (when (<= v 100) (ref-set counter (ref-set counter (inc v))))) (inc v))))) 43 42
STMを使ったコード (def counter (ref 42)) counter 42 Thread A Thread B (dosync (dosync (let [v @counter] (let [v @counter] (when (<= v 100) (when (<= v 100) (ref-set counter (ref-set counter (inc v))))) (inc v))))) 43 この時点の変更はBからは見えない 42
STMを使ったコード (def counter (ref 42)) counter 42 Thread A Thread B (dosync (dosync (let [v @counter] (let [v @counter] (when (<= v 100) (when (<= v 100) (ref-set counter (ref-set counter (inc v))))) (inc v))))) 43 42
STMを使ったコード (def counter (ref 42)) counter 42 Thread A Thread B (dosync (dosync (let [v @counter] (let [v @counter] (when (<= v 100) (when (<= v 100) (ref-set counter (ref-set counter (inc v))))) (inc v))))) 43 他で値が変更されていなければコミット 42
STMを使ったコード (def counter (ref 42)) counter 43 Thread A Thread B (dosync (dosync (let [v @counter] (let [v @counter] (when (<= v 100) (when (<= v 100) (ref-set counter (ref-set counter (inc v))))) (inc v))))) 43 コミット！ 42
STMを使ったコード (def counter (ref 42)) counter 43 Thread A Thread B (dosync (dosync (let [v @counter] (let [v @counter] (when (<= v 100) (when (<= v 100) (ref-set counter (ref-set counter (inc v))))) (inc v))))) 42
STMを使ったコード (def counter (ref 42)) counter 43 Thread A Thread B (dosync (dosync (let [v @counter] (let [v @counter] (when (<= v 100) (when (<= v 100) (ref-set counter (ref-set counter (inc v))))) (inc v))))) 43
STMを使ったコード (def counter (ref 42)) counter 43 Thread A Thread B (dosync (dosync (let [v @counter] (let [v @counter] (when (<= v 100) (when (<= v 100) (ref-set counter (ref-set counter (inc v))))) (inc v))))) 43
STMを使ったコード (def counter (ref 42)) counter 43 Thread A Thread B (dosync (dosync (let [v @counter] (let [v @counter] (when (<= v 100) (when (<= v 100) (ref-set counter (ref-set counter (inc v))))) (inc v))))) Aが値を変更したので失敗 43
STMを使ったコード (def counter (ref 42)) counter 43 Thread A Thread B (dosync (dosync (let [v @counter] (let [v @counter] (when (<= v 100) (when (<= v 100) (ref-set counter (ref-set counter (inc v))))) (inc v))))) トランザクションを最初からやり直す 43
STMを使ったコード (def counter (ref 42)) counter 43 Thread A Thread B (dosync (dosync (let [v @counter] (let [v @counter] (when (<= v 100) (when (<= v 100) (ref-set counter (ref-set counter (inc v))))) (inc v))))) 43
STMを使ったコード (def counter (ref 42)) counter 43 Thread A Thread B (dosync (dosync (let [v @counter] (let [v @counter] (when (<= v 100) (when (<= v 100) (ref-set counter (ref-set counter (inc v))))) (inc v))))) 43
STMを使ったコード (def counter (ref 42)) counter 43 Thread A Thread B (dosync (dosync (let [v @counter] (let [v @counter] (when (<= v 100) (when (<= v 100) (ref-set counter (ref-set counter (inc v))))) (inc v))))) 44
STMを使ったコード (def counter (ref 42)) counter 43 Thread A Thread B (dosync (dosync (let [v @counter] (let [v @counter] (when (<= v 100) (when (<= v 100) (ref-set counter (ref-set counter (inc v))))) (inc v))))) 44
STMを使ったコード (def counter (ref 42)) counter 44 Thread A Thread B (dosync (dosync (let [v @counter] (let [v @counter] (when (<= v 100) (when (<= v 100) (ref-set counter (ref-set counter (inc v))))) (inc v))))) コミット！ 44
ClojureのSTM観 Thread A Thread B a ... @a ... ... (ref-set a ...) ... ... (ref-set b ...) ... b ... (ref-set b ...) ... ... (ref-set c ...) ... c トランザクションは更新するRefを集めていく 途中で他のトランザクションが手を出しているRefに触ったらアボート →リトライ すべてのRefを集めて最後まで行ければゴール→コミット
ClojureのSTM観 Thread A Thread B a ... @a ... ... (ref-set a ...) ... ... (ref-set b ...) ... b ... (ref-set b ...) ... ... (ref-set c ...) ... c トランザクションは更新するRefを集めていく 途中で他のトランザクションが手を出しているRefに触ったらアボート →リトライ すべてのRefを集めて最後まで行ければゴール→コミット writeが多いとリトライが頻発して性能低下
Under the hood of STM
Version Clock すべてのトランザクションで共有するクロック トランザクションの開始やリトライ、コミット のたびにインクリメントされる 各トランザクションは自分が開始されたときの クロックの値を記録する コミット時にはそのときのクロックの値をRefに 記録する
Ref いわゆるAtomic Object 主に以下で構成されている 値の履歴をもつリングバッファ ref-setしたが未コミットのトランザクション Refを参照・更新する際に使われるロック
in-transaction values トランザクション内でアクセスしたRefとその値 をローカルに記録する Refを更新するときはローカルな値を更新する Refから値を読み出すとき、 ローカルな値があればそれを読み出す なければ、Refの履歴をたどってトランザ クション開始以前の値を読み出す
MVCC 多版型同時実行制御 (Multiversion Concurrency Control) トランザクションの実行中、他のトランザクションが既に 更新した値を読み出すと一貫性がなくなる これを防ぐには以下のような方法がある(2つめがMVCC) 他が更新済みの値を読み出そうとした時点でアボート してリトライ 値の履歴をとっておいて、トランザクション開始時ま で って値を読み出す 1つめの方法はリトライの可能性が高くなる
write skew MVCCで起こる現象 複数のトランザクション間で不変条件を破るような変更が行 われたときに発生 不変条件 @a + @b <= 3 Thread A Thread B (dosync (dosync (when (<= (+ @a @b) 2) (when (<= (+ @a @b) 2) (ref-set a (inc a)))) (ref-set b (inc b))))
write skew MVCCで起こる現象 複数のトランザクション間で不変条件を破るような変更が行 われたときに発生 不変条件 @a + @b <= 3 Thread A Thread B (dosync (dosync (when (<= (+ @a @b) 2) (when (<= (+ @a @b) 2) (ref-set a (inc a)))) (ref-set b (inc b)))) AとBで違うRefを変更しているので両者ともコミットに成功する コミット後、不変条件は成り立たなくなる
ensure write skewの問題は、暗に存在する「コミットする まで変更されない」という条件が破られるために発 生する Clojureでは (ensure <ref>) で、それ以降コミットが 完了するまで<ref>が変更されないことを保証する Thread A Thread B (dosync (dosync (when (<= (+ @a @b) 2) (when (<= (+ @a @b) 2) (ensure b) (ensure a) (ref-set a (inc a)))) (ref-set b (inc b)))) ensureしているRefが他方に変更されればリトライ
Contention management Thread A Thread B a ... @a ... ... (ref-set a ...) ... ... (ref-set b ...) ... b ... (ref-set b ...) ... ... (ref-set c ...) ... c
Contention management Thread A Thread B a ... @a ... ... (ref-set a ...) ... ... (ref-set b ...) ... b ... (ref-set b ...) ... ... (ref-set c ...) ... c 2つのトランザクションが同じRefをつかもうとしたとき、どちら を生かし、どちらをアボートするか？
Contention management Thread A Thread B a ... @a ... ... (ref-set a ...) ... ... (ref-set b ...) ... b ... (ref-set b ...) ... ... (ref-set c ...) ... c 2つのトランザクションが同じRefをつかもうとしたとき、どちら を生かし、どちらをアボートするか？ 戦略次第で性能が大きく左右される
Contention managementの戦略
Contention managementの戦略 Agressive: 相手を殺す
Contention managementの戦略 Agressive: 相手を殺す Polite: 自分が死ぬ
Contention managementの戦略 Agressive: 相手を殺す Polite: 自分が死ぬ Karma: あまり仕事をしていない方が死ぬ
Contention managementの戦略 Agressive: 相手を殺す Polite: 自分が死ぬ Karma: あまり仕事をしていない方が死ぬ Priority: 年功序列。若いやつが死ぬ
Contention managementの戦略 Agressive: 相手を殺す Polite: 自分が死ぬ Karma: あまり仕事をしていない方が死ぬ Priority: 年功序列。若いやつが死ぬ ClojureのContention managementはPriority＋α
まとめ ロックを使って同期するのは辛い STM！STM！ Clojureなら初心者でもSTM使えます ただし、writeが多いと性能低下するなど、問題 点もある → 銀の弾丸ではない しかし、将来的にはGCのように適用範囲は広 がっていくのでは…？
参考文献 M. Herlihy and N. Shavit. “The Art of Multiprocessor Programming, Revised Reprint.” Morgan Kaufmann Publishers Inc. 2012 M. Fogus and C. Houser, “The Joy of Clojure.” Manning Pubns Co. 2011 Nielsen, Peder RL, and Patrick T. Kristiansen. "Benchmarking Contention Management Strategies in Clojure’s Software." Artificial Intelligence 8.3 (1977): 323-364. R. Mark Volkmann. “Software Transactional Memory.” http:// java.ociweb.com/mark/stm/article.html

More Related Content

ClojureではじめるSTM入門