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

Question

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

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

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

那么基本上我将如何编写原子 enqueue_if_not_empty 操作？

Answer 1

编辑：正如人们所注意到的，我用完全相反的语义编写了该函数 - 仅排队到一个空队列中。我修改了名称以反映这一点，并决定保留原样，以防万一有人感兴趣。因此，这不是问题的正确答案，但请不要投反对票，除非您找到其他原因:)

---

下面是尝试将 EnqueueIfEmpty() 添加到引用论文中的队列实现中。我没有验证它是否有效，甚至没有编译。
基本思想是，在 head 之后插入一个新节点（而不是尾部），前提是 head 的下一个节点当前为 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 答案中所做的那样）。