ソフトウェアトランザクショナルメモリ

出典: フリー百科事典『ウィキペディア（Wikipedia）』

計算機科学において、software transactional memory(STM)は、データベーストランザクションに似た並行性制御機構であり、並列計算を行う際の共有メモリへのアクセス法である。この機構はロックベースの同期の代替手段として機能し、普通はロックフリーな方法で実装される。ここでいうトランザクションとは、共有メモリに対する一連の読み出しと書き込みを実行するコードを意味する。論理的にはこれらの読み出しと書き込みは、時間的なある一点で行われ、他の(一連の)トランザクションからはその間の状態は見えない。トランザクションを行うためにハードウェアにサポートさせるアイデアは、1986年にTom Knightにより論文と特許として出された。そのアイデアを普及させたのがMaurice HerlihyとJ.Eliot B. Mossである。1995年、Nir ShavitとDan Touitouがこのアイデアをソフトウェアのみで行うtransaction memory(STM)に拡張した。STMは近年非常に研究が進み、実用的な実装も進展している。

[編集] パフォーマンス

現在のたいていのマルチスレッドアプリケーションでロック技術が使われているのとは異なり、STMは楽天的で、すべてのスレッドは他のスレッドが行ったことに対して承認や読み書きのログを記録することなしに、共有メモリに対しての変更を完了する。他の進行中の操作に悪影響を与えない責任を書き込み側に負わせる代わりに、その責任を読み込み側に負わせ、全体のトランザクションが完了した後、読み込み側にアクセス対象のメモリが並行して過去に他のスレッドから変更されていないかを検証させる。この最後の処理、つまりトランザクション中に起きた変更を検証させる処理であるが、この検証により正しいものと確認されたならば、変更は永久なものとして反映される。この処理はcommit（コミット）と呼ばれる。また、トランザクションはロールバックや処理が取り消されたために優先度が変わったとの理由でいつでも中止される可能性がある。もし、トランザクションが変更が競合したためにcommitできなかったならば、普通トランザクションは中止され、成功するまで最初からやり直しする。

この楽観的なアプローチの利点は並列性が向上することである。どのスレッドもリソースにアクセスするために待つ必要がなく、普通は同じロックを使って保護されているひとかたまりのデータ構造に対して、異なるスレッド同士が安全かつ同時にデータ構造内の要素に対してばらばらに変更が可能である。トランザクションが失敗した場合にやり直すオーバーヘッドがあるにもかかわらず、たいていの現実にあるプログラムではリソースのコンフリクトはめったに起こらないので、非常に多数のプロセッサ上でロックベースの仕組みで行う以上の良好なパフォーマンスを得られる。

しかし実際には、STMシステムは少ないプロセッサ(アプリケーションにもよるが1個から4個)上で動作する細粒度ロックベースのシステムと比較してパフォーマンス上の問題に当たる。これは主にログ管理に関連するオーバーヘッドとトランザクションを完了する時にかかる時間によるものである。この様な場合でも通常2倍以上遅いわけではないので、STMの思想から得られる利益からするとこのペナルティは正当なものだと、STM側は主張している。

理論的に(最悪値では)、n個の並列で同時に動作するトランザクションが存在した場合、O(n)のメモリ及びプロセッサ時間を必要とする。実際にはこれらは実装の詳細(オーバーヘッドを避けるのに十分早くトランザクションが失敗するように作られる)によって変化する。しかし、めったにはないが、software transactional memoryよりも理論的に処理時間が短いロックベースアルゴリズムがあることもまた事実である。

[編集] 思想的な利点と欠点

パフォーマンス的な利点に加えて、STMは概念的には非常に単純でマルチスレッドプログラムを理解しやすくするので、オブジェクトやモジュールのような高レベルな抽象化を進めることができ、プログラムをよりメンテナンスしやすくできる。ロックベースのプログラミングは実際にはしばしば非常に良く知られた問題にぶつかる。

