我已经使用基于http://www.boyet.com/articles/LockfreeQueue.html的比较和交换用C语言实现了一个无锁队列。
它工作得很好,但我正在尝试将这个队列集成到我已经实现的无锁跳过列表中。我使用跳过列表作为优先级队列,并希望在发生优先级冲突时使用每个节点内的无锁队列来存储多个值。但是,由于在跳过列表中管理节点的方式,当我检测到优先级冲突时,我需要能够在队列不为空的情况下将项添加到队列中。
由于队列的无锁特性,我不确定如何实际执行此操作。
那么基本上我该如何写一个原子enqueue_if_not_empty操作呢?
发布于 2011-05-04 04:50:30
编辑:正如所注意到的,我用完全相反的语义编写了函数--只将其排入一个空队列。我修改了名称以反映这一点,并决定让它保持原样,以防有人会感兴趣。所以,这不是问题的正确答案,但请不要投反对票,除非你找到另一个原因:)
下面是在参考论文中将EnqueueIfEmpty()
添加到队列实现的尝试。我没有验证它是否正常工作,甚至没有进行编译。基本思想是,假设head的当前为null (这是空队列的必要条件),则在head的next后面插入一个新节点(而不是尾部)。我留下了额外的检查,头部等于尾部,这可能是可以删除的。
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-04 16:48:43
Enqueue-If-Not-Empty看起来相对简单,但有一个限制:其他线程可能会同时从队列中删除所有以前的项,因此在尾部插入完成后,新项可能恰好是队列中的第一个项。由于原子比较和交换操作是使用不同的字段完成的(入队更改tail.Next
,而出队前进head
),因此更强的保证不仅在此函数中需要额外的复杂性,至少在Dequeue()
中也是如此。
对普通Enqueue()
方法进行以下更改就足够了:
1)在函数启动时,检查head.Next
是否为空,如果为空,则立即返回,因为队列为空。
2)在循环条件中加入head.Next!=null
,以防插入成功前初始非空队列变为空,需要停止入队尝试。这并不能防止我上面描述的情况(因为在检查是否为空和插入节点之间有一个时间窗口),但减少了这种情况发生的可能性。
3)在函数结束时,仅在新节点成功入队时才尝试推进尾部(就像我在Enqueue- if -Empty答案中所做的那样)。
https://stackoverflow.com/questions/5864597
复制相似问题