struct - 在 Go 中使用结构进行原子比较和交换

Question

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

这需要使用 “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
}

和节点是类型:

type node_t struct {
    value interface{}
    next  pointer_t
}

如果我理解正确的话，似乎我需要用结构(指针和uint)做一个CAS。使用 atomic 包甚至可以做到这一点吗？

感谢您的帮助!

Answer 1

If I understood it correctly, it seems that I need to do a CAS with a struct (both a > pointer and a uint). Is this even possible with the atomic-package?

不，那是不可能的。大多数体系结构仅支持对单个字的原子操作。然而，许多学术论文使用了当今不可用的更强大的 CAS 语句(例如比较和交换 double )。幸运的是，在这种情况下有一些常用的技巧:

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

• 另一种可能性是使用指向您的(不可变!)pointer_t 结构的指针。每当你想修改 pointer_t 结构中的元素时，你都必须创建一个副本，修改副本并自动替换指向你的结构的指针。这个习惯用法称为 COW(写时复制)，适用于任意大型结构。如果您想使用此技术，则必须将 next 属性更改为 next *pointer_t。

出于教育原因，我最近用 Go 编写了一个无锁列表。您可以在此处找到(恕我直言，有据可查)来源:https://github.com/tux21b/goco/blob/master/list.go

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