进程或线程死锁

发表于 | 分类于

死锁基本概念

死锁是指在一组进程中，每个进程都无限等待该组进程中另一个进程所占有的资源而导致永远无法等到资源的现象，这一组进程被称为死锁进程。死锁一旦发生，将会极大浪费系统资源以及可能造成系统崩溃。

死锁原因

从死锁的基本概念可以得知，死锁是发生在进程申请资源而得不到满足同时又互相僵持导致的，因此死锁原因可以归纳为两种：

1. 资源数量有限，进程之间需要竞争资源
2. 进程请求释放资源顺序不合理，即进程间推进顺序不合理

资源有限导致资源竞争引起死锁

在操作系统中，资源可分为可重用资源以及可消耗资源。可重用资源是指资源可以被重复利用，如CPU、I/O设备、内存、文件、信号量等；而可消耗资源则是只能使用一次，如中断、信号、消息等。可重用资源按照资源属性又可分为以下两种：

  • 可剥夺性资源

指进程在获得某资源后可以其他进程或者系统被剥夺，主要有CPU、IO设备、内存、文件、数据库、信号量等

  • 不可剥夺资源

不可剥夺资源是指资源被分配后不能被强行收回，比如打印机、磁带机等，因为这些资源如果可以被剥夺将会导致输出结果错误

活锁

假设两个资源R1、R2和两个进程P1、P2。P1已经给资源R1加锁，同时申请资源R2；P2已经已经给资源R2加锁，同时申请资源R1。由于资源已被加锁，进程P1、P2不断轮询资源尝试加锁，两个进程即没有推进也没有阻塞，这种情况称为活锁。

饥饿

假设有资源R1，进程P1正在使用资源R1，接着有进程P2、P3、P4也在申请R1，此时系统决定依次将资源R1分配给P3、P4而导致进程P2一直得不到资源的情况。

死锁必要条件

互斥条件

互斥条件又可以称为资源独占，是指在一段时间内资源只能被一个进程中占有，其他进程只能等待直到占有进程把资源释放掉。

占有且等待

又称为请求和保持条件，是指进程在申请其他资源而资源被占用时，申请进程阻塞但是并不释放自己已占有的资源。

不可抢占

又称为不可剥夺条件，指进程已获得资源后，除非使用结束或者主动释放，其他进程不可以抢占

循环等待

是指有一个进程组P1、P2、P3….Pn。P1等待P2占有的资源，P2等待P3占有的资源…..，Pn等待P1资源。形成一个等待环路

死锁资源分配图描述

资源分配图基本定义

为了检测是否有死锁发生，可以使用资源分配图来判断。资源分配图由一组结点N和一组边E所组成的对偶G=(N,E)。结点N分为两个互斥的子集，包括一组进程结点和一组资源结点。边由资源节点与进程结点连线构成，如果进程申请资源则边的方向为进程结点指向资源节点，反之则由资源结点指向进程结点。

如下图为一个简单的资源分配图：图片来源

资源分配图

其中圆圈代表某一个进程，方框代表某一组同类资源。

死锁定理

对于一个确定的资源分配图，死锁定理指出如果图中不存在环路，则一定不会发生死锁，否则有可能发生死锁（每类资源实例有多个）。如果每类资源的个数为1，则环路是否存在将成为死锁存在的充分必要条件，即环路存在可以推断出发生死锁，发生死锁也可以推断出环路存在。

资源分配图简化

在分析复杂的资源分配图时，可以使用简化方式去判断是否存在死锁，简化过程如下：

1. 在资源分配图中找到一个只有分配边的进程结点Pi，由于Pi有全部需要的资源，其可运行结束并释放所有资源，即将分配边删除。
2. 在第一步释放资源后将占有资源分配给等待进程，接着找到只有分配边的进程结点，也将分配边删除
3. 重复上述两步知道所有的边都可以被删除则称资源分配图时可以完全简化的，否则称为不可完全简化的

