面接の準備をしていて、次の質問に出くわしました。試してみましたが、「ロック」なしでスレッドセーフなコレクションを含むクラスを作成できるものは見つかりませんでした。解決策を知っている場合は、助けてください。
Object から派生した C# クラスを作成し、次のメソッドを実装します。
要件：
ローカル コピーで作業し、競合をチェックしながらグローバル コレクションとアトミックにスワップしようとすることで、コレクションのロックなしの変更を実現する方法を次に示します。
public class NonLockingCollection
{
private List<string> collection;
public NonLockingCollection()
{
// Initialize global collection through a volatile write.
Interlocked.CompareExchange(ref collection, new List<string>(), null);
}
public void AddString(string s)
{
while (true)
{
// Volatile read of global collection.
var original = Interlocked.CompareExchange(ref collection, null, null);
// Add new string to a local copy.
var copy = original.ToList();
copy.Add(s);
// Swap local copy with global collection,
// unless outraced by another thread.
var result = Interlocked.CompareExchange(ref collection, copy, original);
if (result == original)
break;
}
}
public override string ToString()
{
// Volatile read of global collection.
var original = Interlocked.CompareExchange(ref collection, null, null);
// Since content of global collection will never be modified,
// we may read it directly.
return string.Join(",", original);
}
}
編集：揮発性の読み取りと書き込みを暗黙的に実行するために使用すると混乱が生じるため、代わりに呼び出しを使用Interlocked.CompareExchangeして同等のコードを以下に投稿します。Thread.MemoryBarrier
public class NonLockingCollection
{
private List<string> collection;
public NonLockingCollection()
{
// Initialize global collection through a volatile write.
collection = new List<string>();
Thread.MemoryBarrier();
}
public void AddString(string s)
{
while (true)
{
// Fresh volatile read of global collection.
Thread.MemoryBarrier();
var original = collection;
Thread.MemoryBarrier();
// Add new string to a local copy.
var copy = original.ToList();
copy.Add(s);
// Swap local copy with global collection,
// unless outraced by another thread.
var result = Interlocked.CompareExchange(ref collection, copy, original);
if (result == original)
break;
}
}
public override string ToString()
{
// Fresh volatile read of global collection.
Thread.MemoryBarrier();
var original = collection;
Thread.MemoryBarrier();
// Since content of global collection will never be modified,
// we may read it directly.
return string.Join(",", original);
}
}
質問に基づいて、スレッドセーフ要件を処理するオブジェクト内に並行コレクションを追加できるはずです。彼らは、使用する内部コレクションのタイプを指定しませんでした。
並行コレクション名前空間からコレクションの 1 つを実装して、これを達成できるはずです。
http://msdn.microsoft.com/en-us/library/system.collections.concurrent.aspx
私の解決策。基本的に、Interlocked.Exchange と AutoResetEvents を使用してロックを模倣します。いくつかの簡単なテストを行い、動作しているようです。
public class SharedStringClass
{
private static readonly int TRUE = 1;
private static readonly int FALSE = 0;
private static int allowEntry;
private static AutoResetEvent autoResetEvent;
private IList<string> internalCollection;
public SharedStringClass()
{
internalCollection = new List<string>();
autoResetEvent = new AutoResetEvent(false);
allowEntry = TRUE;
}
public void AddString(string strToAdd)
{
CheckAllowEntry();
internalCollection.Add(strToAdd);
// set allowEntry to TRUE atomically
Interlocked.Exchange(ref allowEntry, TRUE);
autoResetEvent.Set();
}
public string ToString()
{
CheckAllowEntry();
// access the shared resource
string result = string.Join(",", internalCollection);
// set allowEntry to TRUE atomically
Interlocked.Exchange(ref allowEntry, TRUE);
autoResetEvent.Set();
return result;
}
private void CheckAllowEntry()
{
while (true)
{
// compare allowEntry with TRUE, if it is, set it to FALSE (these are done atomically!!)
if (Interlocked.CompareExchange(ref allowEntry, FALSE, TRUE) == FALSE)
{
autoResetEvent.WaitOne();
}
else
{
break;
}
}
}
}
ノンブロッキング リンク リストを作成できます。たとえば、このようなものです。
.net フレームワークにはCompareExchange(Object, Object, Object)、リスト全体をロックすることなく安全なコードを記述できるようなメソッドが用意されています。
最も簡単な解決策は、 type のフィールドを持つことstring[]です。呼び出し元が文字列を追加したいときはいつでも、新しい項目が追加された新しい配列を作成し、それを古いものと交換します。
このモデルは同期を必要としません。同時書き込みは許容されませんが、同時読み取りは可能です。