スレッド一覧

Load-Link/Store-Conditionalを見直した

CASを持たないアーキテクチャ

CAS(Compare-And-Swap)を持っていないアーキテクチャで、アトミック操作はどうやるのか調べてみました。そういう部分ではLoad-Link/Store-Conditionalという命令を使って実現するみたいです。

  • PowerPCでは、lwarx/stwcx という命令。
  • ARMでは、ldrex/strex という命令。

このLoad-Linkというのが何かしらのロック付きロードで、この命令が発行されるとそれに対するアクセスを見張るらしい。
そして、Store-Conditionalが名前のつき条件付きストア命令で、Load-Linkでとったロックが維持されているときに、ストアを正常に行うことができるようです。
もし、ほかのプロセッサが見張っていたアドレス(バス?)を操作した場合には、ロックが外れ、次段のStore-Conditional命令が失敗するという結果になります。

Load-Link(LL)はLoad and Reserve とも表現するらしい。そのデータに対する変更の予約、という意味合いなんだろう。

このCASじゃない方式は面倒なようだけど、実はCASより優れている点もあるらしい。
実はCASの方式では、ABA問題と呼ばれる不都合な点がある。
これは対象アドレスのデータが書き換わって元に戻されたという挙動を確認できないのです。LL/SCの方式では、対象データ領域からのデータ読み出しから書き込みの間で値が更新されていないことをチェックしてストアできる点で優れています。またバスをロックせずにすむ点も効率がよいとのことです。

このABA問題はロックフリーなデータ構造を作っているときに問題となるらしいです。
詳しくは調べてみてください。


スレッド同期のエトセトラ 第3回

Visual C++ 2005以降のvolatileのMS拡張

さらにvolatileについて、Microsoft独自拡張がなされてる記載を見つけました。
VisualStudio使って、Windowsアプリケーションを作る上ではこのルールだけでやっていけるのかもしれません。

Visual C++ 2005 には、volatile 変数へのアクセスに関して、標準の C++ を補うために、マルチスレッドを想定したセマンティクスが定義されています。Visual C++ 2005 以降では、volatile 変数からの読み取りには Read-Acquire セマンティクスが、volatile 変数への書き込みには Write-Release セマンティクスが適用されるように定義されています。つまり、コンパイラによって、読み取りと書き込みが、互いを飛び越えて移動されることはありません。 さらに、Windows 上では、CPU による順序変更も確実に防ぐことができます。

これを見ると、2005以降のコンパイラで volatile付き変数を読み書きするタイミングで Read-AcquireやWrite-Releaseが適用されるみたいです。現在のvolatile変数だけでうまくいってる例も、実はこの拡張に依存してるのでは?と思った次第です。

あともう1つ。PowerPCのアーキテクチャでは x86/x64のときとは違って大胆にメモリの読み書き順序が異なって見えます。これに対してどのように対処すればいいのか不思議に思っていましたが、InterlockedXXXAcquire/Releaseの命令を通常版の代わりに使えば、きちんと各種メモリバリアを張ってくれるようです。

参考文献

Microsoft – Xbox 360 と Microsoft Windows でのロックレス プログラミングの考慮事項

volatile爆発しろ!


スレッド同期のエトセトラ 第2回

前回のvolatileの変数を同期プリミティブに、な話の第2回です。

Microsoftの文章では、AcquireバリアはRead-Acquireバリア、ReleaseバリアはWrite-Releaseバリアと表現されています。確かにメモリバリアが使用される状況を考えると、アトミック変数代入時にはすなわち書き込みなので、Write-Releaseバリアという表現であってると思います。

Interlocked関数群をWindows環境において使用している状況では、これらの関数群がRead-Acquireバリア/Write-Releaseバリアを備えていると考えてよいとのことです。一方組み込み向けのこれらの関数ではバリアを備えない記述がみられます.

バリアが必要なのは、コンパイラやCPUが結果が変わらない範囲において、命令実行順序を移動するからという点にあります。これがマルチコア(マルチスレッド)が必須となっている昨今では大きな問題になっています。

