Dekker算法与Peterson算法-处理两个进程间互斥

最近在复习操作系统知识，本文主要就是HKU的COMP3230的笔记。

Dekker算法是处理（两个）进程的互斥关系的软件方法，其它方法还有硬件方法、信号量方法、管程等方法，有机会再写。

Dekker’s Algorithm V1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(process i)
Repeat 
  While( turn == j) do no-op;
    critical section
  turn = j;
  remainder section
Until false
(process j)
Repeat 
  While( turn == i) do no-op;
    critical section
  turn = i;
  remainder section
Until false

说明

这个方案只能处理固定顺序的序列，比如i, j, i, j…就算j没有用到临界区，i还是要等j，这被称作”Lockstep synchronization”

Problems

  • 就算不使用临界区也会阻塞别的进程
  • Busy waiting: 一直在测临界区是否是否空闲，浪费处理器资源
  • Lockstep synchronization问题: 只能处理固定顺序的进程序列

Dekker’s Algorithm V2

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
Initially, flag[i] = flag[j] = false;
(process i)
Repeat
  While(flag[j]) do no-op;
  flag[i] = true;
  
  critical section
  
  flag[i] = false;
  
  remainder section
Until false
(process j)
Repeat
  While(flag[i]) do no-op;
  flag[j] = true;
  
  critical section
  
  flag[j] = false;
  
  remainder section
Until false

说明

  1. While(flag[j]) do no-op; 因为flag[j]=false直接pass, 这时候来一个context switch到process j
  2. While(flag[i]) do no-op;因为flag[i]=false直接pass, 这时候来一个context switch到process i
  3. flag[i] = true，context switch到process j
  4. flag[j] = true，context switch到process i
  5. 两边都可以进临界区，引发互斥

Problems

虽然排除了Lockstep synchronization到那时会引发互斥

Dekker’s Algorithm V3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
(process i)
Repeat
  flag[i] = true;
  While(flag[j]) do no-op;
  
  critical section
  
  flag[i] = false
  
  reminder section
Until false
(process j)
Repeat
  flag[j] = true;
  While(flag[i]) do no-op;
  
  critical section
  
  flag[j] = false;
  
  reminder section
Until false

说明

  1. flag[i] = true; #Context switch
  2. flag[j] = true; #Context switch
  3. While(flag[j]) do no-op;#Context switch
  4. While(flag[i]) do no-op;#Context switch
    相互等待，死锁了

Dekker’s Algorithm V4

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
Initially, flag[i]= flag[j]=false; turn=i
(process i)
Repeat
  flag[i] = true;
  While(flag[j]){
    if(trun == j){
    flag[i] = false;
    While(turn == j); #如果是j的turn，就一直等到j结束
    flag[i] = true; #j使用完临界区后会把turn设为i，此时i把flag设为true
    }
  }
  
  critical section
  
  turn = j; flag[i] = false;
  
  reminder section
Until false
(process j)
Repeat
  flag[j] = true;
  While(flag[i]){
    if(trun == i){
    flag[j] = false;
    While(turn == i);
    flag[j] = true;
    }
  }
  
  critical section
  
  turn = i; flag[i] = false;
  
  reminder section
Until false

说明

  • 使用turn来决定哪个进程进入临界区
    • 每个进程都临时把自己的flag设为flag
  • 确保互斥
  • 避免死锁

总结Dekker’s Algorithm V4

Pros

  • 不需要硬件指令支持

    Cons

  • 只能两个进程
  • Busy Waiting (进程默认对面会花时间在临界区，context switch等对面换了flag这边才会退出while）

Peterson’s Algorithm

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
Initially, flag[i]= flag[j]=false; turn=i
(process i)
Repeat 
  flag[i] = true;
  turn = j;
  While(flag[j] and turn == j);
  
  critical section
  
  flag[i] = false;
  
  reminder section
Until false
(process j)
Repeat 
  flag[j] = true;
  turn = i;
  While(flag[i] and turn == i);
  
  critical section
  
  flag[j] = false;
  
  reminder section
Until false

说明

  • While(flag[j] and turn == j);当flag[j] and turn == j是true，说明j比i先跑（后跑的那个把turn覆盖为先跑的），所以i要wait
  • 虽然也要busy waiting，但是比Dekker’s Algorithm简单太多，实现互斥也不会引发死锁。

Extra

举2个不行的例子

example1

1
2
3
4
5
6
7
loop{
  if lock == 0:
    lock = i;
    if lock == i:
      crital_section;
      lock = 0;
}
分析

process1和process2的lock本来都是0，两边都进入if block内，然后process1给lock赋值，lock == i通过，进入临界区； process2那边给lock赋值，lock == i，也可以进入临界区，发生冲突。

exampole2

1
2
3
4
5
6
7
8
9
10
11
shared boolean flag[2];
flag[0] = flag[1] = false;
proc(int i){
  while(true){
    while(flag[(i+1) mod 2] == true);
    flag[i] = true;
    critical section;
    flag[i] = false;
  }
}
分析

两边都是false，两边都把while给pass掉，然后往下跑回同时进入临界区

操作系统算法