• 処理的に離れているもしくはどうみても関連のなさそうな箇所のコードやタスク内の処理がかぶったりすることについて考える必要がある。これは非常に難しくてプログラマに対してエラーを誘発しやすい
• デッドロックやライブロック、その他処理を止めてしまうような問題を回避するために、プログラマはなんらかのロックを必要とする。このロック処理はしばしば無意識のうちに強制され誤りに陥りやすい。また、これらの問題が持ち上がった時には、それらを再現したりデバッグしたりするのが実は難しかったりする。
• ロックは優先順位の逆転を引き起こす。これは優先度が高いスレッドが必要なリソースにアクセスしたいがために、優先度が低いスレッドに強制的に待たされるという現象である。

対照的にメモリトランザクションの考えは大変シンプルである。なぜなら、それぞれのトランザクションはあたかもシングルスレッドで動作しているかのように見えるからである。デッドロックやライブロックはまったく起きないか外部のトランザクションマネージャーによって制御されるので、プログラマはそのような問題について頭を悩ませる必要はまったくない。優先度逆転については課題として残るが、優先度が高いトランザクションはまだトランザクションが完了していない低い優先度のトランザクションとぶつかって処理が中断することはない。

他方、トランザクションの振る舞いにおいて、失敗したトランザクションを中止するのにも制限を設けたいこともある。たいていのI/O処理を含む、トランザクションがロールバックできない操作である。このような制限は普通実際にはバッファを作ることでやりくりする。このバッファによって、取り消せない操作をキューに入れたり、それらを他のトランザクションとは別にあとで実行したりする。

2005年に、Tim Harris、Simon Marlow、Simon Peyton JonesそしてMaurice HerlihyによってSTMがConcurrent Haskell上に構築された。これは任意のアトミックな操作をより大きなアトミックな操作に合成することができる。この役に立つ考えはロックベースプログラミングでは不可能である。以下に筆者の言葉を引用する。

もしかしたら、最も根源的な意見は(中略)ロックベースプログラムは操作を合成できないことでないか。操作をくっ付けると元は正しい操作がうまくいかなくなってしまうかも知れない。例えば、スレッドセーフなハッシュテーブルに挿入と削除をすることを考えてみよう。ここで、アイテムAをテーブルt1から一つ削除し、それをテーブルt2に挿入することを考える。この時、中間の状態(すなわちアイテムAをどちらも含まない状態)は他のスレッドからは見ることができないとする。もしハッシュテーブルの実装者はこの要求を見越すことができなければ、この要求をちゃんと満たす方法はない。端的に言うと、個々に見れば正しい操作(挿入と削除)はより大きな正しい操作に作り直すことはできないのだ ?Tim Harrisその他, "Composable Memory Transactions", 第2章: Background, pg.2

STMにおいては、この問題は単純に解決できる。あるトランザクション中における2つの操作を単にラップしてアトミック名操作としてくっつけてしまえばよいのである。唯一の突っ込み所としてはこの処理を呼び出す側からははっきりしないことがある所である。つまり、コンポーネントが提供する方法の実装の詳細や、もし操作が失敗した場合に、そのトランザクションが再実行を試みるタイミングである。それに対して、筆者はretryコマンドを提案している。これは、トランザクションが失敗したときに生成されるトランザクションログを使って、どのメモリセルが読み出されたかを決定するものである。そして、これらのメモリセルのうちの一つが変更された時に自動的にトランザクションをリトライする。これは、少なくともある一つの値が変化するまでは、トランザクションの振る舞いは変わらないだろうという考えに拠っている。

筆者はまた、操作を合成するための代替手段を提案している。これは'orElseというキーワードである。これは一つのトランザクションが走っていて、そのトランザクションがretryするならば、もう一方が実行されるというものである。もし両方リトライするならば、関連する変更がなされたらすぐに両方ともリトライしようとする。この機能は、POSIXのネットワークで使われるselect()呼び出しの特徴と比較される。orElseを使えば、呼び出し側は複数のイベントのうちどれか一つが変化するのを同時に待つことができる。この機能はまたプログラミングインタフェースを単純化できる。例えば、同期操作および非同期操作を相互に変換する機構を単純に作ることができる。

