并发安全的队列

[xpzouying]

并发安全的队列

最近看了一篇关于并发安全队列的论文，在此记录该笔记。

参考论文

• 《Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms》 by Maged M. Michael, Michael L. Scott

[xpzouying]

首先，定义队列数据结构。其中包括两部分：

1. Node节点

type Node struct {
    Value int
    Next  *Node
}

2. 队列interface

type Queue interface {
    Enqueue(value int)
    Dequeue() (int, error)
}

[xpzouying]

第一版：链表

定义

定义最简单的FIFO的链表。

type SimpleQueue struct {
    Head *Node
    Tail *Node
}

其中数据结构包含：

• Head：指向头节点
• Tail：指向队尾节点

入队

func (q *SimpleQueue) Enqueue(v int) {
    node := &Node{Value: v}
    q.Tail.Next = node
    q.Tail = node
}

1. 在队尾添加节点
2. 更新Tail，指向新的节点

出队

func (q *SimpleQueue) Dequeue() (int, error) {
    // if empty queue
    if q.Head.Next == nil {
        return 0, ErrEmptyQueue
    }

    newHead := q.Head.Next
    retVal := newHead.Value

    oldHead := q.Head
    oldHead.Next = nil
    oldHead = nil

    q.Head = newHead
    return retVal, nil
}

1. 如果当前链表为空，则返回空链表错误。
2. 否则，
   1. 记录头部节点的值；
   2. 更新头部；
   3. 返回头部节点的值；