CAS 无锁队列

2019-03-01

       队列是常用的数据结构,采用的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发生抢占,所以要先进行比较,如果一样再进行操作,这样就能保证一致性。