Peterson 的算法在现实世界中用在什么地方？

Question

我正在阅读《操作系统：三个简单的部分》，我了解彼得森的算法是一种同步机制，可以在进程/线程之间提供互斥，但是我不清楚该算法是否是任何编程语言中并发结构实现的基础。举个例子，这个 Raku 代码片段及其关键部分，即 ，$counter += 1通过使用Lock结构进行保护：

my UInt:D $counter = 0;
my Lock:D $lock = Lock.new;

my Thread:D $t0 = Thread.start({
    for 1..1000 {
        $lock.protect({ $counter += 1 });
    }
});

my Thread:D $t1 = Thread.start({
    for 1..1000 {
        $lock.protect({ $counter += 1 });
    }
});

$t0.finish;
$t1.finish;

say "Counter: $counter";

假设我了解 Peterson 算法的缺点/缺点，我可以Lock用 Peterson 算法替换 Raku 的算法，并且仍然拥有一个带有受保护关键部分的工作程序吗？

总之，彼得森的算法只是一种教学练习吗？例如，它与互斥锁有什么关系？它是否可以在生产代码中使用（再次假设我知道我在做什么）？

Answer 1

早期的计算机系统没有任何指令来执行原子测试和设置等操作，更不用说原子交换、原子递增/递减测试或（特别是）原子比较交换或加载链接/条件存储。添加原子操作使得管理互斥体变得微不足道，因为可以使用任意数量的任务：

if (!test_and_set(&task_busy))
{
  ... do task
  task_busy = 0;
}
else
  ... do_something else for awhile and try again later

另一方面，Peterson 算法假设如果任务 #1 写入 X，然后写入 Y，而任务 #2 读取 Y，然后读取 X，则任务 #2 不可能先读取 Y 的新值，然后再读取旧值X 的保证，但在当今的某些系统上维持这种保证可能会非常昂贵。Peterson 算法中每个步骤的成本已增加到总成本显着超过测试和设置、比较交换或类似操作的成本。