第三章 进程死锁
死锁、饥饿、死循环
死锁：各进程互相等待对方手里的资源，导至各进程都阻塞，无法向前推进。
饥饿：长期得不到想要的资源，某进程无法向前推进。
死循环：某进程执行过程中一直挑不出某个循环现象。
共同点：都是进程无法向前推进。
不同点：死循环是程序逻辑导致的，饥饿和死锁是操作系统资源分配导致的。
死锁
死锁产生的条件
（1）互斥：必须互斥使用的资源才会导致死锁。（哲学家筷子、打印机）
（2）不剥夺条件：进程所获得的资源在未使用完之前，不能由其它进程强行夺走，只能主动释放。
（3）请求和保持条件：进程已经保持了至少一个资源，但又提出了新的请求，该资源被其它进程占有，而自己对已有资源保持不放。
（4）循环等待条件：存在进程资源的循环等待链，链中的每一个进程以获得的资源同时被下一个进程所请求。
死锁一定有循环等待，但是发生循环等待未必是死锁。
导致死锁事件
对资源的竞争，进程推进顺序非法，信号量使用不当。
死锁的处理策略
（1）预防死锁。破坏死锁产生的条件
（2）避免死锁。用某种方法防止系统进入不安全状态。
（3）死锁的检测和解除。允许死锁发生，但是操作系统能检查死锁的发生，采取某种措施解除死锁。
破坏死锁
（1）破坏互斥条件：SPOOLing技术，在进程和互斥资源中加一个输出进程，由输出进程统一分配管理，将独占设备改成共享设备。
（2）破坏不剥夺条件：当进程请求新资源等不到满足时，立即释放拥有的所有资源。
（3）破坏请求和保持条件：采用静态分配方法，一次性申请所需要的全部资源。
（4）破坏循环等待条件：采用顺序资源分配法，给系统的资源编号，每个进程必须按编号递增的顺序请求资源，同类资源（相同编号）一次申请完。
避免死锁
银行家算法
安全序列：系统按照这种序列分配资源，每个进程都能顺利完成，只要能找出一个就是安全状态。
系统处于安全状态，一定不会发生死锁，如果系统进入不安全状态，有可能发生死锁
银行家算法步骤：
（1）检查此次盛情是否超过了之前声明的最大需求数。
（2）检查此时系统剩余的可用资源是否还能满足这次请求。
（3）试探着分配，更改各数据结构。
（4）用安全性算法检查此次分配是否会导致不安全。
习题
一、 单项选择题
1、 在多道程序所提供的可共享的系统资源不足时，可能出现死锁。但是，不适当的（C）也可能产生死锁。
A. 进程优先权 B.资源的线性分配 C. 进程推进顺序 D.分配队列优先权
2、 采用资源剥夺法可解除死锁，还可以采用（B）方法解除死锁
A.执行并行操作 B.撤消进程 C.拒绝分配新资源 D.修改信号量
3、 产生死锁的四个必要条件是：互斥、（B）循环等待和不剥夺。
A.请求与阻塞 B.请求与保持 C.请求与释放 D 释放与阻塞
4、 发生死锁的四个必要条件有四个，要防止死锁的发生，可以破坏这四个必要条件，但是破坏（A）是不太实际。
A.互斥 B.不可抢占 C.部分分配 D循环等待
5、 资源的按序分配策略可以破坏（D）
A.互斥使用资源 B.占有且等待资源 C.非抢占资源 D循环等待资源
6、 在（C）的情况下，系统出现死锁。
A.计算机系统发生了重大故障 B.有多个封锁的进程同时存在
C.若干进程因竞争资源而无休止地相互等待他方释放已占有的资源
D资源数大大小于进程数或进程同时申请的资源数大大超过资源总数
7、 银行家算法是一种（B）算法。
A. 死锁解除 B. 死锁避免 C. 死锁预防 D死锁检测
8、 当进程数大于资源数时，进程竞争资源（B）会产生死锁。
A.一定 B.不一定
9、 某系统中有3个并发进程，都需要同类资源4个，试问该系统不会产生死锁的最少资源数是（B）。
A. 9 B.10 C.11 D12
10、 当检测出发生死锁时，可以通过撤消一个进程解除死锁。上述描述是（B）
A.正确的 B. 错误的
11、 在下列解决死锁的方法中，属于死锁预防策略的是（B）
A.银行家算法 B.资源有序分配法 C. 死锁检测法 D资源分配图化简法
二、 填空题
1、死锁是指在系统中的多个（进程）无限期地等待永远不会发生的条件。
2、死锁产生的必要条件有四个，即（互斥）、（循环等待）、（请求和保持）、（不剥夺条件）
3、解除死锁常用的方法有两种：其中（资源剥夺法）是从其他进程那里剥夺足够数量的资源给（死锁）进程，以解除死锁状态
4、对待死锁，一般应考虑死锁的预防、避免、检测和解除四个问题。典型的银行家算法是属于（死锁的避免），破坏循环等待条件是属于（死锁的预防），而剥夺资源是（死锁的解除）的基本方法。
三、 解析题
1、 为什么说采用有序资源分配法不会产生死锁？
解：为了便于说明，不妨设系统中有M类资源，N个进程，分别用R1，R2……，RM（1，2，……，M看作资源号）和P1，P2……，Pn表示。根据有序资源分配法可知，进程申请资源时必须按照资源编号的升序进行，即任何进程在占有了Ri资源后，再申请的资源Rj的编号j一定大于I。因此在任一时刻，系统中至少存在一个进程Pk，它占有了较高编号的资源Rh，且它继续请求的资源必然是空闲的，因而Pk可以一直向前推进直至完成，当Pk运行完成后即会释放它占有的所有资源，在Pk完成之后，剩下的进程集合中同样会存在一个进程，它占有了较高的资源，且它继续请求的资源必然是空闲的，因而它可以一直向前推进直至完成；以此类推，所有进程均可运行完成，故不会发生死锁。
2、 N个进程共享某种资源R，该资源共有m个可分配单位，每个进程一次一个地申请或释放资源单位。假设每个进程对该资源的最大需求量均小于m，且各进程最大需求之和小于m+n，试证明在这个系统中不可能发生死锁。
解：设：max(i):表示第I进程的最大资源需求量
need(i): 表示第I进程的还需要的资源量
allocation(i): 表示第I进程的已分配到的资源量
由题中给定条件可知：
max(1)+max(2)+…+max(n)=(allocation(1) +allocation(2)+…+allocation (n))+( need(1)+need(2)+…+need(n))<m+n （1）
假若系统发生死锁，则有：（m个资源均应全部分配出去）即
allocation(1) +allocation(2)+…+allocation (n)=m （2）
同时有（所有进程处于无限等待状态）：
need(1)+need(2)+…+need(n)>=n （3）
则由（2）+（3）得：
(allocation(1) +allocation(2)+…+allocation (n))+( need(1)+need(2)+…+need(n))>=m+n
这与（1）式相矛盾。
3、 在哲学家进餐问题中，假定用一个信号量表示一支筷子，由这五个信号构成信号量数组：int stick[5]={1，1，1，1，1} 第I个哲学家的活动描述如下所示，试问这五个哲学家的进餐活动是否发生死锁？
While(1)
{
P(stick[I])
P(stick[(I+1)mod 5]) )
进餐
V(stick[I])
V(stick[(I+1)mod 5]) )
思考
}
解：这种描述虽然可以保证不会有两个相邻的哲学家同时进餐，但可能引起死锁。这种情况发生在当五个哲学家几乎同时饥饿而各自拿起了左边的筷子时，这种五支筷子信号量值为0；当他们试图去拿右边的筷子时，都将因无筷子可拿而无限期地等待，从而导致了死锁的产生。
4、 在银行家算法中，若出现了下述资源分配情况：
| allocation | need | available | |
|---|---|---|---|
| P0 | 0 0 3 2 | 0 0 1 2 | 1 6 2 2 |
| P1 | 1 0 0 0 | 1 7 5 0 | |
| P2 | 1 3 5 4 | 2 3 5 6 | |
| P3 | 0 3 3 2 | 0 6 5 2 | |
| P4 | 0 0 1 4 | 0 6 5 6 |
试问：
（1）该状态是否安全？
安全
（2）如果进程P2提出请求Requst2（1，2，2，2）后，系统能否将资源分配给它？
不能，将资源分配之后
| allocation | need | available | |
|---|---|---|---|
| P0 | 0 0 3 2 | 0 0 1 2 | 0 4 0 0 |
| P1 | 1 0 0 0 | 1 7 5 0 | |
| P2 | 2 5 7 6 | 1 1 3 4 | |
| P3 | 0 3 3 2 | 0 6 5 2 | |
| P4 | 0 0 1 4 | 0 6 5 6 |
可用资源变成0400，不能让任何一个进程满足，发生死锁 。
5、有相同类型的5个资源被4个进程共享，且每个进程最多需要2个这样的资源就可以运行完毕。试问该系统是否由于对这种资源的竞争而产生死锁？
解：该系统不会由于对这种资源的竞争而产生死锁。考虑最坏的情况，四个进程各拥有一个资源，但是第五个资源不管分配给谁，都能保证进程继续执行下去，所以不会产生死锁。