死锁相关知识点梳理如下：

何谓死锁？

定义

1. 在 并发计算 中：
   当两个以上的运算单元，双方都在等待对方停止执行，以获取系统资源，但是没有一方提前退出时，就称为死锁。
2. 在 操作系统中
   当一个 进程或 线程 进入等待 状态 ，因为所请求的 系统资源 被另一个等待进程持有，而另一个等待进程又在等待另一个等待进程持有的另一个资源。 如果一个进程由于它所请求的资源正被另一个本身正在等待的进程使用而无限期地无法更改其状态，则称该系统处于死锁状态。

一个进程 p1占用了显示器，同时又必须使用打印机，而打印机被进程p2占用，p2又必须使用显示器，这样就形成了死锁。 因为p1必须等待p2发布打印机才能够完成工作并发布屏幕，同时p2也必须等待p1发布显示器才能完成工作并发布打印机，形成循环等待的死锁。

题外话：
活锁（livelock）: 与死锁相似，死锁是行程都在等待对方先释放资源；活锁则是行程彼此释放资源又同时占用对方释放的资源。当此情况持续发生时，尽管资源的状态不断改变，但每个行程都无法获取所需资源，使得事情没有任何进展。

活锁：两人互相礼让，却恰巧站到同一侧，再次让开，又站到同一侧，同样的情况不断重复下去导致双方都无法通过。

写一个死锁的例子

代码

1. testDeadLock.cpp代码如下

#include <iostream>
#include <thread>
#include <mutex>
#include <unistd.h>

using namespace std;

int data = 1;
mutex mt1,mt2;

void a2() {
	mt2.lock();
	sleep(1);
	data = data * data;
	mt1.lock();  //此时a1已经对mt1上锁，所以要等待
	cout<<data<<endl;
	mt1.unlock();
	mt2.unlock();
}
void a1() {
	mt1.lock();
	sleep(1);
	data = data+1;
	mt2.lock();  //此时a2已经对mt2上锁，所以要等待
	cout<<data<<endl;
	mt2.unlock();
	mt1.unlock();
}

int main() {
	thread t2(a2);
	thread t1(a1);
	cout<<"main start"<<endl; 
	t1.join();
	t2.join();
	cout<<"main here"<<endl;  //要t1线程、t2线程都执行完毕后才会执行
	return 0;
}
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

编译

g++ -g testDeadLock.cpp -o tt -lpthread
1

运行结果

gdb调试

1. 查看进程号

$ ps -aux|grep tt
***        481  0.0  0.0  22424  1688 pts/1    tl+  11:58   0:00 ./tt
1
2

2. 调试过程

• gdb
• attach 481
• thread apply all bt或者info threads ->thread 3 thread 2查看

$ gdb
GNU gdb (Ubuntu 9.2-0ubuntu1~20.04.1) 9.2
Copyright (C) 2020 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.
Type "show copying" and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
    <http://www.gnu.org/software/gdb/documentation/>.

For help, type "help".
Type "apropos word" to search for commands related to "word".
(gdb) attach 481
Attaching to process 481
[New LWP 482]
[New LWP 483]
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
__pthread_clockjoin_ex (threadid=139624981407488, thread_return=0x0, clockid=<optimized out>,
    abstime=<optimized out>, block=<optimized out>) at pthread_join_common.c:145
145     pthread_join_common.c: No such file or directory.
(gdb) bt
#0  __pthread_clockjoin_ex (threadid=139624981407488, thread_return=0x0, clockid=<optimized out>,
    abstime=<optimized out>, block=<optimized out>) at pthread_join_common.c:145
#1  0x00007efcfa2ec047 in std::thread::join() () from /lib/x86_64-linux-gnu/libstdc++.so.6
#2  0x00005625d738c4de in main ()
(gdb) thread apply all bt

