进程同步中的烘焙算法

先决条件—— 临界截面 , 进程同步 , 进程间通信

这个 烘焙算法 是N过程一般情况下互斥问题的已知最简单解之一。烘焙算法是一个关键的部分解决方案 N 过程。该算法保留了先到先得的服务属性。

• 在进入关键区域之前，流程会收到一个数字。人数最少的持有者进入临界区。
• 如果进程Pi和Pj收到相同的数字，

  if i < j 
  Pi is served first; 
  else 
  Pj is served first.

• 编号方案总是以递增的枚举顺序生成数字；i、 例如，1，2，3，3，3，4，5…

符号- 字典顺序（票证号，进程id）-首先比较票证号。如果相同，则接下来比较进程ID，即-

– (a, b) < (c, d) if a < c or if a = c and b < d
– max(a [0], . . ., a [n-1]) is a number, k, such that k >= a[i]  for i = 0, . . ., n - 1

共享数据–选择的是一个布尔值数组[0..n–1]number是整数值的数组[0..n–1]。两者都初始化为 假&零 分别地

算法伪码-

repeat
    choosing[i] := true;
    number[i] := max(number[0], number[1], ..., number[n - 1])+1;
    choosing[i] := false;
    for j := 0 to n - 1
        do begin
            while choosing[j] do no-op;
            while number[j] != 0
                and (number[j], j) < (number[i], i) do no-op;
        end;

        critical section
    
    number[i] := 0;
    
        remainder section

until false;

解释—— 首先，该过程将其“选择”变量设置为TRUE，表明其进入临界区的意图。然后，它会被分配与其他进程对应的最高票证号。然后，“Selecting”变量被设置为FALSE，表示它现在有了一个新的票号。事实上，这是算法中最重要、最令人困惑的部分。

这实际上是一个小的关键部分本身！前三行的目的是，如果一个进程正在修改其票证值，那么此时不应允许其他进程检查其已过时的旧票证值。这就是为什么在for循环中，在检查票证值之前，我们首先确保所有其他进程的“selection”变量都为FALSE。

之后，我们继续检查进程的票证值，其中票证号/进程id最少的进程进入关键部分。出口部分只是将票证值重置为零。

代码– 下面是烘焙算法的C代码实现。在一个窗口中运行以下命令 UNIX环境 –

输出：