Peterson 算法

示例 9–6 中的代码是 Peterson 算法的实现，该算法可以处理两个线程之间的互斥。此代码尝试保证临界段中只有一个线程。当线程调用 mut_excl() 时，线程会在某一时间“快速”进入临界段。

此处假设在进入临界段后线程很快就退出了。

示例 9–6 两个线程是否互斥？

void mut_excl(int me /* 0 or 1 */) {

    static int loser;

    static int interested[2] = {0, 0};

    int other; /* local variable */

   

    other = 1 - me;

    interested[me] = 1;

    loser = me;

    while (loser == me && interested[other])

        ;



    /* critical section */

    interested[me] = 0;

}

如果多处理器具有强秩序存储器，则此算法可工作一段时间。

某些多处理器（包括某些基于 SPARC 的多处理器）具有存储缓冲区。线程发出存储指令时，数据即被放入存储缓冲区中。缓冲区内容最终会被发送到高速缓存，但不一定会立即发送。每个处理器上的高速缓存都可以维护一致的内存视图，但修改的数据不会立即到达高速缓存。

在存储到多个内存位置时，更改将按正确顺序到达高速缓存和内存，但可能会在一定延迟后到达。具备此属性的基于 SPARC 的多处理器被称为具有全存储序顺序 (total store order, TSO)。

假设您面临的情况是，一个处理器存储到位置 A 并从位置 B 装入。另一个处理器存储到位置 B 并从位置 A 装入。第一个处理器将从位置 B 提取新修改的值，或第二个处理器将从位置 A 提取新修改的值，或者同时发生这两种情况。但是，两个处理器装入原有值的情况不会发生。

此外，由于装入和存储缓冲区导致的延迟，可能会发生“不可能的情况”。

使用 Peterson 算法时可能发生的情况是在不同处理器上运行的两个线程可以同时进入临界段。每个线程都可以存储到其各自的特定数组槽中，然后从其他槽装入。两个线程可以读取原有的值 (0)，每个线程都假设对方不存在，而且都可以进入临界段。测试程序时可能不会检测出这种问题，这种问题只会在稍后发生。

要避免此问题，请使用线程同步元语，其实现会发出特殊指令，从而强制将存储缓冲区写入高速缓存。