前言

如何正确有效的保护共享数据是编写并行程序必须面临的一个难题，通常的手段就是同步。

同步可分为阻塞型同步（Blocking Synchronization）和非阻塞型同步（ Non-blocking Synchronization）。

 

并发方案图示

不同并发方案的复杂程度&加锁力度成反比：

 

阻塞型同步（Blocking Synchronization）

是指当一个线程到达临界区时，因另外一个线程已经持有访问该共享数据的锁， 从而不能获取锁资源而阻塞，直到另外一个线程释放锁。常见的同步原语有 mutex、 semaphore 等。如果同步方案采用不当，就会造成死锁（deadlock），活锁（livelock）和 优先级反转（priority inversion），以及效率低下等现象。

 

非阻塞型同步（ Non-blocking Synchronization）

为了降低风险程度和提高程序运行效率，业界提出了不采用锁的同步方案，依照这种设计思路设计的算法称为非阻塞型算法，其本质特征就是停止一个线程的执行不会阻碍系统中 其他执行实体的运行。

 

当今比较流行的 Non-blocking Synchronization 实现方案有三种：

Wait-free

Wait-free 是指任意线程的任何操作都可以在有限步之内结束，而不用关心其它线程的 执行速度。

Wait-free 是基于 per-thread 的，可以认为是 starvation-free 的。非常遗憾的是 实际情况并非如此，采用 Wait-free 的程序并不能保证 starvation-free，同时内存消耗也随 线程数量而线性增长。目前只有极少数的非阻塞算法实现了这一点。

 

Lock-free

Lock-Free 是指能够确保执行它的所有线程中至少有一个能够继续往下执行。由于每个 线程不是 starvation-free 的，即有些线程可能会被任意地延迟，然而在每一步都至少有一 个线程能够往下执行，因此系统作为一个整体是在持续执行的，可以认为是 system-wide 的。所有 Wait-free 的算法都是 Lock-Free 的。

备注：Lock-Free算法，可以说是乐观锁（CAS？？），如果非激烈竞争的时候，不需要 使用锁，从而开销更小，速度更快。

 

Obstruction-free

Obstruction-free 是指在任何时间点，一个孤立运行线程的每一个操作可以在有限步之 内结束。只要没有竞争，线程就可以持续运行。一旦共享数据被修改，Obstruction-free 要 求中止已经完成的部分操作，并进行回滚。 所有 Lock-Free 的算法都是 Obstruction-free 的。

 

资料整理来自：http://www.cnblogs.com/jobs/archive/2010/07/29/1788156.html