Thread 3 (Thread 0x7efcf96b2700 (LWP 483)):
#0  __lll_lock_wait (futex=futex@entry=0x5625d73901a0 <mt2>, private=0) at lowlevellock.c:52
#1  0x00007efcfa4020a3 in __GI___pthread_mutex_lock (mutex=0x5625d73901a0 <mt2>) at ../nptl/pthread_mutex_lock.c:80
#2  0x00005625d738c60d in __gthread_mutex_lock(pthread_mutex_t*) ()
#3  0x00005625d738c71c in std::mutex::lock() ()
#4  0x00005625d738c424 in a1() ()
#5  0x00005625d738cf84 in void std::__invoke_impl<void, void (*)()>(std::__invoke_other, void (*&&)()) ()
#6  0x00005625d738cf1c in std::__invoke_result<void (*)()>::type std::__invoke<void (*)()>(void (*&&)()) ()
#7  0x00005625d738ceae in void std::thread::_Invoker<std::tuple<void (*)()> >::_M_invoke<0ul>(std::_Index_tuple<0ul>) ()
#8  0x00005625d738ce6b in std::thread::_Invoker<std::tuple<void (*)()> >::operator()() ()
#9  0x00005625d738ce3c in std::thread::_State_impl<std::thread::_Invoker<std::tuple<void (*)()> > >::_M_run() ()
#10 0x00007efcfa2ebde4 in ?? () from /lib/x86_64-linux-gnu/libstdc++.so.6
#11 0x00007efcfa3ff609 in start_thread (arg=<optimized out>) at pthread_create.c:477
#12 0x00007efcfa127163 in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:95

Thread 2 (Thread 0x7efcf9eb3700 (LWP 482)):
#0  __lll_lock_wait (futex=futex@entry=0x5625d7390160 <mt1>, private=0) at lowlevellock.c:52
#1  0x00007efcfa4020a3 in __GI___pthread_mutex_lock (mutex=0x5625d7390160 <mt1>) at ../nptl/pthread_mutex_lock.c:80
#2  0x00005625d738c60d in __gthread_mutex_lock(pthread_mutex_t*) ()
#3  0x00005625d738c71c in std::mutex::lock() ()
#4  0x00005625d738c3a7 in a2() ()
#5  0x00005625d738cf84 in void std::__invoke_impl<void, void (*)()>(std::__invoke_other, void (*&&)()) ()
#6  0x00005625d738cf1c in std::__invoke_result<void (*)()>::type std::__invoke<void (*)()>(void (*&&)()) ()
#7  0x00005625d738ceae in void std::thread::_Invoker<std::tuple<void (*)()> >::_M_invoke<0ul>(std::_Index_tuple<0ul>) ()
#8  0x00005625d738ce6b in std::thread::_Invoker<std::tuple<void (*)()> >::operator()() ()
#9  0x00005625d738ce3c in std::thread::_State_impl<std::thread::_Invoker<std::tuple<void (*)()> > >::_M_run() ()
#10 0x00007efcfa2ebde4 in ?? () from /lib/x86_64-linux-gnu/libstdc++.so.6
#11 0x00007efcfa3ff609 in start_thread (arg=<optimized out>) at pthread_create.c:477
#12 0x00007efcfa127163 in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:95

Thread 1 (Thread 0x7efcf9eb4740 (LWP 481)):
#0  __pthread_clockjoin_ex (threadid=139624981407488, thread_return=0x0, clockid=<optimized out>, abstime=<optimized out>, block=<optimized out>) at pthread_join_common.c:145
#1  0x00007efcfa2ec047 in std::thread::join() () from /lib/x86_64-linux-gnu/libstdc++.so.6
#2  0x00005625d738c4de in main ()
(gdb) info threads
  Id   Target Id                            Frame
* 1    Thread 0x7efcf9eb4740 (LWP 481) "tt" __pthread_clockjoin_ex (threadid=139624981407488, thread_return=0x0,
    clockid=<optimized out>, abstime=<optimized out>, block=<optimized out>) at pthread_join_common.c:145
  2    Thread 0x7efcf9eb3700 (LWP 482) "tt" __lll_lock_wait (futex=futex@entry=0x5625d7390160 <mt1>, private=0)
    at lowlevellock.c:52
  3    Thread 0x7efcf96b2700 (LWP 483) "tt" __lll_lock_wait (futex=futex@entry=0x5625d73901a0 <mt2>, private=0)
    at lowlevellock.c:52
(gdb) thread 1
[Switching to thread 1 (Thread 0x7efcf9eb4740 (LWP 481))]
#0  __pthread_clockjoin_ex (threadid=139624981407488, thread_return=0x0, clockid=<optimized out>, abstime=<optimized out>,
    block=<optimized out>) at pthread_join_common.c:145
