同步互斥与死锁
# 同步互斥和锁
# 同步互斥机制与锁
并发是操作系统的基本特征,引入进程/线程使多道程序可以并发,同时带来很复杂的运行环境,各进程之间既同步(合作实现作业),又互斥(资源占用),为了保证多个进程有条不紊工作,引入同步机制
各种进程之间相互制约,使并发执行的诸进程能够有效的共享资源和相互合作
- 直接制约:由进程合作引起
- 间接制约:由资源共享引起
互斥和同步是协调进程执行顺序的常见方式,均属于低级通信,设计数据量极少,特点是效率低;对用户不透明
一些概念名词
- 临界资源:一次仅允许一个进程访问的资源,如打印机、公共变量(全局变量),需要互斥访问
- 临界区:一段代码,访问临界资源的代码段。进入临界区需要加锁,出临界区解锁
- 互斥:A 访问,其余不能访问
- 同步:必须等 A、C 执行完毕后,B 才能开始执行
- 同步机制:实现进程同步/互斥的方法
同步机制的准则
- 空闲让进:临界区无进程,允许一个请求者执行临界区代码
- 忙则等待:临界区有进程,其余欲进入者需等待
- 有限等待:等待进入临界区的进程,其等待时间必须有限,避免饥饿
- 让权等待:进程无法进入临界区,应立即释放处理机资源
锁是一种同步机制,限制任意时刻只有一个进程进入临界区
- 解锁:锁变量设置为开启状态
- 加锁:读取内存锁变量的值,已加锁返回失败信息,未加锁上锁后返回成功信息
锁的操作控制不当,可能导致多个进程均加锁成功
- 单核状态下,并发进程,进程一读取内存锁变量后,发生中断,进程二也读取内存锁变量,均读到开锁,同时进入临界区
- 多核状态下,并行执行,同时读取同一个锁变量,同时修改锁变量为上锁状态,均返回成功
锁类型
- 互斥锁:最基本的同步方式,用于保护临界区,保证任何时刻仅有一个进程执行临界区代码,各进程串行进入临界区,效率低
- 乐观锁:读直接进行,写前判断锁状态
- 悲观锁:操作数据就上锁
# 硬件的同步互斥
中断:最简单的硬件方法,中断时直接打断原进程,直到中断结束的同步步骤
- 滥关中断可能导致严重后果
- 长时间关中断限制处理器交叉执行程序的能力
- 多核 CPU 下,在一个处理器上关中断,并不能防止其他处理器访问临界资源
TS 指令:借助硬件测试实现互斥
int TS(int *lock){
int old = *lock;
*lock = true; // 令临界资源 lock 为 true,上锁
return old; // 返回上一个 lock 状态
}
2
3
4
5
为每个临界资源设置布尔变量 lock,初值为 false,表示空闲
do{
while(TS(&lock)) {} // 测试,当 lock 为 true,死循环等待
critical section; // 临界区
lock = false; // 解锁
}while(true);
2
3
4
5
等待期间不断测试,始终占用 CPU,不满足让权等待的同步准则
swap 指令:对换指令,交换两个 lock 和 key 布尔值的内容,lock 是表示临界资源是否被占用的全局变量,key 为 true
void swap(int *lock, int *key){
int t = *key;
*lock = *key;
*key = t;
}
2
3
4
5
只有当 key 的值被交换成 false,才能进入临界区
do{
key = true;
do{
swap(&lock, &key);
}while(key != false); // 只有当 lock 的值为 false,交换到 key 时,key 为 false,退出 while 循环
critical section; // 临界区
lock = false; // 解锁
}while(true);
2
3
4
5
6
7
8
TS 和 SWAP 的缺点:若临界资源繁忙,其余欲访问的临界区进程只能不断测试,处于忙等状态,白白占用 CPU 资源,且无法处理复杂的同步问题
# 软件的同步互斥
一定要会推导并发进程的执行过程,发现同步问题
1、单标志:适用一个全局变量 flag 标记一个临界资源,只有 flag 满足当前进程的规定,才能进入临界区,否则等待
int flag = 1;
//进程 p1
void p1(){
do{
while(flag != 1){
critical section;
flag = 2;
}
}while(1);
}
//进程p2
void p2(){
do{
while(flag != 2) {}
critical section;
flag = 1;
}while(1);
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
只有当进程 p1 执行完毕后,将 flag 赋值为 2,进程 p2 才能进入临界区;同理,只有当 p2 结束后,将 flag 赋值为 1,p1 才能进入临界区
- 不符合空闲让进(资源空闲,应接受任何一个请求)的规则:若 p1 不执行,即使资源空闲,p2 也不能进入临界区
2、多标志、先测试:适用一组全局标记对临界资源上锁,每个标记对应一个进程,只有当所有标记均为 false 时,当前进程才能进入临界区
bool flags[] = {false, false};
//进程 p0
void p0(){
while(flags[1]){} // 测试进程p1是否占用临界资源
flags[0] = true; // 上锁
critical section;
flags[0] = false; // 解锁
}
//进程 p1
void p1(){
while(flags[0]){} // 测试进程p0是否占用临界资源
flags[1] = true; // 上锁
critical section;
flags[1] = false; // 解锁
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
如果 p0、p1 并发执行,若执行while(flags[0])后,下一条指令为while(flags[1]),在 p0 中尚未上锁,p1 将测试成功,进程 p0、p1 就会同时进入临界区,违反忙则等待(只能同时一个进程进入同一个资源临界区,其余等待)准则
3、多标志、后测试
bool flags[] = {false, false};
//进程 p0
void p0(){
flags[0] = true; // 先上锁
while(flags[1]){} // 测试进程p1是否占用临界资源
critical section;
flags[0] = false; // 解锁
}
//进程 p1
void p1(){
flags[1] = true; // 先上锁
while(flags[0]){} // 测试进程p0是否占用临界资源
critical section;
flags[1] = false; // 解锁
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
若 p0、p1 并发执行,连续上锁,则会出现死锁,且实际上临界资源并未被占用,违反了空闲让进和有限等待(等待时间必须有限)准则
4、Peterson 算法:在多标志、后测试的基础上再加入一个单标志 turn,当 pi 进程欲进入临界区时,令flags[i] = true; turn = j,其中 i 不等于 j,等待条件为while(flags[j] && turn==j)
bool flags[] = {false, false};
int turn = 0;
//进程 p0
void p0(){
flags[0] = true, turn = 1;; // 当前进程上锁
while(flags[1] && turn == 1){} // 测试进程p1是否占用临界资源
critical section;
flags[0] = false; // 解锁
}
//进程 p1
void p1(){
flags[1] = true, turn = 0;; // 当前进程上锁
// 测试进程p0是否占用临界资源
// 测试并发执行时,turn = 0 和等待语句
while(flags[0] && turn == 0){}
critical section;
flags[1] = false; // 解锁
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
先上锁的进程一定会先进入临界区
# 信号量机制与管程
信号量(semaphore)是常用且有效的同步机制,由“信号量”和“PV操作”两部分组成,用于解决 n 个进程的临界区互斥使用、进程同步、实现前驱关系等
# 信号量
信号量分类
- 整型信号量:表示可用资源数量,除初始化之外,仅能通过以下两个原子操作读写
- 记录型信号量:例如由一个整型变量 value 和一个进程链表 L 构成,当value 大于 0,表示资源有 value 个;小于 0,说明阻塞队列中有 -value 个进程
- AND 型信号量:可以处理多个并发进程共享多个临界资源的情况
- 信号量集:原子操作中对 S 的加减,一次可以进行多个数量,既表示一次加减资源的数量,也表示多种资源
P/V 操作:wait(S),对信号量进行减一操作
void wait(semaphore S){
while(s <= 0){}
S = S-1;
}
2
3
4
V 操作:signal(S),对信号量进行加一操作
void(semaphore S){
S = S+1;
}
2
3
- wait 操作可能导致忙等;不遵循“让权等待”准则
- 让权等待:当进程无法进入临界区时,主动释放资源,放弃进入
信号量应用:为临界资源设置互斥信号量
semaphore mutex = 1;
void P(semaphore S){
while(1){
// 互斥,则自我阻塞,等待
wait(mutex);
critical section; //临界区
signal(mutex);
}
}
2
3
4
5
6
7
8
9
实现进程同步:设 P1,P2并发执行,P1 消费 A,产生 B,P2 消费 B,产生 A
int A = 0, B = n;
void P1(){
wait(A);
make_b();
signal(B);
}
void P2(){
wait(B);
make_a();
signal(A);
}
2
3
4
5
6
7
8
9
10
11
12
实现前驱关系:设 P1、P2 种有语句 S2、S2,希望在执行 S1 后再执行 S2
semaphore S = 0;
void P1(){
S1();
signal(S);
}
void P2(){
wait(S);
S2();
}
void main(){
P1();
P2();
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 管程
信号量机制是一种方便有效的同步机制,但存在不便之处
- 同步操作分散:同步操作分散于各个进程,各个进程使用自己独立的信号量
- 易读性差:是否正确需要分析整个系统或并发程序
为使同步机制更有效,采用封装的面向对象思想,用共享数据结构表示共享资源
管程:将信号量及其操作原语封装在一个对象内部,一个管程定义了一个数据结构和并发进程在该数据结构上执行的一组操作(包括同步机制)
- 其实就相当于一个 JAVA 类,内部需要共享的资源使用 synchronized 修饰的函数对外提供接口,或使用 ReentrantLock 锁对各函数/资源进行相互制约,实现同步
管程属于 OS 内核的资源管理程序,被请求和释放资源的程序所调用,每次仅允许一个进程进入管程,执行管程内的过程,从而实现进程互斥
一个管程由以下几部分组成
- 管程名称
- 管程内的共享数据
- 一组操作过程
- 共享数据的初始化语句
管程特点:进程对系统资源的使用通过管程间接进行
- 模块化:可单独编译
- 抽象化:既包含数据,也 包含过程
- 隐蔽性:数据只能由管程的过程访问,但过程可以由外部进程调用;管程内的数据和过程对外部透明
管程和进程的对比
| 管程 | 进程 |
|---|---|
| 公共数据结构,如消息队列 | 私有数据结构 PCB |
| 主要为同步操作和初始化操作 | 由顺序执行程序执行有关操作 |
| 主要解决共享资源的互斥使用 | 主要实现系统的并发性 |
| 被动工作 | 通过调用管程中的函数对共享数据结构实施操作,为主动工作方式 |
| 管程不能与其调用者并发执行 | 进程间能并发执行 |
| 操作系统的一个资源管理模块,以供进程调用 | 具有动态性,存在生命周期 |
# 条件变量
实现进程同步必须设置同步工具,如 wait() 和 signal(),即 PV 操作,在管程中,同样如此
并且由于管程封装了不止一种系统资源,当其中一种被某一进程占用,若不采用任何处理,使用管程中其他临界资源的进程将被拦在管程外,造成浪费
于是我们在管程内部维护一系列条件变量,每个条件变量有自己单独的一套 wait() / signal() 操作,外部进程发起请求时,找到到某个具体的临界资源,如 x,调用 x.wait() / x.signal() 对其进行同步,而 x 的 PV 操作对另一临界资源 y 不产生影响,如此在管程中封装并分隔不同的临界资源
# 经典同步问题
多道程序环境下,进程同步引起的一些列问题,常考大题
# 生产消费者问题
资源有限,对资源生产消耗的同步互斥,买卖同步问题
生产者和消费者
- 输入时:输入进程是生产者,计算进程是消费者
- 输出时:计算进程是生产者,输出进程是消费者
假设和信号量设置
- 假设:生产者 - 消费者共享有 n 个缓冲区的公共缓冲池
- 信号量设置:互斥信号量,设置 mutex 信号量用于公共缓冲池的互斥使用;同步信号量,设置 empty 表示空缓冲区个数;full 表示已占用缓冲区个数
记录型信号量:结构体的记录形式,注意 wait() 的顺序不能颠倒,必须先同步,再互斥,先检查是否有资源,再占用访问权。如果先占用了访问权,但没有资源,就会忙等,白白占用访问权,不管其余进程是否有资源,都无法消费,有可能导致死锁
int in = 0, out = 0; // 公共变量,生产和消费 下一个 产品的存放的下标
message buffer[n], inM, outM; // 产品缓冲池、生产出的产品、使用掉的产品
semaphore mutex = 1, empty = n, full = 0; // 控制信息:互斥信号量和同步信号量
// 生产者
void procedurer(){
do{
inM = produce_message(); // 生产一个产品并赋值给 inM
wait(empty); // empty>0 表示有空池
wait(mutex); // mutex>0 表示有访权
buffer[in] = inM; // 往缓冲池下标为 in 的位置加入产品 inM
in = (in+1) % n; // 更新下标位置
signal(mutex); // 释放控制权
signal(full); // 令已占用缓冲区 +1
}while(1);
}
void consumer(){
do{
wait(full); // full > 0 才可以取消息
wait(mutex); // 检查访问权
outM = buffer[out];
out = (out+1) % n; // n 为缓冲池大小
signal(mutex); // 释放访问权
signal(empty); // 空缓冲 +1
consume_message(outM); // 消费产品 outM
}while(1);
}
void main(){
procedurer();
consumer();
}
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
信号量集:使用 AND 信号量解决问题 —— AND 信号量可以一次处理多个并发进程共享多个临界资源的情况
- Swait(empty, mutex) 代替 wait(empty) 和 wait(mutex),Swait(full, mutex) 代替 wait(full) 和 wait(mutex)
- Ssignal(empty, mutex) 代替 signal(empty) 和 signal(mutex),Ssignal(full, mutex) 代替 signal(full) 和 signal(mutex)
int in = 0, out = 0; // 公共变量,生产和消费 下一个 产品的存放的下标
message buffer[n], inM, outM; // 产品缓冲池、生产出的产品、使用掉的产品
semaphore mutex = 1, empty = n, full = 0; // 控制信息:互斥信号量和同步信号量
// 生产者
void procedurer(){
do{
inM = produce_message(); // 生产一个产品并赋值给 inM
Swait(full, mutex) // 检查缓冲池是否满,是否有访权
buffer[in] = inM; // 往缓冲池下标为 in 的位置加入产品 inM
in = (in+1) % n; // 更新下标位置
Ssignal(full, mutex) // 已占有+1,释放访权
}while(1);
}
void consumer(){
do{
Swait(empty, mutex) // 检查缓冲池是否空,是否有访权
outM = buffer[out];
out = (out+1) % n; // n 为缓冲池大小
Swait(empty, mutex) // 消费一个产品-1,释放访权
consume_message(outM); // 消费产品 outM
}while(1);
}
void main(){
procedurer();
consumer();
}
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
就是把wait(full/empty)和wait(mutex)访权封装了一下,同理封装了signal(full/empty)和signal(mutex);但注意这里封装之后,是先判断再阻塞,即先判断full/empty以及mutex之后,选择性进入while循环等待
管程:建立名为 PC 的管程,包含 put 和 get 两个进程用于存取产品,用 count 记录缓冲池中产品数量,用条件变量 condition 记录当前缓冲池的状态(满、空),当调用 Cwait() 阻塞后,进入 condition 的阻塞队列,Csignal() 可唤醒由 Cwait() 阻塞的进程(阻塞队列为空则不用唤醒)
class PC{
private:
int in = 0, out = 0, count = 0;
message buffer[n], inM, outM;
condition notFull, notEmpty;
semaphore mutex = 1, empty = n, full = 0;
public:
void put(message m){
if(count >= n){ // 当缓冲池已占用已满,n 为缓冲池大小
Cwait(notFull); // 等待不满
}
buffer[in] = M;
in = (in+1) % n;
count++;
Csignal(notEmpty); // 放入了一个产品,缓冲池不为空,主动唤醒 Cwait(notEmpty)
}
void get(message m){
if(count <= 0){
Cwait(notEmpty);
}
m = buffer[out];
out = (out+1) % n;
count--;
Csignal(notFull); // 消费了一个产品,缓冲池不满,唤醒 Cwait(notFull)
}
};
void producer(){
message inM;
do{
inM = produce_message();
PC.put(inM);
}while(1);
}
void consumer(){
message outM;
do{
PC.get(outM);
// 消费产品 outM
}while(1);
}
void main(){
producer();
consumer();
}
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
# 哲学家进餐问题
资源固定,对资源使用权的同步互斥
五个哲学家共用一张圆桌,左右手各一只筷子,吃饭时需要左右手各拿一只筷子,思考时放下筷子,筷子的数量是有限的,共 5 根,不能满足所有哲学家共同进餐,需要互斥限制
信号量设置
semaphore chopStick[5] = {1,1,1,1,1};
void philosopher_i(){
do{
wait(chopStick[i]); // 等待左手边筷子并获取使用权,chopStick[i] 由 1变为 0
wait(chopStick[(i+1)%5]); // 右手边筷子
// eat
signal(chopStick[i]); // 归还筷子
signal(chopStick[(i+1)%5]);
// think
}while(1);
}
void main(){
philosopher_1();
philosopher_2();
philosopher_3();
philosopher_4();
philosopher_5();
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
思考这样一个情况,当五个进程并发(五个哲学家同时在餐桌上),按顺序执行五条命令,均为占用左手边筷子,均会成功,但都会卡在占用右手边筷子的语句,产生死锁
解决办法一:最多只允许 4 位哲学家同时拿左边筷子,对“左手边筷子数量”设置互斥
semaphore chopStick[5] = {1,1,1,1,1}, maxNum = 4;
void philosopher_i(){
do{
wait(maxNum); // 检查是否有 4 位哲学家拿起了左手筷子
wait(chopStick[i]); // 等待左手边筷子并获取使用权,chopStick[i] 由 1变为 0
wait(chopStick[(i+1)%5]); // 右手边筷子
// eat
signal(chopStick[i]); // 归还筷子
signal(chopStick[(i+1)%5]);
signal(maxNum);
// think
}while(1);
}
void main(){
philosopher_1();
philosopher_2();
philosopher_3();
philosopher_4();
philosopher_5();
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
解决办法二:奇数个哲学家拿左手边筷子,偶数个哲学家拿右手边筷子
semaphore chopStick[5] = {1,1,1,1,1};
void philosopher_i(){
do{
if(i % 2 == 0){
wait(chopStick[(i+1)%5]); // 先拿右手筷子
wait(chopStick[i]); // 再拿左手筷子
} else {
wait(chopStick[i]); // 先拿左手筷子
wait(chopStick[(i+1)%5]); // 再拿右手筷子
}
// eat
signal(chopStick[i]); // 归还筷子
signal(chopStick[(i+1)%5]);
// think
}while(1);
}
void main(){
philosopher_1();
philosopher_2();
philosopher_3();
philosopher_4();
philosopher_5();
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 读者写者问题
共用存储区资源,对内容读写的同步互斥
用信号量实现对共用存储区读写的同步互斥
- 写时不能再写,且不能读
- 读时不能写,但可再读
int readCount = 0; // 记录当前读者数量
semaphore rMutex = 1, wMutex = 1; // 读写信号量
// 读者
void reader(){
do{
wait(rMutex); // 拿取进入权限,避免 readCount 的加一操作混乱
// 如果是第一个读者,要剥夺写权限,若剥夺不了,就等待
// 如果不是第一个读者,说明有读者在进行读操作,自然不用判断是否有人在写(肯定有人在读)
if(readCount == 0){
wait(wMutex);
}
readCount++;
signal(rMutex); // 归还进入权限,允许其他读者进入
// ... read ... //
wait(rMutex); // 拿取退出权限
readCount--;
signal(rMutex); // 归还退出权限
// 当 readCount == 0,说明没有读者,唤醒写进程,若无请求则不操作
if(readCount == 0){
signal(wMutex);
}
}while(1);
}
void writer(){
do{
wait(wMutex); // 拿取写权限
// ... write ... //
signal(wMutex); // 归还写权限
}while(1);
}
void main(){
reader();
writer();
}
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
为什么明明可以多个进程同时“读”,reader 在最开始和最后还得判断一次 rMutex?因为“读”和“进出”不是一个概念,同一时刻(并行)只允许一个进程“进出”读区域,进入之后立马将“进入”权限返回,开始“读”,此时另一个读进程就可以拿取进入权限也开始“读”,rMutex 实际上是”进出“读临界区的信号量
为什么要这么做?因为在进出时要对 readCount 进行 +1 / -1 操作,这一操作并没有原子性,必须要加一层锁,防止 readCount 因为多进程并发产生混乱
这样会有一个问题,就是这种模式下,读优先,写操作处于绝对的弱势 —— 即使当前读操作完毕,写也不一定能执行,因为这里必须完成一批读操作,直到 readCount == 0 时才会归还写权限
解决办法:增加一个公共信号量 mutex,真有区别吗但是?
int readCount = 0;
semaphore rMutex = 1, wMutex = 1, mutex = 1;
// 读者
void reader(){
do{
wait(mutex); // 拿取公共权限
wait(rMutex); // 拿取读进入权限
if(readCount == 0){
wait(wMutex); // 剥夺写权限
}
readCount++;
signal(rMutex); // 归还读进入权限
signal(mutex); // 归还公共权限
// ... read ... //
wait(rMutex); // 拿取读退出权限
readCount--;
signal(rMutex); // 归还读退出权限
if(readCount == 0){
signal(wMutex); // 唤醒写权限
}
}while(1);
}
void writer(){
do{
wait(mutex); // 拿取公共权限
wait(wMutex); // 拿取写权限
// ... write ... //
signal(wMutex); // 归还写权限
signal(mutex); // 归还公共权限
}while(1);
}
void main(){
reader();
writer();
}
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
栗题:一个生产者,两个消费者,生产者负责生产整数,消费者一消费奇数,消费者二消费偶数,利用信号量机制实现 3 个进程的同步与互斥,并用 countOdd() 和 countEven() 函数记录消费的奇偶数个数
- odd:奇数个数
- even:偶数个数
- empty:空缓冲区个数
- mutex:访问权限信号量
semaphore mutex = 1, empty = n, odd = 0, even = 0; // 缓冲区最大值为 n
void P1(){
do{
wait(empty); // 检查是否有空缓冲区
wait(mutex); // 拿取访问权限
int x = produce();
put(x); // 将 x 放入缓冲区
// 增加奇偶数信号量
if(x % 2 == 0){
signal(even);
} else {
signal(odd);
}
signal(mutex);
}while(1);
}
void P2(){
do{
wait(odd);
wait(mutex);
getOdd(); // 从缓冲区拿取奇数
signal(empty); // 空缓冲 +1
signal(mutex); // 归还控制权
countOdd();
}while(1);
}
void P3(){
do{
wait(even);
wait(mutex);
getEven(); // 从缓冲区拿取奇数
signal(empty); // 空缓冲 +1
signal(mutex); // 归还控制权
countEven();
}while(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
这里的缓冲区可以设计为一个二维数组,其中buffer[i][0]存储数据,buffer[i][1]标记该位是否有数据(是否为空,1 表示非空),缓冲区大小为 n
vector<vector<int>> buffer(n, vector<int>(2));
# 死锁问题
过于忙碌 → 死锁,物极必反
# 死锁和资源分类
资源竞争引发的恶果,多个进程在运行过程中可能因争夺资源出现的一种无外力作用时无法向前推进的僵局,称作死锁
- 比如哲学家同时拿左手筷子,出现僵局(死锁)
资源按照是否可重用,可分为
- 可重用资源:可供用户重复使用的资源,其中每个单元每次只能分配给一个进程,不允许多进程共享;一般来说数量固定,程序无法创建
- 可消耗资源:进程运行期间,可由进程动态创建的资源,如指针
按是否可抢占可分为
- 可抢占资源:进程获得资源后(尚未用完),可被强制回收并分配给其他进程,如 CPU 和内存
- 不可抢占资源:进程获取资源后必须得用完自行释放,如磁带打印机
死锁产生的根本原因是资源不足,具体原因很多,如
- 竞争消耗性资源
- 进程间推进顺序非法
- 竞争不可剥夺资源
- 请求和释放资源的顺序不当
死锁产生的必要条件,解决死锁 = 打破必要条件
- 互斥使用:进程对所分配资源具有排他性
- 请求保持:进程已经保持了至少一个资源,又提出新的资源请求,但进程请求的资源已被占用,进程请求资源阻塞,此时进程保持请求,同时该进程已占用的资源将保持不释放
- 不可抢占:进程已获得的资源必须得自己执行完毕后自行释放
- 循环等待:发生死锁时,必然存在进程-资源循环链
# 死锁预防与避免
死锁的一种解决办法
采取限制措施破坏死锁的一个或多个必要条件
- 互斥使用:不可破坏
- 破坏“请求保持”条件
- 协议一:进程执行过程中不申请资源,初始分配时就分配所有所需资源
- 协议二:进程获取初期所需资源后,开始执行
- 破坏“不可抢占”条件:提出新请求无法得到满足时,释放所有已获得的资源
- 破坏“循环等待”条件:对所有系统资源进行线性排序,进程必须按序号递增顺序申请资源
- 问题一:增加新设备排序很麻烦
- 问题二:申请资源的顺序可能很不合理,造成浪费
死锁避免:银行家算法,在资源动态分配过程中,防止进入“不安全”状态(有可能死锁的状态)
系统安全状态:进程序列顺序调度资源时,系统资源能够最大化满足各进程顺序执行完毕,那么我们称这个进程序列是系统安全的
- 安全状态一定不死锁
- 不安全状态不一定死锁
- 避免死锁的实质是系统进行资源分配时,使系统不进入不安全状态
# 银行家算法
银行家算法:设系统 m 类资源,n 个进程
4 个数据结构
- 可利用资源数组
Available[i]:反映第 i 类可利用资源的数量 - 最大需求矩阵
Max[i][j]:表示第 i 个进程对第 j 类资源的最大需求量 - 分配矩阵
Allocation[i][j]:表示第 i 个进程已经具有第 j 类资源的个数 - 需求矩阵
Need[][]:表示第 i 个进程还需要第 j 类资源的个数
其中Max[i][j] = Need[i][j] + Allocation[i][j]
设Request[i]是第 i 个进程 P 的请求向量,若Request[i][j] = k,则说明进程 i 需要第 j 类资源 k 个,当 P 发出请求后,系统将以以下顺序进行检查
Request[i][j] <= Need[i][j],转下一步,否则出错(请求的不大于需要的)Request[i][j] <= Available[j],转下一步,否则等待(请求的不大于空闲的)- 尝试将资源分配给进程 P,同时修改数据结构数值
Available[j] = Available[j] - Request[i][j]Allocation[i][j] = Allocation[i][j] + Request[i][j]Need[i][j] = Need[i][j] - Request[i][j]
- 安全性检测:若分配后系统处于安全状态,则将资源实际分配给 P;否则取消本次尝试,恢复原来的资源分配状态(恢复数据结构),P 进入等待
# 安全性检测
如何进行安全性检测?判断必须要熟且快,因为分少但流程长
- 设置两个向量
- 工作向量
Work[j]:表示当前进程所需第 j 类资源的数量,初始状态时Work[j] == Available[j] - 结束向量
Finish[i]:表示系统能够提供足够资源以供第 i 个进程顺利运行完毕,初值为 false
- 工作向量
- 从进程集合中找到一个
Finish[]为 false 的变量,假设为 i,判断Need[i][j]是否小于等于Work[j], 0 <= j <= m,若全满足,为其分配资源,更新Work[j], Allocation[i][j], Need[i][j],执行后释放资源,恢复Work[j], Available[j],设置Finish[i] = true - 重复第二步,寻找下一个符合的进程,直到遍历结束,若存在进程 k 使得
Finish[k] = false,说明处于不安全状态,否则处于安全状态
注意这里安全性的判断遵循进程编号的先后顺序,从前往后遍历,每次寻找都从头开始,即完成一个进程后,将其从队列中删除,从头开始遍历寻找下一个进程
栗子
在例题中,我们称 P0、P2、P4 打头不存在安全序列,安全序列只有可能由 P1、P3 打头,且 P1 存在安全序列
# 死锁检测和解除
既不预防,也不避免,让系统自己去运行,运行系统发生死锁。此时,系统在固定的时间周期运行死锁检测算法和死锁解除算法,判断系统是否发生死锁。若发生死锁,用死锁解除算法将系统从死锁状态解脱出来
必须对死锁的发生足够敏感,并精确确定与死锁有关的进程和资源(进程 - 资源循环链),系统必须保存资源的请求和分配信息
# 资源分配图及其简化
资源分配图:描述系统资源的分配和空闲情况,用于检测死锁
- G = ( N, E ),N 为 G 的顶点集合,E 表示 G 的边集合
- 顶点包括所有进程和资源
- 边有向
- 若从资源指向进程,则为进程占用资源,称为占用边
- 若从进程指向资源,则为进程请求资源,称为请求边
如
顶点集N = {P1, P2, R1, R2}
边集E = {<P1, R2>, <R2, P2>, <R1, P1>, <R1, P1>, <R1, P2>, <P2, R1>}
简化资源分配图:利用简化资源分配图可以判断当前系统是否存在死锁
- 找到一个不阻塞且不独立的进程节点 P
- 不阻塞意味着资源能够满足其运行,于是我们释放 P 所有的资源,删除和 P 相关的所有边(请求边和占用边),使其孤立
- 继续考虑其他非孤立节点
- 直到所有顶点均孤立,说明不存在死锁,若不能使所有进程孤立,则发生了死锁,称这个图不可完全简化
# 死锁检测中的数据结构
Available[] / Work[]记录每类资源当前可用量,Allocation[]记录每类资源分配出去的量,Request[]表示某一进程对某类资源的请求量,表 L 记录孤立的进程节点
在死锁检测中
- 寻找
Request[i] <= Work[i], 0<=i<=n的进程 - 将其资源分配图简化,释放资源,
Work[i] += Allocation[i] - 将该进程记入 L 表,重复以上过程
若不能将所有进程记入 L,说明当前系统可能发生死锁
# 死锁解除
死锁接触是与死锁检测相配套的一种措施,在发生死锁时将系统从死锁状态中解脱出来。实施方法为回收部分资源,再将这些资源分配给阻塞态进程使之继续运行
回收资源的方法
- 抢占资源
- 撤销 / 挂起 / 终止进程
- 终止所有死锁的进程
- 逐个终止进程,直到能打破循环停止
付出代价最小的死锁解除算法:原始算法和改进算法
原始算法:就是穷举所有终止情况,暴搜,每轮一个个尝试终止各个进程直到不死锁
vector<vector<process>> drop;
void dfs(condition s, vector<process>& path){
if(deadlock(s)){
// 若死锁,穷举所有当前进程,一个个排除
for(int i = 0; i < s.process.size(); i++){
// 将当前要排除的进程添加到路径中
process cur = s.process[i];
path.push_back(cur);
// 获取排除当前进程后的新环境
condition c = s.exclude(i);
// 判断新环境死否死锁
if(locked(c)){ // 若死锁,继续在新环境下排除更多进程,复制当前路径展开新分支
vector<process> branch(path);
dfs(c, branch);
} else { // 若不死锁,将当前路径添加到全局变量 drop 中作为记录,并退出当前情况
drop.push_back(path);
}
}
}
}
vector<process> unlock(condition s){
if(locked(s)){
// 传入第一轮的死锁环境和原始路径,开始暴搜
for(int i = 0; i < s.process.size(); i++){
vector<process> path;
dfs(s.exclude(i), path);
}
}
if(drop.size() == 0){ // 说明没有找到一条解除死锁的路径
return NULL;
}
// 选取一条最短的解除死锁的路径,作为答案返回
vector<process> unlock_path;
int length = INT_MAX;
for(auto& p: drop){
if(p.size() < length){
unlock_path = p;
}
}
return unlock_path;
}
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
改进算法:根据接触进程的代价将各个进程升序排列,每次解除代价最小的进程,直到解除死锁
| 死锁处理方法 | 系统开销 | 资源利用率 |
|---|---|---|
| 死锁预防 | 低 | 低 |
| 死锁避免 | 中 | 中 |
| 死锁检测和解除 | 高 | 高 |
一般来说,在不加限定条件的情况下,为保证系统安全性,把每个进程对资源的最大需求量 -1 处理再求和并 +1,记为 n,要求资源总量大于等于 n
栗子一:如 6 个进程共享 18 个某类资源,每个进程最多申请 3 个该类资源
故 x 最大值为 3,每个进程最多申请不能超过 3
栗子二:三个并发进程互斥使用某一资源,其需求量分别为 3、4、5,问至少要多少个该类资源,才不会发生死锁