- 算法 -

Bakery's Algoritm面包店算法-处理多个进程间互斥

Outline

  • 在进入临界区以前，进程获得一个编号
  • 最小编号的进程进入临界区
  • 出临界区以后，ticket设为0

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Initial 
choosing[0..n]=flase;
ticket[0..n]=0;
Repeat
  choosing[i] = true;
  ticket[i] = max(ticket[0], ticket[1], ..., ticket[n-1]) + 1;  //给i一个最大的ticket号
  choosing[i] = false;
  
  for k = 0 to n - 1
    do begin
      while choosing[k] do no-op; //当前有人在获取ticket号，等待
      while ticket[k] != 0 and ( ticket[k], k) < (ticket[i], i) do no-op;  //有进程优先级更高
      end
      
  critical section
      
  ticket[i] = 0; //当ticket = 0，说明没有拿ticket
  remainder section
until false
Read More
操作系统算法