145     in pthread_join_common.c
(gdb) thread 2
[Switching to thread 2 (Thread 0x7efcf9eb3700 (LWP 482))]
#0  __lll_lock_wait (futex=futex@entry=0x5625d7390160 <mt1>, private=0) at lowlevellock.c:52
52      lowlevellock.c: No such file or directory.
(gdb) thread 3
[Switching to thread 3 (Thread 0x7efcf96b2700 (LWP 483))]
#0  __lll_lock_wait (futex=futex@entry=0x5625d73901a0 <mt2>, private=0) at lowlevellock.c:52
52      in lowlevellock.c
(gdb) bt
#0  __lll_lock_wait (futex=futex@entry=0x5625d73901a0 <mt2>, private=0) at lowlevellock.c:52
#1  0x00007efcfa4020a3 in __GI___pthread_mutex_lock (mutex=0x5625d73901a0 <mt2>) at ../nptl/pthread_mutex_lock.c:80
#2  0x00005625d738c60d in __gthread_mutex_lock(pthread_mutex_t*) ()
#3  0x00005625d738c71c in std::mutex::lock() ()
#4  0x00005625d738c424 in a1() ()
#5  0x00005625d738cf84 in void std::__invoke_impl<void, void (*)()>(std::__invoke_other, void (*&&)()) ()
#6  0x00005625d738cf1c in std::__invoke_result<void (*)()>::type std::__invoke<void (*)()>(void (*&&)()) ()
#7  0x00005625d738ceae in void std::thread::_Invoker<std::tuple<void (*)()> >::_M_invoke<0ul>(std::_Index_tuple<0ul>) ()
#8  0x00005625d738ce6b in std::thread::_Invoker<std::tuple<void (*)()> >::operator()() ()
#9  0x00005625d738ce3c in std::thread::_State_impl<std::thread::_Invoker<std::tuple<void (*)()> > >::_M_run() ()
#10 0x00007efcfa2ebde4 in ?? () from /lib/x86_64-linux-gnu/libstdc++.so.6
#11 0x00007efcfa3ff609 in start_thread (arg=<optimized out>) at pthread_create.c:477
#12 0x00007efcfa127163 in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:95
(gdb)
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

由结果可看出 thread2在等待mt1,thread3在等待mt2,造成了死循环

(gdb) thread 2
[Switching to thread 2 (Thread 0x7efcf9eb3700 (LWP 482))]
#0  __lll_lock_wait (futex=futex@entry=0x5625d7390160 <mt1>, private=0) at lowlevellock.c:52
52      lowlevellock.c: No such file or directory.
(gdb) thread 3
[Switching to thread 3 (Thread 0x7efcf96b2700 (LWP 483))]
#0  __lll_lock_wait (futex=futex@entry=0x5625d73901a0 <mt2>, private=0) at lowlevellock.c:52
52      in lowlevellock.c
1
2
3
4
5
6
7
8

死锁产生的必要条件

• 下述引自维基百科

死锁的四个条件是：

1. 禁止抢占（no preemption）：系统资源不能被强制从一个进程中剥夺。
2. 持有和等待（hold and wait）：一个进程可以在等待时持有系统资源。
3. 互斥（mutual exclusion）：资源只能同时分配给一个进程，无法多个进程共享。
4. 循环等待（circular waiting）：一系列进程互相持有其他进程所需要的资源。

• 下述源自牛客：
  虽然进程在运行过程中，可能发生死锁，但死锁的发生也必须具备一定的条件，死锁的发生必须具备以下四个必要条件：

1. 互斥条件： 指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，则请求者只能等待，直至占有资源的进程用毕释放；
2. 请求和保持条件：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放；
3. 不剥夺条件： 指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放；
4. 环路等待条件： 指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合 {P0，P1，P2，···，Pn} 中的 P0 正在等待一个 P1 占用的资源；P1 正在等待 P2 占用的资源，……，Pn 正在等待已被 P0 占用的资源。

这四个条件是Coffman首先提出的，所以也称为Coffman条件

死锁产生的原因

由于死锁产生的根本原因是可供多个进程共享的系统资源不足。因此本节将从系统资源说起，进而阐述死锁产生的原因。

系统资源

1. 可抢占资源：某进程获得这类资源后，该资源可以再被系统或其他进程抢占。如内存、CPU等
2. 不可抢占资源：某进程获得这类资源后，该资源不能再被其他进程所抢占，只能在进程使用完毕后由该进程自己释放，否则可能导致进程所做工作的出错或失败。如打印机等。

产生原因

竞争不可抢占性资源

