2017年11月5日日曜日

C#の排他制御 - UpgradeableReadLock

.NET4.0/C#5.0以降、どんどん非同期処理に関する機能が増強されてきています。
特にasync/await構文なんかは、今までは非同期で書こうとすると非常に読みにくいコードになっていたのを、上から下へ流れるようにプログラムを書くだけで非同期処理が実現できてしまうという非常に画期的なものでした。

しかし、そこには非同期処理特有の問題が付きまといます。いくら簡単に非同期処理が書けるからと言って、何も知らずに非同期処理を確実に動かすことはできないのです。

さて、非同期処理で注意しなければならないことの1つとして、「データの整合性」が挙げられます。
非同期処理は複数のスレッドが同時に走るわけですから、それぞれのスレッドから1つのデータにアクセスした場合どのような結果になるか、ということを常に想像しながらコードを書かなければなりません。
そして、必要ならば排他制御を行い、片方のスレッドからデータにアクセスしている場合はもう片方のスレッドがデータにアクセスするのを待ってもらう必要があります。

はじめに - lock構文

C#にはそれに関して便利な構文が用意されています。
ご存知、lock構文です。
Stopwatch sw = new Stopwatch();
sw.Start();

Parallel.ForEach(Enumerable.Range(0, 4), i => {
    Console.WriteLine($"{sw.ElapsedMilliseconds,4}ms, {i,2}: Start");
    Thread.Sleep(TimeSpan.FromSeconds(1));
    Console.WriteLine($"{sw.ElapsedMilliseconds,4}ms, {i,2}: Finished");
});

sw.Stop();
まず、こちらがlock構文を使わない場合です。各スレッドで1秒待ってもらっていますが、すべてが並列で実行されるので下記のような実行結果になります（実行結果は環境によって異なります。以下同じ）。

　42ms, 0: Start
　44ms, 2: Start
　44ms, 1: Start
　44ms, 3: Start
1068ms, 0: Finished
1068ms, 1: Finished
1068ms, 2: Finished
1068ms, 3: Finished

基本ですね。

続いてlock構文を入れて、Sleepに入れるのを1つのスレッドのみに絞ってみます。
Stopwatch sw = new Stopwatch();
object lockobj = new object();

sw.Start();

Parallel.ForEach(Enumerable.Range(0, 4), i => {
    lock(lockobj) {
        Console.WriteLine($"{sw.ElapsedMilliseconds,4}ms, {i,2}: Start");
        Thread.Sleep(TimeSpan.FromSeconds(1));
        Console.WriteLine($"{sw.ElapsedMilliseconds,4}ms, {i,2}: Finished");
    }
});

sw.Stop();
　41ms, 0: Start
1068ms, 0: Finished
1068ms, 1: Start
2070ms, 1: Finished
2070ms, 2: Start
3073ms, 2: Finished
3073ms, 3: Start
4078ms, 3: Finished

今度は1つのスレッドが確実に終わってから次のスレッドへ移るような実行結果になりました。

今回はlock構文の動作を確かめるための簡単なプログラムですが、通常はデータの読み書きなど複数のスレッドから同時に行われたら都合が悪い部分をlockで囲み排他制御を行うのに使います。

ReadLockとWriteLock

さて、ここまで来て勘のいいひとなら気づいたでしょう。
何でもかんでもデータアクセスにlockをかけるのは決して効率の良いことではないことだと。

データを読み込むだけなら複数のスレッドから同時に行っても問題ないはずです。
ですが、データを読み込んでいる途中に他のスレッドから書き込みが行われたり、データを書き込むときに他のスレッドから書き込みや読み込みを行われては困ります。
//データを書き込みしている途中でも書き込み前後のどちらかの値が取得できさえすればいいなら読み込みを許可してもいいのでは？と思うかもしれませんが、場合によっては書き込み中には書き込み前後のどちらの値でもない値になりうるのです。

lock構文は有無も言わせず排他制御をする構文です。たとえ複数のスレッドがすべて読み込みだけをしたくても同時に行うことを許しません。


.NETにはそれをサポートするためのクラスがあります。

ReaderWriterLockSlim
//名前がいびつですが、実はReaderWriterLockというクラスもあります。このクラスを整理してもっとシンプルにしたものということで、このような名前になっているようです。

