可递归锁与非递归锁
转载自《线程同步之利器(1)——可递归锁与非递归锁》
http://blog.csdn.net/zouxinfox/archive/2010/08/25/5838861.aspx
最常见的进程/线程的同步方法有互斥锁（或称互斥量Mutex)，读写锁(rdlock)，条件变量(cond)，信号量(Semophore)等。
在Windows系统中，临界区（Critical Section）和事件对象(Event)也是常用的同步方法。
简单的说，互斥锁保护了一个临界区，在这个临界区中，一次最多只能进入一个线程。
如果有多个进程在同一个临界区内活动，就有可能产生竞态条件(race condition)导致错误。
读写锁从广义的逻辑上讲，也可以认为是一种共享版的互斥锁。如果对一个临界区大部分是读操作而只有少量的写操作，
读写锁在一定程度上能够降低线程互斥产生的代价。
条件变量允许线程以一种无竞争的方式等待某个条件的发生。当该条件没有发生时，线程会一直处于休眠状态。
当被其它线程通知条件已经发生时，线程才会被唤醒从而继续向下执行。条件变量是比较底层的同步原语，直接使用的情况不多，
往往用于实现高层之间的线程同步。使用条件变量的一个经典的例子就是线程池(Thread Pool)了。
在学习操作系统的进程同步原理时，讲的最多的就是信号量了。通过精心设计信号量的PV操作，
可以实现很复杂的进程同步情况（例如经典的哲学家就餐问题和理发店问题）。
而现实的程序设计中，却极少有人使用信号量。能用信号量解决的问题似乎总能用其它更清晰更简洁的设计手段去代替信号量。
本系列文章的目的并不是为了讲解这些同步方法应该如何使用（AUPE的书已经足够清楚了）。更多的是讲解很容易被人忽略的一些关于锁的概念，
以及比较经典的使用与设计方法。文章会涉及到递归锁与非递归锁（recursive mutex和non-recursive mutex），
区域锁(Scoped Lock)，策略锁(Strategized Locking)，读写锁与条件变量，双重检测锁(DCL)，锁无关的数据结构(Locking free)，
自旋锁等等内容，希望能够抛砖引玉。
那么我们就先从递归锁与非递归锁说开去吧:)
1 可递归锁与非递归锁
1.1 概念
在所有的线程同步方法中，恐怕互斥锁(mutex)的出场率远远高于其它方法。互斥锁的理解和基本使用方法都很容易，这里不做更多介绍了。
Mutex可以分为递归锁(recursive mutex)和非递归锁(non-recursive mutex)。可递归锁也可称为可重入锁(reentrant mutex)，
非递归锁又叫不可重入锁(non-reentrant mutex)。
二者唯一的区别是，同一个线程可以多次获取同一个递归锁，不会产生死锁。而如果一个线程多次获取同一个非递归锁，则会产生死锁。
Windows下的Mutex和Critical Section是可递归的。Linux下的pthread_mutex_t锁默认是非递归的。
可以显示的设置PTHREAD_MUTEX_RECURSIVE属性，将pthread_mutex_t设为递归锁。
在大部分介绍如何使用互斥量的文章和书中，这两个概念常常被忽略或者轻描淡写，造成很多人压根就不知道这个概念。
但是如果将这两种锁误用，很可能会造成程序的死锁。请看下面的程序。
MutexLock mutex;
void foo()
{
mutex.lock();
// do something
mutex.unlock();
}
void bar()
{
mutex.lock();
// do something
foo();
mutex.unlock();
}
foo函数和bar函数都获取了同一个锁，而bar函数又会调用foo函数。如果MutexLock锁是个非递归锁，则这个程序会立即死锁。
因此在为一段程序加锁时要格外小心，否则很容易因为这种调用关系而造成死锁。
不要存在侥幸心理，觉得这种情况是很少出现的。当代码复杂到一定程度，被多个人维护，调用关系错综复杂时，
程序中很容易犯这样的错误。庆幸的是，这种原因造成的死锁很容易被排除。
但是这并不意味着应该用递归锁去代替非递归锁。递归锁用起来固然简单，但往往会隐藏某些代码问题。
比如调用函数和被调用函数以为自己拿到了锁，都在修改同一个对象，这时就很容易出现问题。因此在能使用非递归锁的情况下，
应该尽量使用非递归锁，因为死锁相对来说，更容易通过调试发现。程序设计如果有问题，应该暴露的越早越好。
1.2 如何避免
为了避免上述情况造成的死锁，AUPE v2一书在第12章提出了一种设计方法。即如果一个函数既有可能在已加锁的情况下使用，
也有可能在未加锁的情况下使用，往往将这个函数拆成两个版本---加锁版本和不加锁版本(添加nolock后缀)。
例如将foo()函数拆成两个函数。
// 不加锁版本
void foo_nolock()
{
// do something
}
// 加锁版本
void fun()
{
mutex.lock();
foo_nolock();
mutex.unlock();
}
为了接口的将来的扩展性，可以将bar()函数用同样方法拆成bar_withou_lock()函数和bar()函数。
在Douglas C. Schmidt（ACE框架的主要编写者）的“Strategized Locking, Thread-safe Interface, and Scoped Locking”论文中，
提出了一个基于C 的线程安全接口模式(Thread-safe interface pattern)，与AUPE的方法有异曲同工之妙。
即在设计接口的时候，每个函数也被拆成两个函数，没有使用锁的函数是private或者protected类型，
使用锁的的函数是public类型。接口如下：
class T
{
public:
foo(); //加锁
bar(); //加锁
private:
foo_nolock();
bar_nolock();
}
作为对外接口的public函数只能调用无锁的私有变量函数，而不能互相调用。在函数具体实现上，这两种方法基本是一样的。
上面讲的两种方法在通常情况下是没问题的，可以有效的避免死锁。但是有些复杂的回调情况下，则必须使用递归锁。
比如foo函数调用了外部库的函数，而外部库的函数又回调了bar()函数，此时必须使用递归锁，否则仍然会死锁。
AUPE 一书在第十二章就举了一个必须使用递归锁的程序例子。
1.3 读写锁的递归性
读写锁（例如Linux中的pthread_rwlock_t）提供了一个比互斥锁更高级别的并发访问。
读写锁的实现往往是比互斥锁要复杂的，因此开销通常也大于互斥锁。
在我的Linux机器上实验发现，单纯的写锁的时间开销差不多是互斥锁十倍左右。
在系统不支持读写锁时，有时需要自己来实现，通常是用条件变量加读写计数器实现的。有时可以根据实际情况，
实现读者优先或者写者优先的读写锁。
读写锁的优势往往展现在读操作很频繁，而写操作较少的情况下。如果写操作的次数多于读操作，并且写操作的时间都很短，
则程序很大部分的开销都花在了读写锁上，这时反而用互斥锁效率会更高些。
相信很多同学学习了读写锁的基本使用方法后，都写过下面这样的程序（Linux下实现）。
程序1
#include
int main()
{
pthread_rwlock_t rwl;
pthread_rwlock_rdlock(&rwl);
pthread_rwlock_wrlock(&rwl);
pthread_rwlock_unlock(&rwl);
pthread_rwlock_unlock(&rwl);
return -1;
}
程序2
#include
int main()
{
pthread_rwlock_t rwl;
pthread_rwlock_wrlock(&rwl);
pthread_rwlock_rdlock(&rwl);
pthread_rwlock_unlock(&rwl);
pthread_rwlock_unlock(&rwl);
return -1;
}
你会很疑惑的发现，程序1先加读锁，后加写锁，按理来说应该阻塞，但程序却能顺利执行。而程序2却发生了阻塞。
更近一步，你能说出执行下面的程序3和程序4会发生什么吗？
/*程序3*/
#include
int main()
{
pthread_rwlock_t rwl;
pthread_rwlock_rdlock(&rwl);
pthread_rwlock_rdlock(&rwl);
pthread_rwlock_unlock(&rwl);
pthread_rwlock_unlock(&rwl);
return -1;
}
/*程序4*/
#include
int main()
{
pthread_rwlock_t rwl;
pthread_rwlock_wrlock(&rwl);
pthread_rwlock_wrlock(&rwl);
pthread_rwlock_unlock(&rwl);
pthread_rwlock_unlock(&rwl);
return -1;
}
在POSIX标准中，如果一个线程先获得写锁，又获得读锁，则结果是无法预测的。这就是为什么程序1的运行出人所料。
需要注意的是，读锁是递归锁（即可重入），写锁是非递归锁（即不可重入）。因此程序3不会死锁，而程序4会一直阻塞。
读写锁是否可以递归会可能随着平台的不同而不同，因此为了避免混淆，
建议在不清楚的情况下尽量避免在同一个线程下混用读锁和写锁。
在系统不支持递归锁，而又必须要使用时,就需要自己构造一个递归锁。通常，递归锁是在非递归互斥锁加引用计数器来实现的。
简单的说，在加锁前，先判断上一个加锁的线程和当前加锁的线程是否为同一个。如果是同一个线程，则仅仅引用计数器加1。
如果不是的话，则引用计数器设为1，则记录当前线程号，并加锁。关于此的一个实现请参照《多线程中递归锁的实现》
需要注意的是，如果自己想写一个递归锁作为公用库使用，就需要考虑更多的异常情况和错误处理，让代码更健壮一些。
