非阻塞队列审查 [英] non-blocking queue review

问题描述

任何人都在评论这个非阻塞队列的实现是否是
声音？


///< summary>

/// NonBlockingQueue的摘要描述。

///建模后：
http://www.cs.rochester.edu/u/scott/...de/queues.html
///< / summary>

公共类NonBlockingQueue

{

队列Q;

int count;


public int Count

{

get {return count; }

}


内部类Node

{

公共对象值; //用户对象。

公共对象下一个; //下一个节点。


公共节点（对象值，节点下一个）

{

this.value = value;

this.next = next;

}

}


内部类队列

{

public object Head = null; //从头开始。

公共对象Tail = null; //入队尾巴。

}


公共NonBlockingQueue（）

{

Q = new Queue（）;

Node node = new Node（null，null）;

Q.Head = node;

Q.Tail =节点;

}


public void Enqueue（对象值）

{

object node = new Node（value，null）;

object tail;

object next;

while（true）

{

tail = Q.Tail;

next =（（Node）tail）.next;

if（tail == Q.Tail ）//尾巴是否等于队列尾巴。

{

if（next == null）

{

//尝试链接链表末尾的节点

if（next == Interlocked.CompareExchange（ref（（Node）tail）.next，node，

下一步））

休息; //入队完成;退出。

}

其他//尾巴没有指向null;将尾巴摆动到下一个节点。

Interlocked.CompareExchange（参考Q.Tail，next，tail）;

}

} //结束循环

//入队已完成。尝试将Tail摆动到插入的节点。

Interlocked.CompareExchange（ref Q.Tail，node，tail）;

Interlocked.Increment（ref count）;

}


公共对象Dequeue（）

{

对象值;

对象头;

对象尾;

对象下一个;

while（true）

{

head = Q.Head;

tail = Q.Tail;

next =（（Node）head）.next;

if（head == Q.Head）

{

if（head == tail）//队列是空的还是Tail落后？

{

if（next == null）//队列是空的吗？

返回null; //队列是空的。

Interlocked.CompareExchange（参考Q.Tail，接下来，尾巴）;

}

其他//不需要处理Tail。

{

//在交换前读取用户值。

//否则，另一个dequeue可能释放下一个节点。

value =（（Node）next）.value;

if（Interlocked.CompareExchange（ref Q.Head，next，head）== head）

{

Interlocked.Decrement（ref count）;

返回值;

}

}

}

} //结束循环。

} //结束出队

} //结束班级


-

William Stacey，MVP

Anyone care to comment on if this non-blocking queue implementation is
sound?

/// <summary>
/// Summary description for NonBlockingQueue.
/// Modeled after:
http://www.cs.rochester.edu/u/scott/...de/queues.html
/// </summary>
public class NonBlockingQueue
{
Queue Q;
int count;

public int Count
{
get { return count; }
}

internal class Node
{
public object value; // User object.
public object next; // Next Node.

public Node(object value, Node next)
{
this.value = value;
this.next = next;
}
}

internal class Queue
{
public object Head = null; // Dequeue from head.
public object Tail = null; // Enqueue to tail.
}

public NonBlockingQueue()
{
Q = new Queue();
Node node = new Node(null, null);
Q.Head = node;
Q.Tail = node;
}

public void Enqueue(object value)
{
object node = new Node(value, null);
object tail;
object next;
while(true)
{
tail = Q.Tail;
next = ((Node)tail).next;
if ( tail == Q.Tail ) // Does tail equal Queue Tail.
{
if ( next == null )
{
// Try to link node at the end of the linked list
if ( next == Interlocked.CompareExchange(ref ((Node)tail).next, node,
next) )
break; // enqueue is done; exit.
}
else // Tail was not pointing to null; Swing tail to next node.
Interlocked.CompareExchange(ref Q.Tail, next, tail);
}
} // End loop
// Enqueue is done. Try to swing Tail to the inserted node.
Interlocked.CompareExchange(ref Q.Tail, node, tail);
Interlocked.Increment(ref count);
}

public object Dequeue()
{
object value;
object head;
object tail;
object next;
while(true)
{
head = Q.Head;
tail = Q.Tail;
next = ((Node)head).next;
if ( head == Q.Head )
{
if ( head == tail ) // Is queue empty or Tail falling behind?
{
if ( next == null ) // Is queue empty?
return null; // Queue is empty.
Interlocked.CompareExchange(ref Q.Tail, next, tail);
}
else // No need to deal with Tail.
{
// Read user value before exchange.
// Otherwise, another dequeue might free the next node.
value = ((Node)next).value;
if (Interlocked.CompareExchange(ref Q.Head, next, head) == head)
{
Interlocked.Decrement(ref count);
return value;
}
}
}
} // End loop.
} // End Dequeue
} // End Class

