algorithm - 互斥算法仅使用原子读写来处理未知数量的进程，并且对进程中止具有鲁棒性

Question

我试图提出一种互斥算法，该算法仅基于共享内存的原子读取和原子写入（即没有比较和交换或类似操作）。

除了相互排斥和死锁自由之外，它还需要满足以下属性：


在任何时候都面临流程死亡的情况下，它必须具有鲁棒性
它需要处理竞争锁的事前未知数量的进程
每隔几秒钟，我需要其中一个过程才能进入关键部分（我不在乎哪个）
它应该尽可能节省内存
我所有的进程都共享一个合理同步的时钟源（亚秒级精度）


我想出了一种看起来可行的方法，但是我想由你们来运行它，看看我是否在某个地方犯了错误，或者是否有更优雅的解决方案。

这个想法是将Szymanski's Three-Bit Linear Wait Algorithm (Figure 1 on page 4 of "Mutual Exclusion Revisited")的修改版本与宽松地基于Moir and Anderson's "Wait-Free Algorithms for Fast, Long-Lived Renaming" (M&A)的进程命名方案结合在一起。

第一步，我为传入流程定义一个“订单”，方法是为它们分配一个ID，例如M＆A：

并购使用以下互斥体原语（请参阅第5页的图2）：

在进入该块的n个进程中，最多1个将停止在此处，最多n-1将向右移动，最多n-1将向下移动。

这些原语可以链接到一个网格中，在此网格中，我决定为框的编号与并购的编号不同，以使我能够在不知道框总数的情况下计算框号：

箱号可以使用box = (m*(m-1))/2 + r进行计算，其中m是移动的总数（包括移动到左上角的箱，即m≥1），r是向右移动的次数（r≥0 ）。

最初，将为任何新进程分配一个较大的全局唯一ID（例如，时间戳+巨大的随机数），该ID将用作上述互斥体基元算法中p的值。然后它将按照图元的规则开始遍历网格，从左上角开始，直到在某个框中停止。现在，它停止所在的框号将为其新的进程ID。

为了使进程ID的数量保持较小（进程可能会消失；而且：如果所有进入的进程都向右或向下移动并且都没有停在那儿，则可以永久锁定框而不使用它们），我将在上面的原语中替换布尔变量Y带有时间戳。

然后，将Y := true行替换为Y := now，这里现在是当前时间。同样，条件if Y then ...将替换为if (now - Y < timeout) then ...，其中超时是将框返回到可用池之前的时间。

当进程仍在运行时，它需要将其框的Y值设置为现在，以使其ID永不过期。虽然较小的超时值将导致较小的ID和较少的内存使用，但从理论上可以选择任意大的值，因此始终应找到一个超时值，以确保进程不会丢失其ID，除非它们实际上退出或退出。死了分钟，小时甚至几天的值应该可以解决问题。

现在，我们可以使用以下流程顺序来实现Szymanski的算法：

communication variables:: a, w, s: boolean = false
private variables:: j: 0..n

p1      ai=true;
p2      for(j=0;j<n;j++)
            while(sj);
p3      wi=true;
        ai=false;
p4      while(!si) {
p5          for (j=0;j<n & !aj;j++);
p6          if (j==n) {
                si=true;
p6.1            for (j=0;j<n & !aj;j++);
p6.2            if (j<n)
                    si=false;
p6.3            else {
                    wi=false;
p6.4                for(j=0;j<n;j++)
                        while(wj);
                }
            }
p7          if (j<n)
                for (j=0;j<n & (wj | !sj);j++);
p8          if (j!=i & j<n) {
p8.1            si=true;
                wi=false;
            }
        }
p9      for(j=0;j<i;j++)
            while(wj | sj);

Critical Section

e1      si=false;

该算法背后的思想有点复杂，为了简洁起见（如果这在目前还不是一个迷失的原因），我将不再尝试在这里重新解释（ Wikipedia also discusses a variant of this algorithm）。

为了使该算法根据需要工作（即面对进程中止和未知的进程总数），可以进行以下更改：

就像上面的Y一样，布尔ai，wi和si将被替换为时间戳。除此之外，这次的超时时间必须足够短，以便仍然允许根据需要频繁输入关键部分，在我的情况下，每隔几秒钟，因此5秒的超时时间可能会起作用。同时，超时时间必须足够长，以使它永远不会过期，除非进程死掉，即，它需要比进程为保持需要设置的标志保持更新时间戳所花费的最坏情况下的时间更长。

