英文名编辑本段回目录
deadlocks(死锁)
简介编辑本段回目录
由于资源占用是互斥的,当某个进程提出申请资源后,使得有关进程在无外力协助下,永远分配不到必需的资源而无法继续运行,这就产生了一种特殊现象死锁。
死锁 |
一种情形,此时执行程序中两个或多个线程发生永久堵塞(等待),每个线程都在等待被其他线程占用并堵塞了的资源。例如,如果线程A锁住了记录1并等待记录2,而线程B锁住了记录2并等待记录1,这样两个线程就发生了死锁现象。
相关背景编辑本段回目录
最好的死锁例子可能是Kansas立法机构于20世纪早期通过的一个法规,其中说到“当两列车在十字路口逼近时,它们要完全停下来,且在一列列车开走之前另一列列车不能启动。”
死锁--在多道程序设计环境下,多个进程可能竞争一定数量的资源。一个进程申请资源,如果资源不可用,那么进程进入等待状态。如果所申请的资源被其他等待进程占有,那么该等待进程有可能无法改变状态。
死锁的特点编辑本段回目录
a、互斥
至少有一个资源必须处于非共享模式;即一次只有一个进程使用。如果另一个进程申请该资源,那么申请进程必须延迟直到该资源释放为止。
b、占有并等待
一个进程必须占有至少一个资源,并等待另一资源,而该资源为其他进程占有。
c、非抢占
资源不能被抢占;即,只在进程完成其任务之后,才会释放其资源。
死锁 |
d、循环等待
有一组进程{P0,P1,...,Pn},P0等待的资源为P1所占有,P1等待的资源为P2所占有,Pn-1等待的资源为Pn所占有,Pn等待的资源为P0所占有。
四个条件必须同时满足才会出现死锁,循环等待条件意味着占有并等待条件,这样四个条件并不完全独立。
死锁预防编辑本段回目录
出先死锁有四个必要条件。只要确保至少一个必要条件不成立,就能预防死锁的发生。
死锁 |
1、确保占有并等待条件不会在系统内出现。必须保证:当一个进程申请一个资源时,它不能占有其他资源。一种可以使用的协议是每个进程在执行前申请并获得所有资源。另外一种协议允许进程在没有资源时才可申请资源。
2、确保“非抢占”。为了确保这一条件不成立,可使用如下协议。如果一个进程占有资源并申请另一个不能立即分配的资源,那么其现已分配的资源都被抢占。
3、确保“循环等待”
确保此条件不成立的方法是对所有资源类型进行完全排序,且要求每个进程按递增顺序来申请资源。
死锁避免编辑本段回目录
银行家算法:
1),进程一开始向系统提出最大需求量.
2),进程每次提出新的需求(分期贷款)都统计是否超出它事先提出的最大需求量.
3),若正常,则判断该进程所需剩余剩余量(包括本次申请)是否超出系统所掌握的
剩余资源量,若不超出,则分配,否则等待.
死锁检测编辑本段回目录
如果一个系统既不采用死锁预防算法也不采用死锁避免算法,那么可能会出现死锁。在这种环境下,系统应提供:
1、一个用来检查系统状态从而确定是否出现了死锁的算法;
2、一个用来从死锁状态中恢复的算法。
方法:
a、每种资源类型只有单个实例
b、每种资源类型有多个单个实例的算法
c、应用检测算法
死锁恢复编辑本段回目录
1、进程终止
a、终止所有死锁进程
b、一次只终止一个进程直到取消死锁循环为止
具体操作需注意:
1)选择中断顺序
2)进程的优先级
3)多少个进程需要计算,需要多长时间
4)进程使用的资源
5)进程完成还需要多少资源
6)多少个进程需要被中断
7)进程是交互的还是批处理
2、资源抢占
需要解决的问题:选择一个牺牲品、回滚、饥饿
资源分配图编辑本段回目录
死锁问题可用称为系统资源分配图的有向图进行更为精确地描述。这种图有一个节点的集合V和一个边的集合E组成。节点的集合V分成两种类型的节点={P0,P1,...,Pn}和R={R0,R1,...,Rn}。
死锁 |
如果图没有环,那么系统就没有进程死锁。如果图有环,那么可能存在死锁。