YON CISE

死锁

29 Jul 2017

定义

一组进程处于死锁状态是指: 如果在一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引发的事件, 则称一组进程或系统此时发生了死锁.

必要条件

1971 年 Coffman 总结出了系统产生死锁的四个 必要条件:

  1. 互斥条件 (mutual exclusion)

    任一时刻, 一个资源仅能被一个进程独占. 另一个进程请求已被占用的资源时, 它将被设置成等待状态, 直到占用者释放资源.

  2. 占有和等待条件 (hold and wait)

    一个进程因请求资源得不到满足而等待时, 不释放已占有的资源.

  3. 不剥夺条件 (no preemption)

    任一进程不能从另一进程那里抢夺资源.

  4. 循环等待条件 (circular wait)

    存在一个循环等待链.

注意了, 这里是死锁产生的必要条件, 不是充分条件. 也就是说当这四个条件满足时, 并不是说系统此时一定发生死锁了, 但是当系统发生死锁时, 这四个条件一定是满足的.

解决

可以从三个方面来解决死锁问题，它们是 死锁防止 (deadlock prevention); 死锁避免 (deadlock avoidance); 死锁检测和恢复 (deadlock detection and recovery).

比较难区分的是死锁防止和死锁避免, 我的理解是, 死锁防止是 客观 上防止四个必要条件满足, 死锁避免是 主观 上避免四个必要条件满足.

如果我们把死锁比喻成在高速公路上开车撞到障碍物导致死亡, 那么死锁防止等同于政府派环卫工人去清理障碍物; 死锁避免是驾驶员通过驾驶技巧来规避障碍物; 死锁检测与恢复是撞倒障碍物之后通过安全气囊防止死亡.

死锁防止

层次化分配是一种有效的死锁防止策略. 简单来说就是将资源排序, 请求资源时只能按照顺序请求. 这样就破坏了四个必要条件中的循环等待条件.

以银行转账为例, 我们可以让程序必须按照用户 ID 大小顺序来锁定账户. (呃, 这个好像是主观避免了)

死锁避免

银行家算法是最有名的死锁避免算法, 但是因为算法要求进程提前知道自己所需的最大资源数量, 这就导致该算法并不具有多大的实际价值. 算法并不复杂, 直接上代码:

import numpy as np

n_processes = int(input('Number of processes? '))
n_resources = int(input('Number of resources? '))

available_resources = [int(x) for x in input('Claim vector? ').split(' ')]

currently_allocated = np.array([[int(x) for x in input('Currently allocated for process ' + str(i + 1) + '? ').split(' ')] for i in range(n_processes)])
max_demand = np.array([[int(x) for x in input('Maximum demand from process ' + str(i + 1) + '? ').split(' ')] for i in range(n_processes)])

total_available = available_resources - np.sum(currently_allocated, axis=0)

running = np.ones(n_processes) # An array with n_processes 1's to indicate if process is yet to run

while np.count_nonzero(running) > 0:
	at_least_one_allocated = False
	for p in range(n_processes):
		if running[p]:
			if all(i >= 0 for i in total_available - (max_demand[p] - currently_allocated[p])):
				at_least_one_allocated = True
				print(str(p) + ' is running')
				running[p] = 0
				total_available += currently_allocated[p]
	if not at_least_one_allocated:
		print('Unsafe')
		exit()
				
print('Safe')

死锁检测和恢复

这是一种比较有实际意义的解决方案, 当检测到系统发生死锁了, 可以强制破坏上述四个必要条件, 比如, 让优先级低的进程释放已占用的资源.

总结

总而言之, 解决死锁就从四个必要条件出发.

操作系统教程

Banker’s algorithm