機能は上記の通りで、読み取りロックが取得されているときは他のスレッドからも読み取りロックを取得することができますが書き込みロックは取得できません。書き込みロック取得中は読み取り/書き込みロック両方とも取得できません。
ReaderWriterLockSlim rwlock = new ReaderWriterLockSlim();
Stopwatch sw = new Stopwatch();
sw.Start();

Parallel.ForEach(Enumerable.Range(0, 12), i => {
    if(i % 2 == 0) {
        try {
            rwlock.EnterReadLock();
            Console.WriteLine($"{sw.ElapsedMilliseconds,4}ms, {i,2}: EnterReadLock");

            Thread.Sleep(TimeSpan.FromSeconds(1));
        }
        finally {
            Console.WriteLine($"{sw.ElapsedMilliseconds,4}ms, {i,2}: ExitReadLock");
            rwlock.ExitReadLock();
        }
    } else if(i % 2 == 1) {
        try {
            rwlock.EnterWriteLock();
            Console.WriteLine($"{sw.ElapsedMilliseconds,4}ms, {i,2}: EnterWriteLock");

            Thread.Sleep(TimeSpan.FromSeconds(1));
        }
        finally {
            Console.WriteLine($"{sw.ElapsedMilliseconds,4}ms, {i,2}: ExitWriteLock");
            rwlock.ExitWriteLock();
        }
    }

});

sw.Stop();
一気にインデントが多くなって見にくくなってしまいました。Lockは取得したら確実に解放しなければならないので、try-finally構文を使っているためです。
//lock構文も内部的にはMonitorクラスを使ったtry-finally文に展開されます。

これを実行すると次のような実行結果になります。

　70ms,　0: EnterReadLock
　71ms,　6: EnterReadLock
　71ms,　4: EnterReadLock
　71ms,　2: EnterReadLock
　95ms,　8: EnterReadLock
1071ms,　0: ExitReadLock
1095ms,　6: ExitReadLock
1095ms,　4: ExitReadLock
1096ms,　8: ExitReadLock
1096ms,　2: ExitReadLock
1096ms, 11: EnterWriteLock
2096ms, 11: ExitWriteLock
2097ms,　7: EnterWriteLock
3098ms,　7: ExitWriteLock
3098ms,　1: EnterWriteLock
4099ms,　1: ExitWriteLock
4099ms,　5: EnterWriteLock
5099ms,　5: ExitWriteLock
5099ms,　3: EnterWriteLock
6100ms,　3: ExitWriteLock
6100ms,　9: EnterWriteLock
7101ms,　9: ExitWriteLock
7101ms, 10: EnterReadLock
8102ms, 10: ExitReadLock


最初は5つのスレッドが同時にReadLockに入っていますが、WriteLockはおそらくブロックされていることがわかります。そして、ReadLockがすべて解放されると待っていたWriteLockに入っています。WriteLockは1つずつ入っており、10番のReadLockもブロックされていることが分かります。

lock構文のような便利な構文が無いのでtry-finallyの冗長さが目立ってしまう書き方ですが、単純なlockより効率的なデータアクセスが見込めるでしょう。

UpgradeableReadLock

さて、話がどんどん大きくなっていきます。

例えばスレッドセーフなDictionaryを設計しているとき、新たな値を渡されたらどういう処理になるでしょうか。
  1. すでにキーが存在するか確かめる
  2. キーが存在しなければキーと値を追加する
  3. キーが存在すればそのキーの値が同じか確かめる
  4. 値が違っていたら値を書き換える
という流れになるかと思います。
ここで、青色で書いたのは読み取りで、赤色で書いたのは書き込みです。
じゃあこれを実装するときは、青の部分のコードはReadLockを掛けて、赤の部分のときはWriteLockを掛ければいいのかと言えば、答えはNoです。

ReadLockをExitしてからWriteLockを取得するまでの間に別のスレッドがWriteLockを取得して値を書き換えたらどうなるでしょう。1.をやって例えばNoと判定したのに、その直後に別スレッドがそのキーを追加していたら2.を実行するときに意図していない状態になってしまいます。
かといって、ReadLockを取得したままWriteLockを取ろうとするとデッドロックを起こします。他のスレッドもReadLock取得中にWriteLockへ昇格しようとしていた場合、互いに他のスレッドのReadLockが解放されるのを待ってしまい、どちらのスレッドもそこから先へ進めなくなってしまうのです。

