我正在尝试使用 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
包甚至可以做到这一点吗?
感谢您的帮助!
最佳答案
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)。它用于确保在您尝试之后直接插入元素时节点未被标记为已删除。您可以随意使用此资源作为您自己项目的起点。
关于struct - 在 Go 中使用结构进行原子比较和交换,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11525406/