进程（例如 for(j=0;j<n;j++)）上的循环将按照框号的顺序从上方转换为进程ID网格的遍历。每个框可以具有3种状态：从来没有任何人访问过该状态，一个进程已停止或所有进程继续运行并且该框当前处于阻塞状态。后两者无需区分，因为一个被阻止的框将仅对应于当前不尝试进入关键部分的进程（即，ai，wi和si为假/已过期）。循环从框0开始。如果遇到已访问过的框（即设置了其X值），则将相邻框添加到其“待检查清单”中（即，如果看到框8，则框12和13将被添加到列表中）。当“待检查清单”已完全处理时，循环终止（当然，除非存在另一个首先触发的停止条件（例如 j < i或 & !aj））。

现在我的问题是：


看起来这样可靠吗？我从未对这种框架做过正式的证明。我的直觉（和深思熟虑）告诉我，它应该牢固，但是我不介意比这更严格的事情。我最担心Szymanski算法的p3和e1之间死于进程的影响，而标志中的其他进程却随机失效。
是否有更好的解决方案（更简单/更少的资源使用）？优化的一个攻击点可能是我不需要所有过程来最终使它进入关键部分，而我只需要一个过程（我不需要不在乎哪一个）。


很抱歉这篇文章的篇幅，感谢您的耐心阅读！缩短欢迎时间的建议... :)

PS：我也将此问题发布在 CS stack exchange上。

Answer 1

由于我并不真正在乎公平或饥饿（哪个过程进入关键部分并不重要），因此我真的不需要使用像Szymanski一样复杂的算法。

我找到了一个非常漂亮的选择：Burns和Lynch的算法：

program Process_i;
    type flag = (down, up);
    shared var F : array [1..N] of flag;
    var j : 1..N;
begin
    while true do begin
        1: F[i] := down;
        2: remainder;     (* remainder region *)
        3: F[i] := down;
        4: for j := 1 to i-1 do
               if F[j] = up then goto 3;
        5: F[i] := up;
        6: for j := 1 to i-1 do
               if F[j] = up then goto 3;
        7: for j := i+1 to N do
               if F[j] = up then goto 7;
        8: critical;      (* critical region *)
    end
end.

您可以在其论文 "Mutual Exclusion Using Indivisible Reads and Writes"的第4页（836）上找到它。

它具有两个主要优点：


简单得多
它使用较少的内存（实际上，他们声明他们的算法在这方面是最佳的）
所有共享内存只有一个写入器（当然有多个读取器）
将忙碌的等待转变为重试很容易（请参见 here）


另外：该算法的思想可以如下所示：

我是一个过程，我与其他人（所有其他过程）排成一排。当我想进入关键部分时，请执行以下操作：


3/4：只要看到有人举手，我就会向左看，并保持手放低。
5：如果我左边没有人举手，我举起我。
6：我再次检查左边的人是否同时举起了手。如果是这样，我放下我的脚，然后重新开始。否则，我会举手。
7：我右边的每个人都先走，所以我往右边看，等到看不到任何举手。
8：一旦我右边的手放下，我就可以进入关键区域。
1：完成后，我将手放回原处。


我使用这种算法从上面实现了整个想法（包括并购），目前正在测试它的效果，到目前为止，它似乎非常稳定。

实现非常简单。我实际上只需要考虑另外两个警告（除非，当然，我错过了一些事情（欢迎指针））：


如果某个进程进入算法中的第7行，则最终可能会碰到 goto，在这种情况下，在我的实现中（请参见 here），关键部分的条目将被拒绝，然后该进程稍后重试。当重试发生时（可能会有很大的延迟），我需要以一种甚至没有标志过期的最短时间刷新进程标志的方式，或者，如果有，我需要检测然后跳回到算法的第3行，而不是继续到第7行。
我添加了一项检查，是否根本需要输入关键部分（即一条限制关键部分输入速率的语句）。在过程甚至试图进入关键部分之前立即执行此检查是最有效的。但是，要确保100％确保没有线程可以超过速率限制，当进程成功进入关键部分时，将需要执行第二次检查。


由于我的代码使用了共享的数据结构，因此目前并没有真正使它有意义的发布状态，但是通过一点点工作，我就可以构建一个独立的版本。如果有人感兴趣，请发表评论，我会这样做。