并发算法
1 阻塞算法
基本所有加锁的算法都可以说是阻塞的。某个线程所引起的意外延迟会阻止其他线程继续运行。在最坏的情况下，某个占有锁的线程可能被睡眠，从而阻止其他等待的线程进行接下来的任何操作。
定义： 一个方法被称为阻塞的，即这个方法在其演进过程中不能正常运行直到其他(占有锁的)线程释放。
1.1 无饥饿(non-starvation)
定义：只有有一个线程在互斥区中，那么一些希望进入互斥区的线程最终都能够进入互斥区域(即使之前在互斥区中的线程意外停止了)。
2 非阻塞算法(non-blocking algorithm)
如果一个线程的失败或暂停不会导致另一个线程的失败或暂停，这样的算法就称为非阻塞算法。 在Java并发包中，volatile和CAS是实现非阻塞算法的基本构造块。
2.1 无锁(Lock-Free)
如果一个方法是lock-free的，它能保证线程无限次调用这个方法都能够在有限步内完成。(A non-blocking algorithm is lock-free if there is guaranteed system-wide progress)
2.2 无等待(wait-Free)
如果一个方法是wait-free的，它能保证每一次调用都可以在有限的步骤内结束。(wait-free if there is also guaranteed per-thread progress)
3 Java中非阻塞数据结构
- ConcurrentLinkedQueue is wait-free according to the javadoc
- ConcurrentLinkedDeque is lock-free according to the source
- ConcurrentSkipListMap is lock-free according to the source
- ConcurrentSkipListSet is based on the CSLMap and has the same guarantees
- NonBlockingHashMap (Highly Scalable Java) is a lock-free according to the javadoc
- NonBlockingHashSet (Highly Scalable Java) is based on the NBHMap and has the same guarantees
- ConcurrentHashMap while not fully lock free this should still be called out since it frequently out performs the CSLMap and the NBHMap
- Disruptor by LMAX-Exchange is a framework with a wait-free ring buffer at its core