- 锁是一种常见的同步机制，用来解决多个线程同时访问共享资源导致的数据竞争问题。在高并发场景下，锁的使用可能会成为性能瓶颈，因为线程需要频繁地加锁和释放锁，这会增加上下文切换开销并降低程序的吞吐量。
- 无锁编程（lock-free programming）是一种并发编程技术，主要用于消除多线程编程中锁操作带来的性能损耗。
lock-free的优势
- 减少线程阻塞和等待时间
- 避免线程的优先级反转
- 提高并发性能
- 消除竞态条件（race condition）、死锁、饿死等潜在问题
- 代码更加清晰易懂
CAS (compare and swap) 是原子操作的一种，用于在多线程中实现原子数据交换，避免多线程同时改写某一共享数据时，由于执行顺序不确定性以及中断的不可预知性产生的数据不一致问题。
示例: 栈操作
// Stack 接口
type StackInterface interface{
Push(interface{})
Pop()interface{}
}
- 有锁: 使用 sync 包
// 互斥锁实现的栈 (有锁编程)
type MutexStack struct{
// 栈元素容器用切片表示
v []interface{}
// 互斥锁
mu sync.Mutex
}
funcNewMutexStack()*MutexStack {
return&MutexStack{v:make([]interface{},0)}
}
func(s *MutexStack)Push(v interface{}){
// 可能同时有多个 goroutine 操作
// 栈元素操作为临界区，需要加锁
s.mu.Lock()
s.v =append(s.v, v)
s.mu.Unlock()
}
func(s *MutexStack)Pop()interface{}{
// 可能同时有多个 goroutine 操作
// 栈元素操作为临界区，需要加锁
s.mu.Lock()
var v interface{}
iflen(s.v)>0{
v = s.v[len(s.v)-1]
s.v = s.v[:len(s.v)-1]
}
s.mu.Unlock()
return v
}
- 无锁: atomic 包
// 栈元素节点
type directItem struct{
next unsafe.Pointer
v interface{}
}
// CAS 操作实现的栈 (无锁编程)
type LockFreeStack struct{
// 栈元素容器用链表表示
top unsafe.Pointer
// 栈长度
lenuint64
}
funcNewLockFreeStack()*LockFreeStack {
return&LockFreeStack{}
}
func(s *LockFreeStack)Push(v interface{}){
item := directItem{v: v}
var top unsafe.Pointer
for{
top = atomic.LoadPointer(&s.top)
item.next = top
if atomic.CompareAndSwapPointer(&s.top, top, unsafe.Pointer(&item)){
// 只有 1 个 goroutine 可以执行到这里
// 栈元素数量 + 1
atomic.AddUint64(&s.len,1)
return
}
}
}
func(s *LockFreeStack)Pop()interface{}{
var top, next unsafe.Pointer
var item *directItem
for{
top = atomic.LoadPointer(&s.top)
if top ==nil{
returnnil
}
item =(*directItem)(top)
next = atomic.LoadPointer(&item.next)
if atomic.CompareAndSwapPointer(&s.top, top, next){
// 只有 1 个 goroutine 可以执行到这里
// 栈元素数量 - 1
atomic.AddUint64(&s.len,^uint64(0))
return item.v
}
}
}
测试结果比较
$ go test -run='^$' -bench=. -count=1 -benchtime=2s
## 输出结果如下
Benchmark_Stack/*performance.LockFreeStack-8 16553013 134.0 ns/op
Benchmark_Stack/*performance.MutexStack-8 20625786 172.5 ns/op
