什么是死锁?如何避免死锁?

by admin on 2019年11月6日

select
request_session_id spid,
OBJECT_NAME(resource_associated_entity_id) tableName
from
sys.dm_tran_locks
where
resource_type=’OBJECT’

关于死锁,死锁

示例:一个标准的死锁

- (void)viewDidLoad
{
[super viewDidLoad];

dispatch_sync(dispatch_get_main_queue(), ^{});

}

dispatch_sync(queue, block)
做了两件事情

  • 将 block 添加到  class=”searchwordd833″>queue 队列;
  • 阻塞调用线程,等待 block() 执行结束,回到调用线程。

dispatch_async(queue, block)
也做了两件事情:

  • 将 block 添加到  > class=”searchwordd833″>queue 队列;
  • 直接回到调用线程(不阻塞调用线程)。

这里也能看到同步派发和异步派发的区别,就是看是否阻塞调用线程。

 

我们忽略了主线程是先进先出的即(FIFO),而viewdidload这样的方法是属于主线程的,所以主线程应该先执行完viewdidload的任务,然后才执行下一个,可是同步的执行加入主线程话就需要viewdidload 先执行完成,viewdidload却在等待同步的完成所以死锁了

 

所以记住这个教训:不要将 block 同步派发到调用 GCD
所在线程的关联队列中

itemprop=”url”> > id=”indexUrl” itemprop=”indexUrl”>www.bkjia.com > id=”isOriginal” itemprop=”isOriginal”>true > id=”isBasedOnUrl”
itemprop=”isBasedOnUrl”> > id=”genre” itemprop=”genre”>TechArticle > itemprop=”description”>关于死锁,死锁 示例:一个标准的死锁 – ( void
)viewDidLoad{[super
viewDidLoad];dispatch_sync(dispatch_get_main_queue(), ^ {});}
dispatch_sync( queue, block) 做了两…

所谓死锁:是指两个或两个以上的进程在执行过程中,因争夺资源而造成的一种互相等待的现象,若无外力作用,它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁,这些永远在互相等待的进程称为死锁进程。由于资源占用是互斥的,当某个进程提出申请资源后,使得有关进程在无外力协助下,永远分配不到必需的资源而无法继续运行,这就产生了一种特殊现象死锁。

死锁是什么,以及在并发程序中如何避免死锁一直是面试官偏爱的一个问题。本文尽量以最简洁的示例来帮助你快速理解,掌握死锁发生的原因及其解决方法。在阅读接下来的内容之前,你必须具备java中独占锁与线程之间通信的基本知识。

死锁,死锁的四个必要条件

死锁的定义:如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的时间,那么该组进程是死锁的。

