临界区执行时间长的情况下，spin_lock 执行效率低于 mutex_lock

spinvsmutex2.c

//Name: spinvsmutex2.c
//http://www.parallellabs.com/2010/01/31/pthreads-programming-spin-lock-vs-mutex-performance-analysis/
//Source: http://www.solarisinternals.com/wiki/index.php/DTrace_Topics_Locks
//Compile(spin lock version): gcc -o spin -DUSE_SPINLOCK spinvsmutex2.c -lpthread
//Compile(mutex version): gcc -o mutex spinvsmutex2.c -lpthread
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <sys/syscall.h>

#define THREAD_NUM 2

pthread_t g_thread[THREAD_NUM];
#ifdef USE_SPINLOCK
pthread_spinlock_t g_spin;
#else
pthread_mutex_t g_mutex;
#endif
__uint64_t g_count;

pid_t gettid()
{
	return syscall(SYS_gettid);
}

void *run_amuck(void *arg)
{
	int i, j;

	printf("Thread %lu started.\n", (unsigned long)gettid());

	for (i = 0; i < 1000; i++) {
#ifdef USE_SPINLOCK
		pthread_spin_lock(&g_spin);
#else
		pthread_mutex_lock(&g_mutex);
#endif
		for (j = 0; j < 10000000; j++) {
			if (g_count++ == 123456789)
				printf("Thread %lu wins!\n", (unsigned long)gettid());
		}
#ifdef USE_SPINLOCK
		pthread_spin_unlock(&g_spin);
#else
		pthread_mutex_unlock(&g_mutex);
#endif
	}

	printf("Thread %lu finished!\n", (unsigned long)gettid());

	return (NULL);
}

int main(int argc, char *argv[])
{
	int i, threads = THREAD_NUM;

	printf("Creating %d threads...\n", threads);
#ifdef USE_SPINLOCK
	pthread_spin_init(&g_spin, 0);
#else
	pthread_mutex_init(&g_mutex, NULL);
#endif
	for (i = 0; i < threads; i++)
		pthread_create(&g_thread[i], NULL, run_amuck, (void *) i);

	for (i = 0; i < threads; i++)
		pthread_join(g_thread[i], NULL);

	printf("Done.\n");

	return (0);
}

pi@I_like_pi:~/c $ time  ./spin
Creating 2 threads...
Thread 24019 started.
Thread 24020 started.
Thread 24020 wins!
Thread 24020 finished!
Thread 24019 finished!
Done.n
real	6m36.263s
user	11m49.910s
sys	0m15.420s
pi@I_like_pi:~/c $ time  ./mutex
Creating 2 threads...
Thread 24378 started.
Thread 24377 started.
Thread 24377 wins!
Thread 24377 finished!
Thread 24378 finished!
Done.n
real	5m57.875s
user	5m52.290s
sys	0m1.650s

由上可以看出，对于锁住耗时比较长的临界区，mutex lock 要比 spin lock 效率要高(spin lock耗费了更多的user time)。
这是因为两个线程分别运行在两个核上，大部分时间只有一个线程能拿到锁，所以另一个线程就一直在它运行的core上进行忙等待，CPU占用率一直是100%；而mutex则不同，当对锁的请求失败后上下文切换就会发生，这样就能空出一个核来进行别的运算任务了。（其实这种上下文切换对已经拿着锁的那个线程性能也是有影响的，因为当该线程释放该锁时它需要通知操作系统去唤醒那些被阻塞的线程，这也是额外的开销）

【转】乐观锁和悲观锁

首先我们理解下两种不同思路的锁，乐观锁和悲观锁。
这两种锁机制，是在多用户环境并发控制的两种所机制。下面看百度百科对乐观锁和悲观锁两种锁机制的定义：

