sherrylso

C++博客 首页 新随笔 联系 聚合 管理
  18 Posts :: 0 Stories :: 124 Comments :: 0 Trackbacks

摘要:
        在对多线程并发的编程环境下,死锁是我们经常碰到的和经常需要解决的问题。所谓死锁,即:由于资源占用是互斥的,当某个线(进)程提出申请资源后,使得有关进程在无外力协助下,永远分配不到必需的资源而无法继续运行,这就产生了一种特殊现象死锁,如下图:

        线程#1在获得Lock A后,需要获得Lock B,而同时,线程#2在Lock B后,需要获得Lock A。对于线程#1和#2,由于都不能获得满足的条件,而无法继续执行,死锁就形成了。
        死锁是多线程并发编程的大难题,我们可以通过Log Trace、多线程编程辅助工具、IDE调试环境等手段进行调试、跟踪。然而,另一个更难对付的问题是“假死锁”(我在这里暂且称为“假死锁”,实在找不到什么更好的称呼)。所谓的假死锁,我给出的定义是:在有限的时间内的死锁。与死锁不同的是,其持续的时间是有限的,而大家都知道,死锁持续的时间是无限的,如果碰到死锁,程序接下来是什么都干不了了。而正是由于假死锁的相对的持续时间,给我们编程人员会带来更大的麻烦。可以想象得到,我们想通过某些工具来Trace这样一个特定的时间段是非常困难的,更多的情况下,我们需要结合LOG进行合理的分析,使得问题得以解决。本文就假死锁产生的条件,环境,以及解决的办法做一个讨论。
一、假死锁的产生条件。

    考虑下面的例子(我只是给给出了伪代码),假设我们系统中的线程个数是确定的,有限的。在本例中,系统总的线程数目是3。如下图:

线程#1,#2,#3都可能被调度进入临界区A,我们假设线程#1执行临界区A时花费了10s的时间,而在这10s的时间里,线程#2与线程#3都处于等待的状态。也就是说:在这个10s的时间里,系统是没法响应任何的其他请求。我们称之为10s的假死锁。如果在这段时间里,系统需要一些关键的请求被执行,这些关键请求是需要real time地被处理,比如说是Timer事件,则后果是不堪设想的。(注意:我们的假定是系统中的线程只有#1,#2,#3)。
       以此,总结一下发生假死锁的条件,如下:
--〉临界区的代码在集中的时间段内,可能被系统中的任意线程执行,完全由操作系统决定。
--〉临界区的代码在某些情况下,可能是很耗时的。(比如:其执行时间大于100ms,或者,甚至是秒级别的)
二、在Proactor(IOCP)中的假死锁。
        在前面的文章中,我提到过在windows平台上,Proactor设计模式是基于IOCP的。在这里,本文不会用过多的语言来阐述Proactor是怎样的设计,重点放在Proactor的假死锁及其一些解决的办法。另外需要说明的是,我这里所说的Proactor,在技术层面上,等同于IOCP,我们也可以按照IOCP来理解我所阐释的概念。
        我们都知道,IOCP是靠工作者线程来驱动的。工作者线程与一个完成端口对象相关联,当IO 请求被投递到完成端口对象时,这些线程为完成端口服务。需要说明的是,应该创建多少个线程来为完成端口服务,是你的应用设计来决定的(很重要的的一点是:在调用CreateIoCompletionPort时指定的并发线程的个数,和创建的工作者线程的个数是有区别的,详细的技术细节,请参考其他资料)。但是总的来说,在你的系统交付运行后,工作者线程的线程数目是一个确定的值。其结构图,大致如下:

         我们假定使用了线程数目为4的工作者线程来为完成端口服务,它们通过调用来GetQueuedCompletionStatus方法来从完成端口中获取IO相关的packet,一旦获得,它们都会回调业务逻辑层的代码来进行相关的业务逻辑处理。到这里我们看到,假设,在业务逻辑层存在临界互斥区,并且在某一个集中的时间段内,工作者线程都可能被调度执行该临界互斥区,那么,假死锁的条件基本形成,如果某一个线程在该区域花费的时间比较长,假死锁就会发生。
        一般来说,解决这样的问题的关键就是打破形成假死锁的条件:
       第一、在回调函数里,尽量减少锁的使用。
       第二、减量减少临界互斥区的执行时间。对于一些慢速的操作尤其注意。比如:当你在临界互斥区访问慢速的IO操作时(打开文件,读写文件等),可能需要考虑Cache机制,通过使用内存来代替慢速的disk。
       第三、将临界互斥区代码委托给另外独立的线程(或线程组)执行,代价是增加这些线程间的通讯。
       第四、通过使用流控等手段,避免让所有的线程在集中的时间段内访问该临界互斥区。
