脚本宝典收集整理的这篇文章主要介绍了现代操作系统:死锁(三),脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
3.4 Deadlock Prevention死锁预防
破坏Coffman/Havender的四个条件中的任意一个。
3.4.1 Attacking the Mutual Exclusion Condition破坏互斥条件
假设一个资源并不会被一个进程独占,那么就根本不会存在死锁的产生,但是两个进程共同持有同一个资源会产生混乱,如两个进程共同控制打印机。但是如果我们采用假脱机(Spooling)技术可以支持若干个进程同时产生输出。例如:打印机假脱机模型中真正使用物理打印机的实际上是打印机守护进程,由于守护进程绝对不会去请求别的资源,所以不会因打印机产生死锁。但是对很多种的资源这种方式并不适用。
3.4.2 Attack the Hold and Wait Condition破坏持有并等待条件
要求每个进程在开始时就请求其运行时所需要的所有资源,这通常被称之为One Shot。一个进程需要运行前系统会给这个进程分配满足它运行的所有资源,那么这个进程一定可以顺利运行完毕,如果当前系统中的资源不能满足该进程则不进行资源分配,让进程等待资源。问题是:很多进程在运行前我们根本不知道它会用到哪些资源,并且一个更大的潜在问题是这个方式对系统资源的使用效率是达不到最优的。
另一种方案是当一个进程请求资源时,先暂时释放其当前占用的所有资源,然后再尝试一次获得所需的全部资源。
3.4.3 Attacking the No Preemption Condition破坏不允许抢占条件
通常是不可能的。也就是说,一些资源本质上是可抢占的(例如内存和CPU),对于这些资源来说,产生死锁不是问题(产生竞争状态是可以被解决的)。其他资源是不可抢占的,例如机器人手臂,通常不可能找到抢占这些资源的方法。一个现代的例外情况,我们不详细阐述,是资源(例如CD-ROM驱动器)是否可以虚拟化(召回管理程序)。
3.4.4 Attacking the Circular Wait Condition破坏循环等待条件
破坏循环等待有几种方法,其中第一种是保证每一个进程在任何时刻都只能占用一个资源,如果要去请求另一个资源就必须先释放当前拥有的这个资源,显然大多数情况下是不可接受的。
另一种方式是将所有的资源统一编号固定顺序,并要求按此顺序请求资源。此时所有的进程都可以在任何时刻提出资源请求,但是所有的请求必须按资源编号的顺序升序提出,因此,如果一个进程持有资源#34和#54,它只能请求资源#55和更高的资源。比如#34是打印机,#54是绘图仪,那么进程A和B都只能先请求打印机再请求绘图仪,也就不会发生死锁,很容易看出,循环已经不可能了。
10. Consider Figure 6-4. Suppose that in step (o) C requested S instead of requesting R. Would this lead to deadlock? Suppose that it requested both S and R.
A: 请求R;请求S;释放R;释放S; B:请求S;请求T;释放S;释放T; C:请求T;请求R;请求S;释放T;释放R;释放S |
3.5 Deadlock Avoidance死锁避免
让我们看看,即使我们的系统允许死锁的所有四个必要条件,我们是否能够小心翼翼地通过一片郁金香田并避免死锁状态。乐观的资源管理器会尽可能快地批准每个请求。在这四种情况都存在的情况下,要避免死锁,管理者必须聪明,而不仅仅是乐观。
3.5.1 Resource Trajectories资源轨迹图
在本节中,我们假设预先了解整个进程的资源请求和释放流程,因此,我们并没有提出一个切实可行的解决方案。我相信,这篇文章可以激励我们提出更接近实际的解决方案——银行家算法。下图描述了两个进程Hor(水平)和Ver(垂直)执行右边显示的程序。
Hor Ver <reg code> <reg code> P(print) P(plot) <reg code> <reg code> P(plot) P(print) <reg code> <reg code> V(print) V(plot) <reg code> <reg code> V(plot) V(print) <reg code> <reg code> |
我们把每个进程的进度画在坐标轴上。在我们下面右边展示的例子中,有两个进程,因此有两个轴。我们在水平轴(即X轴)上绘制Hor的进度,在垂直轴上绘制Ver的进度。
每个过程需要打印机和绘图仪的时间周期沿着坐标轴表示,它们的组合效果由正方形的颜色表示。
虚线表示可能的执行方式,对于单处理器的系统而言,在对角线上完成移动是不可能的,所以我们要么向右移动,要么向上移动。所以一个合理的执行方式可以变成这样。
危机就在眼前!
上述过程对于一般操作系统是不实用的,因为它需要事先知道程序。也就是说,资源管理器提前知道每个进程将发出什么样的请求以及请求的顺序。
17. All the trajectories in the Figure are horizontal or vertical. Under what conditions is is possible for a trajectory to be a diagonal.
首先需要假设当前系统是一个MultiProcessor的系统,否则即便在不产生死锁的前提下,它也会是一条阶梯状的折线。因此回答这个问题的思路就是在什么情况下没有死锁产生,那就不需要有谁先谁后。
A. 两个进程不存在对不可抢占资源的竞争
B. 每一种类型的资源都不止一个实例,如存在两个打印机和两个绘图仪
C. 打印机和绘图仪都是以假脱机形式工作的
18. Can the resource trajectory scheme in the Figure also be used to illustrate the problem of deadlocks with three processes and three resources? If so, how can this be done? If not, why not?
当然可以,但是并不直观,每增加一个进程就相当于多了一个维度,三个进程就变成了一个立方体对象。类比于两个进程的方式,三个进程和三个资源就变成了从一个立方体的左下角走到右上角。同理在最左下角的那个方格是不可进入的,进入即代表死锁产生。
19. In theory, resource trajectory graphs could be used to avoid deadlocks. By clever scheduling, the operating system could avoid unsafe regions. Is there a practical way of actually doing this?
除非我们已经明确知道各个进程在什么时候会产生对具体资源的请求以及要使用多长时间,否则我们是无法在实际应用中使用资源轨迹图的方式来避免死锁产生的。因此实际应用中基本不会使用。
Safe States安全状态
提供一些额外的知识来避免死锁。
Valid/Invalid claims有效/无效声明:假设只有一种资源类型,系统包含该资源的5个单位,并且有两个进程 P 和 Q。
过度声明导致过度保守的一个例子:假设系统有 10 个单位的一类资源 R,进程 P1 和 P2 运行都需要三个单位的 R。
如果每个进程老老实实的声明自己只需要3个单位的资源就不会阻塞。
定义:当进程按照一定的顺序运行且满足以下要求时我们称它为安全状态:如果进程按上述顺序运行并且最终都可以终止。(假设没有一个进程会超过他的资源声明,并且假设每个进程都将在它所有的资源请求被批准时终止)。
在安全状态的定义中,没有对进程的行为做任何假设,也就是说为了保证状态是安全的,无论进程做什么都必须终止(如果单独运行,每个进程都会终止,并且每个进程使用的资源不会超过它的声明)。对流程的行为不做任何假设就等同于做了最悲观的假设。
注意:当我说悲观时,我是从资源管理器的角度说的。从管理人员的角度来看,进程所能做的最糟糕的事情就是请求资源。
比较以上算法在多单元资源下检测死锁和确定安全性。
给出以下四种可能性中的一些示例:
下面的三个图都是相同的可重复使用的研究图表。此外,中间和右边表示每个过程的初始要求。没有一个图表示死锁状态(没有进程被阻塞)。我们的首要目标是确定哪些是安全的。
Question: Does the left figure represent a safe state or not?
Answer: You can NOT tell until you are told the initial claims of each process.
在不知道每个进程的声明之前显然是不能做出任何判断的。
由于状态显然没有死锁(没有进程被阻塞),我们有第四种(有趣的)可能性的例子:没有死锁并且不安全。现在考虑右侧的那张图,它是相同的可重用资源图,但是有以下非常相似的初始声明:
Question: Is the state in the right figure safe?
Answer: Despite its similarity to the middle figure, the right figure represents a state that IS safe.
显而易见,中间的资源图产生了死锁是不安全的,右侧的是安全的。
请解释为什么会这样。
请不要犯不幸的常见考试错误,给出一个涉及安全状态的例子而不给出声明。所以如果我让你画一个资源分配图是安全的还是不安全的,你必须包括每个进程的初始声明。我经常但不总是问这样一个问题,每次我这样做,几个学生忘记给出声明,因此失去了分数。分情况讨论!!!
我预测,如果我这学期问这样的问题,还会有学生犯这样的错误。请证明我错了。
How the Resource Manager Determines if a State is Safe RM如何判断状态是否安全
资源管理器有以下已知信息,这些信息可以确定安全。
然后,资源管理器遵循下列规则,这是dijkstra提出的银行家算法的一部分,以确定状态是否安全。
备注:我已经在课堂上讲述了一个练习,这是期中考试的解决方案!
Example 1
考虑一下下方表格中显示的示例。黑色的数据是问题陈述的一部分。红色部分为计算出的数据。我们想确定这个状态是否安全。
A safe state with 22 units of one resource |
|||
process |
initial claim |
current alloc |
max add'l |
X |
3 |
1 |
2 |
Y |
11 |
5 |
6 |
Z |
19 |
10 |
9 |
Total |
16 |
||
Available |
6 |
重要提示:以上只是表明,银行家有方法来确保进程终止,但是并不能保证银行家会这样做;
Example 2
这个示例是示例1的延续,在示例1中,Z请求2个单位,而经理(愚蠢地?)批准了这个请求。
An unsafe state with 22 units of one resource |
|||
process |
initial claim |
current alloc |
max add'l |
X |
3 |
1 |
2 |
Y |
11 |
5 |
6 |
Z |
19 |
12 |
7 |
Total |
18 |
||
Available |
4 |
这种状态是不安全的,为什么?
注意:
以上是脚本宝典为你收集整理的现代操作系统:死锁(三)全部内容,希望文章能够帮你解决现代操作系统:死锁(三)所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。