当系统中拥有的不可剥夺资源数量不足以满足多个进程运行所需时，进程会在运行过程中因争夺资源而陷入僵局，如磁带机、打印机等。只有对不可剥夺资源的竞争才可能产生死锁，对可剥夺资源的竞争是不会引起死锁的。
示例：

p1已经打开F1，想去打开F2，p2已经打开F2，想去打开F1，但是F1和F2都是不可抢占的，这时发生死锁。

竞争可消耗资源引起死锁

进程间通信，如果顺序不当，会产生死锁。
示例：

p1发消息m1给p2，p1接收p3的消息m3，p2接收p1的m1，发m2给p3，p3，以此类推，如果进程之间是先发信息的那么可以完成通信，但是如果是先接收信息就会产生死锁。(三角恋就很类似死锁，A爱B，B爱C，C爱A，产生了三个单身狗)

进程推进顺序不当

进程在运行过程中，请求和释放资源的顺序不当，也同样会导致产生进程死锁。
示例：

并发进程 P1、P2分别保持了资源R1、R2，而进程P1申请资源R2，进程P2申请资源R1时，两者都 会因为所需资源被占用而阻塞。

死锁处理

一般来说，处理死锁的方法有以下三种：

• 死锁预防或避免 ：不要让系统进入死锁状态。
• 死锁检测和恢复：检测到死锁时中止进程或抢占一些资源，死锁检测相当简单，但死锁恢复需要中止进程或抢占资源，这两者都不是一个有力的选择。
  • 终止（或撤销）进程，终止（或撤销）系统中的一个或多个死锁进程，直至打破循环环路，使系统从死锁状态解脱出来。
  • 抢占资源，从一个或多个进程中抢占足够数量的资源，分配给死锁进程，以解除死锁状态。
• 完全忽略这个问题：如果死锁一年左右只发生一次，最好让它们发生并在必要时重新启动，而不是招致与死锁预防或检测相关的持续开销和系统性能损失。 这是 Windows 和 UNIX 都采用的方法。

示例：
A： 遵循先到先服务的策略，竞争一个资源的两个进程。
B： 当两个进程同时锁定资源时，就会发生死锁。
C： 死锁可以通过打破锁的对称性来解决。
D： 可以通过打破锁机制的对称性来防止死锁。

死锁预防

死锁预防是对进程涉及资源的活动加以限制，以保证死锁不会发生； 可以通过防止以下四个必需条件中的至少一个来防止死锁：

破坏-互斥

说明

只读文件等共享资源不会导致死锁。不幸的是，某些资源，例如打印机和磁带驱动器，需要由单个进程独占访问，换句话说，就是这些资源根本不能同时访问，只能互斥使用。所以，对于本质上就不可共享的资源破坏互斥条件来预防死锁的方法不太可行
一个文件的写操作需要顺序访问，这种破坏互斥是不可行的，但是对于打印机我们却可以使用一个SPOOLing技术来破坏互斥。

假脱机

• 何谓假脱机（SPOOLing技术）？

SPOOLing系统的主要特点有：提高了 I/O的速度；将独占设备改造为共享设备；实现 了虚拟设备功能。

文档 以计算机的速度存储在队列中，然后以打印机的速度检索和打印。 多个进程可以在不等待的情况下将文档写入假脱机，然后可以执行其他任务，而“假脱机”进程则操作打印机

1. 打印机是独占设备，只允许各个进程串行使用设备；
2. 当多个用户提出输出打印的请求时，系统会答应它们的请求，但是并不会真正把打印机分配给它们，而是有假脱机管理进程为每个进程做两件事：
   • 在磁盘输出井中为进程申请一个空闲磁盘块，之后假脱机管理进程会将进程要打印的数据送入刚申请的空闲磁盘块中。
   • 为用户进程申请一张空白的打印请求表，并将用户的打印请求填入表中（其实就是用来说明用户的打印数据存放位置等信息），再将该表挂到假脱机文件队列上。
3. 当打印机空闲时，输出进程会从文件队列的队头取出一张打印请求表，并根据表中的要求将要打印数据从输出井传送到输出缓冲区，再输出到打印机打印。用这种方式可依次处理完全部地打印任务。
   虽然系统中只有一台打印机，但每个进程提出打印请求时，系统都会为在输出井中为其分配一个存储区（相当于一个逻辑设备），使每个用户进程都觉得自己在独占一台打印机，从而实现对打印机的共享。

