マルチスレッド環境で排他制御する時に、先に要求したスレッドほど先に実行させたい、ということを考える機会がありました。
.NETプログラミングで有名な排他制御方法は
Monitor
や
ManualResetEvent でしょうか。C#ではMonitorクラスを便利に使えるlockステートメントもあり、私もよく使います。しかしManualResetEventは単一もしくは複数のスレッドを待たせて一気にスタートさせるものですし、Monitorは待ち状態にある複数のスレッドに対してロックを順番に与えてはくれません。後者はどういうことかというと、
- スレッド1は既に排他ロックを取得し実行中
- スレッド2がロックを求めて待ち状態に入った
- スレッド2より後にスレッド3がロックを求めて待ち状態に入った
という状態でスレッド1がロックを開放した場合、次に排他ロックを取得するのは…どちらか分かりません。待ちスレッドが1個や2個では発生しにくいかもしれませんが、10や20スレッド待たせると順番通りにロックさせてくれないのが分かると思います。
最初に目をつけたのがQueue ジェネリッククラス。
using System.Collections.Generic;
using System.Threading;
class FIFOLock
{
Queue<ManualResetEvent> eventQueue = new Queue<ManualResetEvent>();
public void GetLock()
{
ManualResetEvent myEvent = new ManualResetEvent(false);
lock(eventQueue)
{
eventQueue.Enqueue(myEvent);
if(myEvent.Equals(eventQueue.Peek())) return; // No thread is locking resource
}
myEvent.WaitOne();
}
public void ReleaseLock()
{
lock{eventQueue)
{
eventQueue.Dequeue(); // Remove ManualResetEvent of this thread
eventQueue.Peek().Set(); // Signal to next waiting thread
}
}
}
実際にVisualStudioに打ち込んでないので、文法間違いなどあるかもしれません。打ち込まなかったのは考えている途中で「あ、lock使ってるからダメだ、これは」と思ったから。複数のスレッドがGetLock()に飛び込んできて競合待ち状態になったときに、次にeventQueueにアクセスできるスレッドが不定なため、順番の追い越しが発生する可能性があります。eventQueueがロックされている時間は僅かで、複数のスレッドがGetLock内で競合する確率は低いとはいえ、完璧ではない。ちなみに.NET 4.0ではConcurrentQueue なんていうスレッドセーフなQueueが登場したので、使えるかもしれません。
次にInterlocked クラスを使うこと。Incrementメソッドを使えば確実に早くやってきたスレッドから小さい番号を割り当てることができます。しかし単に数字が分かっただけ。各スレッドに自分の順番が来るまで待たせる上手い方法が分かりません。唯一思いついたのが、もう一個Interlockedで管理される整数を用意して、処理が終わったスレッドはこの数を増やしていくこと。銀行とかにある順番待ち整理券がイメージしやすいでしょうか。前者の変数が整理券の番号で、後者が「○番のカードをお持ちの方…」としゃべる機械。自分の番号が来たスレッドは処理を開始。
ただこの方法は各スレッドが自分の順番が来たかどうかポーリングでチェックせねばならず、CPU負荷が高くなる欠点があります。負荷の低いManualResetEventなどを使いたいのですが、Interlocked.Incrementで得られた数字とManualResetEventを結び付けようとする(Dictionary<int, ManualResetEvent>とか)所でスレッドセーフにする方法が思いつかず。
現時点の答えはReaderWriterLock を使い、全スレッドAcquireWriterLockを呼び出すこと。とりあえず100スレッドAcquireWriterLockを呼び出して待ち状態に入るプログラムを書いてみましたが、順番通りにスレッドがロックを取得していました。こういう使い方って、保障されているのでしょうか? ちなみにReaderLockされている状態ではAcquireWriterLockは待ち状態にされますが、その後にAcquireReaderLockのスレッドが来ると待ち状態のAcquireWriterLockを平気で追い抜きます(複数同時ReaderLockを認めているから)。
[2011/8/2 追記] 最終文訂正(AcquireReaderLock→AcquireWriterLock)
RSS2.0
Y:
Comments