C -锁自由队列，如果不为空

Question

我在C中使用基于http://www.boyet.com/articles/LockfreeQueue.html的比较和交换实现了一个无锁队列。

它的工作很棒，但我正试图将这个队列集成到我已经实现的无锁跳跃列表中。我使用跳跃列表作为优先级队列，并希望在每个节点内使用无锁队列，以便在发生优先级冲突时存储多个值。但是，由于节点在跳跃列表中管理的方式，当我检测到优先级冲突时，我需要能够仅在队列不为空时将项目添加到队列中。

由于队列的无锁特性，我不确定如何实际执行此操作。

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

Answer 1

编辑:正如注意到的那样，我用完全相反的语义编写了这个函数—只将队列加入空队列。我固定了这个名字来反映这一点，并决定留下它，以防有人会感兴趣。所以，这不是问题的正确答案，但请不要投票，除非你找到另一个原因:)

---

下面是在参考论文中将EnqueueIfEmpty()添加到队列实现中的尝试。我没有验证它是否有效，甚至没有验证它是否可以编译。基本思想是在头(而不是尾部)之后插入一个新节点，前提是头的下一个当前为null(这是空队列的必要条件)。我留下了额外的检查头等于尾，这可能是可以删除的。

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;
}

Answer 2

嗯，Enqueue-If-Not-Empty看起来相对简单，但有一个限制:其他线程可能并发地从队列中删除所有先前的项，因此在尾部插入完成后，新项可能恰好是队列中的第一个。由于原子比较和交换操作是在不同的字段上完成的(排队改变tail.Next，而脱队列推进head)，更强的保证不仅在这个函数中需要额外的复杂性，至少在Dequeue()中也是如此。

对正常的Enqueue()方法进行以下更改就足够了:
1)在函数开始时，检查head.Next是否为空，如果是，立即返回，因为队列为空。
2)将head.Next!=null添加到循环条件中，以防在插入成功之前，如果初始非空队列变为空，则需要停止排队尝试。这并不能防止我上面描述的情况(因为在检查空节点和插入节点之间有一个时间窗口)，但是减少了它发生的机会。
3)在函数结束时，只有在新节点成功进入队列时才尝试推进尾部(就像我在Enqueue-If-Empty答案中所做的那样)。