乐观锁（ Optimistic Locking ） 相对悲观锁而言，乐观锁机制采取了更加宽松的加锁机制。悲观锁大多数情况下依靠数据库的锁机制实现，以保证操作最大程度的独占性。但随之而来的就是数据库性能的大量开销，特别是对长事务而言，这样的开销往往无法承受。而乐观锁机制在一定程度上解决了这个问题。乐观锁，大多是基于数据版本（ Version ）记录机制实现。何谓数据版本？即为数据增加一个版本标识，在基于数据库表的版本解决方案中，一般是通过为数据库表增加一个 “version” 字段来实现。读取出数据时，将此版本号一同读出，之后更新时，对此版本号加一。此时，将提交数据的版本数据与数据库表对应记录的当前版本信息进行比对，如果提交的数据版本号大于数据库表当前版本号，则予以更新，否则认为是过期数据。
悲观锁（Pessimistic Lock），正如其名，具有强烈的独占和排他特性。它指的是对数据被外界（包括本系统当前的其他事务，以及来自外部系统的事务处理）修改持保守态度，因此，在整个数据处理过程中，将数据处于锁定状态。悲观锁的实现，往往依靠数据库提供的锁机制（也只有数据库层提供的锁机制才能真正保证数据访问的排他性，否则，即使在本系统中实现了加锁机制，也无法保证外部系统不会修改数据）。
简而言之：
悲观锁：假定会发生并发冲突，屏蔽一切可能违反数据完整性的操作。[1]
乐观锁：假设不会发生并发冲突，只在提交操作时检查是否违反数据完整性。[1] 乐观锁不能解决脏读的问题。
Java中的乐观锁和悲观锁：我们都知道，cpu是时分复用的，也就是把cpu的时间片，分配给不同的thread/process轮流执行，时间片与时间片之间，需要进行cpu切换，也就是会发生进程的切换。切换涉及到清空寄存器，缓存数据。然后重新加载新的thread所需数据。当一个线程被挂起时，加入到阻塞队列，在一定的时间或条件下，在通过notify()，notifyAll()唤醒回来。在某个资源不可用的时候，就将cpu让出，把当前等待线程切换为阻塞状态。等到资源(比如一个共享数据）可用了，那么就将线程唤醒，让他进入runnable状态等待cpu调度。这就是典型的悲观锁的实现。独占锁是一种悲观锁，synchronized就是一种独占锁，它假设最坏的情况，并且只有在确保其它线程不会造成干扰的情况下执行，会导致其它所有需要锁的线程挂起，等待持有锁的线程释放锁。
但是，由于在进程挂起和恢复执行过程中存在着很大的开销。当一个线程正在等待锁时，它不能做任何事，所以悲观锁有很大的缺点。举个例子，如果一个线程需要某个资源，但是这个资源的占用时间很短，当线程第一次抢占这个资源时，可能这个资源被占用，如果此时挂起这个线程，可能立刻就发现资源可用，然后又需要花费很长的时间重新抢占锁，时间代价就会非常的高。
所以就有了乐观锁的概念，他的核心思路就是，每次不加锁而是假设没有冲突而去完成某项操作，如果因为冲突失败就重试，直到成功为止。在上面的例子中，某个线程可以不让出cpu,而是一直while循环，如果失败就重试，直到成功为止。所以，当数据争用不严重时，乐观锁效果更好。比如CAS就是一种乐观锁思想的应用。
JDK1.5中引入了底层的支持，在int、long和对象的引用等类型上都公开了CAS的操作，并且JVM把它们编译为底层硬件提供的最有效的方法，在运行CAS的平台上，运行时把它们编译为相应的机器指令。在java.util.concurrent.atomic包下面的所有的原子变量类型中，比如AtomicInteger，都使用了这些底层的JVM支持为数字类型的引用类型提供一种高效的CAS操作。
在CAS操作中，会出现ABA问题。就是如果V的值先由A变成B，再由B变成A，那么仍然认为是发生了变化，并需要重新执行算法中的步骤。有简单的解决方案：不是更新某个引用的值，而是更新两个值，包括一个引用和一个版本号，即使这个值由A变为B，然后为变为A，版本号也是不同的。AtomicStampedReference和AtomicMarkableReference支持在两个变量上执行原子的条件更新。AtomicStampedReference更新一个“对象-引用”二元组，通过在引用上加上“版本号”，从而避免ABA问题，AtomicMarkableReference将更新一个“对象引用-布尔值”的二元组。

引用《深入理解Java虚拟机第二版》中原文：

13.2.2　线程安全的实现方法
了解了什么是线程安全之后，紧接着的一个问题就是我们应该如何实现线程安全，这听
起来似乎是一件由代码如何编写来决定的事情，确实，如何实现线程安全与代码编写有很大
的关系，但虚拟机提供的同步和锁机制也起到了非常重要的作用。本节中，代码编写如何实
现线程安全和虚拟机如何实现同步与锁这两者都会有所涉及，相对而言更偏重后者一些，只
要读者了解了虚拟机线程安全手段的运作过程，自己去思考代码如何编写并不是一件困难的
事情。
1.互斥同步
互斥同步（Mutual Exclusion＆Synchronization）是常见的一种并发正确性保障手段。同步
是指在多个线程并发访问共享数据时，保证共享数据在同一个时刻只被一个（或者是一些，
使用信号量的时候）线程使用。而互斥是实现同步的一种手段，临界区（Critical
Section）、互斥量（Mutex）和信号量（Semaphore）都是主要的互斥实现方式。因此，在这
4个字里面，互斥是因，同步是果；互斥是方法，同步是目的。
在Java中，最基本的互斥同步手段就是synchronized关键字，synchronized关键字经过编译
之后，会在同步块的前后分别形成monitorenter和monitorexit这两个字节码指令，这两个字节
码都需要一个reference类型的参数来指明要锁定和解锁的对象。如果Java程序中的
synchronized明确指定了对象参数，那就是这个对象的reference；如果没有明确指定，那就根
据synchronized修饰的是实例方法还是类方法，去取对应的对象实例或Class对象来作为锁对
象。
根据虚拟机规范的要求，在执行monitorenter指令时，首先要尝试获取对象的锁。如果这
个对象没被锁定，或者当前线程已经拥有了那个对象的锁，把锁的计数器加1，相应的，在
执行monitorexit指令时会将锁计数器减1，当计数器为0时，锁就被释放。如果获取对象锁失
败，那当前线程就要阻塞等待，直到对象锁被另外一个线程释放为止。
在虚拟机规范对monitorenter和monitorexit的行为描述中，有两点是需要特别注意的。首
先，synchronized同步块对同一条线程来说是可重入的，不会出现自己把自己锁死的问题。其
次，同步块在已进入的线程执行完之前，会阻塞后面其他线程的进入。第12章讲过，Java的
线程是映射到操作系统的原生线程之上的，如果要阻塞或唤醒一个线程，都需要操作系统来
帮忙完成，这就需要从用户态转换到核心态中，因此状态转换需要耗费很多的处理器时间。
对于代码简单的同步块（如被synchronized修饰的getter（）或setter（）方法），状态转换消
耗的时间有可能比用户代码执行的时间还要长。所以synchronized是Java语言中一个重量级
（Heavyweight）的操作，有经验的程序员都会在确实必要的情况下才使用这种操作。而虚拟
机本身也会进行一些优化，譬如在通知操作系统阻塞线程之前加入一段自旋等待过程，避免
频繁地切入到核心态之中。
除了synchronized之外，我们还可以使用java.util.concurrent（下文称J.U.C）包中的重入锁
（ReentrantLock）来实现同步，在基本用法上，ReentrantLock与synchronized很相似，他们都
具备一样的线程重入特性，只是代码写法上有点区别，一个表现为API层面的互斥锁
（lock（）和unlock（）方法配合try/finally语句块来完成），另一个表现为原生语法层面的互
斥锁。不过，相比synchronized,ReentrantLock增加了一些高级功能，主要有以下3项：等待可
中断、可实现公平锁，以及锁可以绑定多个条件。
等待可中断是指当持有锁的线程长期不释放锁的时候，正在等待的线程可以选择放弃等
待，改为处理其他事情，可中断特性对处理执行时间非常长的同步块很有帮助。
公平锁是指多个线程在等待同一个锁时，必须按照申请锁的时间顺序来依次获得锁；而
非公平锁则不保证这一点，在锁被释放时，任何一个等待锁的线程都有机会获得锁。
synchronized中的锁是非公平的，ReentrantLock默认情况下也是非公平的，但可以通过带布尔
值的构造函数要求使用公平锁。
锁绑定多个条件是指一个ReentrantLock对象可以同时绑定多个Condition对象，而在
synchronized中，锁对象的wait（）和notify（）或notifyAll（）方法可以实现一个隐含的条
件，如果要和多于一个的条件关联的时候，就不得不额外地添加一个锁，而ReentrantLock则
无须这样做，只需要多次调用newCondition（）方法即可。
如果需要使用上述功能，选用ReentrantLock是一个很好的选择，那如果是基于性能考虑
呢？关于synchronized和ReentrantLock的性能问题，Brian Goetz对这两种锁在JDK 1.5与单核处
理器，以及JDK 1.5与双Xeon处理器环境下做了一组吞吐量对比的实验 [1] ，实验结果如图13-1
和图13-2所示。
图　13-1　JDK 1.5、单核处理器下两种锁的吞吐量对比
从图13-1和图13-2可以看出，多线程环境下synchronized的吞吐量下降得非常严重，而
ReentrantLock则能基本保持在同一个比较稳定的水平上。与其说ReentrantLock性能好，还不
如说synchronized还有非常大的优化余地。后续的技术发展也证明了这一点，JDK 1.6中加入
了很多针对锁的优化措施（13.3节我们就会讲解这些优化措施），JDK 1.6发布之后，人们就
发现synchronized与ReentrantLock的性能基本上是完全持平了。因此，如果读者的程序是使用
JDK 1.6或以上部署的话，性能因素就不再是选择ReentrantLock的理由了，虚拟机在未来的性
能改进中肯定也会更加偏向于原生的synchronized，所以还是提倡在synchronized能实现需求
的情况下，优先考虑使用synchronized来进行同步。
图　13-2　JDK 1.5、双Xeon处理器下两种锁的吞吐量对比
2.非阻塞同步
互斥同步最主要的问题就是进行线程阻塞和唤醒所带来的性能问题，因此这种同步也称
为阻塞同步（Blocking Synchronization）。从处理问题的方式上说，互斥同步属于一种悲观的
并发策略，总是认为只要不去做正确的同步措施（例如加锁），那就肯定会出现问题，无论
共享数据是否真的会出现竞争，它都要进行加锁（这里讨论的是概念模型，实际上虚拟机会
优化掉很大一部分不必要的加锁）、用户态核心态转换、维护锁计数器和检查是否有被阻塞
的线程需要唤醒等操作。随着硬件指令集的发展，我们有了另外一个选择：基于冲突检测的
乐观并发策略，通俗地说，就是先进行操作，如果没有其他线程争用共享数据，那操作就成
功了；如果共享数据有争用，产生了冲突，那就再采取其他的补偿措施（最常见的补偿措施
就是不断地重试，直到成功为止），这种乐观的并发策略的许多实现都不需要把线程挂起，
因此这种同步操作称为非阻塞同步（Non-Blocking Synchronization）。
为什么笔者说使用乐观并发策略需要“硬件指令集的发展”才能进行呢？因为我们需要操
作和冲突检测这两个步骤具备原子性，靠什么来保证呢？如果这里再使用互斥同步来保证就
失去意义了，所以我们只能靠硬件来完成这件事情，硬件保证一个从语义上看起来需要多次
操作的行为只通过一条处理器指令就能完成，

这类指令常用的有：
测试并设置（Test-and-Set）。
获取并增加（Fetch-and-Increment）。
交换（Swap）。
比较并交换（Compare-and-Swap，下文称CAS）。
加载链接/条件存储（Load-Linked/Store-Conditional，下文称LL/SC）。

其中，前面的3条是20世纪就已经存在于大多数指令集之中的处理器指令，后面的两条
是现代处理器新增的，而且这两条指令的目的和功能是类似的。在IA64、x86指令集中有
cmpxchg指令完成CAS功能，在sparc-TSO也有casa指令实现，而在ARM和PowerPC架构下，
则需要使用一对ldrex/strex指令来完成LL/SC的功能。
CAS指令需要有3个操作数，分别是内存位置（在Java中可以简单理解为变量的内存地
址，用V表示）、旧的预期值（用A表示）和新值（用B表示）。CAS指令执行时，当且仅当
V符合旧预期值A时，处理器用新值B更新V的值，否则它就不执行更新，但是无论是否更新
了V的值，都会返回V的旧值，上述的处理过程是一个原子操作。
在JDK 1.5之后，Java程序中才可以使用CAS操作，该操作由sun.misc.Unsafe类里面的
compareAndSwapInt（）和compareAndSwapLong（）等几个方法包装提供，虚拟机在内部对
这些方法做了特殊处理，即时编译出来的结果就是一条平台相关的处理器CAS指令，没有方
法调用的过程，或者可以认为是无条件内联进去了 [2] 。
由于Unsafe类不是提供给用户程序调用的类（Unsafe.getUnsafe（）的代码中限制了只有
启动类加载器（Bootstrap ClassLoader）加载的Class才能访问它），因此，如果不采用反射
手段，我们只能通过其他的Java API来间接使用它，如J.U.C包里面的整数原子类，其中的
compareAndSet（）和getAndIncrement（）等方法都使用了Unsafe类的CAS操作。
我们不妨拿一段在第12章中没有解决的问题代码来看看如何使用CAS操作来避免阻塞同
步，代码如代码清单12-1所示。我们曾经通过这段20个线程自增10000次的代码来证明
volatile变量不具备原子性，那么如何才能让它具备原子性呢？把“race++”操作或increase（）
方法用同步块包裹起来当然是一个办法，但是如果改成如代码清单13-4所示的代码，那效率
将会提高许多。
代码清单13-4　Atomic的原子自增运算
/**
*Atomic变量自增运算测试
*
@author
/
public class AtomicTest{
public static AtomicInteger race=new AtomicInteger（0）；
public static void increase（）{
race.incrementAndGet（）；
}
private static final int THREADS_COUNT=20；
public static void main（String[]args）throws Exception{
Thread[]threads=new Thread[THREADS_COUNT]；
for（int i=0；i＜THREADS_COUNT；i++）{
threads[i]=new Thread（new Runnable（）{
@OverRide
public void run（）{
for（int i=0；i＜10000；i++）{
increase（）；
}
}
}）；
threads[i].start（）；
}
while（Thread.activeCount（）＞1）
Thread.yield（）；
System.out.println（race）；
}
}
运行结果如下：
200000
使用AtomicInteger代替int后，程序输出了正确的结果，一切都要归功于
incrementAndGet（）方法的原子性。它的实现其实非常简单，如代码清单13-5所示。
代码清单13-5　incrementAndGet（）方法的JDK源码
/
*Atomically increment by one the current value.
*@return the updated value
*/
public final int incrementAndGet（）{
for（；）{
int current=get（）；
int next=current+1；
if（compareAndSet（current,next））
return next；
}
}
incrementAndGet（）方法在一个无限循环中，不断尝试将一个比当前值大1的新值赋给
自己。如果失败了，那说明在执行“获取-设置”操作的时候值已经有了修改，于是再次循环
进行下一次操作，直到设置成功为止。
尽管CAS看起来很美，但显然这种操作无法涵盖互斥同步的所有使用场景，并且CAS从
语义上来说并不是完美的，存在这样的一个逻辑漏洞：如果一个变量V初次读取的时候是A
值，并且在准备赋值的时候检查到它仍然为A值，那我们就能说它的值没有被其他线程改变
过了吗？如果在这段期间它的值曾经被改成了B，后来又被改回为A，那CAS操作就会误认
为它从来没有被改变过。这个漏洞称为CAS操作的“ABA”问题。J.U.C包为了解决这个问题，
提供了一个带有标记的原子引用类“AtomicStampedReference”，它可以通过控制变量值的版本
来保证CAS的正确性。不过目前来说这个类比较“鸡肋”，大部分情况下ABA问题不会影响程
序并发的正确性，如果需要解决ABA问题，改用传统的互斥同步可能会比原子类更高效。

锁优化
高效并发是从JDK 1.5到JDK 1.6的一个重要改进，HotSpot虚拟机开发团队在这个版本上
花费了大量的精力去实现各种锁优化技术，如适应性自旋（Adaptive Spinning）、锁消除
（Lock Elimination）、锁粗化（Lock Coarsening）、轻量级锁（Lightweight Locking）和偏向
锁（Biased Locking）等，这些技术都是为了在线程之间更高效地共享数据，以及解决竞争问
题，从而提高程序的执行效率。

并发下的单例模式：
http://blog.csdn.net/cselmu9/article/details/51366946