• 限制

1. 假脱机只能用于具有关联内存的资源，如打印机。
2. 它也可能导致竞态条件。竞态条件是指两个或多个进程正在访问一个资源，但无法确定最终结果的情况。
3. 它不是一个完全可靠的方法，因为在队列满后，进入的进程将处于等待状态。

破坏-持有和等待

为了防止这种情况，必须防止进程在等待一个或多个其他资源的同时持有一个或多个资源。 有几种可能性：

• 破坏等待： 要求所有进程同时请求所有资源，以便在进程执行开始后不必等待分配资源。 如果一个进程在其执行的早期需要一个资源并且直到很久以后才需要一些其他资源，这可能会浪费系统资源。
• 破坏持有：要求持有资源的进程必须在请求新资源之前释放它们，然后在单个新请求中重新获取释放的资源和新资源。 如果一个进程已经部分完成了使用资源的操作，然后在释放它后未能重新分配它，这可能是一个问题。
• 如果进程需要一个或多个资源，则上述任何一种方法都可能导致饥饿。

饥饿：什么是饥饿?
供给不足是指进程在很长一段时间内无法获得所需的资源，因为资源被分配给了其他进程。它通常发生在基于优先级的调度系统中。

破坏-不剥夺条件（禁止抢占）

在可能的情况下，进程资源分配的抢占可以防止这种死锁情况。

• 如果一个进程在请求新资源时被迫等待，则该进程之前持有的所有其他资源都被隐式释放（可以理解为该进程占用的资源被抢占），并再次发出对所需资源的新请求。一旦拥有了所需的所有资源，进程就可以恢复。

如果一个进程有资源R1、R2和R3，它正在等待资源R4，那么它必须释放R1、R2和R3，并再次发出所有资源的新请求。

• 当资源被请求但不可用时，系统会查看当前有哪些其他进程拥有这些资源 ，并且它们本身被阻塞以等待其他一些资源。 如果找到这样的进程，那么它们的一些资源可能会被抢占并添加到进程正在等待的资源列表中。

如果一个进程P1正在等待某个资源，而另一个进程P2正在持有该资源，并且阻塞在等待其他资源。然后从P2中获取资源并分配给P1。这样，进程P2将被抢占，它将再次请求所需的资源以恢复任务。

这些方法中的任何一种都可能适用于状态易于保存和恢复的资源，例如寄存器和内存，但通常不适用于其他设备，例如打印机和磁带机。

存在的问题：

1. 引起错误

如果一个进程正在写入一个文件，并且在它完全更新该文件之前，它对该进程的访问被撤销，那么该文件将保持不可用且处于不一致的状态。

2. 再次对所有资源提出请求是低效且耗时的
3. 总是被抢占后导致饥饿。

破坏-循环等待

说明

避免循环等待的一种方法是对所有资源进行编号，并要求进程仅以严格的递增（或递减）顺序请求资源。换句话说，为了请求资源 Rj，进程必须首先释放所有的 Ri，使得 i >= j。该方案的一大挑战是确定不同资源的相对顺序

1. 示例1 ：

1. 进程P1,使用资源R1,R2;进程P2，使用资源的顺序为R2,R1；
2. 若采用动态分配有可能形成环路条件，造成死锁。
3. 若采用有序资源分配法，R1的编号为1，R2的编号为2,那么进程P1的申请顺序应为R1,R2，进程P2的申请顺序为R1,R2，这样就破坏了环路条件，避免了死锁。

2. 示例2

如果 P1 进程分配了 R5 资源，现在如果 P1 请求 R4，R3 小于 R5 的请求将不被批准，只有超过 R5 的资源请求才会被批准。

缺点

1. 进程实际使用资源的顺序不一定与编号顺序一致，可能会造成浪费。
2. 难找到最优的资源编号方法。

媒体播放器会给打印机较低的优先级，而文档处理器可能会给它较高的优先级。根据情况和用例，资源的优先级是不同的。

3. 资源的编号必须相对稳定，当系统添加新种类设备后处理起来比较麻烦；
4. 严格的资源分配顺序使用户编程的自主性受到限制

死锁避免

死锁预防是静态的，而死锁避免则是动态的，即动态检查进程对资源的申请是否会造成死锁。

安全状态方法

说明