[編集] 言語側のサポートについての提案

比較的単純な言語文法を使うことで、プログラマはSTMの思想の単純さに触れることができる。Tim Harrisと Keir Fraserは "軽量トランザクションの為の言語サポート" を古典的な条件付critical region(CCR)を使ってトランザクションを表現するアイデアを提案した。この最も単純な形式の中には、"atomic block"というものがあり、理論的に同時に一つのスレッドしか実行できないコードブロックがある。

 // Insert a node into a doubly-linked list atomically
 atomic {
     newNode->prev = node;
     newNode->next = node->next;
     node->next->prev = newNode;
     node->next = newNode;
 }

ブロックの最後に到達すると、トランザクションは可能であればcommitするか中止ないしリトライを行う。CCRはまたguard conditionを許可しており、そのコードを実行するまでトランザクションを待たせることができる。

 atomic (queueSize > 0) {
     remove item from queue and use it
 }

ある条件が満足されていないならば、トランザクションマネージャーは他のトランザクションがリトライ前の条件に影響を与えるようなcommitを行うまで、そのトランザクションの実行を待たせるだろう。このことにより、スレッド間で明確に情報のやりとりを行う方法と比較して、生産者と消費者の間の結びつきを弱くし、各ブロックのモジュール化を強化する方向に働く。"Compsable Memory Transcations"ではこの例をretryコマンドを使った一つのステップとして扱っている。このコマンドはいつでもトランザクションを中止し、以前リトライをする前にそのトランザクションが値を変更したら、その値が以前読み込んだとある値になるまで待つというものである。例えば...

 atomic {
     if (queueSize > 0) {
         remove item from queue and use it
     } else {
         retry
     }
 }

トランザクション中にリトライ動作を動的に遅延できる能力は、プログラミングモデルを単純化し、また新しい可能性を広げる。課題の一つとして、トランザクションの外で発生した例外が伝播したときにどのように振舞うかというものである。"Composable Memory Transactions"では、筆者らはこの場合はトランザクションを中止すべきだと断じている。なぜなら、例外は通常Concurrent Haskellでは期待していないエラーを示しているからである。しかし、発生理由を診断する目的のために、例外はトランザクションによって割り当てられた情報や、トランザクション中に読み出された情報を例外は保持している。これが、他の条件では妥当だと思われた設計がやりづらくなっている理由である。

[編集] 実装上の問題

楽観的な読み出しを伴うsoftware transactional memoryの実装には一つ問題がある。それは、読み出しに矛盾が生じるためにトランザクションを完了できないことがある。(つまり、他のトランザクションによって書き込まれた値のうち古いのと新しいのとを混同して読んでしまうことがある）。このようなトランザクションはcommiしようとするなら不運にも実行が中断されるので、トランザクションシステムによって強制される条件の一貫性には違反しない。しかし、この仮の矛盾した状態のために、セグメンテーションフォールトや無限ループに入るなど致命的な例外条件を引き起こすトランザクションの原因となる。"Lanaguage Suppport for Lightweight Transactions"の図4から次の不自然な例を示す。

atomic {
    if (x != y) 
        while (true) { }
}

atomic {
    x++;
    y++;
}

最初にx=yと与えられれば、上記のどちらのトランザクションもこの変数を変更することはない。しかし、トランザクションBが変数xをアップデートする前にxをトランザクションAが読み出すことは可能ではあるが、トランザクションBがyをアップデートした後でyをトランザクションAが読み出すと無限ループに陥る。このような問題に対してのよくやる方法としては、致命的な例外を横取りし、それぞれのトランザクションが正常かどうかを定期的にチェックすることである。もし正常でなければすぐにトランザクションを中止する。そうなったらどんな場合でも残念ながら失敗してしまうだろう。

これらの問題をうまく扱うために、楽観的な読み出しを使ったSTMの実装は、不正な操作の実行を行うトランザクションを検知し、失敗した場合は終了したり、トランザクションをちゃんと中断できるようにしなければならない。