非阻塞队列

非阻塞队列 

首先我们要简单的理解下什么是非阻塞队列： 
与阻塞队列相反，非阻塞队列的执行并不会被阻塞，无论是消费者的出队，还是生产者的入队。 在底层，非阻塞队列使用的是CAS(compare and swap)来实现线程执行的非阻塞。 

非阻塞队列简单操作 

与阻塞队列相同，非阻塞队列中的常用方法，也是出队和入队。 

入队方法： 

n  add()：底层调用offer(); 

n  offer()：Queue接口继承下来的方法，实现队列的入队操作，不会阻碍线程的执行，插入成功返回true； 出队方法： 

n  poll()：移动头结点指针，返回头结点元素，并将头结点元素出队；队列为空，则返回null； 

n  peek()：移动头结点指针，返回头结点元素，并不会将头结点元素出队；队列为空，则返回null； 

➢ 非阻塞算法CAS 

首先我们需要了解悲观锁和乐观锁 
悲观锁：假定并发环境是悲观的，如果发生并发冲突，就会破坏一致性，所以要通过独占锁彻底禁止冲突发生。有一个经典比喻，“如果你不锁门，那么捣蛋鬼就回闯入并搞得一团糟”，所以“你只能一次打开门放进

一个人，才能时刻盯紧他”。 

乐观锁：假定并发环境是乐观的，即，虽然会有并发冲突，但冲突可发现且不会造成损害，所以，可以不加任何保护，等发现并发冲突后再决定放弃操作还是重试。可类比的比喻为，“如果你不锁门，那么虽然捣蛋鬼会闯入，但他们一旦打算破坏你就能知道”，所以“你大可以放进所有人，等发现他们想破坏的时候再做决定”。 通常认为乐观锁的性能比悲观所更高，特别是在某些复杂的场景。这主要由于悲观锁在加锁的同时，也会把某些不会造成破坏的操作保护起来；而乐观锁的竞争则只发生在最小的并发冲突处，如果用悲观锁来理解，就是“锁的粒度最小”。但乐观锁的设计往往比较复杂，因此，复杂场景下还是多用悲观锁。 

首先保证正确性，有必要的话，再去追求性能。 

CAS 
乐观锁的实现往往需要硬件的支持，多数处理器都都实现了一个CAS指令，实现“Compare And Swap”的语义（这里的swap是“换入”，也就是set），构成了基本的乐观锁。 

CAS包含3个操作数： 

n  需要读写的内存位置V

n  进行比较的值A 

n  拟写入的新值B 
当且仅当位置 V 的值等于A 时，CAS 才会通过原子方式用新值 B 来更新位置 V 的值；否则不会执行任何操作。无论位置V的值是否等于A，都将返回V原有的值。 

一个有意思的事实是，“使用CAS控制并发”与“使用乐观锁”并不等价。CAS只是一种手段，既可以实现乐观锁，也可以实现悲观锁。乐观、悲观只是一种并发控制的策略。