CAS(Compare and Swap)无锁算法 与 ConcurrentLinkedQueue 队列

• 了解CAS 我们就先了解一下乐观锁与悲观锁：

  独占锁是一种悲观锁，synchronized就是一种独占锁，它假设最坏的情况，并且只有在确保其它线程不会造成干扰的情况下执行，会导致其它所有需要锁的线程挂起，等待持有锁的线程释放锁。而另一个更加有效的锁就是乐观锁。

  所谓乐观锁就是，每次不加锁而是假设没有冲突而去完成某项操作，如果因为冲突失败就重试，直到成功为止。CAS就是乐观锁运用到的策略。

• CAS比较交换（无锁算法）

  与锁相比，使用比较交换（下文简称CAS)会使程序看起来更加复杂一些。但由于其非阻塞性，它对死锁问题天生免疫，并且，线程间的相互影响也远远比基于锁的方式要小。更为重要的是，使用无锁的方式完全没有锁竞争带来的系统开销，也没有线程间频繁调度带来的开销，因此，它要比基于锁的方式拥有更优越的性能。

  CAS算法的过程是这样：它包含三个参数CAS(V，E，N)。V表示要更新的变量，E表示预期值，N表示新值。仅当V值等于E值时，才会将V的值设为N,如果V值和E值不同，则说明己经有其他线程做了更新，则当前线程什么都不做。最后，CAS返回当前V的真实值。 CAS操作是抱着乐观的态度进行的，它总是认为自己可以成功完成操作。当多个线程同时使用CAS操作一个变量时，只有一个会胜出，并成功更新，其余均会失败。失败的线程不会被挂起，仅是被告知失败，并且允许再次尝试，当然也允许失败的线程放弃操作。基于这样的原理， CAS操作即使没有锁，也可以发现其他线程对当前线程的干扰，并进行恰当的处理。

  简单地说，CAS需要你额外给出一个期望值，也就是你认为这个变量现在应该是什么样子的。如果变量不是你想象的那样，那说明它己经被别人修改过了。你就重新读取，再次尝试就好了。
  我们简单来说一下 volatile Atomic
  volatile似乎是有时候可以代替简单的锁，似乎加了volatile关键字就省掉了锁。但又说volatile不能保证原子性（java程序员很熟悉这句话：volatile仅仅用来保证该变量对所有线程的可见性，但不保证原子性）（有机会我详细了解一下volatile ）
  AtomicXXX运用了上面的CAS+volatile 进行完善，使之不尽具有原子性与可见性结合。
  - ConcurrentLinkedQueue 队列

  我们简单了解了 CAS ，那我们就来看看乐观的LinkedQueue ，想要了解ConcurrentLinkedQueue 必须 他的插入原理即offer（）方法，先了解一下他理论的插入情景（图片来源：http://ifeve.com/concurrentlinkedqueue/）：
  
  其实在ConcurrentLinkedQueue 设计中它允许在运行时链表处于多个不同的状态，如tail为例，一般我们是期望tail总是为链表的尾部，但实际上tail是允许两次或者更多的节点延迟（参考很多地方并没有提出更多的节点延误，但是代码里确实是有展示的，并且源码有提醒了，可能大家都没太注意吧，如果是我理解错误，希望提醒）。那我们来看下这个方法的代码实现吧：

    public boolean offer(E e) {
        checkNotNull(e);
        final Node<E> newNode = new Node<E>(e);

        for (Node<E> t = tail, p = t;;) {
            Node<E> q = p.next;
            if (q == null) {
                // p is last node（p节点已经是最后一个节点）
                if (p.casNext(null, newNode)) {
                    // Successful CAS is the linearization point
                    // for e to become an element of this queue,
                    // and for newNode to become "live".（插入成功）
                    if (p != t) // hop two nodes at a time（每次跳跃两个节点）
                        casTail(t, newNode);  // Failure is OK.
                        //（失败也是可以的，正式因为这句话，如果失败了，可能导致节点延误2个节点以上）
                    return true;
                }
                // Lost CAS race to another thread; re-read next（插入失败再次进入循环）
            }
            else if (p == q)
                // We have fallen off list.  If tail is unchanged, it
                // will also be off-list, in which case we need to
                // jump to head, from which all live nodes are always
                // reachable.  Else the new tail is a better bet.
                //进入哨兵节点从head从新遍历
                //进行最后赌注行测试是否tail已经改变。改变则用tail
                p = (t != (t = tail)) ? t : head;
            else
                // Check for tail updates after two hops.
                //取下一个节点或者最后节点。
                p = (p != t && t != (t = tail)) ? t : q;
        }
    }

处理了 p=q的情况。这种情况是由于遇到了哨兵（sentinel)节点导致的。所谓哨兵节点，就是next指向自己的节点。这种节点在队列中的存在价值不大，主要表示要删除的节点，或者空节点。当遇到哨兵节点时，由于无法通过next取得后续的节点，因此很可能直接返回head，期望通过从链表头部开始遍历，进一步查找到链表末尾。但一旦发生在执行过程中，tail被其他线程修改的情况，则进行一次“打赌”，使用新的tail作为链表末尾（这样就避免了重新查找tail的开销）。

这句代码虽然只有短短一行，但是包含的信息比较多。首先“!=”并不是原子操作，它是可以被中断的。也就是说，在执行“!=”是，程序会先取得t的值，再执行并取得新的t的值。然后比较这两个值是否相等。在单线程时，t!=t这种语句显然不会成立。但是在并发环境中，有可能在获得左边的t值后，右边的t值被其他线程修改。这样，t!=t就可能成立。这里就是这种情况。如果在比较过程中，tail被其他线程修改，当它再次赋值给t时，就会导致等式左边的 t和右边的 t不同。如果两个 t不相同，表示 tail在中途被其他线程篡改。这时，我们就可以用新的tail作为链表末尾，也就是这里等式右边的t。但如果tail没有被修改，则返回head,要求从头部开始，重新查找尾部。

• ConcurrentLinkedQueue性能
  我测试了一下ConcurrentLinkedQueue 是锁插入速度的2倍。也就是说不使用锁而单纯地使用CAS操作会要求在应用层面保证线程安全，并处理一些可能存在的不一致问题，大大增加了程序设计和实现的难度。但是它带来的好处就是可以得到性能的飞速提升。因此，在有些场合也是值得的。