杂记：Java 的无锁编程和锁优化
Peterson 算法（Dekker 算法的演化），这个算法设计得很巧妙，理解的核心就是搞清楚三个标志位是怎样控制两个方法对临界区的访问的：
volatile int flag1 = 0; //主观因素：flag1 表示方法 1 自身是否要求进入临界区
volatile int flag2 = 0; //主观因素：flag2 表示方法 2 自身是否要求进入临界区
volatile int turn = 1; //客观因素：turn 取 1 和 2 分别表示当前临界区针对方法 1 还是方法 2 开放
void fun1(){
flag1 = 1;
turn = 2;
while( flag2==1 && turn==2 ){} //只有在方法 2 自身要求进入临界区且临界区针对方法 2 开放时，方法 1 才会阻塞
//Critical Section
... //临界区内
flag1 = 0;
}
void fun2(){
flag2 = 1;
turn = 1;
while( flag1==1 && turn==1 ){} //只有在方法 1 自身要求进入临界区且临界区针对方法 1 开放时，方法 1 才会阻塞
//Critical Section
... //临界区内
flag2 = 0;
} ConcurrentHashMap，设计巧妙，用桶粒度的锁，避免了 put 和 get 中对整个 map 的锁定，尤其在 get 中，只对一个 HashEntry 做锁定操作，性能提升是显而易见的。
细节参见 http://www.iteye.com/topic/344876 ，有详细的讨论；而在 https://www.ibm.com/developerworks/java/library/j-jtp08223/ ，这里有关于 Java 内存模型结合 ConcurrentHashMap 的分析。
HashMap 不是线程安全的，错误的使用并发状况下可能出现 CPU100% 的状况：
/**
* Transfers all entries from current table to newTable.
*/
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry e = src[j];
if (e != null) {
src[j] = null;
do {
Entry next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
} 问题最终就出现在 HashMap 中 transfer 方法的这个 while 循环上，这个方法在 HashMap 扩容时调用，详细分析见：
http://blog.sina.com.cn/s/blog_56146a210100owft.html
在 Lock-Free 世界里，最简单也最普遍的一个通用原语是CAS(Compare and Swap) 操作。支持并发的现代的处理器都提供了这个原语的硬件实现。CAS 原语负责比较某个内存地址处的内容与一个期望值，如果比较成功则将该内存地址处的内容替换为一个新值。这整个操作是原子的。
这里有对无锁并发编程的介绍：http://www.cnblogs.com/lucifer1982/archive/2008/04/16/1154727.html
如果站在语言层面之上，仅从设计的层面看，可以免锁的思路至少包括：
1、单线程来主导行为，多线程池化操作避开状态变量。
比如在一个 WEB 应用中，每一个 Action 都可以给相应的用户线程分配一个实例，线程之间互不干扰；但是到了业务逻辑 Service 内，避开 Service 状态变量的使用，减少了开发人员对并发编程的关注。
2、函数式编码。
函数式编码是最天然的和最高效的免锁方式，如果你对函数式编码还不了解，请参看这篇文章。
3、资源局部复制、异步处理。
总所周知对资源的争夺是造成锁的一个重要原因，在很多情况下，资源只能有一份，但是对使用资源的每个线程来说，都可以看到属于它自己的一份（这一份并非是真正的资源，很可能只是一个缓冲区，每个线程使用它自己的一个缓冲区，到一定程度时将缓冲区的数据处理到唯一资源中，这就减少了需要加锁对线程的影响），无需考虑并发地去使用。
4、不变对象。
不妨参考 ConcurrentHashMap 的实现，其中的节点是不变的。对象不变性是保证线程安全的重要方式之一。
Java 的锁操作和锁优化：
锁自旋
线程要进入阻塞状态，肯定需要调用操作系统的函数来完成从用户态进入内核态的过程，这一步通常是性能低下的。
那么在遇到锁的争用时，或许等待线程可以不那么着急进入阻塞状态，而是等一等，看看锁是不是马上就释放了，这就是锁自旋。锁自旋在多处理器上有重要价值。
当然锁自旋也带来了一些问题，比如如何判断自旋周期，如何确定自旋锁的个数，如何处理线程优先级差异等。
锁偏向
锁偏向是 JDK1.6 引入的，主要为了解决在没有竞争情况下锁的性能问题。
锁都是可重入的，在已经获得锁的情况下，该线程可以多次锁住该对象，但是每次执行这样的操作会因为 CAS（CPU 的 Compare-And-Swap 指令）操作而造成一些开销，为了减少这种开销，这个锁会偏向于第一个获得它的线程，如果在接下来的执行过程中，该锁没有被其他的线程获取，则持有偏向锁的线程将永远不需要再进行同步。
锁消除
（JDK1.6）锁削除是指虚拟机即时编译器在运行时，对一些代码上要求同步，但是被检测到不可能存在共享数据竞争的锁进行削除。
锁膨胀
（JDK1.6）和数据库中的锁升级有些相似，多个或多次调用粒度太小的锁，进行加锁解锁的消耗，反而还不如一次大粒度的锁调用来得高效，因此 JVM 可将锁的范围优化到更大的区域。
轻量级锁
（JDK1.6）轻量级锁能提升程序同步性能的依据是 “对于绝大部分的锁，在整个同步周期内都是不存在竞争的”，这是一个经验数据。轻量级锁在当前线程的栈帧中建立一个名为锁记录的空间，用于存储锁对象目前的指向和状态。如果没有竞争，轻量级锁使用 CAS 操作避免了使用互斥量的开销，但如果存在锁竞争，除了互斥量的开销外，还额外发生了 CAS 操作，因此在有竞争的情况下，轻量级锁会比传统的重量级锁更慢。
———————————————————————————————————-
2012 年 11 月 16 日：
今天看到一个 C#实现的读共享写互斥的代码：
class ReaderAndWriter
{
private static Mutex mut = new Mutex();//用于保护读者数量的互斥信号量
private static Mutex rw = new Mutex();//保证读者写者互斥的信号量
static int count = 0;//读者数量
private static void Reader()
{
mut.WaitOne();
if (count == 0)
{
rw.WaitOne();
}
count++;
mut.ReleaseMutex();
Thread.Sleep(new Random().Next(2000));//读取耗时 1S
Console.WriteLine("读取完毕");
mut.WaitOne();
count--;
mut.ReleaseMutex();
if (count == 0)
{
rw.ReleaseMutex();
}
}
private static void writer()
{
rw.WaitOne();
Console.WriteLine("写入数据");
rw.ReleaseMutex();
}
}这种方式是写线程的逻辑比较简单的一种实现，只管获取到 rw 锁（用于表示互斥锁），而读线程在每次进行读区域前，通过 mut 锁的机制保证至少有一个互斥锁被读线程所占据（这样写线程就没法并行操作了），然后再真正开始读的时候放开 mut 锁，让其它读线程可以并发地进行读操作。其中的 count 用于表示当前读者的个数，当 count 降为 0 的时候，进入的读线程必须去获取一个写锁，以保证有读者的时候，写锁一定被某个读者占有。
文章未经特殊标明皆为本人原创，未经许可不得用于任何商业用途，转载请保持完整性并注明来源链接 《四火的唠叨》
×Scan to share with WeChat