2

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

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

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

所以基本上我将如何编写一个原子 enqueue_if_not_empty 操作？

4

2 回答 2

0

嗯，Enqueue-If-Not-Empty 看起来比较简单，但有一个限制：其他线程可能同时从队列中删除所有先前的项目，因此在尾部插入完成后，新项目可能恰好是队列中的第一个。由于原子比较和交换操作是使用不同的字段完成的（tail.Next在出队前进时将更改入队head），因此更强的保证不仅在此函数中而且至少在此函数中需要额外的复杂性Dequeue()。

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

于 2011-05-04T08:48:42.713 回答
0

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

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-03T20:50:30.410 回答