C++多线程 之 死锁

死锁:指多个进程因竞争共享资源而造成的一种僵局,若无外力作用,这些进程都将永远不能再 向前推进。


在计算机系统中有很多一次只能由一个进程使用的资源,如打印机,写文件等。在多道程序设计环境中,若干进程往往要共享这类资源,而且一个进程所需要的资源不止一个。这样,就会出现若干进程竞争有限资源,又推进顺序不当,从而构成无限期循环等待的局面。这种状态就是死锁。系统发生死锁现象不仅浪费大量的系统资源,甚至导致整个系统崩溃,带来灾难性后果。所以,对于死锁问题在理论上和技术上都必须给予高度重视。


1965年,Dijkstra提出并解决了一个他称之为哲学家就餐的同步问题。

从那时起,每个发明新的同步原语的人都希望通过解决哲学家就餐问题来展示其同步原语的精妙之处。

这个问题可以简单地描述如下:

五个哲学家围坐在一张圆桌周围,每个哲学家面前都有一盘菜。相邻两个盘子之间放有一根筷子 

哲学家的生活中有两种交替活动时段:即吃饭和思考。

当一个哲学家觉得饿了时,他就试图分两次去取其左边和右边的筷子,每次拿一只,但不分次序。如果成功地得到了两根筷子,就开始吃饭,吃完后放下筷继续思考。

能在某一个瞬间,所有的哲学家都同时拿起其左边筷子,看到右边的筷子不可用,又都放下左筷,等一会儿,又同时拿起左筷,如此这样永远重复下去。对于这种情况,所有的程序都在不停地运行,但都无法取得进展,就称为饥饿(starvation)



安全状态与不安全状态:安全状态指系统能按某种进程顺序来为每个进程分配其所需资源,直 至最大需求,使每个进程都可顺利完成。若系统不存在这样一个序列, 则称系统处于不安全状态。

 

  

 

产生死锁的原因:(1)竞争系统资源 (2)进程的推进顺序不当

产生死锁的必要条件

互斥条件:进程要求对所分配的资源进行排它性控制,即在一段时间内某资源仅为一进程所占用。

请求和保持条件:当进程因请求资源而阻塞时,对已获得的资源保持不放。

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

环路等待条件:在发生死锁时,必然存在一个进程–资源的环形链。

决死锁的基本方法:

预防死锁:

资源一次性分配:(破坏请求和保持条件

可剥夺资源:即当某进程新的资源未满足时,释放已占有的资源(破坏不可剥夺条件

资源有序分配法:系统给每类资源赋予一个编号,每一个进程按编号递增的顺序请求资源,释放则相反(破坏环路等待条件

 

避免死锁:

预防死锁的几种策略,会严重地损害系统性能。因此在避免死锁时,要施加较弱的限制,从而获得 较满意的系统性能。由于在避免死锁的策略中,允许进程动态地申请资源。因而,系统在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态,则将资源分配给进程;否则,进程等待。其中最具有代表性的避免死锁算法银行家算法

 (银行家算法(Banker's Algorithm)是一个避免死锁(Deadlock)的著名算法,是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础,判断并保证系统的安全运行。)



检测死锁

首先为每个进程和每个资源指定一个唯一的号码;

然后建立资源分配表进程等待表

 

 

 

解除死锁:

当发现有进程死锁后,便应立即把它从死锁状态中解脱出来,常采用的方法有:

剥夺资源:从其它进程剥夺足够数量的资源给死锁进程,以解除死锁状态

撤消进程:可以直接撤消死锁进程或撤消代价最小的进程,直至有足够的资源可用,死锁状态.消除为止;所谓代价是指优先级、运行代价、进程的重要性和价值等。

 

发表评论

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