三、结束语:

         事实上,类似这样的问题,一旦存在,是很难发现和调试的。不过对于多线程的编程,我们都应该遵守以下的基本原则,以最大化的防止死锁和假死锁的发生。

         --> 尽量减少锁的使用频率和保护范围。
         --> 当线程在互斥锁的保护范围内执行代码时,应该:尽量减少对慢速IO设备的访问(如:disk),尽量避免获得其它互斥资源。
         --〉正确使用各种锁,包括:原子操作原语,Read Lock, Write Lock, 和Recursive Lock等。这些锁在不同的场景下有着不同的作用。
posted on 2007-08-12 15:41 爱上龙卷风 阅读(3938) 评论(9)  编辑 收藏 引用

Feedback

# re: 线程互斥执行之假死锁现象 2007-08-12 20:30 若弱
你所说的其实叫做“活锁”是资源紧俏造成的,另外,其实完全可以用lock-free来代理锁机制的。这样就可以不会死锁了
  回复  更多评论
  

# re: 线程互斥执行之假死锁现象 2007-08-13 13:26 阿福
为了吸引眼球,创建一个新名词…………拜托,一点学术精神都没有!  回复  更多评论
  

# re: 线程互斥执行之假死锁现象 2007-08-13 15:23 SuperPlayeR
最后的总结第二点,应该说是尽量减少互斥锁保护范围内代码的执行时间。减少对慢速IO设备的访问其实目的只是缩短时间而已。  回复  更多评论
  

# re: 线程互斥执行之假死锁现象 2007-08-13 22:42 爱上龙卷风
@阿福
我确实不知道该把这类现象称为什么,你有什么好主意,给点建设性的意见!
另外,这里不是在发表学术文章,只是开发经验的总结,OK?  回复  更多评论
  

# re: 线程互斥执行之假死锁现象 2007-08-13 22:53 爱上龙卷风
@若弱
直接原因是由于加锁保护的代码执行时间长造成的。
另外,阁下说的ock-free来代理锁机制,是什么意思?  回复  更多评论
  

# re: 线程互斥执行之假死锁现象 2007-08-16 10:53 若弱
不好意思,我打错了一个字,应该是“代替”

其实所谓的lock-free(无锁)实质上是使用了一个CPU的时钟周期的锁,
锁的时间是要尽可能的短,但是再短也不能完全避免资源不足造成活锁(或者说较长时间等待)现象。当然是有可能采用wait-free机制的,不过目前的实现代价太大,效率还没传统的锁机制高呢。  回复  更多评论
  

# re: 线程互斥执行之假死锁现象 2007-08-17 15:55 爱上龙卷风
@若弱
谢谢你的comments。
至于你提到的livelock的概念,我在网上查了些资料,基本上有两种定义:
1)livelock-An endless loop in program execution. It occurs when a process repeats itself, because it continues to receive erroneous information. It can also occur when a process that calls another process is itself called by that process, and there is no logic to detect this situation and stop the operation. A livelock differs from a "deadlock," in that processing continues to take place, rather than just waiting in an idle loop(From answers).
2)活锁-如果事务T1封锁了数据R,事务T2又请求封锁R,于是T2等待。T3也请求封锁R,当T1释放了R上的封锁之后系统首先批准了T3的请求,T2仍然等待。然后T4又请求封锁R,当T3释放了R上的封锁之后系统又批准了T4的请求,...,T2有可能永远等待,这就是活锁的情形(来自数据库领域)
对于这两种定义,我个人偏向于第一个定义:即程序进入无止的循环当中,无法结束。
不过无论哪种方式,都不适合本文的定义,即:既定时间的内的死锁。
关于你说的Lock-free机制,一般来说,有两种方法:
第一、对现有的算法改动,使用新的Lock-free算法。这种方法比较难于实现。
最简单的莫过于:将临界互斥区代码委托给另外独立的线程,使同步的操作变成异步(本文已经提到过)。
第二、使用原子操作原语,比如windows平台上的互锁函数族,如InterlockedCompareExchange。但是他们不能解决事务的问题。

  回复  更多评论
  

# re: 线程互斥执行之假死锁现象 2007-08-20 10:37 若弱
@爱上龙卷风
关于活锁,我个人也是倾向于第一种理解,事实上,有这样一种情况出现,系统并没有死锁,但是因为资源不足,造成推进速度过慢,系统花太多的时间用于等待足够的资源出现。就好比是餐馆的例子,厨师等帮工清洗好盘子,帮工客人吃完的盘子,而客人不愿意整个桌子空荡荡的而不愿意把盘子吃空知道新的菜上来。这种情况在计算机环境中很容易出现,但是绝对不会推进不下去,只是速度非常慢,看起来像死锁一样,但是绝对不是死锁。当然解决这个问题的办法是增加盘子(资源)的供应量,或者减少资源的占用时间。

  回复  更多评论
  

# re: 线程互斥执行之假死锁现象 2008-01-07 23:14 abettor.org
如果有个类似TryLock之类的方法就好了。  回复  更多评论
  


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理