MSDN上SimplePriorityQueue示例中的严重错误
本文关键字:严重错误 SimplePriorityQueue MSDN | 更新日期: 2023-09-27 18:01:17
我需要使用并发优先级队列,并且我正在考虑适应如何:将边界和阻塞功能添加到MSDN上的集合教程中给出的SimplePriorityQueue<TPriority, TValue>
示例。然而,我对上述样本中似乎存在的漏洞的严重性感到惊讶。有人能证实这些问题是否真的存在吗?
1) TryAdd
和ToArray
之间存在竞争危险,这可能导致ArgumentException
从后者抛出。TryAdd
方法首先向内部队列添加一个项目,然后增加m_count
计数器。另一方面,ToArray
首先初始化一个大小为m_count
的新数组,然后将内部队列复制到该数组中。如果在执行ToArray
的同时调用TryAdd
,那么ToArray
最终可能会尝试复制比它在数组中分配的空间更多的项目,导致CopyTo
调用抛出ArgumentException
。
private ConcurrentQueue<KeyValuePair<int, TValue>>[] _queues;
private int m_count;
// ...
// IProducerConsumerCollection members
public bool TryAdd(KeyValuePair<int, TValue> item)
{
_queues[item.Key].Enqueue(item);
Interlocked.Increment(ref m_count);
return true;
}
public int Count
{
get { return m_count; }
}
public KeyValuePair<int, TValue>[] ToArray()
{
KeyValuePair<int, TValue>[] result;
lock (_queues)
{
result = new KeyValuePair<int, TValue>[this.Count];
// *** context switch here; new item gets added ***
int index = 0;
foreach (var q in _queues)
{
if (q.Count > 0)
{
q.CopyTo(result, index); // *** ArgumentException ***
index += q.Count;
}
}
return result;
}
}
2) GetEnumerator
方法中存在另一个竞争危险:内部队列的更新之间没有同步。
public IEnumerator<KeyValuePair<int, TValue>> GetEnumerator()
{
for (int i = 0; i < priorityCount; i++)
{
foreach (var item in _queues[i])
yield return item;
}
}
考虑下面的代码片段,它从队列中获取一个项目,并以递增的优先级重新添加它:
if (queue.TryTake(out item) && item.Key < maxPriority - 1)
queue.TryAdd(new KeyValuePair<int, string>(item.Key + 1, item.Value))
如果上面的代码片段与枚举并发运行,则可以期望该项最多出现一次,要么以原始优先级,要么以递增的优先级出现,或者可能根本不出现。人们不会期望项目在两个优先级上都出现两次。然而,由于GetEnumerator
在其内部队列上按顺序迭代,因此它不能防止队列之间的顺序不一致。
3)公共Count
属性可以返回陈旧的值,因为它读取共享m_count
字段而没有任何内存围栏。如果一个消费者在一个循环中访问这个属性,而这个循环本身并没有产生内存栅栏,就像下面这样,他们可能会被困在一个无限循环中,尽管其他线程已经将项目添加到队列中。
while (queue.Count == 0)
{ }
在读取共享变量时需要内存围栏已经在其他几个帖子中讨论过了:
- 如何正确读取互锁。增量输入字段?
- 读取被其他线程互锁更新的int 并发互锁和读需要内存屏障或锁定吗?
4)在_queues
数组的初始化和SimplePriorityQueue
构造函数的完成之间没有内存障碍。当另一个线程上的外部消费者在初始化完成之前调用TryAdd
并访问_queues
(或在其内存缓存上显示为已完成)时,可能会出现竞争危险。这将在我的另一个关于构造函数和内存屏障的问题中进一步讨论。
5) TryTake
和ToArray
通过使用lock
关键字进行保护。除了不充分(由于上面讨论的错误)之外,这也违背了设计并发集合的整个目的。考虑到它的缺点,我认为最好的方法是将内部的ConcurrentQueue
结构降级为普通的Queue
,到处添加锁,并开始将其视为非并发但线程安全的结构。
我认为这取决于你如何使用这个类。如果您将自己限制为TryAdd
和TryTake
(这是BlockingCollection<T>
所依赖的两个主要内容),您应该不会有任何问题,并且您将拥有一个非常快的锁定最小优先级队列。
如果您开始使用Count
, CopyTo
或任何其他方法,您可能会遇到您指出的问题