在Go语言中，sync/atomic包的原子操作通常仅支持基本类型（如整数和指针），不直接支持结构体。本文探讨了在实现并发无锁数据结构时，如何通过“位窃取”或“写时复制”（COW）模式来模拟对包含指针和计数器的复合结构体进行原子比较与交换（CAS），从而克服这一限制，并提供实际应用示例。
Go原子操作与复合结构体的挑战
在并发编程中，无锁（lock-free）数据结构是实现高性能的关键技术之一。这类结构通常依赖原子操作，特别是比较与交换（compare and swap, cas）指令，来确保数据的一致性。go语言的sync/atomic包提供了多种原子操作，如compareandswapint32、compareandswappointer等，但这些操作通常针对单个机器字长（word-sized）的数据类型。
当我们需要对一个包含多个字段的复合结构体（例如，一个包含指针和计数器的pointer_t结构体）进行原子CAS操作时，Go的标准atomic包并不能直接支持。例如，在实现Maged M. Michael和Michael L. Scott的无锁队列算法时，可能需要对类似以下定义的pointer_t结构体进行原子更新：
type node_t struct { value interface{} next pointer_t // 假设这里需要原子更新}type pointer_t struct { ptr *node_t count uint}
伪代码中常见的CAS(&tail.ptr->next, next, node, next.count+1>)操作，意味着需要原子地比较和交换next字段，而next是一个包含指针和计数的结构体。由于大多数硬件架构只支持对单个机器字进行原子操作，直接对整个pointer_t结构体进行原子CAS是不可能的。为了解决这一问题，业界通常采用以下两种策略。
策略一：指针位窃取（Bit Stealing）
指针位窃取是一种巧妙的优化技术，它利用了64位系统上指针地址的特性。在64位系统中，虽然指针理论上可以寻址整个64位地址空间，但实际上，现代CPU和操作系统通常不会使用所有64位来表示内存地址。例如，许多系统只使用低48位或56位来表示虚拟地址，这意味着指针的高位或低位（如果地址是对齐的）可能存在未使用的比特位。
原理：通过将额外的少量信息（例如一个小的计数器或标记位）编码到指针的这些未使用的比特位中，可以将复合信息“压缩”到一个单个机器字中。这样，就可以使用atomic.CompareAndSwapPointer对这个“编码后”的指针进行原子操作。
实现考量：
立即学习“go语言免费学习笔记（深入）”；
编码与解码： 在进行CAS操作之前，需要将*node_t和uint的count值编码成一个uintptr类型的值。CAS成功后，再从uintptr中解码出原始的*node_t和count。位操作： 这通常涉及位移（>）和位掩码（&）操作。对齐要求： 如果将信息编码到指针的低位，需要确保实际的内存地址是足够对齐的，以保证低位始终为零，从而不会与编码的信息冲突。例如，如果将count编码到低3位，则要求指针地址是8字节对齐的。容量限制： 这种方法只能编码少量信息，因为可用的比特位是有限的。
示例（概念性）：
import ( "sync/atomic" "unsafe")// 假设我们有2位可以用来存储count (0-3)const ( countMask uintptr = 0x3 // 低2位 ptrMask uintptr = ^countMask)// encodePtrAndCount 将指针和计数编码为单个uintptrfunc encodePtrAndCount(ptr *node_t, count uint) uintptr { // 确保count不会超出可用位数 if count > countMask { panic("count exceeds available bits") } // 确保ptr是8字节对齐的，这样低2位才可用 if uintptr(unsafe.Pointer(ptr))&countMask != 0 { panic("pointer not sufficiently aligned for bit stealing") } return uintptr(unsafe.Pointer(ptr)) | uintptr(count)}// decodePtrAndCount 从uintptr中解码出指针和计数func decodePtrAndCount(encoded uintptr) (*node_t, uint) { ptr := (*node_t)(unsafe.Pointer(encoded & ptrMask)) count := uint(encoded & countMask) return ptr, count}// 假设node_t的next字段现在直接存储编码后的uintptr// type node_t struct {// value interface{}// next uintptr // 存储编码后的指针和计数// }// 示例CAS操作（伪代码，需要包装在实际逻辑中）func tryUpdateNext(node *node_t, oldPtr *node_t, oldCount uint, newPtr *node_t, newCount uint) bool { oldEncoded := encodePtrAndCount(oldPtr, oldCount) newEncoded := encodePtrAndCount(newPtr, newCount) // 使用atomic.CompareAndSwapUintptr进行原子操作 return atomic.CompareAndSwapUintptr(&node.next, oldEncoded, newEncoded)}
优点： 节省内存，避免了额外的内存分配。缺点： 实现复杂，依赖于特定的硬件/操作系统特性，并且只能存储少量信息。
策略二：写时复制（Copy-on-Write, COW）模式
写时复制（COW）是一种更通用且更易于理解的策略，适用于需要原子更新任意大小结构体的场景。其核心思想是将待原子更新的结构体视为不可变对象，每次需要修改时，不是直接修改原结构体，而是创建一个新的结构体副本，修改这个副本，然后原子地将指向旧结构体的指针替换为指向新结构体的指针。
原理：
将需要原子更新的结构体字段类型从struct_t改为*struct_t。每次读取时，获取当前指向结构体的指针。如果需要修改，先解引用指针，得到结构体副本。修改这个副本。创建一个新的指针，指向修改后的副本。使用atomic.CompareAndSwapPointer原子地将旧指针替换为新指针。
实现考量：
立即学习“go语言免费学习笔记（深入）”；
类型修改： 将node_t中的next字段从pointer_t改为*pointer_t。循环CAS： 由于CAS可能失败（有其他并发操作），通常需要在一个循环中尝试CAS，直到成功为止。内存分配： 每次修改都会创建一个新的结构体实例，这会带来额外的内存分配和垃圾回收（GC）开销。
示例：
import ( "sync/atomic" "unsafe")type pointer_t struct { ptr *node_t count uint}type node_t struct { value interface{} next *pointer_t // 修改为指针类型}// UpdateNext atomically updates the next pointer_t in a node.// It attempts to replace the old state (oldNextP) with a new state (newNextP).// Returns true on success, false otherwise (e.g., if oldNextP was not the current value).func UpdateNext(node *node_t, oldNextP *pointer_t, newNextP *pointer_t) bool { // atomic.CompareAndSwapPointer expects unsafe.Pointer return atomic.CompareAndSwapPointer( (*unsafe.Pointer)(unsafe.Pointer(&node.next)), // 地址 unsafe.Pointer(oldNextP), // 旧值 unsafe.Pointer(newNextP), // 新值 )}// 假设我们想更新node的next字段，使其指向一个新的节点newNode，并增加计数func exampleUpdate(node *node_t, newNode *node_t) { for { // 1. 原子读取当前的next指针 oldNextPtr := atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&node.next))) oldNext := (*pointer_t)(oldNextPtr) // 如果oldNext为nil，表示next尚未初始化，需要特殊处理 if oldNext == nil { // 初始化一个空的pointer_t，然后尝试CAS initialNext := &pointer_t{ptr: nil, count: 0} if atomic.CompareAndSwapPointer( (*unsafe.Pointer)(unsafe.Pointer(&node.next)), nil, unsafe.Pointer(initialNext), ) { // 成功初始化，现在oldNext指向initialNext oldNext = initialNext oldNextPtr = unsafe.Pointer(initialNext) } else { // 其他协程已经初始化了，重试 continue } } // 2. 创建一个新副本并修改 newNext := &pointer_t{ ptr: newNode, // 设置新的ptr count: oldNext.count + 1, // 增加计数 } // 3. 尝试原子替换：将旧的*pointer_t指针替换为新的*pointer_t指针 if UpdateNext(node, oldNext, newNext) { // CAS成功，更新完成 return } // CAS失败，说明在读取oldNext后，其他协程已经修改了node.next // 循环重试 }}
优点： 适用于任意大小的结构体，逻辑清晰，易于理解和实现。缺点： 每次修改都会产生新的内存分配，可能增加GC压力。
实际应用与参考
上述两种策略在实现复杂的无锁数据结构时都非常有用。例如，在Go语言中，可以参考github.com/tux21b/goco项目中的list.go文件。该项目实现了一个教育性质的无锁链表，其中MarkAndRef结构体（包含一个布尔标记和一个指针）与本教程中的pointer_t结构体非常相似。它通过类似COW的模式和atomic.CompareAndSwapPointer来确保在并发操作中（如删除节点时）的原子性和一致性。
MarkAndRef结构体用于标记一个节点是否已被逻辑删除，同时保留对下一个节点的引用。在更新链表时，它需要原子地检查和修改这个复合状态，这正是atomic.CompareAndSwapPointer结合COW模式的典型应用场景。
总结
在Go语言中，直接对复合结构体进行原子比较与交换是不受sync/atomic包支持的。为了实现这一目标，开发者需要采用更高级的策略：
指针位窃取适用于需要极度优化内存和性能，且复合信息量很小（如计数器或标记位）的场景。但其实现复杂，且依赖于特定的硬件特性。写时复制（COW）模式则是一种更通用、更易于维护的解决方案。它通过将结构体字段改为指针，并在修改时创建副本并原子替换指针，实现了对任意大小结构体的原子更新。虽然会带来额外的内存分配和GC开销，但在大多数场景下，其带来的代码清晰度和可维护性是值得的。
在设计无锁数据结构时，理解这些底层机制和替代方案至关重要。选择哪种策略取决于具体的性能要求、内存限制以及代码的复杂性。对于大多数应用，COW模式通常是更推荐的选择，因为它在实现复杂无锁结构时提供了良好的平衡。
以上就是在Go语言中实现结构体的原子比较与交换：策略与实践的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1405173.html
微信扫一扫 
支付宝扫一扫 
