《现代操作系统》– 死锁、银行家算法

1.资源:进程对设备、文件等获得独占性的访问权时有可能会发生死锁,为了尽可能地通用化,我们将这种需排它使用的对象称为资源。资源可以是硬件设备(如磁带机),或一组信息(如数据库中一个加锁的记录)。计算机中通常有多种资源。有些类型的资源有多个相同的实例,如三台磁带机。当某一资源有若干拷贝时,其中任一个均可用来满足对资源的请求。简言之,资源是在任何时刻只能被单个进程使用的任何对象。

 

2.资源又分为可抢占资源和不可抢占资源。

可抢占资源:可从拥有它的进程处剥夺而没有任何副作用,存储器是一类可剥夺资源。

不可抢占资源:无法在不导致相关计算失败的情况下将其从属主进程处剥夺。若一个进程已开始打印,那么剥夺其占用的打印机并分配给另一进程将使打印结果一片混乱。打印机是不可剥夺的。

使用一个资源的事件顺序是:
(1)申请资源
(2)使用资源
(3)释放资源

 

3.死锁的定义:如果一个进程集合中的每个进程都在等待只能由该进程集合中的其他进程才能引发的事件,那么,该进程集合就是死锁的。

 

4.死锁的四个必要条件

①:互斥条件。每个资源要么已经分配给了一个进程,要么就是可用的,不能同时被两个或两个以上的进程占有。

②:占有和等待条件。已经得到了某个资源的进程可以再请求新的资源。

③:不可抢占条件。已经分配给了一个进程的资源不能强制性的被占用,它只能被占有它的进程显式地释放。

④:环路等待条件。死锁发生时,系统中一定有由两个或两个以上的进程组成的一条环路,该环路中的每个进程都在等待下一个进程所占用的资源。

死锁发生时,以上四个条件一定是同时满足。如果其中任何一个条件不成立,死锁就不会发生。

 

5.死锁如何产生以及如何避免的例子:

总而言之,有四种处理死锁的策略:

①:忽略该问题。也许如果你忽略它,它也会忽略你。

②:检测死锁并恢复。让死锁发生,检测他们是否发生,一旦发生死锁,采取行动解决问题。

③:仔细对资源进行分配,动态地避免死锁。

④:通过破坏引起死锁的四个必要条件之一,防止死锁的产生。

 

6.检测死锁的算法:

①:对图中的每一个节点N,将N作为起始点执行下面5个步骤。

②:将L初始化为空表,并清除所有的有向边标记。

③:将当前节点添加到L的尾部,并检测该节点是否在L中已出现过两次。如果是,那么该图包含了一个环(已经在L中),算法结束。

④:从给定的节点开始,检测是否存在没有标记的从该节点的弧(有向边)。如果存在的话,做第5步,如果不存在,跳到第6步。

⑤:随机选取一条没有标记的从该节点出发的弧(有向边),标记它。然后顺着这条弧线找到新的当前节点,返回第3步。

⑥:如果这一节点是起始节点,那么表明该图不存在任何环,算法结束。否则意味着我们走进了死胡同,所以需要移走该节点,返回到前一个节点,即当前节点前面的一个节点,并将它作为新的当前节点,同时转到第3步。

其实这一算法就是一次将每一个节点作为一棵树的根节点,并进行深度优先搜索。

image

 

7.每种类型多个资源的死锁检测

死锁检测算法如下:

①:寻找一个没有标记的进程Pi,对于它而言R矩阵的第i行向量小于或等于A。

②:如果找到了这样一个进程,那么将C矩阵的第i行向量加到A中,标记该进程,并转到第1步。

③:如果没有这样的进程,那么算法终止。

算法结束时,所有没有标记过的进程(如果存在的话)都是死锁进程。

image

进程3被满足,然后进程2,进程1,所以上图不存在死锁。

 

8.从死锁中恢复

①利用抢占恢复:在不通知原进程的情况下,将某一资源从一个进程强行取走给另一个进程使用,接着又送回。

