multithreading - 彼得森的算法如何在不做出不切实际的假设的情况下工作？

Question

我不明白像 Peterson 和 Lamport 的纯软件临界区算法是如何工作的。

维基百科列出了彼得森的伪代码:

flag[me] = true;
turn  = other;
while (flag[other] == true && turn == 1)
     {
         // busy wait
     }
 // critical section
 // end of critical section
 flag[me] = false;

在我看来，这在实践中是行不通的。如果另一个执行线程远远落后于 flag[other] 甚至没有初始化，会发生什么情况？

对于面包店算法:

   Entering[i] = true;

  Number[i] = 1 + max(Number[1], ..., Number[NUM_THREADS]);

  Entering[i] = false;

  for (integer j = 1; j <= NUM_THREADS; j++) {

      // Wait until thread j receives its number:

      while (Entering[j]) { /* nothing */ }

      // Wait until all threads with smaller numbers or with the same

      // number, but with higher priority, finish their work:

      while ((Number[j] != 0) && ((Number[j], j) < (Number[i], i))) { /* nothing */ }

  }

如果一个线程在其他线程完成上面的初始化步骤之前进入 for 循环怎么办？我错过了什么吗？

维基百科甚至说:

The algorithm satisfies the three essential criteria to solve the critical section problem, provided that changes to the variables turn, flag[0], and flag[1] propagate immediately and atomically.

这不是一个不合理的假设吗？似乎这些算法都采用了其他一些同步方式，因此其他线程不会在您执行自己的操作的过程中执行操作，但如果我们已经有了，难道不是所有这些算法都应该给您，因为当您没有可以为您锁定其他人的硬件时，例如 LOCK 指令？

Answer 1

What happens if the other thread of execution is far behind enough that flag[other] isn't even initialized?

你是对的:彼得森算法要求将标志初始化为零。

What if one thread gets down into the for loop before the others have completed that initialization step above it?

definitions面包店算法的作者说数字数组的内容必须从 0 开始。

It seems like these algorithms all assume some other means of synchronization so other threads don't perform operations in the middle of you doing your own operations

事实上，面包店算法出人意料地没有这些假设。例如，wikipedia article声明:

Each thread only writes its own storage, only reads are shared. It is remarkable that this algorithm is not built on top of some lower level "atomic" operation, e.g. compare-and-swap. The original proof shows that for overlapping reads and writes to the same storage cell only the write must be correct. The read operation can return an arbitrary number. Therefore this algorithm can be used to implement mutual exclusion on memory that lacks synchronisation primitives, e.g., a simple SCSI disk shared between two computers.

的确，它们依赖于以初始化值开头的共享值，但根据我的经验，这从来没有造成问题。例如，大多数多线程进程都是作为一个单独的线程开始的，它会 fork 其余的线程，因此只要所有初始化都是静态完成的或在其他线程启动之前就没有问题。