不透明性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/04/05 03:33 UTC 版)
「ソフトウェアトランザクショナルメモリ」の記事における「不透明性」の解説
楽観的な読み出しを伴うソフトウェアトランザクショナルメモリの実装には一つ問題がある。それは、実行中の（完了していない）トランザクションは、一貫性の破れた状態を読んでしまっていることがあるというものである（つまり、他のトランザクションによる更新の前の値と後の値を混ぜて読んでいることがある）。このようなトランザクションは、例えatomicブロック内の終端まで処理が進んだとしても必ずアボートされる運命にあるので、トランザクションシステムによって強制される一貫性条件が破られるわけではない。しかし、この仮の矛盾した状態のために、セグメンテーションフォールトやゼロ除算のような致命的な例外(fatal exception) を引き起こしたり、無限ループに陥ってしまうことはありうる。"Language Support for Lightweight Transactions" の図4にある作られた例を示す。 atomic { local_x = x; local_y = y; if (local_x != local_y) while (true) { }} atomic { x++; y++;} トランザクション Aトランザクション B最初に関係 x=y が成り立っていたとすると、上記のどちらのトランザクションもこの関係を崩すことはない（不変条件になっている）。しかし、トランザクション A の処理において、x をトランザクションBによる更新前に読み、一方 y をトランザクションBによる更新後に読み、結果として無限ループに陥るということは起こり得る。これは既に致命的な状態に陥っているにも関わらずトランザクションが継続されるためゾンビトランザクションとも呼ばれる。この問題へ対策としては、致命的な例外を横取りし、それぞれのトランザクションが正常かどうかを定期的にチェックし、異常ならばトランザクションをアボートするという方法があるが、言語によっては実装も大掛かりになりがちである。 ゾンビトランザクションに対して定期チェックなどを行わず、そもそも腐った値を読み出さない保証の事を不透明性（Opacity）と呼ぶ。不透明性を保証する方法として単純なものにIncremental Validationが挙げられる。これは新しく値を読むたびにこれまでに読んだ値が以前に読んだ値と一致している事を確かめる物である。例えばあるトランザクションの中でA,B,Cの3つの変数を読み出す場合「Aを読む→Bを読む際にAも読んで前回と一致する事を確かめる→Cを読む際にA,Bも読んで前回と一致することを確かめる」という手順を踏むこととなり、読み出し操作は変数の数に対しO(n2)でスケールする。他にグローバルバージョンクロックを用いる手法もある。トランザクションが完了するごとにインクリメントされる共有カウンタを用意しておき、値を読み出す側がカウンタをチェックする事で他のトランザクションによる書き換えを検知する方法である。カウンタの値が増えている場合にIncremental Validationと同様に再チェックを行う手法や、書き換え時のカウンタの値を保護対象のメモリと同時に書き込んでおくことによって、無駄な再チェック無しに値の非一貫性を検知する手法がある。不透明性を保証しているソフトウェアトランザクショナルメモリはこれらの手法を用いる事で非一貫な値を読みそうになった時にアボートする。
※この「不透明性」の解説は、「ソフトウェアトランザクショナルメモリ」の解説の一部です。
「不透明性」を含む「ソフトウェアトランザクショナルメモリ」の記事については、「ソフトウェアトランザクショナルメモリ」の概要を参照ください。
- 不透明性のページへのリンク
