Peterson 无锁互斥算法

我们知道要解决线程互斥问题,我们一般使用锁机制来实现。实现互斥的一种软件方法是采用锁机制,即提供一对上锁和开锁原语,以及一个锁变量 W 进入临界区前,通过锁变量来判断临界资源是否被占用。

Peterson 算法是一个实现互斥锁的并发程序设计算法,可以控制两个进程访问一个共享的单用户资源而不发生访问冲突。

同步机制应该遵循的准则:

  1. 空闲让进 当无进程处于临界区内时,必须让一个要求进入临界区的进程立即进入,以有
    效地利用临界资源。
  2. 忙则等待 当已有进程处于临界区内时,其它试图进入临界区的进程必须等待,以保证它
    们互斥地进入临界区。
  3. 有限等待 对要求进入临界区的进程,应在有限时间内使之进入,以免陷入“死等”。
  4. 让权等待 对于等待进入临界区的进程而言,它必须立即释放处理机,以免进程“忙等”

假设有两个进程需要互斥的访问某一个临界区。

算法实现如下:

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
package com.gizwits.concurrent;

/**
* Peterson 互斥算法
*/

public class Peterson {

/**
* 用于表示进程进入临界区的意愿,下标对应进程号. 主观地表示某一个进程是否希望使用资源
*/

private static boolean[] in = {false, false};

/**
* 用于表示轮到哪个进程, 客观地表示哪一个进程有权使用进程
*/

private static volatile int turn = 0;


/**
* 进入临界区
*
* @param process 进程号
*/

public void enterRegion(int process) {
int cnt = 5;
while (cnt-- > 0) {
// 进程 id 想进入临界区, 表示本进程想使用资源
in[process] = true;

// 另一个进程的进程号
int other = 1 - process;
// 设置轮到自己进入临界区了, 谦让,把使用进程的权限让给对方进程
turn = other;

// 如果对方进程想使用资源,且对方进程有使用资源的权限时,本进程等待
while (in[other] && turn == other) {
System.out.println("[" + process + "] - wait...");
}
System.out.println("-------------------[" + process + "] Working");
leaveRegion(process); // 本进程用完资源后,必须表示不再想用资源
}

}

private void leaveRegion(int process) {

in[process] = false; // 本进程用完资源后,必须表示不再想用资源
}

public static void main(String[] args) {

final Peterson peterson = new Peterson();
int threadNum = 2;


for (int i = 0; i < threadNum; i++) {

final int finalI = i;
new Thread(new Runnable() {
@Override
public void run() {

peterson.enterRegion(finalI);
}
}).start();
}
}


}

多次运行出现互斥:

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
-------------------[0] Working
[1] - wait...
-------------------[1] Working
[1] - wait...
[1] - wait...
[1] - wait...
[1] - wait...
[1] - wait...
[1] - wait...
[1] - wait...
[1] - wait...
[1] - wait...
[1] - wait...
[1] - wait...
[1] - wait...
[1] - wait...
[1] - wait...
[1] - wait...
[0] - wait...
-------------------[0] Working
[0] - wait...
[1] - wait...
-------------------[1] Working
[0] - wait...
-------------------[0] Working
[0] - wait...
[0] - wait...
[0] - wait...
[0] - wait...
[0] - wait...
[0] - wait...
[0] - wait...
[0] - wait...
[0] - wait...
[0] - wait...
[0] - wait...
[0] - wait...
[0] - wait...
[0] - wait...
[0] - wait...
[0] - wait...
[0] - wait...
[0] - wait...
[0] - wait...
[0] - wait...
[0] - wait...
[0] - wait...
[0] - wait...
[0] - wait...
[0] - wait...
[1] - wait...
-------------------[1] Working
[1] - wait...
[1] - wait...
[1] - wait...
[1] - wait...
[1] - wait...
[1] - wait...
[1] - wait...
[1] - wait...
[1] - wait...
[1] - wait...
[1] - wait...
[1] - wait...
[0] - wait...
-------------------[0] Working
[1] - wait...
-------------------[1] Working
[0] - wait...
-------------------[0] Working
[1] - wait...
-------------------[1] Working

扩展到 N 个线程互斥访问一个资源的 filter 算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// initialization
level[N] = { -1 }; // current level of processes 0...N-1
waiting[N-1] = { -1 }; // the waiting process of each level 0...N-2
// code for process #i
for(l = 0; l < N-1; ++l) {
level[i] = l;
waiting[l] = i;
while(waiting[l] == i &&
(there exists k ≠ i, such that level[k] ≥ l)) {
// busy wait
}
}
// critical section
level[i] = -1; // exit section