Java并发编程-CAS与非阻塞算法

一. 锁的弊端

频繁的线程挂起和恢复
当多个线程发生锁竞争时, 那些没有获取锁的线程可能会被挂起并在稍后恢复执行(当发生锁竞争时, jvm不一定直接挂起线程, 而是根据之前获取操作中对锁的持有时间长短来判断是挂起还是自旋等待). 而当线程被唤醒后, 还要等待其他线程执行完他们的时间片以后, 才能被调度执行; 当锁上存在激烈的时候, 调度开销与工作开销的壁纸会非常高
悲观锁与乐观锁
1. 悲观锁:
  锁独占是一项悲观技术, 它假设最坏情况(如果不锁门, 捣蛋鬼就会闯进物资搞得一团糟), 只有在确保其他线程不会对其进行干扰后才能执行下去
2. 乐观锁:
  这种方法首先进行冲突检查判断在更新过程中是否有来自其他线程的干扰, 如果存在, 这个操作失败, 并且继续重试
比较并交换CAS
1. 大多数处理器架构中, 都有cas指令, 即"我认为v的值是A, 如果是则将v的值更新为B, 否则不更新"
2. CAS操作失败时, 不再次进行尝试而是什么不做, 这种做法是可取的; 因为在非阻塞算法中, 如下面的非阻塞链表or队列, 如果cas失败, 意味着其他线程完成了你要执行的操作.
3. CAS在大多数情况下都能执行成功(所竞争不激烈的情况下), 因此硬件能够准确地预测while循环内的分支, 将复杂控制逻辑的开销降到最低
使用CAS维持多个变量的不可变性条件

cas.png

二. 非阻塞算法

基于锁的算法可能发生各种活跃性故障, 如某个线程再持有锁时由于I/O阻塞, 内存缺页或其他延迟导致推迟执行, 则由于延迟中并没有释放锁, 所以其他线程获取锁的操作也会推迟;
如果算法中, 一个线程的失败或挂起不会导致其它线程也失败或挂起, 则这种算法称作非阻塞算法;
如果算法的每个步骤中都存在某个线程可以执行下去, 则这种算法也称为无锁(Lock-Free)算法
许多数据结构都可以使用非阻塞算法实现, 包括栈, 队列, 优先级队列和散列表等, 来实现非阻塞的并发数据结构

2.1 非阻塞的栈

实现相同功能的前提下, 非阻塞算法要比阻塞算法更为复杂; 创建非阻塞算法的关键在于: 如何将原子修改限制于单个变量上, 同时还维护数据的一致性
对于非阻塞算法下实现的栈, 同样要满足上诉2点. 栈是简单的, 因为栈中每个节点仅有一个指针指向另一个节点, 数据一致性也仅仅是栈顶top节点的指向, 且新插入的节点不会改变栈中已有节点的状态
1. push算法:
  1. 首先创建一个新节点newNode, 并将newNode的next指针指向当前旧的top节点, 此时新节点构造完毕;
  2. 若构造节点期间, top没有发生变化, 则更新top为newNode, 否则进入重试. (该步骤由top.compareAndSet(top,newNode))实现
2. pop算法:
  1. 先获取新栈顶top.next
  2. 更新top指针, 若top和获取top.next时的top一样, 说明获取新栈顶的操作没发生其他操作, 则cas更新top

concurrentStack2.png

2.2 非阻塞的队列