产生死锁的必要条件:(产生死锁必须同时具备下面四个必要条件

  • 互斥条件:简单的说就是进程抢夺的资源必须是临界资源,一段时间内,该资源只能同时被一个进程所占有
  • 请求和保持条件:当一个进程持有了一个(或者更多)资源,申请另外的资源的时候发现申请的资源被其他进程所持有,当前进程阻塞,但不会是放自己所持有的资源
  • 不可抢占条件:进程已经获得的资源在未使用完毕的情况下不可被其他进程所抢占
  • 循环等待条件:发生死锁的时候,必然存在一个进程—资源的循环链

这里所说的资源不仅包括硬件资源或者其他的资源,还包括锁,锁也是一种资源,锁的争用也会导致死锁

  • 死锁的几个例子(为了好描述,这里用锁作为资源来描述死锁,这里的锁换成资源完全没问题)

自死锁,简单的说一个进程持有了一个锁之后,在临界区内又去申请该锁,它将不得不等待该锁被释放,但因为它本身在等待申请该锁,所以永远不会有机会释放锁并得到锁,最终结果就是死锁。因为很多锁都不是可递归锁,所以不要尝试在一个线程内多次申请同一个锁。

ABBA死锁(该死锁常发生于多个进程多个锁),简单的说就是每个进程都持有其他进程想要获得的锁,上图

图片 1

图片 2

 

 

这个最经典的例子当属,哲学家用餐问题(不再多说,基本原理就是上图和上面所说的ABBA死锁,可以百度一下)

死锁的处理方法又分为好几大类

  • 预防死锁

预防死锁的办法就是破坏死锁的四个必要条件,只要破坏了条件,死锁自然就不会产生了,简单的描述一下破坏四个条件的思想

破坏请求和保持条件:1.所有进程在开始运行之前,必须一次性获得所有资源,如果无法获得完全,释放已经获得的资源,等待;2.所有进程在开始运行之前,只获得初始运行所需要的资源,然后在运行过程中不断请求新的资源,同时释放自己已经用完的资源。    相比第一种而言,第二种方式要更加节省资源,不会浪费(因为第一种可能出现一种资源只在进程结束用那么一小下,但却从头到尾都被占用,使用效率极低),而且,减少了进程饥饿的情况。

破坏不可抢占条件:说起来简单,只要当一个进程申请一个资源,然而却申请不到的时候,必须释放已经申请到的所有资源。但是做起来很复杂,需要付出很大的代价,加入该进程已经持有了类似打印机(或者其他的有必要连续工作的)这样的设备,申请其他资源的时候失败了,必须释放打印机资源,但是人家用打印机已经用过一段时间了,此时释放打印机资源很可能造成之后再次是用打印机时两次运行的信息不连续(得不到正确的结果)

破坏循环等待条件:设立一个规则,让进程获取资源的时候按照一定的顺序依次申请,不能违背这个顺序的规则。必须按照顺序申请和释放,想要申请后面的资源必须先把该资源之前的资源全部申请,想要申请前面的资源必须先把该资源之后的资源(前提是已获得)全部释放

破坏互斥条件:没法破坏,是资源本身的性质所引起的

  • 避免死锁

最常听到的算法来袭!银行家算法来了!!

银行家算法需要的数据结构:1.可利用资源向量(Available);2.最大需求矩阵(Max);3.分配矩阵(Allocation);4.需求矩阵(Need)。

上述三个矩阵存在如下关系  Need[i,j]=Max[i,j]-Allocation[i,j];

说的看似很难懂的样子,下面详解一下就很好理解了。

 

 

可利用资源向量(Available):这么说吧,比如当前有三种资源A,B,C,可利用资源向量就是一个数组(为了在程序中使用),我们理解的话就说ABC各有多少个资源,例子

A  B  C

7  2  5     这里7,2,5三个资源的数目组合起来就是一个数组(向量)

 

最大需求矩阵(Max):说是矩阵完全是为了在编程时使用方便(就是一个二维数组),我们理解的话就说是进程工作需要的每个资源的总数目,例子

       A   B   C

P1    1   1    1  
这样一看就明白了,进程P1需要三种资源各一个(这个不是二维数组啊,是一维的?怎么可能只有一个进程这是一对进程思死锁的解决办法!),多加几个进程就二维数组了

分配矩阵(Allocation):和需求矩阵类似,只是数值的含义变成了,目前已经给进程某某(行值i),分配了多少的某某(列值j)资源

需求矩阵(Need):根据上面的公式就可以看出,这个是进程目前还需要多少资源才可以运行,和最大需求不一样,最大需求是一共需要的数目。

有了这些我们使用银行家算法就够了,我们使用该算法的目的是什么?是避免死锁,避免死锁的意思就是我们使用这些数据结构来推断如果按某种顺序执行进程队列,是否是安全的(是否会造成死锁)

图片 3

 

上图是一个简单的图实例,为了计算机程序运行方便,我们一般假设从P0进程开始运行,那么就要给P0分配足够运行的资源(就是把NEED都给了,前提是当前Available资源数目足够该进程的Need),然后计算Available(new)=Available(old)+Allocation(P),其中Allocation就是执行的进程之前已经分配的资源执行完成之后自然要会收到Available里。

题目一般都会给上图的表,然后让你写出安全序列,用当前的Available看满足哪个进程的Need然后就先执行它,执行完后回收(加到Available中)该进程的Allocation就可以了,这样一步一步算到最后如果Available一直算下来没有亏损不够的情况证明这个序列就是一个安全队列了~!

 

  • 死锁的检测和解除

使用类似银行家算法的方式就可以简单的检测死锁

死锁解除:1.终止进程(简单粗暴),就是字面上的,你们死锁了,我就把你们一起杀掉,缺点就是如果一个进程跑了很长时间,但是被杀了,还得从头来。

2.逐个终止进程,按照某种顺序,挨个杀死进程,每杀一个进程就去看看死锁解除了没有(每杀一个进程都会释放一些资源,如果释放好粗来的资源解决了死锁问题,就没必要再滥杀无辜了),没解除就继续杀。

第二种方式显然人性化了许多,但是按照某种顺序显得很朦胧,这里的某种顺序就是指死锁解除算法,有很多,这里不再赘述。

 

 

推荐书籍:《计算机操作系统(第四版)》第三章第五节,P104

死锁的定义:如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的时间,那么该组进程…

 

虽然进程在运行过程中,可能发生死锁,但死锁的发生也必须具备一定的条件,死锁的发生必须具备以下四个必要条件。

死锁当线程A持有独占锁a,并尝试去获取独占锁b的同时,线程B持有独占锁b,并尝试获取独占锁a的情况下,就会发生AB两个线程由于互相持有对方需要的锁,而发生的阻塞现象,我们称为死锁。

然后kill 里面的进程

1)互斥条件:指进程对所分配到的资源进行排它性使用,即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源,则请求者只能等待,直至占有资源的进程用毕释放。