上诉简化完成后死锁的充分必要条件有：如果资源图是可以完全简化的则不存在死锁，否则存死锁。

死锁解决

根据死锁解决的思想，死锁解决可分为几种情况

1. 不考虑死锁问题，即鸵鸟算法
2. 不让死锁发生，有死锁预防（静态策略）与死锁避免（动态策略）
3. 让死锁发生，然后解除死锁

死锁预防

死锁预防是指在设计资源分配算法时就考虑不发生死锁，是一种静态的死锁解决方案。其通过设定某些限制条件去破坏死锁的四个必要条件，但是可能由于施加的限制过于严格而导致系统资源利用率低下，减少资源吞吐量。

根据破坏四个条件不同有如下做法：

1. 破坏互斥条件，虚拟化技术将互斥资源虚拟成共享资源，如打印机的SPOOLing技术
2. 破坏占有且等待，比如一次性申请所需资源或者再申请新资源得不到满足时释放已占有的资源
3. 破坏不可抢占条件，优先级抢占等，需要保证资源易于恢复
4. 破坏循环等待条件，系统给资源进行线性排队，进程资源申请只能按照线性顺序逐步申请，可能会造成资源浪费

死锁避免

死锁避免是指算法跟踪资源的分配情况，评估系统的安全状态，使得资源分配不会使系统进入不安全状态，死锁避免的限制较弱，可以获得较高的资源利用率和系统吞吐量。死锁避免经典算法有银行家算法。

安全序列是指这样一个进程序列{P1,P2,P3…Pn}，对于每一个进程Pi，Pi所需要的资源总数不大于系统剩余资源总数以及进程Pi之前进程占有资源总数之和，则称为安全序列。

银行家算法应用有系列的条件，如下所示：

1. 在固定数量的进程中共享数量固定的资源
2. 每个进程预先指定完成工作量所需的最大资源数量
3. 进程不允许申请比系统可用资源总数还多的资源
4. 进程等待资源时间有限
5. 如果系统满足了进程的资源请求，进程应该在有限时间内归还

银行家基本数据结构如下：

1. 可用资源数量available，含有m个元素，表示第i个元素的可用资源数量
2. 最大需求矩阵maxNeed，是一个n*m的矩阵，maxNeed[i][j]代表第i个进程对第j个资源的最大需求量
3. 分配矩阵allocation，是一个n*m的矩阵，allocation[i][j]代表第i个进程已获得第j个资源数量
4. 需求矩阵need，是一个n*m的矩阵，need[i][j]代表第i个进程还需要第j个资源数量
5. 请求资源矩阵request，是一个n*m的矩阵，request[i][j]代表第i个进程向系统请求第j个资源数量

银行家算法实现基本步骤如下：

1. 先检查request[i][0~m-1]<=need[i][0~m-1]，如果不满足则出错返回
2. 再检查request[i][0~m-1]<=available[0~m-1]，如果不满足则出错返回
3. 系统尝试将资源分配给进程，并修改available、allocation、need矩阵
4. 运行安全状态检查算法，检查如果按照当前分配是否会导致不安全状态出现，如果不安全则恢复，否则完成分配

银行家安全状态检查算法基本步骤如下：

1. 定义工作向量work[m]表示系统可提供的资源数量，安全算法执行初态work=available
2. 定义finish[n]向量，初始值为false，当有足够资源分配给进程i时令finish[i]=true
3. 在进程集合中找到满足以下条件的进程i：finish[i]=false，need[i][0~m]<=work[0~m]
4. 若第三步成功更新work[j]=work[j]+allocation[i][j]，finish[i]=true
5. 如果所有进程最后finish[i]=true，则系统处于安全状态，否则处于不安全状态，不能分配资源

以下为银行家算法的实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
//数据结构
const int m = 3; //资源类别数
const int n = 5; //进程数

struct Banker
{
	int available[m]; //可用资源数向量
	int maxNeed[n][m]; //每个进程最大资源需求量
	int allocation[n][m]; //已分配资源
	int need[n][m]; //还需要的资源数
};