②利用回滚恢复:将进程复位到一个更早的状态,那时它还没有取得所需资源,接着就把这个资源分配给一个死锁进程。

③通过杀死进程恢复:杀死环中的一个进程,如果走运的话,其他进程将可以继续。如果这样行不通的话,就需要继续杀死别的进程直到打破死循环。

 

9.死锁避免

image

资源轨迹图

安全和不安全状态

进程序列{P1,P2, ……Pn}在Ti时刻是安全的序列,当且仅当存在

Pi申请的附加资源数≤Pi已保持的资源数+当前系统可用的资源数

 

10.银行家算法:就是对每一个请求进行检查,检查如果满足这一请求是否会达到安全状态。若是,那么就满足该请求;若否,那么就推迟对这一请求的满足。为了看状态是否安全,银行家看他是否有足够的资源满足某一客。如果可以,那么这笔投资认为是 能够收回的,并且接着检查最接近最大限额的一个客户,以此类推。如果所有投资最终都被收回,那么该状态是安全的,最初的请求可以批准。

image

a.安全 b.安全 c.不安全

多个资源的银行家算法:

下边的三个向量分别表示总的资源E、已分配资源P,和剩余资源A。由E可知系统中共有6台磁带机,3台绘图仪,4台汀印机和2台CD-ROM。由P可知当前已分配 了5台磁盘机,3台绘图仪,2台打印机和2台CDROM。该向量可通过将左边短阵的各列 相加得到,剩余资源向量可通过从资源总数中减去已分配资源数得到。

image

检查一个状态是否安全的步骤如下:

(1)查找右边矩阵中是否有一行,其未被满足的设备数均小于或等于向量A。如果找不到,则系统将死锁,因为任何进程都无法运行结束。

(2)若找到这样一行,则可以假设它获得所需的资源并运行结束,将该进程标记为结束,并将资源加到向量A上。

(3)重复以上两步,直到所有的进程都标记为结束。若达到所有进程结束。则状态是安
全的,否则将发生死锁。

 

11.死锁预防:

①破坏互斥条件:如果资源不被一个进程所独占,那么死锁肯定不会产生。当然,允许两个进程同时使用打印机会造成混乱,通过采用假脱机打印机技术允许若干个进程同时产生输出。

②破坏占有和等待条件:规定所有进程在开始执行前请求所需的全部资源,如果所需的全部资源可用,那么就将他们分配给这个进程,于是该进程肯定能运行结束。如果有一个或多个资源正被使用,那么就不进行分配,进程等待。

③破坏不可抢占条件:即允许进程强行从占有者那里夺取某些资源。就是说,当一个进程已占有了某些资源,它又申请新的资源,但不能立即被满足时,它必须释放所占有的全部资源,以后再重新申请。它所释放的资源可以分配给其它进程。这就相当于该进程占有的资源被隐蔽地强占了。

④破坏环路等待条件:一种是保证每个进程在任何时刻只能占用一个资源,如果要请求另外一个资源,它必须先释放第一个资源。第二种是将所有资源统一编号,所有请求必须按资源编号提出。

 

12.饥饿:和死锁非常相近的一个问题是饥饿(starvation)。在动态运行的系统中,在任何时刻都会产生申请资源。这就需要规定一些策略来决定在什么时候,谁获得什么资源。虽然这个策略表面上很有道理,但依然有叫能使一些进程永远得不到服务,虽然它们并没有被死锁。

在一个繁忙的系统中,有一个进程有一个很大的文件要打印,每当打印机空闲,系统纵观所有进程,并把打印机分配给打印最小文件的进程。如果存在一个固定的进程流,其中的进程都是只打印小文件,那么,要打印大文件的进程永远也得不到打印机。很简单,它会如饥饿而死一般(无限制地推后,尽管它没有被阻塞)。

饥饿可以通过先来先服务资源分配策略来避免。

 

转载请标注来源:www.blogfshare.com    By:AloneMonkey

本文链接:http://www.alonemonkey.com/operating-system-five.html