CAS 无锁队列
CAS 无锁队列
队列是常用的数据结构，采用的FIFO(first in firstout)原则，新元素（等待进入队列的元素）总是被插入到尾部，而读取的时候总是从头部开始读取。在计算中队列一般用来做排队(如线程池的等待排队，锁的等待排队)，用来做解耦（生产者消费者模式），异步等等。在java多线程应用中，队列的使用率很高，多数生产消费模型的首选数据结构就是队列。队列在现实生活中也很常见，例如去超市买东西排队付钱，先来的先付账走人回家，后来的要等前面的人付完钱才能付账。
首先我们看一段队列代码：
type Queue struct { head unsafe.Pointer tail unsafe.Pointer Reset func(interface{}) New func() interface{} } // one node in queue type Node struct { val interface{} next unsafe.Pointer } func QueueNew()(*Queue){ queue := new(Queue) queue.head = unsafe.Pointer(new(Node)) queue.tail = queue.head return queue } func (self *Queue) EnQueue(val interface{}) { if self.Reset!= nil{ self.Reset(val) } newNode := unsafe.Pointer(&Node{val: val, next: nil}) var tail, next unsafe.Pointer tail = self.tail ((*Node)(tail)).next = newNode self.tail = newNode } func (self *Queue) DeQueue() (val interface{}) { var head, tail, next unsafe.Pointer head = self.head tail = self.tail next = ((*Node)(head)).next if head == tail { // There's no data in the queue. return nil } val = ((*Node)(next)).val self.head = next return val }
这是一般的队列实现方法，适用于单线程但如果是多线程操作就麻烦了。例如在超市柜台结账，大家都按规则进行排队没有问题，但是如果有两个人张大妈和李大妈都着急结账回家接孙子，同时跑到了同一个队列的队尾，她们两都说自己应该排在队尾。那么问题就来了。那么对于多线程操作同一个队列，可以用锁的方法来实现，在入队和出队前加上锁即可：
type Queue struct { sync.RWMutex head unsafe.Pointer tail unsafe.Pointer Reset func(interface{}) New func() interface{} } func (self *Queue) EnQueue(val interface{}) { self.Lock() defer self.Unlock() if self.Reset != nil { self.Reset(val) } newNode := unsafe.Pointer(&Node{val: val, next: nil}) var tail, next unsafe.Pointer tail = self.tail ((*Node)(tail)).next = newNode self.tail = newNode } func (self *Queue) DeQueue() (val interface{}) { var head, tail, next unsafe.Pointer self.Lock() defer self.Unlock() head = self.head tail = self.tail next = ((*Node)(head)).next if head == tail { // There's no data in the queue. return nil } val = ((*Node)(next)).val self.head = next return val }
但是，这种加锁的方法在多进程的操作中会消耗很多系统资源，使用不当还会造成死锁，下面推荐一种CAS的方法来实现队列的安全出队和入队。CAS（Compare and Swap），比较并交换，在大多数处理器架构，CAS的具体是判断一个内存上的数据是否是所判断的值，如果是，那么执行修改；如果不是，那么将不做操作并返回当前值。CAS是一种乐观锁，多线程执行过程中，多个线程去修改内存中的数据，有且只有一个能修改成功，但是失败的线程不会中断或者挂起。具体代码如下：
func (self *Queue) EnQueue(val interface{}) {
if self.Reset!= nil{
self.Reset(val)
}
newNode := unsafe.Pointer(&Node{val: val, next: nil})
var tail, next unsafe.Pointer
for {
tail = self.tail
next = ((*Node)(tail)).next
if tail != self.tail{
runtime.Gosched()
continue
}
//[PositionA]-----------A new node may already enqueue-------------
if next != nil {
atomic.CompareAndSwapPointer(&(self.tail), tail, next)
continue
}
if atomic.CompareAndSwapPointer(&((*Node)(tail).next), nil,newNode ) {
break
}
runtime.Gosched()
}
atomic.CompareAndSwapPointer(&(self.tail),tail, newNode)
}
func (self *Queue) DeQueue() (val interface{}) {
var head, tail, next unsafe.Pointer
for {
head = self.head
tail = self.tail
next = ((*Node)(head)).next
if head != self.head{
runtime.Gosched()
continue
}
if next == nil{
if self.New != nil{
return self.New()
}else{
return nil
}
}
if head == tail {
atomic.CompareAndSwapPointer(&(self.tail), tail, next)
}else{
val = ((*Node)(next)).val
//[PositionB]---------The head node may already Dequeue---------
if atomic.CompareAndSwapPointer(&(self.head), head, next) {
return val
}
}
runtime.Gosched()
}
}
多线程在运行这段代码的过程中可能在位置A和位置B发生抢占，所以要先进行比较，如果一样再进行操作，这样就能保证一致性。
版权声明：本文为best-farmer原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。