Chapter 06 死锁 习题
知识点小记
- 从死锁中恢复：1.利用抢占恢复2.利用回滚恢复3.通过杀死进程恢复；
- 安全状态：即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕。 不安全状态：任何分配资源实力的序列都无法保证工作的完成。 安全状态和不安全状态的区别是：从安全状态出发，系统能够保证所有进程都能完成；而从不安全状态出发，就没有这样的保证。
- 死锁预防：
- 破坏互斥条件：一 切都使用假脱机技术 。实现可能性较小，思路是避免分配那些不是绝对必须的资源；
- 破坏占有并等待条件： 在开始就请求全部资源 。一种实现方法是一次性分配请求所需的全部资源（资源利用率低）；另一种方法是，当一个进程请求资源时，先暂时是放弃当全占用的所有资源，然后再尝试一次获得所需的全部资源；
- 破环不可抢占条件： 抢占资源
- 破坏环路等待条件： 对资源按序编号 。将所有资源统一编号，进程可以在任何时刻提出资源请求，但是所有请求必须按照资源编号的顺序提出，按此规则资源分配途中肯定不会出现环；（变种）取消必须按升序请求资源的限制，而仅仅要求不许进程请求比当前所占有资源编号低的资源。
- 通信死锁是协同同步的异常情况； 资源死锁是竞争性同步的问题。
- 活锁指的是任务或者执行者没有被阻塞，由于某些条件没有满足，导致一直重复尝试—失败—尝试—失败的过程。处于活锁的实体是在不断的改变状态，活锁有可能自行解开。
1.给出一个由策略产生的死锁的例子。
A：在美国，考虑总统选举，三个或更多的候选人正在争取某个政党的提名。初选结束后，当代表们到达党的选举大会时，可能没有候选人获得多数票，也没有任何代表愿意改变自己的投票。这是一个死锁。每个候选人都有一些资源（选票），但需要更多的选票才能胜出。在议会中有多个政党的国家，每个政党都支持不同版本的年度预算，但无法通过召集多数党来通过预算。这也是一个死锁。
2.学生们在机房的个人计算机上将自己要打印的文件发送给服务器，服务器会将这些文件暂存在它的硬盘上。如果服务器磁盘空间有限，那么，在什么情况下会产生死锁？这样的死锁应该怎样避免？
A：磁盘缓冲区是有限的资源。每一个新到达的任务都需要请求更多的资源。如果具备10MB的缓冲空间，如何10个2MB的任务的一半到来，磁盘缓冲区将会填满，没有更多的空间可以存储，就会发生一个死锁。死锁可以通过让一个任务在缓冲区填满之前就开始打印，并且在打印完成后释放空间。这样一来，任务实际上会打印完成，然后下一个可以做同样的事情。如果在缓冲区被填满前，任务还不能开始打印，死锁是可能的。
3.在前一题中，哪些资源是可抢占的，哪些资源是不可抢占的？
A：打印机不可抢占，磁盘空间可抢占。
4.在图6-1中，资源释放的顺序与获得的顺序相反，以其他的顺序释放资源能否得到同样的结果？
A：可以，没有区别。
5.一个资源死锁的发生有四个必要条件（互斥使用资源、占有和等待资源、不可抢占资源和环路等待资源）。举一个例子说明这些条件对于一个资源死锁的发生不是充分的。何时这些条件对一个资源死锁的发生是充分条件？
A：假设有三个进程A，B和C和两种资源类型R和S。并假设有一个R的实例和两个S的实例。考虑下面的场景：A请求R并得到它；B请求S并得到它；C请求S并得到它（有两个S实例）；B请求R但被阻塞；A请求S被阻塞。在这个阶段四条件都成立。但是，没有发生死锁。当C完成时，S的一个实例被释放到分配给A。现在A可以完成执行然后释放R，并分配给B，然后B可以完成其执行。如果有每种类型的资源只有一个实例，这4个条件就是充分的。
6.城市街道很容易遇到循环阻塞的情况,我们称之为“僵局”。“僵局”是一个资源死锁和同步竞争的问题。纽约市的预防算法称为“非阻塞盒子”，除非一个交叉路口的后续空间是非阻塞的，否则禁止汽车进入这个交叉路口。这是哪种预防算法？你能否提供其他的预防算法来解决“僵局”问题？
A：属于“破坏占有并等待条件”，因为我们假设汽车可以在交叉路口后进入街道空间，从而释放交叉路口。另一种策略可能允许汽车暂时停在车库里，释放出足够的空间来解决交通堵塞。一些城市有交通管制政策来塑造交通；随着城市街道变得更加拥挤，交通监督员调整红灯的设置，以限制进入严重拥挤地区的交通。流量越小，资源竞争越少，从而降低了发生交通堵塞的可能性。