7

我正在尝试使用 Maged M. Michael 和 Michael L. Scott 的算法为并发应用程序创建一个非阻塞队列包，如此处所述。

这需要使用"sync/atomic"包提供的原子 CompareAndSwap。
但是，我不确定与以下伪代码等效的 Go 是什么：

E9:   if CAS(&tail.ptr->next, next, <node, next.count+1>)

其中tail和next是类型：

type pointer_t struct {
    ptr   *node_t
    count uint
}

并且node是类型：

type node_t struct {
    value interface{}
    next  pointer_t
}

如果我理解正确，似乎我需要用一个结构（指针和一个uint）做一个 CAS。这甚至可以通过atomic-package 实现吗？

感谢帮助！

4

2 回答 2

13

如果我理解正确，似乎我需要用一个结构（一个 > 指针和一个 uint）做一个 CAS。这甚至可以使用 atomic-package 吗？

不，那是不可能的。大多数架构仅支持对单个单词的原子操作。然而，许多学术论文使用更强大的 CAS 语句（例如比较和交换双精度），而这些语句在今天是不可用的。幸运的是，在这种情况下通常使用一些技巧：

  • 例如，您可以从指针中窃取几位（尤其是在 64 位系统上）并使用它们来编码您的计数器。然后你可以简单地使用 Go 的 CompareAndSwapPointer，但你需要在尝试取消引用之前屏蔽指针的相关位。

  • 另一种可能性是使用指向您的（不可变的！）pointer_t 结构的指针。每当您想从您的 pointer_t 结构中修改一个元素时，您都必须创建一个副本，修改该副本并以原子方式替换指向您的结构的指针。这个习语称为 COW（写时复制），适用于任意大型结构。如果要使用此技术，则必须将下一个属性更改为next *pointer_t.

出于教育原因，我最近在 Go 中编写了一个无锁列表。您可以在这里找到（恕我直言）来源：https ://github.com/tux21b/goco/blob/master/list.go

这个相当简短的示例过度使用atomic.CompareAndSwapPointer并且还为标记指针（MarkAndRef 结构）引入了原子类型。这种类型与您的 pointer_t 结构非常相似（除了它存储的是 bool+pointer 而不是 int+pointer）。它用于确保在您尝试之后直接插入元素时未将节点标记为已删除。随意使用此源作为您自己项目的起点。

于 2012-07-17T16:43:23.190 回答
0

你可以这样做：

 if atomic.CompareAndSwapPointer(
    (*unsafe.Pointer)(unsafe.Pointer(tail.ptr.next)), 
    unsafe.Pointer(&next), 
    unsafe.Pointer(&pointer_t{&node, next.count + 1})
 )
于 2012-07-17T15:47:06.990 回答