じゃあどうするか、一つの答えは全体をWriteLockにすれば良いでしょう。ですが、1.や3.を行っている間は別スレッドが読み取り操作をするだけなら許されるべきです。全体をWriteLockにしてしまうとそれすら許されなくなってしまいます。lock構文は条件が厳しすぎて効率が悪いからReadLockとWriteLockに分けようという話になったのに、結局それが生かせなくなってしまいます。


そこで登場するのがUpgradeableReadLockです。
「WriteLockに昇格予定があるReadLock」は唯一にすることで、昇格時にデッドロックを起こすのを防ぎます。逆に言えば、ただのReadLockは昇格予定の無いReadLockということになります。

具体的には、下表のような動きをします。
現在のLock＼取得しようとしているLockReadLockUpgradeableReadLockWriteLock
なし○○○
ReadLock○○×
UpgradeableReadLock○××
WriteLock×××

○がブロックされない（取得できる）Lock、×がブロックされるLockということになります。

実際に動作を試してみましょう。
ReaderWriterLockSlim rwlock = new ReaderWriterLockSlim();
Stopwatch sw = new Stopwatch();
sw.Start();

Parallel.ForEach(Enumerable.Range(0, 12), i => {
    if(i % 3 == 0) {
        try {
            rwlock.EnterUpgradeableReadLock();
            Console.WriteLine($"{sw.ElapsedMilliseconds,4}ms, {i,2}: EnterUpgradeableReadLock");

            Thread.Sleep(TimeSpan.FromSeconds(1));
        }
        finally {
            Console.WriteLine($"{sw.ElapsedMilliseconds,4}ms, {i,2}: ExitUpgradeableReadLock");
            rwlock.ExitUpgradeableReadLock();
        }
    } else if(i % 3 == 1) {
        try {
            rwlock.EnterReadLock();
            Console.WriteLine($"{sw.ElapsedMilliseconds,4}ms, {i,2}: EnterReadLock");

            Thread.Sleep(TimeSpan.FromSeconds(1));
        }
        finally {
            Console.WriteLine($"{sw.ElapsedMilliseconds,4}ms, {i,2}: ExitReadLock");
            rwlock.ExitReadLock();
        }
    } else if(i % 3 == 2) {
        try {
            rwlock.EnterWriteLock();
            Console.WriteLine($"{sw.ElapsedMilliseconds,4}ms, {i,2}: EnterWriteLock");

            Thread.Sleep(TimeSpan.FromSeconds(1));
        }
        finally {
            Console.WriteLine($"{sw.ElapsedMilliseconds,4}ms, {i,2}: ExitWriteLock");
            rwlock.ExitWriteLock();
        }
    }

});

sw.Stop();
　59ms,　0: EnterUpgradeableReadLock
　59ms,　7: EnterReadLock
　59ms,　1: EnterReadLock
　59ms,　4: EnterReadLock
1059ms,　0: ExitUpgradeableReadLock
1060ms,　4: ExitReadLock
1060ms,　1: ExitReadLock
1060ms,　7: ExitReadLock
1061ms,　8: EnterWriteLock
2062ms,　8: ExitWriteLock
2063ms, 11: EnterWriteLock
3064ms, 11: ExitWriteLock
3064ms,　5: EnterWriteLock
4065ms,　5: ExitWriteLock
4065ms,　2: EnterWriteLock
5066ms,　2: ExitWriteLock
5066ms, 10: EnterReadLock
5066ms,　6: EnterUpgradeableReadLock
6068ms, 10: ExitReadLock
6069ms,　6: ExitUpgradeableReadLock
6069ms,　3: EnterUpgradeableReadLock
7069ms,　3: ExitUpgradeableReadLock
7069ms,　9: EnterUpgradeableReadLock
8070ms,　9: ExitUpgradeableReadLock

UpgradeableReadLock中はReadLockは許されていますが、WriteLockや他のUpgradeableReadLockはブロックされているであろうことがわかります。


ちなみに、UpgradeableReadLock中にWriteLockに昇格するには単にEnterWriteLock()～ExitWriteLock()の一連の構文を入れればいいだけです。
ReaderWriterLockSlim rwlock = new ReaderWriterLockSlim();
Stopwatch sw = new Stopwatch();
sw.Start();

