问题描述
我正在尝试使用Maged M. Michael和Michael L. Scott的算法为并发应用程序创建一个非阻塞队列包，如此处.
I am trying to create a non-blocking queue package for concurrent application using the algorithm by Maged M. Michael and Michael L. Scott as described here.
这需要使用由"sync/atomic" 包提供的atomic CompareAndSwap.
但是，我不确定与以下伪代码的等效关系是什么:
This requires the use of atomic CompareAndSwap which is offered by the "sync/atomic" package.
I am however not sure what the Go-equivalent to the following pseudocode would be:
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甚至可以做到这一点?
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语句(例如，比较和交换双精度).幸运的是，在这种情况下通常会使用一些技巧:
No, that is not possible. Most architectures only support atomic operations on a single word. A lot of academic papers however use more powerful CAS statements (e.g. compare and swap double) that are not available today. Luckily there are a few tricks that are commonly used in such situations:
-
例如，您可以从指针中窃取几个位(尤其是在64位系统上)，然后使用它们来对计数器进行编码.然后，您可以简单地使用Go的CompareAndSwapPointer，但是在尝试取消引用指针之前，您需要屏蔽指针的相关位.
You could for example steal a couple of bits from the pointer (especially on 64bit systems) and use them, to encode your counter. Then you could simply use Go's CompareAndSwapPointer, but you need to mask the relevant bits of the pointer before you try to dereference it.
另一种可能性是使用指向您的(不可变！)pointer_t结构的指针.每当您要修改pointer_t结构中的元素时，都必须创建一个副本，修改该副本，并以原子方式替换指向您的结构的指针.这个习惯用法称为COW(写入时复制)，可用于任意大型结构.如果要使用此技术，则必须将下一个属性更改为 next * pointer_t .
The other possibility is to work with pointers to your (immutable!) pointer_t struct. Whenever you want to modify an element from your pointer_t struct, you would have to create a copy, modify the copy and atomically replace the pointer to your struct. This idiom is called COW (copy on write) and works with arbitrary large structures. If you want to use this technique, you would have to change the next attribute to next *pointer_t.
出于教育原因，我最近在Go中编写了无锁列表.您可以在此处找到(imho记录良好的)来源: https://github.com/tux21b/goco/blob/master/list.go
I have recently written a lock-free list in Go for educational reasons. You can find the (imho well documented) source here: https://github.com/tux21b/goco/blob/master/list.go
这个简短的示例过度使用了 atomic.CompareAndSwapPointer ，并且还引入了一种原子类型用于标记的指针(MarkAndRef结构).此类型与您的pointer_t结构非常相似(除了它存储的是bool + pointer而不是int + pointer).它用于确保您尝试在之后直接插入元素时未将节点标记为已删除.随时使用此源代码作为您自己的项目的起点.
This rather short example uses atomic.CompareAndSwapPointer excessively and also introduces an atomic type for marked pointers (the MarkAndRef struct). This type is very similar to your pointer_t struct (except that it stores a bool+pointer instead of an int+pointer). It's used to ensure that a node has not been marked as deleted while you are trying to insert an element directly afterwards. Feel free to use this source as starting point for your own projects.
这篇关于Go中的struct与原子比较和交换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！