线程同步机制的概念_线程同步机制的概念和特点

Linux多线程同步机制 　　概述 　　最常见的进程/线程的同步方法有互斥锁（或称互斥量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设为递归锁。 　　在大部分介绍如何使用互斥量的文章和书中，这两个概念常常被忽略或者轻描淡写，造成很多人压根就不知道这个概念。但是如果将这两种锁误用，很可能会造成程序的死锁。请看下面的程序。 　　  　　  [cpp] view plaincopy   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()函数拆成两个函数。 　　  [cpp] view plaincopy   // 不加锁版本   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类型。接口如下： 　　  [cpp] view plaincopy   class T   {   public:       foo(); //加锁       bar(); //加锁   private:       foo_nolock();       bar_nolock();   }   　　  　　作为对外接口的public函数只能调用无锁的私有变量函数，而不能互相调用。在函数具体实现上，这两种方法基本是一样的。 　　   上面讲的两种方法在通常情况下是没问题的，可以有效的避免死锁。但是有些复杂的回调情况下，则必须使用递归锁。比如foo函数调用了外部库的函数，而外部库的函数又回调了bar()函数，此时必须使用递归锁，否则仍然会死锁。AUPE 一书在第十二章就举了一个必须使用递归锁的程序例子。 　　1.3 读写锁的递归性 　　    读写锁（例如Linux中的pthread_rwlock_t）提供了一个比互斥锁更高级别的并发访问。读写锁的实现往往是比互斥锁要复杂的，因此开销通常也大于互斥锁。在我的Linux机器上实验发现，单纯的写锁的时间开销差不多是互斥锁十倍左右。 　　在系统不支持读写锁时，有时需要自己来实现，通常是用条件变量加读写计数器实现的。有时可以根据实际情况，实现读者优先或者写者优先的读写锁。 　　   读写锁的优势往往展现在读操作很频繁，而写操作较少的情况下。如果写操作的次数多于读操作，并且写操作的时间都很短，则程序很大部分的开销都花在了读写锁上，这时反而用互斥锁效率会更高些。 　　   相信很多同学学习了读写锁的基本使用方法后，都写过下面这样的程序（Linux下实现）。 　　  [cpp] view plaincopy   #include <pthread.h>   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 <pthread.h>   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会发生什么吗？ 　　  [cpp] view plaincopy   /*程序3*/   #include <pthread.h>   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 <pthread.h>   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，则记录当前线程号，并加锁。一个例子可以看这里。需要注意的是，如果自己想写一个递归锁作为公用库使用，就需要考虑更多的异常情况和错误处理，让代码更健壮一些。 　　  　　下一节，我会介绍一下平时很常见的加锁手段—区域锁（Scoped Locking）技术。 　　什么是区域锁 　　确切的说，区域锁(Scoped locking)不是一种锁的类型，而是一种锁的使用模式(pattern)。这个名词是Douglas C. Schmidt于1998年在其论文Scoped Locking提出，并在ACE框架里面使用。但作为一种设计思想，这种锁模式应该在更早之前就被业界广泛使用了。 　　区域锁实际上是RAII模式在锁上面的具体应用。RAII(Resource Acquisition Is Initialization)翻译成中文叫“资源即初始化”，最早是由C++的发明者 Bjarne Stroustrup为解决C++中资源分配与销毁问题而提出的。RAII的基本含义就是：C++中的资源（例如内存，文件句柄等等）应该由对象来管理，资源在对象的构造函数中初始化，并在对象的析构函数中被释放。STL中的智能指针就是RAII的一个具体应用。RAII在C++中使用如此广泛，甚至可以说，不会RAII的裁缝不是一个好程序员。 　　问题提出 　　先看看下面这段程序，Cache是一个可能被多个线程访问的缓存类，update函数将字符串value插入到缓存中，如果插入失败，则返回-1。 　　  [cpp] view plaincopy   Cache *cache = new Cache;   ThreadMutex mutex;   int update(string value)   {       mutex.lock();       if (cache == NULL)       {           mutex.unlock();           return -1;       }       If (cache.insert(value) == -1)       {       mutex.unlock();           return -1;       }       mutex.unlock();       return 0;   }   　　  　　  　　从这个程序中可以看出，为了保证程序不会死锁，每次函数需要return时，都要需要调用unlock函数来释放锁。不仅如此，假设cache.insert(value)函数内部突然抛出了异常，程序会自动退出，锁仍然能不会释放。实际上，不仅仅是return，程序中的goto, continue, break语句，以及未处理的异常，都需要程序员检查锁是否需要显示释放，这样的程序是极易出错的。 　　同样的道理，不仅仅是锁，C++中的资源释放都面临同样的问题。例如前一阵我在阅读wget源码的时候，就发现虽然一共只有2万行C代码，但是至少有5处以上的return语句忘记释放内存，因此造成了内存泄露。 　　区域锁的实现 　　但是自从C++有了有可爱的RAII设计思想，资源释放问题就简单了很多。区域锁就是把锁封装到一个对象里面。锁的初始化放到构造函数，锁的释放放到析构函数。这样当锁离开作用域时，析构函数会自动释放锁。即使运行时抛出异常，由于析构函数仍然会自动运行，所以锁仍然能自动释放。一个典型的区域锁 　　  [cpp] view plaincopy   class Thread_Mutex_Guard    {   public:       Thread_Mutex_Guard (Thread_Mutex &lock)       : lock_ (&lock)        {            // 如果加锁失败，则返回-1           owner_= lock_->lock();        }          ~Thread_Mutex_Guard (void)        {           // 如果锁失败，就不释放           if (owner_ != -1)               lock_->unlock ();       }   private:       Thread_Mutex *lock_;       int owner_;   };   　　  　　将策略锁应用到前面的update函数如下 　　  [cpp] view plaincopy   Cache *cache = new Cache;   ThreadMutex mutex;   int update(string value)   {       Thread_Mutex_Guard (mutex)       if (cache == NULL)       {           return -1;       }       If (cache.insert(value) == -1)       {           return -1;       }       return 0;   }   　　  　　基本的区域锁就这么简单。如果觉得这样锁的力度太大，可以用中括号来限定锁的作用区域，这样就能控制锁的力度。如下 　　  [cpp] view plaincopy   {       Thread_Mutex_Guard guard (&lock);       ……………       // 离开作用域，锁自动释放   }   　　  　　区域锁的改进方案 　　上面设计的区域锁一个缺点是灵活行，除非离开作用域，否则不能够显式释放锁。如果为一个区域锁增加显式释放接口，一个最突出的问题是有可能会造成锁的二次释放，从而引发程序错误。 　　例如 　　  [cpp] view plaincopy   {       Thread_Mutex_Guard guard (&lock);       If (…)       {           //显式释放（第一次释放）           guard.release();           // 自动释放(第二次释放)           return -1;       }   }   　　  　　为了避免二次释放锁引发的错误，区域锁需要保证只能够锁释放一次。一个改进的区域锁如下： 　　  [cpp] view plaincopy   class Thread_Mutex_Guard    {   public:       Thread_Mutex_Guard (Thread_Mutex &lock)       : lock_ (&lock)        {            acquire();        }       int acquire()       {           // 加锁失败，返回-1           owner_= lock_->lock();           return owner;       }       ~Thread_Mutex_Guard (void)        {           release();       }       int release()       {           // 第一次释放           if (owner_ !=  -1)           {               owner = -1;               return lock_->unlock ();           }           // 第二次释放           return 0;       }   private:       Thread_Mutex *lock_;       int owner_;   };   　　  　　可以看出，这种方案在加锁失败或者锁的多次释放情况下，不会引起程序的错误。 　　缺点： 　　区域锁固然好使，但也有不可避免的一些缺点 　　(1) 对于非递归锁，有可能因为重复加锁而造成死锁。 　　(2) 线程的强制终止或者退出，会造成区域锁不会自动释放。应该尽量避免这种情形，或者使用一些特殊的错误处理设计来确保锁会释放。 　　(3) 编译器会产生警告说有变量只定义但没有使用。有些编译器选项甚至会让有警告的程序无法编译通过。在ACE中，为了避免这种情况，作者定义了一个宏如下 　　#define UNUSED_ARG(arg) { if (&arg) /* null */; } 　　使用如下： 　　  [cpp] view plaincopy   Thread_Mutex_Guard guard (lock_);   UNUSED_ARG (guard);   　　  　　这样编译器就不会再警告了。 　　扩展阅读：小技巧–如何在C++中实现Java的synchronized关键字 　　借助于区域锁的思想，再定义一个synchronized宏，可以在C++中实现类似Java中的synchronized关键字功能。链接：http://www.codeproject.com/KB/threads/cppsyncstm.aspx 　　【转载】死锁原因及解决、避免办法   　　死锁的条件 　　     互斥条件(Mutual exclusion)     ：资源不能被共享，只能由一个进程使用。 　　     请求与保持条件(Hold and wait)：进程已获得了一些资源，但因请求其它资源被阻塞时，对已获得的资源保持不放。 　　     不可抢占条件(No pre-emption)    ：有些系统资源是不可抢占的，当某个进程已获得这种资源后，系统不能强行收回，只能由进程使用完时自己释放。 　　     循环等待条件(Circular wait)      ：若干个进程形成环形链，每个都占用对方申请的下一个资源。 　　处理死锁的策略 　　1、忽略该问题。例如鸵鸟算法。 　　 2、检测死锁并且恢复。 　　3、仔细地对资源进行动态分配，以避免死锁。 　　4、通过破除死锁四个必要条件之一，来防止死锁产生。 　　鸵鸟算法： 　　该算法可以应用在极少发生死锁的的情况下。为什么叫鸵鸟算法呢，因为传说中鸵鸟看到危险就把头埋在地底下，可能鸵鸟觉得看不到危险也就没危险了吧。跟掩耳盗铃有点像。 　　银行家算法： 　　        所谓银行家算法，是指在分配资源之前先看清楚，资源分配后是否会导致系统死锁。如果会死锁，则不分配，否则就分配。 　　按照银行家算法的思想，当进程请求资源时，系统将按如下原则分配系统资源： 　　(1) 当一个进程对资源的最大需求量不超过系统中的资源数时可以接纳该进程。 　　(2) 进程可以分期请求资源，当请求的总数不能超过最大需求量。 　　(3) 当系统现有的资源不能满足进程尚需资源数时，对进程的请求可以推迟分配，但总能使进程在有限的时间里得到资源。 　　(4) 当系统现有的资源能满足进程尚需资源数时，必须测试系统现存的资源能否满足该进程尚需的最大资源数，若能满足则按当前的申请量分配资源，否则也要推迟分配。 　　解决死锁的策略 　　对待死锁的策略主要有： 　　(1) 死锁预防：破坏导致死锁必要条件中的任意一个就可以预防死锁。例如，要求用户申请资源时一次性申请所需要的全部资源，这就破坏了保持和等待条件；将资源分层，得到上一层资源后，才能够申请下一层资源，它破坏了环路等待条件。预防通常会降低系统的效率。 　　(2) 死锁避免：避免是指进程在每次申请资源时判断这些操作是否安全，例如，使用银行家算法。死锁避免算法的执行会增加系统的开销。 　　(3) 死锁检测：死锁预防和避免都是事前措施，而死锁的检测则是判断系统是否处于死锁状态，如果是，则执行死锁解除策略。 　　(4) 死锁解除：这是与死锁检测结合使用的，它使用的方式就是剥夺。即将某进程所拥有的资源强行收回，分配给其他的进程。 　　  　　死锁的避免： 　　死锁的预防是通过破坏产生条件来阻止死锁的产生，但这种方法破坏了系统的并行性和并发性。 　　死锁产生的前三个条件是死锁产生的必要条件，也就是说要产生死锁必须具备的条件，而不是存在这3个条件就一定产生死锁，那么只要在逻辑上回避了第四个条件就可以避免死锁。 　　避免死锁采用的是允许前三个条件存在，但通过合理的资源分配算法来确保永远不会形成环形等待的封闭进程链，从而避免死锁。该方法支持多个进程的并行执行，为了避免死锁，系统动态的确定是否分配一个资源给请求的进程。方法如下： 　　1.如果一个进程的当前请求的资源会导致死锁，系统拒绝启动该进程； 　　2.如果一个资源的分配会导致下一步的死锁，系统就拒绝本次的分配； 　　显然要避免死锁，必须事先知道系统拥有的资源数量及其属性