Aタイプとタイプのイベントを生成するスレッドがたくさんありBます。
私のプログラムはこれらのイベントを受け取り、メッセージでラップしてネットワーク経由で送信します。メッセージは、1つのAイベント、1つのBイベント、または1つのAイベントと1つのイベントのいずれかを保持できますB。
SendMessage(new Message(a: 1, b: null));
SendMessage(new Message(a: null, b: 2 ));
SendMessage(new Message(a: 3, b: 4 ));
タイプのイベントはA非常に頻繁に発生しますが、タイプのイベントはBそれほど頻繁には発生しません。したがって、スレッドがBイベントを生成するとき、私のプログラムは、別のスレッドがイベントを生成するかどうかを確認するために少し待機し、可能であればイベントとAイベントを結合します。AB
これが私のコードです：
object gate = new object();
int? pendingB;
Message WrapA(int a, int millisecondsTimeout)
{
int? b;
lock (gate)
{
b = pendingB;
pendingB = null;
Monitor.Pulse(gate);
}
return new Message(a, b);
}
Message WrapB(int b, int millisecondsTimeout)
{
lock (gate)
{
if (pendingB == null)
{
pendingB = b;
Monitor.Wait(gate, millisecondsTimeout);
if (pendingB != b) return null;
pendingB = null;
}
}
return new Message(null, b);
}
これは今のところ機能します。ただし、2つの問題があります。
イベントがたくさんあり、
Aイベントがたくさんある場合B、アルゴリズムはあまり効率的ではありません。十分なイベントがある場合でも、特定の割合のBイベントのみがイベントに関連付けられます。AAAしばらくの間イベントが生成されない場合（まれですが、不可能ではありません）、アルゴリズムは完全に不公平です。Bイベントを生成する1つのスレッドは毎回待機する必要がありますが、他のすべてのスレッドはBイベントをすぐに送信できます。
アルゴリズムの効率と公平性をどのように改善できますか？
制約：
• WrapAそしてWrapB、短い決定論的な時間内に終了する必要があります。
• SendMessageロックの外部で呼び出す必要があります。
•以外に利用可能な同期メカニズムはありませんgate。
•利用可能な追加のスレッド、タスク、タイマーなどはありません。
•A通常の場合、タイプのイベントは非常に頻繁に発生するため、ビジーウェイトインWrapBは問題ありません。
ベンチマークとして使用できるテストプログラムは次のとおりです。
public static class Program
{
static int counter0 = 0;
static int counterA = 0;
static int counterB = 0;
static int counterAB = 0;
static void SendMessage(Message m)
{
if (m != null)
if (m.a != null)
if (m.b != null)
Interlocked.Increment(ref counterAB);
else
Interlocked.Increment(ref counterA);
else
if (m.b != null)
Interlocked.Increment(ref counterB);
else
Interlocked.Increment(ref counter0);
}
static Thread[] Start(int threadCount, int eventCount,
int eventInterval, int wrapTimeout, Func<int, int, Message> wrap)
{
Thread[] threads = new Thread[threadCount * eventCount];
for (int i = 0; i < threadCount; i++)
{
for (int j = 0; j < eventCount; j++)
{
int k = i * 1000 + j;
int l = j * eventInterval + i;
threads[i * eventCount + j] = new Thread(() =>
{
Thread.Sleep(l);
SendMessage(wrap(k, wrapTimeout));
});
threads[i * eventCount + j].Start();
}
}
return threads;
}
static void Join(params Thread[] threads)
{
for (int i = 0; i < threads.Length; i++)
{
threads[i].Join();
}
}
public static void Main(string[] args)
{
var wrapper = new MessageWrapper();
var sw = Stopwatch.StartNew();
// Only A events
var t0 = Start(10, 40, 7, 1000, wrapper.WrapA);
Join(t0);
// A and B events
var t1 = Start(10, 40, 7, 1000, wrapper.WrapA);
var t2 = Start(10, 10, 19, 1000, wrapper.WrapB);
Join(t1);
Join(t2);
// Only B events
var t3 = Start(10, 20, 7, 1000, wrapper.WrapB);
Join(t3);
Console.WriteLine(sw.Elapsed);
Console.WriteLine("0: {0}", counter0);
Console.WriteLine("A: {0}", counterA);
Console.WriteLine("B: {0}", counterB);
Console.WriteLine("AB: {0}", counterAB);
Console.WriteLine("Generated A: {0}, Sent A: {1}",
10 * 40 + 10 * 40, counterA + counterAB);
Console.WriteLine("Generated B: {0}, Sent B: {1}",
10 * 10 + 10 * 20, counterB + counterAB);
}
}