并发-原子变量与非阻塞同步机制

原子变量

1. CAS操作

   • CAS(比较并交换)包含三个操作,需要读写的内存位置V丶进行比较的值A和拟写入的新值B.当且仅当V的值等于A时,CAS才会通过原子方式用新值B来更新V的值,否则不会执行任何操作,无论位置V的值是否等于A,都将返回V原有的值,(比较并设置,无论操作成功都会返回)
   • CAS使用一项乐观的技术,它希望能成功的执行更新操作,当多个线程尝试使用CAS同时更新一个变量时,只有其中一个线程能更新成功,其他线程都会失败,但是失败的线程不会被挂机,而是被告知在这次竞争中失败,并可再次尝试(可以决定是否重新尝试:自旋丶终止)
   • 基于CAS可以实现原子操作,通常情况下比使用锁效率高(多线程高度竞争的情况下,锁的性能将超过原子变量的性能)

2. 原子变量类型

   • 原子变量比锁的粒度更细,将发生竞争的范围缩小到单个变量上

     计数器: AtomicInteger AtomicLong AtomicBoolean AtomicReference
     域更新器: AtomicIntegerFieldUpdater AtomicLongFieldUpdater AtomicReferenceFieldUpdater
     数组: AtomicIntegerArray AtomicLongArray AtomicReferenceArray
     复合变量: AtomicMarkableReference AtomicStampedReference

   • 原子引用(AtomicReference),底层采用compareAndSwapObject实现CAS,比较的是两个对象地址是否相等,仅保证修改对象引用的原子性

     @Test
     public void ReferenceTest(){
       People p1 = new People("Tom");
       People p2 = new People("Jerry");
       //原子引用
       AtomicReference<People> reference = new AtomicReference<>(p1);
       p1.name = "Tom1";
       System.out.println(reference.get().name); //Tom1
       reference.compareAndSet(p1,p2);//原子的更新引用: 将reference引用由p1变为p2
       System.out.println(reference.get().name); //Jerry
     }

   • 操作非原子变量的字段属性,XXXFieldUpdater是基于反射的工具类,它能对指定类的指定volatile引用字段进行原子更新(这个字段不能是private的)

     @Test
     public void atomicTest(){
       AtomicReferenceFieldUpdater<People,String> updater = AtomicReferenceFieldUpdater.newUpdater(People.class,String.class,"name");
       People p = new People();
       //原子更新操作
       updater.compareAndSet(p,p.name,"Tom");
       System.out.println(p.name);//Tom
     }
     
     class People{
       //要更新的非原子变量(必须volatile修饰)
       volatile String name;
     }

   • 复合变量: 解决CAS操作的ABA问题,AtomicStampedReference内部额外增加int类型时间戳(一般自增)记录变量的修改次数,可以知道引用变量中途被修改了几次;AtomicMarkableReference内部使用的是boolean变量,用来表示变量是否被修改过,适用于单纯的关心是否被更改过,不关系更新次数

非阻塞算法

非阻塞算法: 如果在某种算法中,一个线程的失败或者挂起不会导致其他线程也失败或挂起,那么这种算法就是非阻塞算法

无锁(Lock-Free)算法: 如果算法的每个步骤中都存在某个线程能够执行下去,那么这种算法也被称为无锁算法

如果算法中仅将CAS用于协调线程之间的操作,并能正确地实现,那么它既是一种无阻塞算法,又是一种无锁算法

1. 非阻塞的栈

   //非阻塞的链式栈
   public class ConcurrentStack<E> {
    private AtomicReference<Node<E>> top = new AtomicReference<>();
    //非static的内部类对象会隐式的在外部类中保存一个引用,指向创建它的外部类对象
    private static class Node<E>{
        public final E item;
        public Node<E> next;
   
        public Node(E item) {
            this.item = item;
        }
    }
    public void push(E item){
        Node<E> newHead = new Node<>(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;
    }
   }

2. 非阻塞链表

   //非阻塞链表的插入算法
   public class LinkedQueue<E> {
    private static class Node<E>{
        final E item;
        final AtomicReference<Node<E>> next;
        public Node(E item, AtomicReference<Node<E>> next) {
            this.item = item;
            this.next = next;
        }
    }
    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);
   
    //插入: 先更新next,再更新tail,可能状态: 开始->中间状态(next完成)->结束(tail完成)
    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)) {//1.尝试更新next
                        //更新next成功,2.尝试推进尾节点(可能失败,其他线程帮助推进好了)
                        tail.compareAndSet(curTail, newNode);
                        return true;
                    }//否则更新next失败,自旋重新尝试插入操作
                }
            }//否则: 结束状态,无需处理,重新尝试插入操作
        }
    }
   }