2008/02 STMの紹介
- 1. An Introduction to Software Transactional Memory 【見覚え】 小林浩一 (koichik) 【あります】
- 4. ACID特性 Atomicity 不可分性 Consistency 完全性 Integrity 一貫性 Durability 永続性
- 5. 並行性 直列化可能性 (Serializability) 並列実行 直列実行 直列実行 t1 t2 t1 t2 どちらかと 同じ結果 t2 t1
- 6. 並行性制御 悲観的並行性制御 (blocking) 競合が起きることを前提とする リソースへのアクセスを排他的に行う 通常DBMSレベルで実現 楽観的並行性制御 (non blocking) 競合は滅多に起きないことを前提とする 競合が起きた場合はいずれかのトランザクションを ロールバックしてリトライする リソースへのアクセスは並行に行う 通常アプリケーションレベルで実現
- 7. トランザクション まとめ ACID特性 並行性 直列化可能性 並行性制御 悲観的並行性制御 楽観的並行性制御
- 9. トランザクショナルメモリ トランザクションの特性をメモリアクセスに応用 ACI特性 揮発性のメモリではdurabilityは不要 並行性 楽観的並行性制御への関心が高い
- 10. 目的 並行性の向上 Multi Core?Many Core時代に対応 モジュール性の向上 従来の場合 スレッドセーフなモジュールの組み合わせが スレッドセーフになるとは限らない トランザクショナルメモリの場合 スレッドセーフなモジュールを組み合わせても スレッドセーフ 操作は合成 (compose) 可能
- 12. 実現位置 ソフトウェア (STM) ソフトウェアで実現 ハードウェア (HTM) ハードウェアで実現 ハイブリッド (HyTM) ソフトとハードで実現
- 13. 粒度 トランザクショナルなデータの単位 ワードレベル (word granularity) 32bit/64bitのワード単位 HTMに多い オブジェクトレベル (object granularity) プログラミング言語のオブジェクト単位 STMに多い
- 14. 更新タイミング 更新を共有メモリに反映するタイミング 遅延書込 (deferred update) 更新時はコピーを作成 コミット時にまとめて反映 直接書込 (direct update) 更新時にバックアップを取得 ロールバック時に元に戻す
- 15. 競合の検出 オープン時 (detected on open) トランザクション開始時にチェック トランザクション開始時に使用するデータを列挙 非現実的 バリデーション時 (detected on validation) データをリード／ライトする際にチェック オーバーヘッド大 コミット時 (detected on commit) コミットの際にチェック 無駄な処理を行う可能性大
- 16. 同期アルゴリズム 同期 (blocking，悲観的) 非同期 (non blocking，楽観的) wait-freedom 全てのスレッドが前進 lock-freedom 少なくとも一つのスレッドが前進 obstraction-freedom 他のスレッドと衝突しなければ前進 衝突はContention Managerが管理 自由度が高くて現実的
- 17. トランザクショナルメモリ まとめ 実現方式は様々 まだまだ研究?評価段階 具体的な説明しにくいのよ 当面は柔軟性の高いSTMで模索 HTMは時期尚早(？) Sunは2009年(当初は2008年)出荷予定の 次世代プロセッサ(Rock)でHTMをサポート IntelはHardware Accelerated STMを研究中
- 21. 言語レベル 主要なキーワード atomic retry orElse
- 22. atomic トランザクション境界を定義 atomic { if (x == null) { x = new Foo(); } }
- 23. retry (1) 問題 atomic { while (x == null) { sleep(); 無限ループ } x.bar(); }
- 24. retry (2) トランザクションをロールバックして再試行 atomic { if (x == null) { retry; } x.bar(); }
- 25. or else ロールバックした場合の処理 retryした場合も含む atomic { return getElement(); } orElse { return null; }
- 26. ソフトウェアトランザクショナルメモリ まとめ 実現方式は様々 まだまだ研究?評価段階 具体的な説明しにくいのよ キーワード atomic retry orElse 当面は柔軟性の高いライブラリで模索か？
- 28. Sun DSTM2 Dynamic Software Transactional Memory 2.0 http://www.sun.com/download/products.xml?id=453fb28e STMのためのフレームワーク STM実現のためのメカニズムを提供 様々な実装を選択可能
- 29. コンポーネント (1) アトミックオブジェクト トランザクショナルなオブジェクト getter/setterを持ったインタフェース 実装はファクトリが動的に作成 @Atomicアノテーションを付ける ファクトリ アトミックインタフェースの実装クラスを動的に生成する Apache BCELを使用 アダプタ アトミックオブジェクトの振る舞いを提供 STMを実現するキモ
- 30. コンポーネント (2) コンテンションマネージャ 競合を調停する スレッド java.lang.Threadのサブクラス トランザクションやコンテキスト情報を管理 トランザクション トランザクションの状態を管理
- 31. アトミックオブジェクトクラス トランザクショナルなオブジェクトの インタフェース getter/setterメソッドを定義する @Atomic public interface AtomicData { void setValue(int value); int getValue(); }
- 32. ファクトリの生成 アトミックオブジェクトとアダプタの クラスを指定 AtomicFactory<AtomicData> atomicFactory = new AtomicFactory<AtomicData>( AtomicData.class, Adapter.class);
- 33. アトミックオブジェクトの生成 ファクトリから生成 アトミックインタフェースを実装した 動的に生成されたクラスのインスタンス AtomicData atomicData = atomicFactory.create();
- 34. アトミックオブジェクトの操作 Callable／Runnableを使用 atomicブロックに相当 Callable<Integer> readOperation = new Callable<Integer>() { public Integer call() { return atomicData.getValue(); } };
- 35. トランザクショナルに実行 Threadを使用 java.lang.Threadのサブクラス 使用するContentionManagerクラスを設定 Thread.setContentionManagerClass( BackoffManager.class); int value = Thread.doIt(readOperation);
- 37. アボート時の操作 RunnableをThreadに登録 orElseブロック相当 Thread.onAbort(new Runnable() { public void run() { ... } });
- 39. アダプタ アトミックオブジェクトを実現するクラス DSTM2標準のアダプタ dstm2.factory.ofree.Adapter 同期：non blocking (obstraction-freedom) 粒度：object level 更新：defered update 競合検出：detected on validation dstm2.factory.twophase.Adapter 同期：blocking (synchronize) dstm2.factory.shadow.Adapter ？？？
- 40. ofree.Adapter Factoryが 構造 Factoryが 生成 生成 <Atomic> Locator writer Transaction AtomicData state new AtomicData$ Version AtomicData$ value old Adapter start Version AtomicData$ value Atomic Reference
- 41. ofree.Adapter 初期状態 <Atomic> Adapter writer Transaction AtomicData committed new AtomicData$ Version AtomicData$ value old Adapter start Version null
- 42. ofree.Adapter ①committed リード(1) なので <Atomic> Adapter writer Transaction AtomicData committed new AtomicData$ Version AtomicData$ value old Adapter start Version ②newVersion null を読む
- 43. <Atomic> ofree.Adapter AtomicData ライト AtomicData$ Locator writer committed new Version value old Adapter start Version null ①前の値を コピーして 新しい値を Locator writer 書き込む active ②新しいAdapterを new 作成して繋ぎ替え Version value old Version
- 44. ofree.Adapter ①active リード(2) なので <Atomic> Locator writer Transaction AtomicData active new AtomicData$ Version AtomicData$ value old Adapter start Version AtomicData$ value ②oldVersion を読む
- 45. ofree.Adapter ①committed コミット後 にする <Atomic> Locator writer Transaction AtomicData committed new AtomicData$ Version AtomicData$ value old Adapter start Version AtomicData$ value
- 46. コンテンションマネージャ 競合の調整役 競合 参照と更新 更新と更新 調整 競合したトランザクションのいずれかを アボートさせる どのトランザクションを選択するか？ 様々なポリシーが考えられる
- 48. デモ AtomicData intの値1つ インスタンスを2つ作成 (AとB) atomicブロックAtoB Aの値+1→Bの値 atomicブロックBtoA Bの値+1→Aの値 Runner AtoBとBtoAをトランザクショナルに実行 atomicな操作の合成 トランザクションを10回実行 Test Runnerを2つのスレッドで実行
- 49. Sun DSTM2 まとめ DSTM2はSTMのフレームワーク 様々な実現方法を組み込み可能 Adapter ContentionManager 標準のAdapterは3つ obstraction-freedom (楽観的) two phase lock (悲観的) stripe (？？？)
- 50. 参考文献 Transactional Memory James R.Larus Ravi Rajwar ISBN1-598291-24-6