Go中的原子比较和交换结构

Question

我想创建一个非阻塞队列包描述使用算法通过马吉德·M. Michael和迈克尔·L.·斯科特并发应用在这里.

这需要使用"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 可以实现这一点吗？

感谢帮助!

Answer 1

如果我理解正确,似乎我需要使用结构(包括>指针和uint)来执行CAS.原子包是否可以实现？

不,那是不可能的.大多数架构仅支持单个单词的原子操作.然而,许多学术论文使用了今天无法获得的更强大的CAS语句(例如比较和交换双重).幸运的是,在这种情况下通常会使用一些技巧:

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

• 另一种可能性是使用指向你的(immutable!)pointer_t结构的指针.无论何时想要修改pointer_t结构中的元素,都必须创建副本,修改副本并原子地替换指向结构的指针.这个成语称为COW(写入时复制),适用于任意大型结构.如果要使用此技术,则必须将下一个属性更改为next *pointer_t.

由于教育原因,我最近在Go写了一个无锁列表.你可以在这里找到(imho记录良好的)来源:https://github.com/tux21b/goco/blob/master/list.go

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