--
William Stacey, MVP

推荐答案

William Stacey [MVP ]< st *********** @ mvps.org>写道：

William Stacey [MVP] <st***********@mvps.org> wrote:

任何人都在关注这个非阻塞队列实现是否健全？


好​​吧，它里面有一些奇怪的代码：

tail = Q.Tail;
next =（（Node） tail）.next;
if（tail == Q.Tail）//尾部是否等于队列尾部。

Anyone care to comment on if this non-blocking queue implementation is
sound?
Well, it''s got some very odd code in it:
tail = Q.Tail;
next = ((Node)tail).next;
if ( tail == Q.Tail ) // Does tail equal Queue Tail.

为什么尾部*不等于Q 。在这个阶段？大概是因为

其他东西在同一时间排队了？


坦率地说，这一切都是为了非常聪明而不是为了/>
完全阻止 - 根据我的经验，这样的代码需要仔细查看

*非常小心，最好是特定内存中的专家

你正在使用的平台模型。


你真的需要这个吗？如你所知，你有证据证明正常吗？b $ b&b'block" （非常简短！）队列在你的

应用程序中杀死了性能？


-

Jon Skeet - < sk ***@pobox.com>
http://www.pobox.com / ~siget

如果回复群组，请不要给我发邮件

Why would tail *not* equal Q.Tail at this stage? Presumably because
something else has done some queuing in the mean time?

Frankly, it all smacks of trying to be extremely clever so as not to
block at all - in my experience, code like that needs to be looked at
*very* carefully, preferrably by an expert in the particular memory
model of the platform you''re using.

Do you really need this? As in, do you have evidence that a normal
"blocking" (very briefly!) queue is killing the performance in your
app?

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet
If replying to the group, please do not mail me too

这个双锁队列 ;。

-

William Stacey，MVP

And this "Two-Lock Queue".
--
William Stacey, MVP

>嗯，它有一些非常奇怪的代码：

> Well, it''s got some very odd code in it:

tail = Q.Tail;
next =（（Node）tail）.next ;
if（tail == Q.Tail）//尾部是否等于队列尾部。

tail = Q.Tail;
next = ((Node)tail).next;
if ( tail == Q.Tail ) // Does tail equal Queue Tail.

是的，它基于Michael Scott的队列之一：
http://www.cs.rochester.edu / u / scott / synchronization /

在快速并发队列算法下。我们相信这些算法是可用的最佳并发队列，......


只是想在c＃中复制。

为什么尾巴*不等于Q.Tail在这个阶段？大概是因为其他东西在同一时间排队了吗？


我有同样的问题Jon。我假设你的第二句话就是同样的事情

约。

坦率地说，这一切都非常聪明，以至于根本不会阻止 - 根据我的经验，这样的代码需要非常仔细地查看，最好是由您正在使用的平台的特定内存模型中的专家。


我同意，公开发帖。希望我能在这里利用一些灰色的

问题。

你真的需要这个吗？如你所知，你有证据表明正常的阻塞 （非常简短！）队列在你的
应用程序中杀死了性能？

Yes, it is based on one of Michael Scott''s queues at:
http://www.cs.rochester.edu/u/scott/synchronization/
Under "Fast concurrent queue algorithms. We believe these algorithms to be
the best concurrent queues available,..."

Just trying to duplicate in c#.
Why would tail *not* equal Q.Tail at this stage? Presumably because
something else has done some queuing in the mean time?
I had same question Jon. I assume the same thing your second sentence talks
about.
Frankly, it all smacks of trying to be extremely clever so as not to
block at all - in my experience, code like that needs to be looked at
*very* carefully, preferrably by an expert in the particular memory
model of the platform you''re using.
I would agree, hense the public post. Hopefully I can leverage some gray
matter out here.
Do you really need this? As in, do you have evidence that a normal
"blocking" (very briefly!) queue is killing the performance in your
app?

不，只是做精神挑战和学习锻炼。我还发布了一个非常优雅且易于IMO可视化的
TwoLockQueue，但仍然需要通过大量使用来验证

。即使是专家也是如此。随着时间的推移，他们自己的算法证明是错误的，所以我尽量验证。


-

William Stacey，MVP

No, just doing as a mental challenge and learning exercize. I also posted a
TwoLockQueue that is very elegant and easy to visualize IMO, but still needs
to be verified by eye and heavy use. Even the "experts" are proved wrong on
their own algorithms over time, so I try to verify as much as possible.

--
William Stacey, MVP

这篇关于非阻塞队列审查的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！