安全状态：当进程请求可用资源时，系统必须决定立即分配是否使系统处于安全状态。 如果存在所有进程的安全序列，则系统处于安全状态。
**不安全状态：**操作系统的所有调度方案都无法使所有进程能够在有限时间内得到所需的全部资源

1. 如果系统能够分配所有进程请求的所有资源(直到它们指定的最大资源)，而不进入死锁状态，则这种状态是安全的。
2. 更正式地说，如果存在 安全的进程序列 { P0, P1, P2, …, PN }，则状态是安全的，这样对 Pi 的所有资源请求都可以使用当前分配给 Pi 和所有进程的资源来授予Pj 其中 j < i。 （即，如果 Pi 之前的所有进程都完成并释放了它们的资源，那么 Pi 也将能够使用它们释放的资源完成。）
3. 如果不存在安全序列，则系统处于不安全状态，这 可能导致死锁。（所有安全状态都是无死锁的，但并非所有不安全状态都会导致死锁。）
   示例
   例如，考虑一个具有 12 个磁带驱动器的系统，分配如下。 这是一个安全的状态吗？ 什么是安全顺序？

由上可知，12个资源现在用了9个还剩3个，系统只要按照安全序列p1 p2 p0分配资源，则每个进程都能顺利完成,此时系统便进入安全状态,否则进入不安全状态。若还不明了，点此看看
注：安全状态方法的关键是，当请求资源时，只有在结果分配状态是安全的情况下才会批准该请求。

银行家算法

何为银行家算法

在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。

用在操作系统中，银行家、出借资金、客户，就分别对应操作系统、资源、申请资源的进程。

每一个新进程进入系统时，必须声明需要每种资源的最大数目，其数目不能超过系统所拥有的的资源总量。当进程请求一组资源时，系统必须首先确定是否有足够的资源分配给该进程，若有，再进一步计算在将这些资源分配给进程后，是否会使系统处于不安全状态如果不会才将资源分配给它，否则让进程等待。

关键数据结构

• 系统可用资源向量 Available[m] ： 表示每种类型当前有多少资源可用。
• 最大需求矩阵Max[n][m]： 表示每个进程对每个资源的最大需求（定义了系统中所有 n 个进程对 m 类资源的最大需求量）。
• 分配矩阵Allocation[n][m] ：表示分配给每个进程的各个资源类别的数量（表示系统中的所有 n 个进程当前已获得各
  类资源的数量）。
• 需求矩阵Need[n][m] ：表示每个进程需要的每种类型的剩余资源（表示系统中的所有 n 个进程当前还需要各类资
  源的数量）。
• 请求向量Request[m]：若 Request[j]=k，则表示当前运行进程 i 正请求 k 个第j类资源。

注： n是进程的数量，m是资源类别的数量

算法

当进程 i 向系统提出 k 个 j 类资源请求时，系统按下述步骤进行检查。
（ 1）若 Request[j]≤Need[i][j]，转步骤（ 2）；否则认为出错，因为进程i申请的 j 类资源已经超出它宣称的最大资源请求。
（ 2）若 Request[j]≤Available[j]，转步骤（ 3）；否则表示当前可供使用的 j 类资源无法满足本次k个数量的申请，进程i阻塞。
（ 3）系统进行试探性分配，并暂时修改下面数据结构中的数值（该修改既可以恢复为修改前的数值，也可变为正式修改）。

• Available[j] = Available[j]－ Request[j] (j=1,2,…,m)
• Allocation[i][j] = Allocation[i][j]+Request[j] (j=1,2,…,m)
• Need[i][j] = Need[i][j]－Request[j] (j=1,2,…,m)

（ 4）调用“判断当前状态是否安全”子算法，判断试探性分配后系统是否处于安全状态。若安全，则正式将资源分配给进程i（暂时修改变为正式修改）；若不安全，则拒绝此次资源分配，即恢复到修改前的资源状态并使进程i阻塞。

“判断当前状态是否安全”子算法

为了实现“判断当前状态是否安全”子算法，需要设置以下两个数组。
（ 1）向量 Work。一个具有m个数组元素的一维数组，代表在检测过程中的某个时刻每类资源空闲的数量。 Work 的初始值等于 Available。
（ 2）向量 Finish。一个具有n个数组元素的一维数组， Finish[i]（ i=1,2,…,n）代表进程i 是否能得到足够的资源而运行结束。若 Finish[i]为 true，则表示进程 i 可以运行结束。刚开始进行检查时， Finish[i] = false，若有足够资源分配给进程 i，再置 Finish[i] = true。“判断当前状态是否安全”子算法描述如下。
（ 1）初始化 Work 和 Finish 向量。

