为什么不用队列来执行 Peterson 的算法？

Question

Peterson's algorithm 是一种算法，用于确保共享内存的进程不会同时访问该内存。我在下面为索引为 i 的线程转载了它。

do {
    flag[i] = true
    turn = j
    while(flag[j] == true && turn == j){};

    #enter critical section

    flag[i] = false

    #remainder

} while (true);

为什么以下算法（使用共享队列 'queue'）不能像 Peterson 那样提供进程同步？

do {
    #push i into process queue
    queue.push i
    #busy wait until i is first
    while(queue.first != i){};

    #enter critical section

    #remove i from the queue and let the next process begin
    queue.pop

    #remainder

} while (true);

Answer 1

它会，前提是您可以使用某种原子机制实现 queue.push 和 queue.pop。通常，queue.push 必须自动更新多个位置。为此，您需要某种形式的序列化，例如 Petersons 算法。

Peterson 算法的要点是在没有任何花哨的硬件或软件支持的情况下提供此服务——只需一个简单的相干存储设备就足够了。