15_02_原子变量

原子变量

一、原子变量类

原子变量类相当于是一种泛化的 volatile 变量，能够支持原子和有条件的读写操作。

1.1 原子类型

• 标量类：AtomicInteger、AtomicLong、AtomicBoolean、AtomicReference
• 数组类：AtomicIntegerArray、AtomicLongArray、AtomicBooleanArray
• 更新器类：AtomicIntegerFieldUpdater、AtomicLongFieldUpdater、AtomicBooleanFieldUpdater
• 复合变量类：AtomicMarkableReference

1.2 性能比较

• 原子变量比锁的粒度更细、量级更轻
• 原子变量将发生竞争的范围缩小至单个变量上
• 原子变量通常会更快，因为它不需要挂起或重新调度线程
• 在高度竞争的情况下，锁的性能会比原子变量更好，原因是锁会挂起线程，避免了很多线程上下文切换
• 在中低竞争的情况下，原子变量能提供更高的可伸缩性

二、非阻塞算法

• 非阻塞的计数器：单状态
• 非阻塞的数字区域：单不可变对象，包含多状态
• 非阻塞的栈：单状态
• 非阻塞的队列：多状态

2.1 非阻塞的计数器

/**
 * 《并发编程实战》-第15章
 * 基于 CAS 实现的非阻塞计数器
 * @since 2022/4/27
 */
public class CasCounter {

    private SimulatedCAS value;

    public int getValue() {
        return value.get();
    }

    public int increment() {
        int v;
        do {
            v = value.get();
        } while (v != value.compareAndSwap(v, v + 1));
        return v + 1;
    }

}

2.2 非阻塞的数字区域

/**
 * 《并发编程实战》-第15章
 *  原子变量 + 不可变对象实现多状态更新
 * @since 2022/4/27
 */
public class CasNumberRange {

    private static class IntPair {
        // 不变性条件：lower <= upper
        final int lower;
        final int upper;

        public IntPair(int lower, int upper) {
            this.lower = lower;
            this.upper = upper;
        }
    }

    private final AtomicReference<IntPair> values = new AtomicReference<>(new IntPair(0, 0));

    public int getLower() {
        return values.get().lower;
    }

    public int getUpper() {
        return values.get().upper;
    }

    public void setLower(int i) {
        while (true) {
            IntPair oldValue = values.get();
            if (i > oldValue.upper) {
                throw new IllegalArgumentException("Can't set lower to " + i + " > upper");
            }
            IntPair newValue = new IntPair(i, oldValue.upper);
            if (values.compareAndSet(oldValue,newValue)) {
                break;
            }
        }
    }

    public void setUpper(int i) {
        while (true) {
            IntPair oldValue = values.get();
            if (i < oldValue.lower) {
                throw new IllegalArgumentException("Can't set upper to " + i + " < lower");
            }
            IntPair newValue = new IntPair(oldValue.lower, i);
            if (values.compareAndSet(oldValue,newValue)) {
                break;
            }
        }
    }

}

2.2 非阻塞的栈

/**
 *《并发编程实战》-第15章
 * 非阻塞栈
 * @since 2022/4/27
 */
public class ConcurrentStack<E> {

    private AtomicReference<Node<E>> top = new AtomicReference<>();

    public void push(E item) {
        Node<E> newTop = new Node<>(item);
        Node<E> oldTop;
        do {
            oldTop = top.get();
            newTop.next = oldTop;
        } while (!top.compareAndSet(oldTop, newTop));
    }

    public E pop() {
        Node<E> oldTop;
        do {
            oldTop = top.get();
            if (oldTop == null) {
                return null;
            }
        } while (!top.compareAndSet(oldTop, oldTop.next));
        oldTop.next = null;
        return oldTop.item;
    }

    private static class Node<E> {
        public final E item;
        public Node<E> next;

        public Node(E item) {
            this.item = item;
        }
    }

}

2.3 非阻塞的队列

/**
 *《并发编程实战》-第15章
 * 非阻塞链表
 * @since 2022/4/30
 */
public class LinkQueue<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);

    /**
     * 推入队列尾部
     * 分 2 步 CAS：
     * 1. 设置 tail.next 为 newNode
     * 2. 设置 tail 为 tail.next
     */
    public boolean put(E item) {
        Node<E> newNode = new Node<>(item, null);
        while (true) {
            Node<E> curTail = tail.get();
            Node<E> next = curTail.next.get();
            if (curTail != tail.get()) {
                continue;
            }
            if (next != null) {
                // 中间态，可能成功或失败
                // 2. 设置 tail 为 tail.next
                tail.compareAndSet(curTail, next);
            } else {
                // 1. 设置 tail.next 为新增加的 item
                if (curTail.next.compareAndSet(null, newNode)) {
                    // 中间态，可能成功或失败
                    // 2. 设置 tail 为 tail.next
                    tail.compareAndSet(curTail, newNode);
                    return true;
                }
            }
        }
    }

    /**
     * 返回队列头部
     */
    public E pop() {
        while (true) {
            // head 是一个哨兵节点，下一个节点才是数据
            Node<E> curHead = head.get();
            Node<E> firstNode = curHead.next.get();
            if (firstNode == null) {
                return null;
            }
            Node<E> secondNode = firstNode.next.get();
            if (curHead.next.compareAndSet(firstNode, secondNode)) {
                firstNode.next.set(null);
                return firstNode.item;
            }
        }
    }

    private static class Node<E> {
        final E item;
        final AtomicReference<Node<E>> next;

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

}