int request[n][m]; //进程请求资源矩阵


bool SafeStatusCheck(Banker &inStatus)
{
	int work[m];
	for (int i = 0; i < m; i++) {
		work[i] = inStatus.available[i];
	}
	bool finish[n] = {false};
	set<int> okSet;
	while (1) {
		bool hasOne = false;
		for (int i = 0; i < n; i++) {
			if ((okSet.find(i)) != okSet.end()) {
				continue;
			}
			bool ok = true;
			for (int j = 0; j < m; j++) {
				if (inStatus.need[i][j] > work[j]) {
					ok = false; break;
				}
			}
			if (ok) {
				okSet.insert(okSet.end(), i);
				for (int j = 0; j < m; j++) {
					work[j] += inStatus.allocation[i][j];
				}
				hasOne = true; break;
			}
		}
		if (okSet.size() >= n) {
			return true;
		}
		if (!hasOne) {
			return false;
		}
	}
	return true;
}

bool BankerAllocate(Banker &inStatus, int pid, int request[m])
{
	for (int i = 0; i < m; i++) {
		if (inStatus.need[pid][i] < request[i] || request[i] > inStatus.available[i]) {
			return false;
		}
	}
	for (int i = 0; i < m; i++) {
		inStatus.available[i] -= request[i];
		inStatus.allocation[pid][i] += request[i];
		inStatus.need[pid][i] -= request[i];
	}
	bool canAlloc = SafeStatusCheck(inStatus);
	if (canAlloc) {
		return true;
	}
	else {
		for (int i = 0; i < m; i++) {
			inStatus.available[m] += request[i];
			inStatus.allocation[pid][i] -= request[i];
			inStatus.need[pid][i] += request[i];
		}
		return false;
	}
	
}


void CopyData(Banker &inStatus, int inAv[m], int inMax[n][m], int inAlloc[n][m], int inNeed[n][m])
{
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			inStatus.available[j] = inAv[j];
			inStatus.maxNeed[i][j] = inMax[i][j];
			inStatus.allocation[i][j] = inAlloc[i][j];
			inStatus.need[i][j] = inNeed[i][j];
		}
	}
}

int main()
{
	Banker TestStatus = {0};
	int tmpAv[m] = {3,3,2};
	int tmpMax[n][m] = {{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};
	int tmpAlloc[n][m] = {{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}};
	int tmpNeed[n][m] = {{7,4,3},{1,2,2},{6,0,0},{0,1,1},{4,3,1}};
	CopyData(TestStatus, tmpAv, tmpMax, tmpAlloc, tmpNeed);

	//初始状态
	int request1[m] = {0};
	cout << "ini status(true):" << BankerAllocate(TestStatus, 0, request1) << endl;

	//进程P1发出资源请求1,0,2
	int request2[m] = {1,0,2};
	cout << "P1 can satisfied(true):" << BankerAllocate(TestStatus, 1, request2) << endl;

	//进程P4再发出资源请求3,3,0
	int request3[m] = {3,3,0};
	cout << "P4 can satisfied(false):" << BankerAllocate(TestStatus, 4, request3) << endl;
	return 0;
}

死锁检测与解除

如果系统没有采用策略去防止死锁的产生，那么系统必须要能够检测死锁的发生同时能够解除掉死锁。系统检测死锁可以使用资源分配图结合死锁定理完成。系统检测死锁时机可以是发现进程长时间等待或者定时检测或者检测到资源利用率下降时检测死锁。由于使用资源分配图判断死锁需要系统记录资源分配使用情况，因此系统要能够统计这些信息。在解除死锁时，在尽可能以最小代价的方式下解除，主要有撤销所有死锁进程（代价大）、进程回退再启动（代价大）、剥夺资源分配给死锁进程、逐步撤销死锁进程直到解除死锁。

在死锁检测中，数据结构与银行家算法基本类似，可以直接调用SafeStatusCheck函数完成。