下面用一个非常简单的死锁示例来帮助你理解死锁的定义。

2)请求和保持条件:指进程已经保持至少一个资源,但又提出了新的资源请求,而该资源已被其它进程占有,此时请求进程阻塞,但又对自己已获得的其它资源保持不放。

public class DeadLockDemo { public static void main(String[] args) { // 线程a Thread td1 = new Thread(new Runnable() { public void run() { DeadLockDemo.method1; // 线程b Thread td2 = new Thread(new Runnable() { public void run() { DeadLockDemo.method2; td1.start(); td2.start(); } public static void method1() { synchronized (String.class) { try { Thread.sleep; } catch (InterruptedException e) { e.printStackTrace(); } System.out.println("线程a尝试获取integer.class"); synchronized (Integer.class) { } } } public static void method2() { synchronized (Integer.class) { try { Thread.sleep; } catch (InterruptedException e) { e.printStackTrace(); } System.out.println("线程b尝试获取String.class"); synchronized (String.class) { } } }}----------------线程b尝试获取String.class线程a尝试获取integer.class..........无限阻塞下去

3)不剥夺条件:指进程已获得的资源,在未使用完之前,不能被剥夺,只能在使用完时由自己释放。

教科书般的回答应该是,结合“哲学家就餐[1]”模型,分析并总结出以下死锁的原因,最后得出“避免死锁就是破坏造成死锁的,若干条件中的任意一个”的结论。

4)环路等待条件:指在发生死锁时,必然存在一个进程——资源的环形链,即进程集合{P0,P1,P2,···,Pn}中的P0正在等待一个P1占用的资源;P1正在等待P2占用的资源,……,Pn正在等待已被P0占用的资源。

造成死锁必须达成的4个条件:

在系统中已经出现死锁后,应该及时检测到死锁的发生,并采取适当的措施来解除死锁。目前处理死锁的方法可归结为以下四种:

  1. 互斥条件:一个资源每次只能被一个线程使用。
  2. 请求与保持条件:一个线程因请求资源而阻塞时,对已获得的资源保持不放。
  3. 不剥夺条件:线程已获得的资源,在未使用完之前,不能强行剥夺。
  4. 循环等待条件:若干线程之间形成一种头尾相接的循环等待资源关系。
  1. 预防死锁。

