锁定空闲队列入队如果不为空

我已经在C中使用基于http://www.boyet.com/articles/LockfreeQueue.html的比较和交换实现了一个锁定空闲队列。锁定空闲队列入队如果不为空

它的工作很好，但我试图将这个队列整合到我已经实现的锁定自由跳过列表中。我使用跳过列表作为优先级队列，并希望在每个节点内使用锁定空闲队列在存在优先级冲突时存储多个值。然而，由于在跳过列表中管理节点的方式，当我检测到优先级冲突时，只有当队列不为空时，我才需要能够将该项添加到队列中。

由于队列的锁定自由性im不知道如何实际执行此操作。

所以基本上我会怎么写一个原子enqueue_if_not_empty操作？

来源

2011-05-03 luke

此代码有一个微妙的错误。正如文档所述（http://www.boyet.com/articles/ABAProblem.html），它在C＃中工作，因为垃圾收集。它将**不工作**在C中。 – 2011-05-03 03:13:39

我正在使用引用计数系统来解决队列中节点上的ABA问题。所以保证节点不会早早释放。 – luke 2011-05-03 03:34:38

我从来没有遇到任何基于ref count的解决方案，它允许免费（）的队列元素。我可以想象一个基于ref count的解决方案，它允许元素返回freelist，但就是这样。你是否说过你已经设计了基于ref count的安全内存回收算法？ – 2011-05-04 11:01:35

编辑：正如它被注意到，我写了功能与完全相反的语义 - 只入队到一个空队列。我固定了这个名字以反映这一点，并决定放弃它，以防万一有人感兴趣。所以，这是不正确的答案的问题，但不downvote请，除非你找到另一个原因:)

下面是一个企图在引用的文件添加EnqueueIfEmpty()到队列实现。我没有验证它是否有效，甚至没有编译。基本思想是在头（而不是尾部）后面插入一个新节点，前提是头的下一个当前为空（这是空队列的必要条件）。我留下额外的头等于尾巴的检查，这可能会被删除。

public bool EnqueueIfEmpty(T item) { 
    // Return immediately if the queue is not empty. 
    // Possibly the first condition is redundant. 
    if (head!=tail || head.Next!=null) 
     return false; 

    SingleLinkNode<T> oldHead = null; 

    // create and initialize the new node 
    SingleLinkNode<T> node = new SingleLinkNode<T>(); 
    node.Item = item; 

    // loop until we have managed to update the tail's Next link 
    // to point to our new node 
    bool Succeeded = false; 
    while (head==tail && !Succeeded) { 

    // save the current value of the head 
    oldHead = head;   

    // providing that the tail still equals to head... 
    if (tail == oldHead) { 

     // ...and its Next field is null... 
     if (oldhead.Next == null) { 

     // ...try inserting new node right after the head. 
     // Do not insert at the tail, because that might succeed 
     // with a non-empty queue as well. 
     Succeeded = SyncMethods.CAS<SingleLinkNode<T>>(ref head.Next, null, node); 
     } 

     // if the head's Next field was non-null, another thread is 
     // in the middle of enqueuing a new node, so the queue becomes non-empty 
     else { 
     return false; 
     } 
    } 
    } 

    if (Succeeded) { 
    // try and update the tail field to point to our node; don't 
    // worry if we can't, another thread will update it for us on 
    // the next call to Enqueue() 
    SyncMethods.CAS<SingleLinkNode<T>>(ref tail, oldHead, node); 
    } 
    return Succeeded; 
}

来源

2011-05-03 20:50:30

如果head.next为null并且tail == head，那么队列为空......所以我们希望排队失败。我认为你写enqueue_if_empty不enqueue_if_not_empty ...除非我感到困惑。 – luke 2011-05-04 01:44:57

很棒！我的错误 - 的确，我写了与所期望的相反的东西:)我将把它留在这个答案中，也许再写一个。 – 2011-05-04 07:42:43

如果head == tail和oldHead = head，那么oldHead.next会不会总是NULL？为什么要检查它？ – 2011-05-04 11:05:37

好，入队，如果不能提空似乎是相对简单的，但有一个限制：其他线程可以同时从队列中删除所有以前的项目，使插入在尾完成后，新项目可能恰好是队列中的第一项。由于原子比较和交换操作是通过不同的字段完成的（排列变化tail.Next，同时使预排列head出列），更强大的保证不仅需要此功能，而且至少在Dequeue()中还需要额外的复杂性。

到正常Enqueue()方法可以进行如下更改足够：
1）在函数开始时，检查head.Next被空，如果是这样，立即返回作为队列是空的。
2）将head.Next!=null添加到循环条件中，以防排队尝试应该停止，如果在插入成功之前最初的非空队列变空。这并不妨碍我上面描述的情况（因为在检查虚拟和节点插入之间存在时间窗口），但减少了发生的可能性。
3）在函数结束时，如果新节点已成功排队，只尝试前进尾部（就像我在Enqueue-If-Empty答案中那样）。

来源

2011-05-04 08:48:42

锁定空闲队列入队如果不为空

回答

相关问题