在Go语言中，直接对包含指针和整数的复合结构体执行原子比较与交换（CAS）操作是不被标准sync/atomic包支持的，因为大多数架构仅支持对单个机器字进行原子操作。本文将探讨两种实现类似功能的策略：利用指针位窃取（Bit Stealing）在64位系统上编码额外信息，以及采用写时复制（Copy-On-Write, COW）模式通过原子替换结构体指针来间接实现对结构体内容的原子更新。
原子操作与结构体：Go语言的限制
在构建高性能的无锁数据结构时，原子比较与交换（compare and swap, cas）是核心原语。例如，在maged m. michael和michael l. scott的无锁队列算法中，经常需要对包含指针和计数器的复合类型（如pointer_t）进行cas操作。然而，go语言的sync/atomic包提供的compareandswappointer、compareandswapuint64等函数，仅支持对单一机器字（如uintptr、int64）进行原子操作。
当尝试对以下结构体执行原子CAS时：
type pointer_t struct { ptr *node_t count uint}type node_t struct { value interface{} next pointer_t // 目标是对此字段进行原子更新}
直接使用atomic.CompareAndSwap是不可能的，因为pointer_t是一个包含两个字段的结构体，其大小通常超过一个机器字。大多数CPU架构只支持对单个机器字进行原子CAS操作。为了解决这个问题，我们需要采用一些间接策略。
策略一：指针位窃取 (Bit Stealing)
原理：在64位系统中，内存地址空间通常远小于64位所能表示的范围（例如，在现代系统中，通常只使用48位或52位地址线）。这意味着64位指针的高位或低位可能存在未被使用的比特位。我们可以“窃取”这些未使用的比特位来存储额外的小型数据，例如一个计数器。
实现细节与注意事项：
位掩码操作： 在将指针存储到uintptr类型时，使用位掩码将计数器编码到指针的空闲位中。原子操作： 使用atomic.CompareAndSwapPointer对这个编码后的uintptr进行原子操作。解码： 在使用指针之前，需要通过位掩码将计数器从指针中分离出来，并将指针恢复到其原始形式。局限性：此方法仅适用于64位系统，因为32位系统上的指针通常没有足够的空闲位。能存储的计数器值大小有限，取决于可用的比特位数。需要对指针进行复杂的位操作，增加了代码的复杂性和出错的可能性。需要确保被窃取的位确实是空闲的，这可能依赖于特定的操作系统和架构特性。
示例概念：假设我们决定使用指针的最低有效位来存储一个小的计数器（例如，2-4位）。
编码： encodedPtr = (uintptr(actualPtr) & ^mask) | (count & mask)解码指针： decodedPtr = (*node_t)(unsafe.Pointer(encodedPtr & ^mask))解码计数： decodedCount = uint(encodedPtr & mask)原子更新： atomic.CompareAndSwapUintptr(&target, oldEncoded, newEncoded)
这种方法虽然高效，但其复杂性和平台依赖性使其在实际应用中需要谨慎评估。
立即学习“go语言免费学习笔记（深入）”；
策略二：写时复制 (Copy-On-Write, COW)
原理：写时复制（COW）是一种更通用且更安全的方法，适用于需要原子更新任意大小结构体的场景。其核心思想是将需要原子更新的结构体视为不可变对象。当需要修改结构体时，不直接修改原始结构体，而是：
创建一个原始结构体的副本。在副本上进行修改。使用原子操作（如atomic.CompareAndSwapPointer）将指向旧结构体的指针替换为指向新结构体的指针。
实现细节与注意事项：
修改结构体定义： 将node_t中的next字段从pointer_t类型修改为*pointer_t类型。这样，node.next就变成了一个指向pointer_t结构体的指针，我们可以对这个指针进行原子操作。
type pointer_t struct { ptr *node_t count uint}type node_t struct { value interface{} next *pointer_t // 修改为指针类型}
原子更新逻辑： 当需要更新node.next时，执行以下步骤：
读取当前的node.next指针，得到旧的pointer_t实例。创建一个新的pointer_t实例，复制旧实例的内容，并进行必要的修改（例如，更新ptr或count）。使用atomic.CompareAndSwapPointer尝试将node.next字段从指向旧pointer_t的指针原子地替换为指向新pointer_t的指针。如果CAS失败（说明在读取和更新之间有其他协程修改了该字段），则需要重试。
示例代码：
import ( "sync/atomic" "unsafe")// pointer_t 定义不变type pointer_t struct { ptr *node_t count uint}// node_t 的 next 字段改为 *pointer_ttype node_t struct { value interface{} // next 字段现在是一个指向 pointer_t 结构体的指针 // 我们将对这个指针进行原子操作 next *pointer_t}// updateNodeNext 尝试原子地更新一个 node_t 的 next 字段// node: 目标 node_t 实例// oldNextPointerT: 期望的当前 node.next 指向的 pointer_t 实例// newNodeRef: 新的 node_t 实例，用于更新 pointer_t.ptrfunc updateNodeNext(node *node_t, oldNextPointerT *pointer_t, newNodeRef *node_t) bool { // 1. 创建一个新的 pointer_t 结构体实例 // 包含更新后的 node 引用和递增的计数 newNextPointerT := &pointer_t{ ptr: newNodeRef, count: oldNextPointerT.count + 1, // 计数器递增 } // 2. 使用 atomic.CompareAndSwapPointer 原子地替换 node.next 字段 // 参数解释： // - (*unsafe.Pointer)(unsafe.Pointer(&node.next)): 获取 node.next 字段的地址，并转换为 *unsafe.Pointer 类型 // - unsafe.Pointer(oldNextPointerT): 期望的旧值（oldNextPointerT 的内存地址） // - unsafe.Pointer(newNextPointerT): 新值（newNextPointerT 的内存地址） return atomic.CompareAndSwapPointer( (*unsafe.Pointer)(unsafe.Pointer(&node.next)), unsafe.Pointer(oldNextPointerT), unsafe.Pointer(newNextPointerT), )}// 示例使用func main() { // 假设我们有一个初始的 node 和它的 next 字段 initialNode := &node_t{value: "A"} initialNextPointer := &pointer_t{ptr: nil, count: 0} initialNode.next = initialNextPointer // 假设我们想要将 initialNode 的 next 字段更新为指向 newChildNode newChildNode := &node_t{value: "B"} // 尝试原子更新 success := updateNodeNext(initialNode, initialNextPointer, newChildNode) if success { // 更新成功，initialNode.next 现在指向一个新的 pointer_t 实例 // 这个新实例的 ptr 字段指向 newChildNode，count 为 1 println("Atomic update successful!") println("New next pointer count:", initialNode.next.count) // 应该输出 1 } else { println("Atomic update failed, retry needed.") }}
注意事项：
内存分配： 每次修改都会创建一个新的pointer_t实例，这会引入额外的内存分配和潜在的垃圾回收开销。对于频繁更新的场景，需要评估其性能影响。不可变性： pointer_t结构体本身在被引用后，其内容应被视为不可变。所有修改都通过创建新副本来实现。Go 1.19+ atomic.Pointer[T]： 对于Go 1.19及更高版本，可以使用atomic.Pointer[T]来更安全、更简洁地实现对任意类型指针的原子操作，避免直接使用unsafe.Pointer。上述示例为兼容性考虑使用了unsafe.Pointer。
实际应用与参考
上述COW模式是实现无锁数据结构（如无锁队列、无锁链表）的常用技术。例如，在实现无锁链表时，节点的next指针可能需要携带一个“标记”或“版本号”来处理节点删除等并发问题。Go语言中，可以参考开源项目中的实现，例如tux21b/goco库中的list.go文件。该文件中的MarkAndRef结构体与pointer_t非常相似，它使用一个布尔值（标记）和一个指针，并通过原子操作来确保节点状态的一致性。
总结
在Go语言中直接对复合结构体进行原子比较与交换是不支持的。为了实现类似功能，我们可以选择两种主要策略：
指针位窃取： 利用64位指针的空闲位编码额外信息，通过atomic.CompareAndSwapPointer进行原子操作。此方法高效但复杂且平台依赖性强。写时复制 (COW)： 将结构体视为不可变，通过原子替换指向结构体实例的指针来间接更新其内容。此方法通用、安全，但会引入内存分配开销。
在大多数情况下，写时复制（COW）模式是更推荐的选择，因为它更易于理解和维护，并且适用于更广泛的场景。在设计无锁数据结构时，选择合适的原子操作策略是确保并发正确性和性能的关键。
以上就是Go语言中对结构体进行原子比较与交换的实现策略的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1405133.html
微信扫一扫 
支付宝扫一扫 
