我正在撰寫一個管理一個集合的應用程式，該集合需要在多執行緒環境中頻繁地對專案進行入隊和出隊。對于單執行緒，一個簡單的 List 可能就足夠了，但是環境的并發性質會帶來一些問題。
這是摘要：
結構體需要有 bool TryAdd(T) 方法，最好是 Add(TKey, TValue);
該結構需要有一個 T TryRemove() 方法，該方法采用隨機或最好是第一個添加的專案（實質上實作了 FIFO 佇列）；
該結構需要有一個bool TryRemove(T)方法，最好是Remove(TKey)；
到目前為止，我有三個想法，都有他們的問題：
- 實作一個包含 ConcurrentDictionary<TKey, TValue> 和 ConcurrentQueue 的類，如下所示：
internal class ConcurrentQueuedDictionary<TKey, TValue> where TKey : notnull
{
ConcurrentDictionary<TKey, TValue> _dictionary;
ConcurrentQueue<TKey> _queue;
object _locker;
public bool TryAdd(TKey key, TValue value)
{
if (!_dictionary.TryAdd(key, value))
return false;
lock (_locker)
_queue.Enqueue(key);
return true;
}
public TValue TryRemove()
{
TKey key;
lock (_locker) {
if (_queue.IsEmpty)
return default(TValue);
_queue.TryDequeue(out key);
}
TValue value;
if (!_dictionary.Remove(key, out value))
throw new Exception();
return value;
}
public bool TryRemove(TKey key)
{
lock (_locker)
{
var copiedList = _queue.ToList();
if (copiedList.Remove(key))
return false;
_queue = new(copiedList);
}
return _dictionary.TryRemove(key, out _);
}
}
但這將需要一個 Lock on Remove(T)，因為它需要初始 Queue 的完整深層副本而沒有洗掉的專案，同時不允許從其他執行緒讀取，這意味著至少 Remove() 也會有這個鎖，這是意味著經常進行的操作；
- 實作一個包含 ConcurrentDictionary<TKey, TValue> 和 ConcurrentDictionary<int order, TKey> 的類，其中 order 在 TryAdd 上定義，具有兩個屬性 _addOrder 和 _removeOrder，如下所示：
internal class ConcurrentQueuedDictionary<TKey, TValue> where TKey : notnull
{
ConcurrentDictionary<TKey, TValue> _dictionary;
ConcurrentDictionary<int, TKey> _order;
int _addOrder = 0;
int _removeOrder = 0;
public bool TryAdd(TKey key, TValue value)
{
if (!_dictionary.TryAdd(key, value))
return false;
if (!_order.TryAdd(unchecked(Interlocked.Increment(ref _addOrder)), key))
throw new Exception(); //Operation faulted, mismatch of data in _order
return true;
}
public TValue TryRemove()
{
TKey key;
if (!(_order.Count > 0 && _order.Remove(unchecked(Interlocked.Increment(ref _removeOrder)), out key)))
return default(TValue);
return _dictionary[key];
}
public bool TryRemove(TKey key)
{
if (!_order.Remove(_order.Where(item => item.Value.Equals(key)).First().Key, out _))
return false;
if (!_dictionary.Remove(key, out _))
throw new Exception();
return true;
}
}
但我很確定只是表達這個實作已經把我放在了某個地方的精神病觀察名單上，因為要讓它正常作業將是一場受虐狂的噩夢；
- 直接鎖定串列，因為無論如何選項1都需要鎖定。
有任何想法嗎？我有點被這個問題難住了，因為我對并發集合沒有最好的掌握。我需要自定義 IProducerConsumerCollection 嗎？是否有可能同時擁有對并發集合元素的隨機（或排隊）和特定訪問？你們有沒有人遇到過這個問題，也許我看錯了這個問題？
編輯：錯別字，格式
uj5u.com熱心網友回復：
通過組合內置的并發集合來創建這樣的并發結構應該幾乎是不可能的，當然前提是正確性是最重要的，并且嚴格禁止競爭條件。好訊息是，lock每秒獲取幾千次遠未達到爭用開始成為問題的極限。根據我的實驗，您需要每秒至少 100,000 次操作才能開始（稍微）擔心爭用，前提是這些操作是輕量級的（它們具有 O(1) 復雜性并且它們的持續時間以納秒為單位測量）。
實作 O(1) 操作復雜性的一種方法是將 aLinkedList<T>和 a結合起來Dictionary<K,V>：
/// <summary>
/// Represents a thread-safe first in-first out (FIFO) collection of key/value pairs,
/// where the key is unique.
/// </summary>
public class ConcurrentKeyedQueue<TKey, TValue>
{
private readonly LinkedList<KeyValuePair<TKey, TValue>> _queue;
private readonly Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>>
_dictionary;
public ConcurrentKeyedQueue(IEqualityComparer<TKey> comparer = default)
{
_queue = new();
_dictionary = new(comparer);
}
public int Count { get { lock (_queue) return _queue.Count; } }
public bool TryEnqueue(TKey key, TValue value)
{
lock (_queue)
{
if (_dictionary.ContainsKey(key)) return false;
LinkedListNode<KeyValuePair<TKey, TValue>> node = new(new(key, value));
_queue.AddLast(node);
_dictionary.Add(key, node);
Debug.Assert(_queue.Count == _dictionary.Count);
return true;
}
}
public bool TryDequeue(out TKey key, out TValue value)
{
lock (_queue)
{
if (_queue.Count == 0) { key = default; value = default; return false; }
var node = _queue.First;
(key, value) = node.Value;
_queue.RemoveFirst();
bool removed = _dictionary.Remove(key);
Debug.Assert(removed);
Debug.Assert(_queue.Count == _dictionary.Count);
return true;
}
}
public bool TryTake(TKey key, out TValue value)
{
lock (_queue)
{
bool removed = _dictionary.Remove(key, out var node);
if (!removed) { value = default; return false; }
_queue.Remove(node);
(_, value) = node.Value;
Debug.Assert(_queue.Count == _dictionary.Count);
return true;
}
}
public KeyValuePair<TKey, TValue>[] ToArray()
{
lock (_queue) return _queue.ToArray();
}
}
這種組合也用于創建LRU 快取。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/486664.html