但是,“哲学家就餐”光看名字就很讨厌,然后以上这4个条件看起来也很绕口,再加上笔者又是个懒人,所以要让我在面试时把这些“背诵”出来实在是太难了!必须要想办法把这4个条件简化一下!于是,通过对4个造成死锁的条件进行逐条分析,我们可以得出以下4个结论。

这是一种较简单和直观的事先预防的方法。方法是通过设置某些限制条件,去破坏产生死锁的四个必要条件中的一个或者几个,来预防发生死锁。预防死锁是一种较易实现的方法,已被广泛使用。但是由于所施加的限制条件往往太严格,可能会导致系统资源利用率和系统吞吐量降低。

  1. 互斥条件 —> 独占锁的特点之一。
  2. 请求与保持条件 —>
    独占锁的特点之一,尝试获取锁时并不会释放已经持有的锁
  3. 不剥夺条件 —> 独占锁的特点之一。
  4. 循环等待条件 —> 唯一需要记忆的造成死锁的条件。
  1. 避免死锁。

不错!复杂的死锁条件经过简化,现在需要记忆的仅只有独占锁与第四个条件而已。

该方法同样是属于事先预防的策略,但它并不须事先采取各种限制措施去破坏产生死锁的的四个必要条件,而是在资源的动态分配过程中,用某种方法去防止系统进入不安全状态,从而避免发生死锁。

所以,面对如何避免死锁这个问题,我们只需要这样回答!:
在并发程序中,避免了逻辑中出现复数个线程互相持有对方线程所需要的独占锁的的情况,就可以避免死锁。

3)检测死锁。

下面我们通过“破坏”第四个死锁条件,来解决第一个小节中的死锁示例并证明我们的结论。

这种方法并不须事先采取任何限制性措施,也不必检查系统是否已经进入不安全区,此方法允许系统在运行过程中发生死锁。但可通过系统所设置的检测机构,及时地检测出死锁的发生,并精确地确定与死锁有关的进程和资源,然后采取适当措施,从系统中将已发生的死锁清除掉。

public class DeadLockDemo2 { public static void main(String[] args) { // 线程a Thread td1 = new Thread(new Runnable() { public void run() { DeadLockDemo2.method1; // 线程b Thread td2 = new Thread(new Runnable() { public void run() { DeadLockDemo2.method2; td1.start(); td2.start(); } public static void method1() { synchronized (String.class) { try { Thread.sleep; } catch (InterruptedException e) { e.printStackTrace(); } System.out.println("线程a尝试获取integer.class"); synchronized (Integer.class) { System.out.println("线程a获取到integer.class"); } } } public static void method2() { // 不再获取线程a需要的Integer.class锁。 synchronized (String.class) { try { Thread.sleep; } catch (InterruptedException e) { e.printStackTrace(); } System.out.println("线程b尝试获取Integer.class"); synchronized (Integer.class) { System.out.println("线程b获取到Integer.class"); } } }}-----------------线程a尝试获取integer.class线程a获取到integer.class线程b尝试获取Integer.class线程b获取到Integer.class

4)解除死锁。

在上面的例子中,由于已经不存在线程a持有线程b需要的锁,而线程b持有线程a需要的锁的逻辑了,所以Demo顺利执行完毕。

这是与检测死锁相配套的一种措施。当检测到系统中已发生死锁时,须将进程从死锁状态中解脱出来。常用的实施方法是撤销或挂起一些进程,以便回收一些资源,再将这些资源分配给已处于阻塞状态的进程,使之转为就绪状态,以继续运行。死锁的检测和解除措施,有可能使系统获得较好的资源利用率和吞吐量,但在实现上难度也最大。

是否能够简单明了的在面试中阐述清楚死锁产生的原因,并给出解决死锁的方案,可以体现程序员在面对对并发问题时思路是否清晰,对并发的基础掌握是否牢固等等。而且在实际项目中并发模块的逻辑往往比本文的示例复杂许多,所以写并发应用之前一定要充分理解本文所总结的要点,并切记,并发程序编程在不显著影响程序性能的情况下,一定要尽可能的保守。

  1. 关于哲学家就餐问题详细请参考wiki ↩

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图