这是否使用静态队列线程安全?
msdn文档声明静态通用队列是线程安全的。 这是否意味着以下代码是线程安全的? 换句话说,当一个线程将一个int排队并且另一个线程同时将一个int排队时,是否存在问题? 我是否必须为线程安全锁定Enqueue和Dequeue操作?
class Test { public static Queue queue = new Queue(10000); Thread putIntThread; Thread takeIntThread; public Test() { for(int i = 0; i < 5000; ++i) { queue.Enqueue(0); } putIntThread = new Thread(this.PutInt); takeIntThread = new Thread(this.TakeInt); putIntThread.Start(); takeIntThread.Start(); } void PutInt() { while(true) { if(queue.Count 0) {//no need to lock here as only itself can change this condition queue.Dequeue(); } } } }
编辑:我必须使用.NET 3.5
这绝对不是线程安全的。 来自Queue
的文档。
此类型的公共静态(在Visual Basic中为Shared)成员是线程安全的。 任何实例成员都不保证是线程安全的。
只要未修改集合,
Queue
就可以同时支持多个读取器。 即便如此,枚举通过集合本质上不是一个线程安全的过程。 要在枚举期间保证线程安全,可以在整个枚举期间锁定集合。 要允许多个线程访问集合以进行读取和写入,您必须实现自己的同步。
重读你的问题,你似乎对“这种静态成员”这个短语感到困惑 – 它不是在谈论“静态队列”,因为没有这样的东西。 对象不是静态的或不是 – 成员是。 当谈到静态成员时,它正在谈论像Encoding.GetEncoding
( Queue
实际上没有任何静态成员)之类的东西。 实例成员是Enqueue
和Dequeue
类的东西 – 与类型实例相关的成员而不是类型本身。
因此,您需要为每个操作使用锁定,或者如果您使用的是.NET 4,请使用ConcurrentQueue
。
是的,正如这里所说的,静态实例的实例成员与静态成员不同,并且只有后者才能保证线程安全,因此您必须锁定入队和出列操作。
如果锁定被certificate是一个瓶颈,那么队列是以无锁方式编写的更简单的集合之一,只要一个不需要Queue
提供的完整ICollection
实现:
internal sealed class LockFreeQueue { private sealed class Node { public readonly T Item; public Node Next; public Node(T item) { Item = item; } } private volatile Node _head; private volatile Node _tail; public LockFreeQueue() { _head = _tail = new Node(default(T)); } #pragma warning disable 420 // volatile semantics not lost as only by-ref calls are interlocked public void Enqueue(T item) { Node newNode = new Node(item); for(;;) { Node curTail = _tail; if (Interlocked.CompareExchange(ref curTail.Next, newNode, null) == null) //append to the tail if it is indeed the tail. { Interlocked.CompareExchange(ref _tail, newNode, curTail); //CAS in case we were assisted by an obstructed thread. return; } else { Interlocked.CompareExchange(ref _tail, curTail.Next, curTail); //assist obstructing thread. } } } public bool TryDequeue(out T item) { for(;;) { Node curHead = _head; Node curTail = _tail; Node curHeadNext = curHead.Next; if (curHead == curTail) { if (curHeadNext == null) { item = default(T); return false; } else Interlocked.CompareExchange(ref _tail, curHeadNext, curTail); // assist obstructing thread } else { item = curHeadNext.Item; if (Interlocked.CompareExchange(ref _head, curHeadNext, curHead) == curHead) { return true; } } } } #pragma warning restore 420 }
此队列只有一个Enqueue
和TryDequeue
(如果队列为空,则返回false)方法。 使用互锁增量和减量添加Count属性是微不足道的(确保在实际属性中易于读取count字段),但除此之外,添加任何无法写入委托给其中一个成员的内容变得非常棘手已经定义,或者在构造期间发生(在这种情况下,你将只有一个线程在那时使用它,除非你做了一些非常奇怪的事情)。
实现也是等待的,好像一个线程的动作不会阻止另一个线程进行(如果一个线程在第二个线程尝试这样做时进入入队过程的一半,第二个线程将完成第一个线程)线程的工作)。
尽管如此,我还是要等到锁定实际certificate是一个瓶颈(除非你只是在尝试;与异国情调一起玩,与熟悉的人一起工作)。 实际上,在许多情况下,这将certificate比锁定Queue
更昂贵,特别是因为它不太擅长将项目保持在内存中彼此靠近,因此您可能会发现大量紧密连续的操作不太适合那个原因。 锁定通常非常便宜,只要没有频繁的锁定争用。
编辑:
我现在有时间补充上述工作原理的说明。 我通过阅读其他人的相同想法的版本来写这篇文章,为自己写这个想法来复制这个想法,然后与我之后阅读的版本进行比较,并发现这是一个非常有用的练习。
让我们从非锁定免费实现开始。 这是一个单独的链表。
internal sealed class NotLockFreeYetQueue { private sealed class Node { public readonly T Item; public Node Next{get;set;} public Node(T item) { Item = item; } } private Node _head; private Node _tail; public NotLockFreeYetQueue() { _head = _tail = new Node(default(T)); } public void Enqueue(T item) { Node newNode = new Node(item); _tail.Next = newNode; _tail = newNode; } public bool TryDequeue(out T item) { if (_head == _tail) { item = default(T); return false; } else { item = _head.Next.Item; _head = _head.Next; return true; } } }
到目前为止关于实施的一些注释。
Item
和Next
可以合理地为字段或属性。 因为它是一个简单的内部类,一个必须readonly
而另一个是“哑”读写(在getter或setter中没有逻辑),这里真的没什么可供选择的。 我在这里做了一个属性纯粹是因为以后不会工作,当我们到达那里时我想谈谈这个。
将_head
和_tail
开始指向一个sentinel而不是null
通过不必为空队列设置特殊情况简化了事情。
因此,在成为新尾部之前,排队将创建一个新节点并将其设置为_tail
的Next
属性。 出列将检查是否为空,如果它不为空,则从头节点获取值并将head设置为旧头的Next
属性的节点。
此时需要注意的另一件事是,由于新节点是根据需要而不是在预先分配的数组中创建的,因此在正常使用中它将比Queue
具有更差的性能。 这不会变得更好,事实上我们现在要做的每件事都会使单线程性能变差。 同样,只有在激烈的争论中,这才会击败锁定的Queue
。
让我们排队无锁。 我们将使用Interlocked.CompareExchange()
。 这将第一个参数与第三个参数进行比较,如果它们相等,则将第一个参数设置为第二个参数。 在任何情况下,它都返回旧值(无论是否覆盖)。 比较和交换是作为一个primefaces操作完成的,因此本身就是线程安全的,但是我们需要做更多的工作来使这些操作的组合也是线程安全的。
CompareExchange和其他语言中的等价物有时缩写为CAS(用于Compare-And-Swap)。
使用它们的常用方法是循环,我们首先获得通过正常读取覆盖的值(请记住.NET读取的32位值,较小的值和引用类型始终是primefaces的)并尝试覆盖它如果它没有改变,循环直到我们成功:
private sealed class Node { public readonly T Item; public Node Next; public Node(T item) { Item = item; } } /* ... */ private volatile Node _tail; /* ... */ public void Enqueue(T item) { Node newNode = new Node(item); for(;;) { Node curTail = _tail; if(Interlocked.CompareExchange(ref curTail.Next, newNode, null) == null) { _tail = newNode; return; } } }
我们想要添加到尾部的Next
只有它是null
– 如果没有写入它的另一个线程。 所以,我们做一个只有在这种情况下才会成功的CAS。 如果是,我们将_tail
设置为新节点,否则我们再试一次。
接下来必须改为成为一个领域,我们不能用属性来做。 我们还使_tail
volatile
以便_tail
在所有CPU缓存中都是新鲜的( CompareExchange
具有易失性语义,因此它不会因为缺乏波动性而被打破,但它可能会经常旋转而不是必要,我们将会做更多的事情_tail
也)。
这是无锁的,但不是等待的。 如果一个线程到CAS,但尚未写入_tail,然后暂时没有任何CPU时间,那么所有其他尝试入队的线程将继续循环,直到它被安排并设法这样做。 如果线程被中止或暂停很长时间,这将导致一种永久的活锁。
因此,如果我们处于CAS失败的状态,我们处于这种情况。 我们可以通过执行其他线程的工作来解决这个问题:
for(;;) { Node curTail = _tail; if(Interlocked.CompareExchange(ref curTail.Next, newNode, null) == null) { Interlocked.CompareExchange(ref _tail, newNode, curTail); //CAS in case we were assisted by an obstructed thread. return; } else { Interlocked.CompareExchange(ref _tail, curTail.Next, curTail); //assist obstructing thread. } }
现在,在大多数情况下,写入curTail.Next
的线程会将新节点分配给_tail
– 但是如果已经完成则通过CAS。 但是,另一个线程无法写入curtail.Next
它可以尝试将curTail.Next
分配给_tail
来完成第一个线程的工作并继续使用它。
所以,一个无锁,无等待的入队。 是时候出发了。 首先让我们考虑一下我们不怀疑队列是空的情况。 就像入队一样,我们将首先获得我们感兴趣的节点的本地副本; _head
, _tail
和_head.Next
(对于空队列,再次不使用_head.Next
或尾部会使生活更轻松;这意味着在任何状态下读取_head.Next
都是安全的)。 和排队一样,我们将依赖于波动性,这次不仅仅是_tail
,而是_head
,因此我们将其更改为:
private volatile Node _head;
我们将TryDequeue更改为:
public bool TryDequeue(out T item) { Node curHead = _head; Node curTail = _tail; Node curHeadNext = curHead.Next; if (_head == _tail) { item = default(T); return false; } else { item = curHeadNext.Item; if (Interlocked.CompareExchange(ref _head, curHeadNext, curHead) == curHead) return true; } }
空队列案例现在不正确,但我们会回过头来看。 将item设置为curHeadNext.Item
是安全的,就好像我们没有完成操作一样,我们将再次覆盖它,但是我们必须使操作写入_head
primefaces并保证只有在_head
未更改时才会发生。 如果没有,那么_head
已被另一个线程更新,我们可以再次循环(不需要为该线程工作,它已经完成了所有会影响我们的东西)。
现在考虑如果_head == _tail
会发生什么。 可能它是空的,但可能是_tail.Next
(与curHeadNext
相同)由enqueue写入。 在这种情况下,我们更可能想要的不是空quque的结果,而是我们将部分排队的项目出列的结果。 所以,我们协助该线程并再次继续循环:
if (curHead == curTail) { if (curHeadNext == null) { item = default(T); return false; } else Interlocked.CompareExchange(ref _tail, curHeadNext, curTail); }
最后,剩下的唯一问题是我们不断收到420警告,因为我们将volatile字段传递给byref
方法。 这通常会阻止volatile语义(因此警告),但不会与CompareExchange
(因此我们这样做)。 我们可以禁用警告,包括注释来解释我们为什么这样做(我尝试永远不会在没有正当评论的情况下禁用警告)并且我们已经提供了之前给出的代码。
请注意,我们在GC支持框架中执行此操作非常重要。 如果我们还必须处理释放,那将会变得更加复杂。
MSDN声明的是Queue的静态方法是线程安全的,而不是静态实例的实例方法是线程安全的。
是的,你必须像MSDN所说的那样锁定
要允许多个线程访问集合以进行读取和写入,您必须实现自己的同步。