Work[j]＝ Available[j] (j=1,2,…,m)
Finish[i]＝ false (i=1,2,…,n)
1
2

（ 2）在进程集合中尝试寻找一个能满足以下条件的进程 h。

Finish[h] = false
Need[h][j]≤Work[j] (j=1,2,…,m)
1
2

若找到则转步骤（ 3），否则转步骤（ 4）。
（ 3）由于步骤（ 2）找到的进程h其全部资源需求均可满足，因此进程 h 获得资源后可顺利运行完毕，然后释放它所占有的全部资源，故应执行。

Work[j] = Work[j]+Allocation[h][j] (j=1,2,…,m)
Finish[h] = true
1
2

然后转回到步骤（ 2）。
（ 4）如果对所有的进程 i（ i=1,2,…,n）， Finish[i]值均为 true，则表示系统处于安全状态；否则系统处于不安全状态。

示例

#include <iostream>
using namespace std;

// 进程数
const int P = 5;

// 资源数
const int R = 3;

// 查找每个进程需要的资源
void calculateNeed(int need[P][R], int maxm[P][R],
				   int allot[P][R])
{
	// 计算每个进程P所需的资源
	for (int i = 0; i < P; i++)
		for (int j = 0; j < R; j++)

			// 需求 = maxm  - allocated 
			need[i][j] = maxm[i][j] - allot[i][j];
}

// 检查系统是否处于安全状态
bool isSafe(int processes[], int avail[], int maxm[][R],
			int allot[][R])
{
	int need[P][R];

	// 计算 need 矩阵
	calculateNeed(need, maxm, allot);

	// 标记所有的进程的finish序列为未完成 
	bool finish[P] = {0};

	// 安全队列缓存
	int safeSeq[P];

	// 做一个可用资源的拷贝
	int work[R];
	for (int i = 0; i < R; i++)
		work[i] = avail[i];

	// 当所有进程未完成或系统未处于安全状态时。
	int count = 0;
	while (count < P)
	{
		// Find a process which is not finish and whose needs can be satisfied with current work[] resources.

		bool found = false;
		for (int p = 0; p < P; p++)
		{
			// 首先检查一个进程是否完成，
			// 若无，进入下一个判断
			if (finish[p] == 0)
			{
                // 检查当前进程P所需的所有资源是否少于work 
				int j;
				for (j = 0; j < R; j++)
					if (need[p][j] > work[j])
						break;

				// 进程P需要的所有资源均满足
				if (j == R)
				{
					// Add the allocated resources of current P to the available/work resources i.e.free the resources
                    //将当前进程P的已分配资源添加到可用/工作资源中，即释放资源
					for (int k = 0; k < R; k++)
						work[k] += allot[p][k];

					// 将此进程添加到安全序列中
					safeSeq[count++] = p;

					// 把这个进程p标记为已完成
					finish[p] = 1;

					found = true;
				}
			}
		}

		// 如果我们不能以安全的顺序找到下一个进程。
		if (found == false)
		{
			cout << "系统处于不安全状态";
			return false;
		}
	}

	// 如果系统处于安全状态，则安全顺序如下
	cout << "系统处于安全状态\n安全序列为: ";
	for (int i = 0; i < P; i++)
		cout << safeSeq[i] << " ";

	return true;
}

int main()
{
	int processes[] = {0, 1, 2, 3, 4};

	// 可用的资源实例
	int avail[] = {3, 3, 2};

	// 可分配给进程的最大资源R
	int maxm[][R] = {{7, 5, 3},
					 {3, 2, 2},
					 {9, 0, 2},
					 {2, 2, 2},
					 {4, 3, 3}};

	// 分配给进程的资源
	int allot[][R] = {{0, 1, 0},
					  {2, 0, 0},
					  {3, 0, 2},
					  {2, 1, 1},
					  {0, 0, 2}};

	// 检查系统是否处于安全状态
	isSafe(processes, avail, maxm, allot);

	system("pause");
	return 0;
}

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
116
117
118
119
120
121
122
123

运行结果

系统处于安全状态
安全序列为: 1 3 4 0 2 
1
2

死锁预防与死锁避免的区别

死锁检测与恢复

死锁检测

数据结构

