Skip to content

Latest commit

 

History

History
183 lines (141 loc) · 6.85 KB

02-非阻塞同步机制.md

File metadata and controls

183 lines (141 loc) · 6.85 KB
Raw

非阻塞同步机制

对比锁与非阻塞同步机制

锁

  • 优势： 线程之间存在竞争时，锁能自动处理竞争问题，即让一个线程拿到锁执行，然后阻塞其他线程。
  • 劣势： 线程被阻塞到恢复执行的过程中存在很大的性能开销。
    • 有一些智能的 JVM 会根据之前的操作对锁的持有时间的长短，判断是自旋等待还是挂起线程，以提高性能。

非阻塞同步：CAS（Compare and Set）比较并设置

  • 输入：
    • 需要读写的内存位置 V
    • 我们认为这个位置现在的值 A
    • 想要写入的新值 B
  • 输出： V 位置以前的值（无论写入操作是否成功）
  • 含义： 我们认为 V 处的值应该是 A，如果是，把 V 处的值改为 B，如果不是则不修改，然后把 V 处现在的值返回给我。

乐观锁与悲观锁

锁与 CAS 分别对应着悲观锁与乐观锁这两种不同的锁。它们的定义如下：

  • 悲观锁
    • 就是独占锁，假设最坏情况，同一时刻只允许一个线程执行
    • 适合写多读少，锁竞争严重的情况 （当资源竞争严重时，CAS 大概率会自旋，会浪费 CPU 资源）
  • 乐观锁
    • 借助冲突检查机制判断在更新状态的过程中有没有其他线程修改状态，如果有，更新操作失败，可以选择重试
    • 适合读多写少，资源竞争少的情况 （资源竞争少时，使用 synchronized 同步锁会进行线程的阻塞和唤醒，而 CAS 不需要切换线程，并且自旋概率较低）

非阻塞算法

我们一般通过使用原子变量类来实现非阻塞同步算法，因为它们有 compareAndSet 方法

非阻塞计数器（基于 1 个CAS）

public class CasCounter {
    private SimulatedCAS value;
    
    public int getValue() {
        return value.get();
    }
    
    public int increment() {
        int v;
        // 以下3行为CAS的标准使用方式：
        // 1. 使用do-while循环，在do中先获取oldValue值
        // 2. 在while的判断中进行CAS操作，并将返回值与do语句块中获取的oldValue比较
        // 3. 直到CAS成功才结束循环
        do {
            v = value.get();
        } while (v != value.compareAndSwap(v, v + 1));
        return v + 1;
    }
}

非阻塞栈（基于 1 个CAS）

通过链表实现，链表头是栈顶元素，在进行 push 和 pop 操作时，判断栈顶元素是否发生了了改变，以此为依据判断该栈是否被修改过。因为栈被修改的话，变的只能是栈顶元素，所以我们只需要通过 CAS 维护一个栈顶元素即可。

public class ConcurrentStack <E> {
    AtomicReference<Node<E>> top = new AtomicReference<Node<E>>(); // 栈顶元素

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

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

    private static class Node <E> {
        public final E item;
        public Node<E> next;
        public Node(E item) {
            this.item = item;
        }
    }
}

非阻塞链表队列（基于 2 个CAS）！！！

非阻塞链表队列的实现要比栈复杂很多，因为它的插入和删除节点的操作需要修改两个指针，也就是说需要两个CAS！

链表队列的插入操作需要更新以下两个指针：

  • 当前最后一个元素的 next 指针
  • 尾结点指针

在这两个操作中间，链表队列处在一种中间状态。

解决方法：

  • 可以通过检查 tail.next 是否为空来判断队列当前的状态。
    • tail.next 为空，链表队列处于稳定状态
    • tail.next 不为空，链表队列处于中间状态
  • 对于处于中间状态的链表队列，我们就进行 tail = tail.next，提前结束其他线程正在进行的插入操作，提前使队列恢复稳定状态。
public class LinkedQueue <E> {
    private static class Node <E> {
        final E item;
        final AtomicReference<LinkedQueue.Node<E>> next;
        public Node(E item, LinkedQueue.Node<E> next) {
            this.item = item;
            this.next = new AtomicReference<LinkedQueue.Node<E>>(next);
        }
    }

    private final LinkedQueue.Node<E> dummy = new LinkedQueue.Node<E>(null, null);
    private final AtomicReference<LinkedQueue.Node<E>> head
            = new AtomicReference<LinkedQueue.Node<E>>(dummy);
    private final AtomicReference<LinkedQueue.Node<E>> tail
            = new AtomicReference<LinkedQueue.Node<E>>(dummy);

    public boolean put(E item) {
        LinkedQueue.Node<E> newNode = new LinkedQueue.Node<E>(item, null);
        while (true) {
            LinkedQueue.Node<E> curTail = tail.get();
            LinkedQueue.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;
                    }
                }
            }
        }
    }
}

ABA 问题

问题描述： V 处的值经历了 A -> B -> A 的变化后，也认为是发生了变化的，而传统的 CAS 是无法发现这种变化的。

解决方法：

  • 使用 AtomicStampedReference 的 int stamp 版本号判断数据是否被修改过
  • 使用 AtomicMarkableReference 的 boolean marked 判断数据是否被修改过