我不明白像 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 循环怎么办？我错过了什么吗？
维基百科甚至说：
该算法满足解决临界区问题的三个基本标准，前提是对变量 turn、flag[0] 和 flag[1] 的更改立即以原子方式传播。
这不是一个不合理的假设吗？似乎这些算法都假定了其他一些同步方式，因此其他线程不会在您执行自己的操作的过程中执行操作，但是如果我们已经拥有了，那么所有这些算法不应该给您，因为当你没有可以像LOCK指令一样为你锁定其他人的硬件时？
如果另一个执行线程远远落后于 flag[other] 甚至没有初始化，会发生什么？
您是对的：彼得森算法要求将标志初始化为零。
如果一个线程在其他线程完成上面的初始化步骤之前进入 for 循环怎么办？
面包店算法的定义说数字数组的内容必须从 0 开始。
似乎这些算法都假定了其他一些同步方式，因此其他线程不会在您执行自己的操作的过程中执行操作
事实上，面包店算法令人惊讶地没有这些假设。例如，维基百科文章声称：
每个线程只写自己的存储，只有读取是共享的。值得注意的是，该算法不是建立在一些较低级别的“原子”操作之上，例如比较和交换。原始证明表明，对于同一存储单元的重叠读取和写入，只有写入必须是正确的。读取操作可以返回任意数字。因此，该算法可用于在缺少同步原语的内存上实现互斥，例如，两台计算机之间共享的简单 SCSI 磁盘。
确实，它们依赖于从初始化值开始的共享值，但根据我的经验，这从未引起过问题。例如，大多数多线程进程作为一个单独的线程开始，它会分叉其余的线程，因此如果所有初始化都是静态完成的，或者在其他线程启动之前完成，就不会有问题。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句