在 Java 中使用 CAS 来实现队列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

public class LinkedQueue<E> {

  private final Node<E> dummy = new Node<>(null, null);

  private final AtomicReference<Node<E>> head = new AtomicReference<>(dummy);

  private final AtomicReference<Node<E>> tail = new AtomicReference<>(dummy);

  public boolean put(E item) {
    Node<E> newNode = new Node<>(item, null);
    while (true) {
      Node<E> curTail = tail.get();
      Node<E> tailNext = curTail.next.get();
      if (curTail == tail.get()) {
        if (tailNext != null) {
          // 队列处于中间状态，推进尾节点
          tail.compareAndSet(curTail, tailNext);
        } else {
          // 处于稳定状态，尝试插入新节点
          if (curTail.next.compareAndSet(null, newNode)) {
            // 插入操作成功，尝试推进尾节点
            tail.compareAndSet(curTail, newNode);
            return true;
          }
        }
      }
    }
  }

  public E take() {
    while (true) {
      if (head.get() == tail.get()) {
        return null;
      }

      Node<E> oldHead = head.get();
      Node<E> newHead = oldHead.next.get();
      // 队列处于中间状态，可能另外一个线程已经 CAS 成功， 只剩下一个元素 dummy 了
      if (newHead == null) {
        return null;
      }
      if (head.compareAndSet(oldHead, newHead)) {
        oldHead.next = null;
        return oldHead.item;
      }
    }
  }

  private static class Node<E> {

    private final E item;

    private AtomicReference<Node<E>> next;

    public Node(E item, Node<E> next) {
      this.item = item;
      this.next = new AtomicReference<>(next);
    }
  }
}