Parallel.ForEach(Enumerable.Range(0, 20), i => {
    if(i % 10 == 0) {
        try {
            rwlock.EnterUpgradeableReadLock();
            Console.WriteLine($"{sw.ElapsedMilliseconds,4}ms, {i,2}: EnterUpgradeableReadLock");
            //Thread.Sleep(TimeSpan.FromSeconds(1));
            try {
                rwlock.EnterWriteLock();
                Console.WriteLine($"{sw.ElapsedMilliseconds,4}ms, {i,2}: Upgraded");
                Thread.Sleep(TimeSpan.FromSeconds(1));
            }
            finally {
                Console.WriteLine($"{sw.ElapsedMilliseconds,4}ms, {i,2}: Downgraded");
                rwlock.ExitWriteLock();
            }
            Thread.Sleep(TimeSpan.FromSeconds(1));
        }
        finally {
            Console.WriteLine($"{sw.ElapsedMilliseconds,4}ms, {i,2}: ExitUpgradeableReadLock");
            rwlock.ExitUpgradeableReadLock();
        }
    } else {
        try {
            rwlock.EnterReadLock();
            Console.WriteLine($"{sw.ElapsedMilliseconds,4}ms, {i,2}: EnterReadLock");
            Thread.Sleep(TimeSpan.FromSeconds(1));
        }
        finally {
            Console.WriteLine($"{sw.ElapsedMilliseconds,4}ms, {i,2}: ExitReadLock");
            rwlock.ExitReadLock();
        }
    }
});

sw.Stop();
　49ms,　3: EnterReadLock
　49ms,　1: EnterReadLock
　49ms,　2: EnterReadLock
　49ms,　4: EnterReadLock
　49ms,　0: EnterUpgradeableReadLock
　83ms,　5: EnterReadLock
　86ms,　6: EnterReadLock
　86ms,　7: EnterReadLock
　88ms,　8: EnterReadLock
1050ms,　3: ExitReadLock
1084ms,　1: ExitReadLock
1084ms,　2: ExitReadLock
1085ms,　4: ExitReadLock
1085ms,　5: ExitReadLock
1087ms,　7: ExitReadLock
1087ms,　6: ExitReadLock
1088ms,　8: ExitReadLock
1088ms,　0: Upgraded
2089ms,　0: Downgraded
2089ms, 17: EnterReadLock
2089ms, 15: EnterReadLock
2089ms, 13: EnterReadLock
2089ms, 12: EnterReadLock
2089ms, 14: EnterReadLock
2089ms, 18: EnterReadLock
2089ms, 11: EnterReadLock
2089ms, 16: EnterReadLock
2089ms,　9: EnterReadLock
3037ms, 19: EnterReadLock
3089ms,　0: ExitUpgradeableReadLock
3089ms, 10: EnterUpgradeableReadLock
3092ms, 15: ExitReadLock
3092ms, 17: ExitReadLock
3093ms, 12: ExitReadLock
3093ms, 14: ExitReadLock
3094ms, 11: ExitReadLock
3093ms, 13: ExitReadLock
3095ms, 16: ExitReadLock
3095ms,　9: ExitReadLock
3093ms, 18: ExitReadLock
4037ms, 19: ExitReadLock
4037ms, 10: Upgraded
5038ms, 10: Downgraded
6038ms, 10: ExitUpgradeableReadLock

UpgradeableReadLockからWriteLockに昇格している間は他スレッドがReadLockを取得するのをブロックされていますが、WriteLock終了後（降格後）はUpgradableReadLockをExitしていなくても再びReadLockが取れるようになっていることがわかります。


この節の最初で「UpgradeableReadLockはスレッドセーフなDictionaryを作るのに使える」と言いましたが、多分Dictionary程度だとこの程度の効率化はたかが知れています。
しかし、MVVMなどのフレームワークにおいては大きく効果が出ます。値の変更後に逐一イベントが飛んで、イベントでいろいろな更新作業を行います。 その更新作業中ずっとWriteLockにして他のReadアクセスをブロックしていたら効率がかなり落ちてしまいます。このUpgradeableReadLockそのような場面で威力を発揮する排他制御手法となるでしょう。
投稿者 時刻:
ラベル:

0 件のコメント:

コメントを投稿

登録: コメントの投稿 (Atom)