具体的に x86/x64のアーキテクチャでは、この実行順序の移動について調べてみると、アウトオブオーダーなのに思った以上に順序の変更をしないようです。PowerPCアーキテクチャでは逆で結構強引に実行順序の入れ替わりが起こるようです。
x86/x64環境で起こる実行順序の入れ替わりは、“読み取りを書き込みの先に移動する “というケースのようです。x86/x64のPC環境では MemoryBarrier() という関数があり、これを実行することでメモリバリアをはることができます。

一方でコンパイラの最適化によるメモリ読み書きバリアとしては、_ReadBarrier(), _WriteBarrier(), _ReadWriteBarrier() があります。これはコンパイラに対しての指示となっています。ただこの_ReadBarrier命令は日本語のMSDNヘルプを見ると、メモリバリアとして機能しそうな訳になっていますが、英語のMSDNを見ると単にコンパイラへの命令であるという点がきちんと書かれています。

日本語訳だとこんな感じでした。

_ReadWriteBarrier は、次に続くメモリ アクセスが開始される前に、前のすべてのメモリ アクセスを強制的に完了させます。
_WriteBarrier は、次に続く書き込み処理が開始される前に、前のすべてのメモリの書き込み処理を強制的に完了させます。
_ReadBarrier は、次に続く読み取り処理が開始される前に、前のすべてのメモリの読み取り処理を強制的に完了させます。

英語の文章では、次のように書かれていました。

The _ReadBarrier_WriteBarrier, and _ReadWriteBarrier compiler intrinsics prevent only compiler re-ordering.
To prevent the CPU from re-ordering read and write operations, use the MemoryBarrier macro


スレッド同期についてのエトセトラ

世の中には、volatile付けただけでその変数を同期プリミティブとして使用OKという誤った認識があるような気配だったので、ちょっと調べてみました。自分の認識を整理するためでもあるけど。

volatile修飾は何をしてくれるのか。まずはこれを考えてみます。
volatileはコンパイラによる最適化を抑制してくれます。これは、コンパイラによる命令の移動、メモリアクセスは高コストになるから変数をレジスタに割り当てる、といった部分が抑制されます。

この「レジスタに割り当てることをしない」という部分の話が、「常にメモリからデータを読み取る」と解釈されて広まった結果、マルチスレッド環境での同期プリミティブとして使用されてしまう、という状況のように感じます。

volatile変数で何とか同期プリミティブのようにしていた箇所は、アトミック変数+メモリバリア(メモリフェンス)の組み合わせで正しく作ることができます。メモリバリアは、CPUが命令を実行する際に起こる命令のリオーダーに関して働きます。簡単には、バリア命令の位置を超えてメモリ操作の命令を移動しない、という感じになります。

このメモリバリアも大別してacquireバリア/releaseバリアがあります.

  • アトミック変数への代入時には releaseバリアを併用します。
  • アトミック変数の読み取り操作時には、acquireバリアを併用します。
このバリアについてコード風に説明すると以下のようになります。

もう1つの例。

このように操作をまたがないようにする処理ということで、バリアと呼ばれます。

これを併用することにより、アトミック変数の値を取得した時点には、後続のメモリアクセス命令はまだ各種変数に代入されていない(評価されていない)ことが保証できます。
逆に、アトミック変数の更新時には、それまでのメモリ操作系の命令が、アトミック変数更新タイミングを超えて、後方で実行されるという点を防ぐことができます。

正しく同期化されたコードを書くためには、アトミック変数を使用するだけでなく、メモリバリア命令を併用する必要があります。

ちなみに、Mutex,Semaphoreなどの同期プリミティブはこれらのメモリバリアの内容を含んでいます。そのためこれらを使用してさえいれば、上記のやっかいな部分を意識しなくてすみます。

さてvolatile変数が同期プリミティブとして機能しない理由を考えてみます。
volatile変数はそもそも操作がアトミックではありません。
メモリからロード、演算、結果のストアというように加減算などは複数の命令の合成で処理されます。
また、先ほどのメモリバリアの効果も持たないので、前後のプログラムコードのメモリアクセスについて、アウトオブオーダーのCPUが実行順序を移動させることができてしまいます。これらの点からvolatile変数は同期プリミティブとして使用できないとなります。

話はまた次回へ続く。