英文:
Atomic Compare And Swap with struct in Go
问题
我正在尝试使用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
包是否可能实现这一点?
谢谢帮助!
英文:
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.
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>)
where tail
and next
is of type:
type pointer_t struct {
ptr *node_t
count uint
}
and node
is of type:
type node_t struct {
value interface{}
next pointer_t
}
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?
Thanks for help!
答案1
得分: 14
如果我理解正确的话,似乎我需要使用一个结构体(包括指针和一个无符号整数)进行CAS操作。使用atomic包是否可能实现这个?
不,这是不可能的。大多数架构只支持对单个字进行原子操作。然而,许多学术论文使用更强大的CAS语句(例如比较和交换双字),但这些语句目前不可用。幸运的是,在这种情况下有一些常用的技巧:
-
例如,你可以从指针中窃取一些位(特别是在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结构体非常相似(除了它存储了一个布尔值+指针,而不是一个整数+指针)。它用于确保在你尝试在其后直接插入元素时,节点没有被标记为已删除。请随意将此源代码用作你自己项目的起点。
英文:
> 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?
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:
-
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.
-
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
.
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
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.
答案2
得分: 0
你可以这样做:
if atomic.CompareAndSwapPointer(
(*unsafe.Pointer)(unsafe.Pointer(tail.ptr.next)),
unsafe.Pointer(&next),
unsafe.Pointer(&pointer_t{&node, next.count + 1})
)
英文:
You can do something like this:
if atomic.CompareAndSwapPointer(
(*unsafe.Pointer)(unsafe.Pointer(tail.ptr.next)),
unsafe.Pointer(&next),
unsafe.Pointer(&pointer_t{&node, next.count + 1})
)
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论