进程管理----死锁

 

1.死锁、饥饿、死循环

	共同点	区别
死锁	都是进程无法顺利向前推进的现象 （故意设计的死循环除外）	一定是“循环等待对方手里的资源"导致的，因此如果有死锁现象，那至少有两个或两个以上的进程同时发生死锁。另外，发生死锁的进程一定处于阻塞态。
饥饿		可能只有一个进程发生饥饿。发生饥饿的进程既可能是阻塞态(如长期得不到推进的现象需要的I/O设备)，也可能是就绪态(长期得不到处理机)
死循环		可能只有一个进程发生死循环。死循环的进程可以上处理机运行(可以是运行态)，只不过无法像期待的那样顺利推进。死锁和饥饿问题是由于操作系统分配资源的策略不合理导致的，而死循环是由代码逻辑的错误导致的。死锁和饥饿是管理者(操作系统)的问题，死循环是被管理者的问题。

 

 

 

 

 

2.预防死锁的两种方式及优缺点

	方案	缺点
破坏互斥条件	将资源改造为共享使用资源（如SPOOLing技术）	可行性不高，很多时候无法破坏互斥条件
破坏不剥夺条件	申请的资源得不到满足时，立即释放所拥有的资源	实现复杂；剥夺资源可能导致部分工作失效；反复申请和释放资源导致系统开销大；可能导致饥饿
	申请的资源被其他进程占用时，由操作系统协助剥夺
破坏请求和保持条件	运行前分配好所有需要的资源，之后一直保持	资源利用率低，可能导致饥饿
破坏循环等待条件	给资源编号，必须按照编号从小到大的顺序申请资源	不方便增加新设备；会导致资源浪费；用户编程麻烦

 

 

 

 

 

 

3.银行家算法

假设系统中有n个进程，m种资源
每个进程在运行前先声明对各种资源的最大需求数，则可用一个n*m的矩阵(可用二维数组实现)表示所有进程对各种资源的最大需求数。不妨称为最大需求矩阵Max，Max[i, j]=K表示进程Pi最多需要K个资源Rj。同理，系统可以用一个n*m的分配矩阵Allocation表示对所有进程的资源分配情况。Max - Allocation=Need 矩阵，表示各进程最多还需要多少各类资源。另外，还要用一个长度为m的一维数组Available表示当前系统中还有多少可用资源。
某进程Pi向系统申请资源，可用一个长度为m的一维数组Request表示本次申请的各种资源量。

例子：系统中有5个进程P0~P1，3种资源R0~R2，初始量为（10,5,7），在某一时刻的情况如下表：

已使用（7，2 ，5）

	Available = （3,3,2）         Request(0) = （7,4,3）
	Max矩阵	Allocation矩阵	Need矩阵
进程	最大需求	已分配	最多还需要
P0	（7,5,3）	（0,1,0）	（7,4,3）
P1	（3,2,2）	（2,0,0）	（1,2,2）
P2	（9,0,2）	（3,0,2）	（6,0,0）
P3	（2,2,2）	（2,1,1）	（0,1,1）
P4	（4,3,3）	（0,0,2）	（4,3,1）

 

 

 

 

 

 

可用银行家算法预判本次分配是否会导致系统进入不安全状态:

①如果Request(i)[j] <= Need[i, j] (0 <= j <= m)便转向②:否则认为出错。

②如果Request(i)[j] <= Available[j] (0 <= j <= m),便转向③;否则表示尚无足够资源，Pi必须等待。

③系统试探着把资源分配给进程Pi，并修改相应的数据(并非真的分配，修改数值只是为了做预判) :

Available        = Available - Request(i);

Allocation[i, j] = Allocation[i, j] + Request(i)[j];

Need[i, j]         = Need[i, j] - Request(i)[j]

④操作系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式分配:否则，恢复相应数据，让进程阻塞等待。

最终可选出一个安全序列P1、P3、P0、P2、P4

4.死锁检测算法

按照P1、P2的顺序资源分配 图可化简为：

称该图是可完全简化的。