A bit inside of Transactional Language Constructs for C++ - part.1 Atomic transaction

Boost.勉強会 #10 にて @yohhoy さんが Transactional Language Constructs for C++ (C++ における Transactional Memory 拡張)について発表 されました。丁度自分も提案文書を読んでいるところであり Transactional Memory (以下 TM)というか並列プログラミング全般について知識がないので勉強会駆動の発表ネタになるかなと思っていたところだったので非常にタイムリーでした。発表内容としては現在提案されている TM 拡張の syntax と semantics についての説明で、実装については対象外だったわけですが(もともと提案文書には実装については含まれていない)、その発表の中で

• (Atomic Transaction で、他の transaction だけでなく)他のスレッドに途中状態を見せないってどう実現するのか分からない

というコメントがありました(多分)。その時は、ピンと来なかったのですが色々調べたりするうちにその感覚が分かってきました。その心は

• ゼロオーバーヘッドか？(TM 有効にしても実際に TM を使用しなければオーバーヘッドはないか？)

という質問にも通じます。私は TM 拡張は基本的に transaction 内部のコードだけ変更すればいいと考えていたので実行時にはほぼゼロオーバーヘッドだと思っていたのですが、(transaction 外の)他のスレッドにも途中状態を見せないということは transaction 外のコードに対しても何かガードなりを設ける必要があるのではないか？という懸念があった訳です。

が、なんというか「確かに嘘は書いてないんだけどさぁ」という解釈が可能であることに気付きましたので、本稿ではそのことについて書いてみます。

さて、提案文書では Atomic transaction について以下のように書かれています。

In a data-race-free program, an atomic transaction appears to execute atomically; that is, the compound statement appears to execute as a single indivisible operation whose operations do not interleave with the operations of other threads.

データ競合がないプログラムでは、atomic transaction はアトミックに実行される。(atomic transaction として指定された)複文は他のスレッドの操作とインターリーブされない単一の分割不可能な操作として実行される。

さて、ここでどうしても後半に意識がいってしまうわけですが、この文章で最も重要なのは最初の部分 "In a data-race-free program" です(appear であることも多分重要)。

data-race-free とは何かについては TM 提案の最初の方にも簡単に触れられています。C++11 では 1 スレッド内の実行順序について "sequenced before" という関係で順序が定められているものがあります。またスレッド間の実行順序について "synchronized with" という関係で順序が定められているものがあります。これらをもとに "happens before" という関係が定められています(厳密にはもうちょっと複雑)。

• A is sequenced before B → A happens before B
• A synchronizes with B → A happens before B
• A happens before B ∧ B happens before C → A happens before C

そして、あるメモリ領域に対する書き込み操作と、別の読み込み操作あるいは書き込み操作が同じメモリ領域に対して行われている時、これらを conflict と称します。以上を元に data race (データ競合) は、次のように規定されています。

The execution of a program contains a data race if it contains two conflicting 2 operations in different threads, at least one of which is not an atomic operation, and neither happens before the other.

異なるスレッドの 2 つの操作が conflict しており、"happens before" の関係になく、かつ、少なくとも一方は atomic ではない場合、data race が発生している。

要するに、「同一メモリ領域に対する書き込みと、読み込みないし書き込み」(=conflict)について順番が定められていないケースを data-race と呼んでいる訳です。

さて、transaction 間については、ある transaction の終了と別の transaction の開始には "synchronized with" の関係があるとされ、実行がインターリーブしません。従って、transaction 間では data-race は発生しません。では、transaction と transaction 外ではどうなるでしょうか？

atomic transaction はロックや atomic など他の同期機構を含むことができません。このため、transaction 内のコードと transaction 外のコードについて "synchronized with" 関係が発生しません。この状況下で data-race-free、つまり順序不定な conflict が存在しないためには、

1. 同一スレッド内で sequenced before 関係にあるか、
2. そもそも conflict が存在しないか、
3. 別の transaction 内に存在しているか、

のいずれかである必要があります。結果として別スレッドの transaction 外のコードは transaction の途中状態を見ることがありません。この場合、2 しか有り得ず、そもそも transaction が変更するメモリ領域に対するアクセス、conflict が存在しない訳ですから。

つまり、atomic transaction において他のスレッドが transaction の途中状態を見ないというのは atomic transaction によって保証されているというよりは、その前提、data-race-free なプログラムである、というところに依るところが大きいと言えます。data-race-free であることはプログラマが保証してやらねばなりません。一番簡単なのは conflict があるところを transaction で囲むことでしょう。この場合、atomic transaction である必要はありません(transaction 間であれば relaxed transaction でも順序が規定されるので)。

本記事では A bit inside of Transactional Language Constructs for C++ part.1 として TM 提案 での atomic transaction の記述の解釈について書いてみました。心づもりとしては part.2 では TM 提案の対とも言える文書、Intel TM ABI を元にコンパイラがどのように C++ TM を実現しようとするかについての概要、part.3 では Intel TM ABI を実装しているライブラリ RSTM の実装を簡単に覗いてみたいと思っています。