死锁 & 银行家算法

死锁是多线程环境中由于对资源竞争分配不合理而产生的阻塞行为，银行家算法是一种动态避免死锁的策略。

I、死锁

1.1 死锁定义

如果一个线程集合中的每个线程都在等待这个集合中另一个线程的执行结果才能继续执行下去，若无其他外力，它们都无法推进，这就形成了死锁。

1.2 死锁的4个必要条件

1、互斥条件：一个资源在某时刻内只能允许一个线程进行访问；

2、占有且等待：一个线程A占有一部分资源，此时去申请另外的资源，但申请的资源被线程B占有，此时线程A的请求阻塞，但是也不对自己本来的资源进行释放。

3、 不可剥夺条件：线程对已获得的资源，在未完成使用之前，不可剥夺，只能使用完成后才释放。

4、 循环等待：若干个线程之间形成了一种头尾相连的循环等待资源关系。

1.3 死锁的避免方式

死锁主要有三种避免方法：
1、 预防死锁发生：通过对死锁产生的四个必要条件进行限制；

2、 检测与拆除死锁：这种方式使允许死锁发生，检测死锁产生，然后解除死锁；
检测的具体实施可以维护两个资源矩阵，对可用资源和需要资源进行比较；
解除死锁的方式主要可以实施抢占剥夺；kill掉进程；回滚系统等；

3、 动态避免：在资源分配过程中，确保资源请求批准后系统不会进入死锁或潜在的死锁状态。如银行家算法。

II、银行家算法

银行家算法是仿照银行发放贷款时采用的控制方式而设计的一种死锁避免算法，该算法的策略是实现动态避免死锁。

2.1 算法思想

银行家算法的基本思想是：分配资源之前，判断系统是否安全，如果安全才会进行资源分配。

我们把操作系统看做是银行家，操作系统管理的资源相当于银行家的资金，线程向操作系统请求分配资源就是用户向银行家要贷款。

算法在每次分配资源前需要要求： request < available && request < needing;

2.2 银行家算法实例

我们以一个实例来说明银行家算法：
系统中有R1，R2，R3三种资源，在time0时刻，5个线程T0，T1，T2，T3，T4对资源占用和需求的情况如下表，此时系统的可用资源向量为(3,3,2)。求T0时刻系统是否存在安全序列？

thread	sum_need	allocated	needing	available
T0	(7,5,3)	(0,1,0)	(7,4,3)	(3,3,2)
T1	(3,2,2)	(2,0,0)	(1,2,2)
T2	(9,0,2)	(3,0,2)	(6,0,0)
T3	(2,2,2)	(2,1,1)	(0,1,1)
T4	(4,3,3)	(0,0,2)	(4,3,1)

我们假设每个线程执行时间为一个时刻。

1、在time0时刻，available(3,3,2) > T1.needing(1,2,2)； 所以T1可以执行，T1执行完毕之后available = T1.allocated(2,0,0) + available(3,3,2) = (5,3,2);

thread	sum_need	allocated	needing	available
T0	(7,5,3)	(0,1,0)	(7,4,3)	(5,3,2)
T2	(9,0,2)	(3,0,2)	(6,0,0)
T3	(2,2,2)	(2,1,1)	(0,1,1)
T4	(4,3,3)	(0,0,2)	(4,3,1)

2、进入time1时刻，available(5,3,2) > T3.needing(0,1,1)；所以T3可以执行，T3执行完毕之后available = T3.allocated(2,1,1)+available(5,3,2) = (7,4,3)；

thread	sum_need	allocated	needing	available
T0	(7,5,3)	(0,1,0)	(7,4,3)	(7,4,3)
T2	(9,0,2)	(3,0,2)	(6,0,0)
T4	(4,3,3)	(0,0,2)	(4,3,1)

3、进入time2时刻，available(7,4,3) > T4.needing(4,3,1)；所以T4可以执行，T4执行完毕之后available = T4.allocated(0,0,2) + available(7,4,3) = (7,4,5)；

thread	sum_need	allocated	needing	available
T0	(7,5,3)	(0,1,0)	(7,4,3)	(7,4,5)
T2	(9,0,2)	(3,0,2)	(6,0,0)

4、进入time3时刻，available(7,4,5) > T2.needing(6,0,0)；所以T2可以执行，T2指向完毕之后available = T2.allocated(3,0,2) + available(7,4,5) = (10,4,7)；

thread	sum_need	allocated	needing	available
T0	(7,5,3)	(0,1,0)	(7,4,3)	(10,4,7)

5、进入time4时刻，因为available(10,4,7) > T0.needing(7,4,3)；所以执行T0。完成安全序列。

上面只是安全序列的一个例子，可能还存在其他安全序列。

【参考】
[1] 《深入理解计算机系统》
[2] 死锁基础原理

欢迎转载，转载请注明出处wenmingxing 死锁&银行家算法