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

Outline

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

伪代码

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

说明

• 取ticket的时候没有加保护条件（期间可能产生context switch），所以获得的ticket序列可能是1, 2, 3, 3, 3, 3, 4, 5…不过相同ticket号码时，进程序列号小的先跑
• 还是会空等
• 实现要规定号进程数量

Reference

• 进程互斥软件算法(Lamport面包店算法和Eisenberg算法) johnny710vip