不可抢占资源(nonpreemtable resource) 指的是除非引起错误或者异常,否则进程无法抢占指定资源,这种不可抢占的资源比如有光盘,在进程执行调度的过程中,其他进程是不能得到该资源的。
死锁如果要对死锁进行一个定义的话,下面的定义比较贴切
如果一组进程中的每个进程都在等待一个事件,而这个事件只能由该组中的另一个进程触发,这种情况会导致死锁。
资源死锁的条件针对我们上面的描述,资源死锁可能出现的情况主要有
互斥条件:每个资源都被分配给了一个进程或者资源是可用的
保持和等待条件:已经获取资源的进程被认为能够获取新的资源
不可抢占条件:分配给一个进程的资源不能强制的从其他进程抢占资源,它只能由占有它的进程显示释放
循环等待:死锁发生时,系统中一定有两个或者两个以上的进程组成一个循环,循环中的每个进程都在等待下一个进程释放的资源。
发生死锁时,上面的情况必须同时会发生。如果其中任意一个条件不会成立,死锁就不会发生。可以通过破坏其中任意一个条件来破坏死锁,下面这些破坏条件就是我们探讨的重点
死锁模型Holt 在 1972 年提出对死锁进行建模,建模的标准如下:
圆形表示进程
方形表示资源
从资源节点到进程节点表示资源已经被进程占用,如下图所示
在上图中表示当前资源 R 正在被 A 进程所占用
由进程节点到资源节点的有向图表示当前进程正在请求资源,并且该进程已经被阻塞,处于等待这个资源的状态
在上图中,表示的含义是进程 B 正在请求资源 S 。Holt 认为,死锁的描述应该如下
这是一个死锁的过程,进程 C 等待资源 T 的释放,资源 T 却已经被进程 D 占用,进程 D 等待请求占用资源 U ,资源 U 却已经被线程 C 占用,从而形成环。
有四种处理死锁的策略:
忽略死锁带来的影响(惊呆了)
检测死锁并回复死锁,死锁发生时对其进行检测,一旦发生死锁后,采取行动解决问题
通过仔细分配资源来避免死锁
通过破坏死锁产生的四个条件之一来避免死锁
下面我们分别介绍一下这四种方法
鸵鸟算法最简单的解决办法就是使用鸵鸟算法(ostrich algorithm),把头埋在沙子里,假装问题根本没有发生。每个人看待这个问题的反应都不同。数学家认为死锁是不可接受的,必须通过有效的策略来防止死锁的产生。工程师想要知道问题发生的频次,系统因为其他原因崩溃的次数和死锁带来的严重后果。如果死锁发生的频次很低,而经常会由于硬件故障、编译器错误等其他操作系统问题导致系统崩溃,那么大多数工程师不会修复死锁。
死锁检测和恢复第二种技术是死锁的检测和恢复。这种解决方式不会尝试去阻止死锁的出现。相反,这种解决方案会希望死锁尽可能的出现,在监测到死锁出现后,对其进行恢复。下面我们就来探讨一下死锁的检测和恢复的几种方式
每种类型一个资源的死锁检测方式每种资源类型都有一个资源是什么意思?我们经常提到的打印机就是这样的,资源只有打印机,但是设备都不会超过一个。
可以通过构造一张资源分配表来检测这种错误,比如我们上面提到的
如果这张图包含了一个或一个以上的环,那么死锁就存在,处于这个环中任意一个进程都是死锁的进程。
每种类型多个资源的死锁检测方式如果有多种相同的资源存在,就需要采用另一种方法来检测死锁。可以通过构造一个矩阵来检测从 P1 -> Pn 这 n 个进程中的死锁。
现在我们提供一种基于矩阵的算法来检测从 P1 到 Pn 这 n 个进程中的死锁。假设资源类型为 m,E1 代表资源类型1,E2 表示资源类型 2 ,Ei 代表资源类型 i (1 <= i <= m)。E 表示的是 现有资源向量(existing resource vector),代表每种已存在的资源总数。