目次

概要

(書きかけ)

複数のスレッドが同じデータを読み書きする場合、以下のような問題が起きる可能性があります。

  • 読む → 加工 → 書き戻す という一連の作業の間に別の処理が割り込むことで、加工結果が正しく書き戻せないことがある。

  • 書き換えの途中で読み込み処理が走ることで、中途半端な不正なデータになってしまう。

このような問題を避けるためには、一連の処理を原子的に(他のスレッドに割り込まれることなく)行えるような仕組みが必要になります。 「マルチスレッド」で説明した「ロック」も、そのための仕組みの1つです。

ここでは、原子性の保証に必要ないくつかの概念について説明して行きます。

予定

●前置き
ここで話すような内容、実際のところ、ライブラリの内部とかに閉じ込めて、エンド ユーザーが直接触らない方がいい。

並列処理、マルチ スレッド プログラミングの怖さはテストのしにくさ。
100万回に1回とか、もっと低確率でしか発生しない不具合とかざら。
発生は確率論的に起こるので、100万回テストを動かしても出ないときは出ない。

この辺り、ちょっと脅しかけておきたい。


●ここから本題

原子性(atomicity)の保証が必要
方法としては、

・CPU が原子性を保証するための命令を持ってるのでそれを使う
・OS 機能を使って、他のスレッドの動きを止めてもらう(ロック)

原子性を保証する命令は、通常の命令よりは多少オーバーヘッドがかかる。
それでも、OS にロックしてもらうよりは圧倒的に高速。

● 数値型の原子性
int とかの読み込み、あるいは書き込みだけなら、原子性の保証あり(.NET の仕様)。
「8バイト以下で、適切なアライメントになっているものは、読み書きがあ原子的」

int x = 0;
x = 0x12345678;
とか書いたとき、x の値が 0x12340000 とか 0x00005678 とか、中途半端にならないことは保証あり。

なので、プリミティブ型に対して読むだけのスレッドは特にロック不要。
(逆に、この条件満たさない(decimal とか)は読むだけでもロック必要。)

● volatile 性
volatile(揮発性): 他のスレッドでも書き換えられるかもしれないから最適化しないで

・勝手にload/storeを消さないで
・勝手に実行順序を変えないで

後者、実行順序の問題は以下のような場合で問題に。

あるスレッド
x1 = 1;
x2 = 2;

別のスレッド
if(x2 == 2)
  Console.Write(x1); // 絶対 1 になってそうに見えるけど、その保証ない

最適化のためにコンパイラが順序を並べ変えるかもしれないし、
Out of Order 実行(機械語の命令が順序通りでも CPU が実行順序を入れ替える)されるかもしれない。

メモリ バリア、あるいは、メモリ フェンスと呼ばれる、読み書きの順序保証の仕組みが必要。
.NET 1.0 時代は想定してなかった
Java でも、volatile に順序保証まで盛り込まれたのは5から。

Thread.MemoryBarrier を使えば、その前後の読み書きを順序保証できる。
Thread.VolatileRead/Write(内部的にMemoryBarrierを利用した、順序保証付きの読み書き)

volatile 修飾子を付けた変数はすべての読み書きがこのVolatileRead/Write相当に。

● interlocked 演算
volatile があれば、読むだけ、書くだけという場合の原始性保証可能。
読み書き両方行う場合、++i みたいな単純な操作すら非原子的。

一方で、インクリメントとか値の交換とか、読み書き両方伴う物も。
CPU によっては、interlocked (連結)命令ってのを持ってて、これを使えば原始的にインクリメントとか交換が可能。

.NET では Interlocked クラスを使う。

特に重要なのが CompareExchange(条件付きの値の交換)。
意味的には、以下のようなものを、原子性の保証付きで行う。

public int CompareExchange(ref int loc, int value, int comp)
{
    int ret = loc;

    if (ret == comp)  
        loc = value;

    return ret;

}

http://d.hatena.ne.jp/NyaRuRu/20060721#p1
http://msdn.microsoft.com/ja-jp/magazine/ee532386.aspx

これを使えば、OS 機能に頼らないロックや、ロックなしで任意の操作を原子的に行うような実装が可能。
(スピン ロック、インターロック アップデート)

スピン ロック: while ループでフラグを監視。
競合発生頻度が低いときは OS 機能のロックよりも、スピン ロックの方が良いことも。
競合が起きてるときには無駄なループが周り続けるという問題あり。

インターロック アップデート: 一時変数上で処理、最後にCompareExchangeを試みる。
競合が起きてたらCompareExchangeに失敗するように書いておいて、失敗したら最初からやり直し。
いわば、(データベースでよく使う)楽観的な同時実行制御を in-memory でやる。

余談: event の実装
.NET 3.5 までは、[MethodImpl(MethodImplOptions.Synchronized)] 属性付きのメソッドが作られてた。
.NET 4 では、インターロック アップデートを使った実装に変更。

● OS 機能でロック
EventWaitHandle(AutoResetEvent)とかを利用。

別のスレッドがハンドルを握っている状態でWaitOneメソッドを呼ぶと、そこで一度スレッド止める。
ハンドルを握っているスレッドが「解放したよ」という信号を発する(Setメソッドを呼ぶ)まで、スケジューリングの対象から外してもらう。

カーネル モード実行されるので、それなりに高負荷。
(余談: 実行モード
  ・ユーザー モード
  ・カーネル モード
  それぞれの間の遷移)

● Monitor クラス
ハイブリッド
最初、スピン ロックでちょっと待つ → その後、OS 機能でロック。
最初の段階で競合が起きなければカーネル モードへの移行しないのでそれなりに高速。
競合が起きた時に無駄なループ空回りを避ける。

更新履歴

ブログ