对于有 m 类资源和 n 个进程的系统，其定义的数据结构有以下三种表示方式。
（ 1）系统可用资源向量 Available。一个具有 m 个数组元素的一维数组，每个数组元素代表一类资源当前可用的数量，初始值为系统中该类资源的总量。
（ 2）分配矩阵 Allocation。一个 n×m 矩阵，表示系统中的所有进程当前已获得的各类资源数量。
（ 3）请求矩阵 Request。一个 n×m 矩阵（与银行家算法中的 Request 不同，银行家算法中的 Request 为向量 1×m，仅表示当前运行进程的 Request），表示 n 个进程在执行中还需要请求的各类资源数量

算法

死锁检测算法如下。
（ 1）对 Allocation 矩阵中出现一行全为 0 的进程进行标记。
（ 2）初始化一个拥有 m 个数组元素的一维数组 Work（临时向量），并用 Available 向量对其进行初始化，即
Work[j] = Available[j] (j=1,2,…,m)
（ 3）在 Request 矩阵中寻找一个未被标记进程 i，且 Request 矩阵第 i 行对应位置的 m个元素值都小于或等于 Work 向量其对应位置上的元素值（即意味着进程 i 可获得所需要的全部资源，即能顺利执行到结束），即满足Request[i][j]≤Work[j] (j=1,2,…,m)
如果找到这样的 i 则转（ 4）；否则，则终止死锁检测算法。
（ 4）执行。Work[j] = Work[j]+Request[i][j] (j=1,2,…,m) 对进程 i（进程 i 运行结束收回为其分配的资源）进行标记后转步骤（ 3）。
该算法执行结束时，系统中如果存在未被标记的进程，则表示系统发生了死锁，未被标记的进程即为死锁进程。

死锁恢复

示例：
两个进程以相反的顺序竞争两个资源。
A：一个进程单独运行占用资源
B：一个进程占用资源时后面的进程必须等待。
C：当第一个进程在第二个进程锁定第二个资源的同时锁定第一个资源时，就会发生死锁。
D：死锁可以通过取消并重新启动第一个进程来解决。

示例

四个进程(蓝线)按照从右到左的策略争夺一个资源(灰圈)。当所有进程同时锁定资源时，就会发生死锁(黑线)。这种僵局可以通过打破对称性来解决。

相关题目

题目1.

死锁检测时检查的是（）

A. 资源有向图

B. 前驱图

C. 搜索树

D. 安全图

解析：死锁检测是在资源分配图中进行检测，资源分配图也就是资源有向图。

题目2.

系统的资源分配图在下列情况下，无法判断是否处于死锁状态的有（）

I. 出现了环路

II. 没有环路

III. 每个资源只有一个，并出现环路

IV. 每个进程节点至少有一条请求边

A. I，II，III，IV

B. I，III，IV

C. I，IV

D. 以上答案都不正确

解析：

I：出现了环路，只是满足了循环等待的必要条件，但是并不能保证一定出现死锁。

II：没有环路，说明破坏了循环等待条件，所以一定不会发生死锁。

III：每种资源只有一个，又出现了环路，这是死锁的充分必要条件，所以，一定会有死锁的出现。

IV：每个进程至少有一条请求边的时候，如果资源充足，则不会发生死锁，但若资源不充足，就有发生死锁的可能。故只有I，IV可以确定是否产生死锁

题目3.

下列关于死锁的叙述中，正确的是（）

I. 可以通过剥夺进程资源解除死锁

II. 死锁的预防方法能保证系统不发生死锁

III. 银行家算法可以判断系统是否处于死锁状态

IV. 当系统出现死锁时，必然有两个或两个以上的进程处于阻塞态

A. 仅II，III

B. 仅I，II，IV

C. 仅I，II，III

D. 仅I，III，IV

解析：在之前将的死锁解除的方法中有介绍可以通过剥夺进程资源解除死锁，故I正确。死锁预防，破坏的是死锁产生的4个必要条件之一，可以确保系统不发生死锁。银行家算法是一种死锁避免算法，判断系统是否处于死锁状态得用死锁定理。IV，死锁是由于资源进程造成得僵局，竞争就说明了至少有两个或以上的进程进行。所以IV正确。

参考文献

[参考1] 死锁产生的原因以及解决方法
[参考2] 使用gdb调试死锁线程
[参考3] 详解操作系统之银行家算法
[参考4] 《操作系统概念》
[参考5] 维基百科：银行家算法