难度更大的非阻塞队列
非阻塞的队列实现比非阻塞的栈要复杂, 一个原因是队列需要维护两个节点, head和tail, 前者用于获取队列头部, 后者用于插入元素到队列尾部; 其次, 由于队列数据结构的特点, 其插入操作也更为复杂, 原因如下:
1. 创建新节点后, 既要更新原tail.next指针指向新节点, 又要更新tail指针指向新节点, 是2个独立的更新操作; 如果第一个成功二第二个失败会造成数据不一致
2. 即使这两个更新操作都正常执行, 如果在这两个CAS操作之间, 又有其他线程访问这个队列执行更新, 同样会造成数据不一致
因此我们需要一些技巧:
1. 第一个技巧是: 当线程B执行更新时, 若发现存在另一个线程A正在执行更新(标记变量), 那么B就知道已有一个操作已局部完成, 此时线程B可以等待, 直到A的全部操作完成, 再执行自己的更新, 从而使2个线程互不干扰. 这个方法的一个缺点是, 如果一个线程在更新操作中失败了, 则其他线程再也无法更新队列
2. 另一个技巧是: 线程A的操作执行了一半就因为时间片轮转而挂起了, 此时轮到线程B执行. 若线程B可以发现另一个线程A执行了一半的更新操作, 且B可以帮助A完成剩余的更新操作, 则在此之后B就可以继续执行自己的更新操作; 且在A线程恢复后试图完成这部分操作时, 发现B已经替他完成了. 非阻塞队列都是使用此种方法实现的2个引用的原子操作

线程辅助实现非阻塞队列插入操作
经以上分析, 将采用第二种更新算法同时修改2个指针: 原tail.next指针,和更新tail指针; 现在问题转化为: 线程B如何知道线程A是"2个指针全部更新完毕"还是"2个指针只更新完了1个", 亦或是"2个指针都没有更新"? 如下代码展示了过程:

如果发现tail指针发生变化, 则说明另一个线程已经完成全部2个指针的更新, 自己需要重试;
如果发现tail指针未变化, 则有2种可能:
- (1) 存在另一个线程只完成了第一个指针tail.next的更新(此时tail.next不为空), 还未完成tail的更新: 由于该线程可以知道tail.next指向什么, 因此该线程可以代替完成tail的原子更新
- (2) 不存在另一个线程执行更新操作(此时tail.next = null):
  先后完成自己的2个指针的更新操作, tail.next和tail指针的更新

class ConcurrentLinkedQueue<E>{
    private final Node<E> dummy = new Node<E>(null,null);
    private final AtomicReference<Node<E>> head = new AtomicReference<>(dummy);
    private final AtomicReference<Node<E>> tail = new AtomicReference<>(dummy);

    public boolean put(E elem){
        Node<E> newNode = new Node<E>(elem,null); // 构造新节点
        for(;;){
            Node<E> curTail = tail.get();
            Node<E> curTailNext = curTail.next.get();
            /** 如果第二个指针tail未变化, 则由2中可能: 没有其他线程执行操作,或其他线程完成了第一个指针cur.next的更新
            *  如果第二个指针tail发生了变化, 则应直接进入下一次循环(继续获取tail和tail.next)*/
            if(curTail == tail.get()){   // 第二个指针tail未变化
                if(curTailNext!=null){ // 说明由存在其他线程A更新了第一个指针tail.next, 线程B应该提它完成tail指针的更新(可能A在阻塞)
                    tail.compareAndSet(curTail,curTailNext);
                }else{  // 没有其它线程完成第一个指针tail.next的更新, 则尝试更新自己的tail.next和tail指针
                    if(curTail.next.compareAndSet(null,newNode)){ // 第一个指针更新成功
                        tail.compareAndSet(curTail,newNode); // 第二个指针执行更新
                        return true;
                    }
                }
            }
        }
    }
    private static class Node<E>{
        private final E elem;
        private AtomicReference<Node<E>> next;
        Node(E elem, Node<E> next) {
            this.elem = elem;
            this.next = new AtomicReference<>(next);
        }
    }
}

JDK的ConcurrentLinkedQueue中的算法
JDK的ConcurrentLinkedQueue中的算有一个改进是: 并未使用原子引用 AtomicReference<Node<E>> 表示每个Node, 而是使用普通的volatile类型引用, 并通过基于反射的 AtomicReferenceFieldUpdater 来更新next引用.使用这个方法更新有点繁琐, 但完全是为了提升性能
```
static final AtomicReferenceFieldUpdater<Node,Node> nextUpdater =
        AtomicReferenceFieldUpdater.newUpdater(Node.class,Node.class,"next");
```