计算机系统（18）----- 进程互斥的软件实现方法

一、进程互斥的软件实现方法

1.1 单标志法

算法思想：

两个进程在访问完临界区后会把使用临界区的权限交给另一个进程，也就是每个进程进入临界区的权限智能被另一个进程赋予，同一时刻只有一个进程访问临界区

代码演示：

int turn = 0;//turn 表示当前允许进入临界区的进程号

P0 进程：
while( turn != 0 );
critical section;
turn = 1;
remainder section;

P1 进程：
while( turn != 1 );
critical section;
turn = 0;
remainder section;

1
2
3
4
5
6
7
8
9
10
11
12
13
14

这个算法的问题是：

如果此时允许进入临界区的进程是 P0 ，而 P0 一直不访问临界区，那么虽然这个时刻临界区空闲，但是并不允许 P1 访问；

违背了 “空闲让进” 的原则；

1.2 双标志先检查法

算法思想：

设置一个布尔型数组，数组中各个元素用来标记各进程想进入临界区的意愿；

代码演示：

bool flag[2];
flag[0] = false;
flag[1] = false;

P0 进程：
while( flag[1] );
flag[0] = true;
critical section;
flag[0] = false;
remainder section;

P1 进程：
while( flag[0] );
flag[1] = true;
critical section;
flag[1] = false;
remainder section;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这个算法的问题是：

如果两个进程并发执行，P0 和 P1 可能会出现同时访问临界区的情况；

违反 " 忙则等待 " 原则；

1.3 双标志后检查法

算法思想：

双标志先检查法的改版，由先 " 检查 " 后 " 上锁 " 更变为先 " 上锁 " 后 " 检查 " ；

代码演示：

bool flag[2];
flag[0] = false;
flag[1] = false;

P0 进程：
flag[0] = true;
while( flag[1] );
critical section;
flag[0] = false;
remainder section;

P1 进程：
flag[1] = true;
while( flag[0] );
critical section;
flag[1] = false;
remainder section;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

这个算法的问题是：

如果两个进程并发执行，P0 和 P1 可能会出现都无法访问临界区的情况；

产生 " 饥饿 " 现象；

1.4 Peterson 算法

算法思想：

Peterson 算法是基于双线程互斥访问的 单标志法与 双标志后检查法 算法而来，核心思想是主动让对方进程先进入临界区；

代码演示：

bool flag[2];
int turn = 0;
flag[0] = false;
flag[1] = false;

P0 进程：
flag[0] = true;
turn = 1;
while( flag[1] && turn == 1 );
critical section;
turn = 1;
flag[0] = false;
remainder section;

P1 进程：
flag[1] = true;
turn = 0;
while( flag[0] && turn == 0);
critical section;
turn = 0;
flag[1] = false;
remainder section;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

这个算法的问题是：

Peterson 算法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是没有遵循让权等待的原则；

Peterson 算法相较于之前三种解决方案来说是最好的，但是依然不够好；