Peterson算法

Peterson算法是一个实现互斥锁的并发程序设计算法，可以控制两个进程访问一个共享的单用户资源而不发生访问冲突。Gary L. Peterson于1981年提出此算法 。

互斥访问

P0与P1显然不会同时在临界区: 如果进程P0在临界区内，那么或者flag[1]为假(意味着P1已经离开了它的临界区)，或者turn为0(意味着P1只能在临界区外面等待，不能进入临界区).

空闲让进

进入(Progress)定义为：如果没有进程处于临界区内且有进程希望进入临界区, 则只有那些不处于剩余区(remainder section)的进程可以参与到哪个进程获得进入临界区这个决定中，且这个决定不能无限推迟。剩余区是指进程已经访问了临界区，并已经执行完成退出临界区的代码，即该进程当前的状态与临界区关系不大。

有限等待

有限等待(Bounded waiting)意味着一个进程在提出进入临界区请求后，只需要等待临界区被使用有上限的次数后，该进程就可以进入临界区。即进程不论其优先级多低，不应该饿死(starvation)在该临界区入口处。Peterson算法显然让进程等待不超过1次的临界区使用，即可获得权限进入临界区。

注解

Peterson算法不需要原子(atomic)操作，即它是纯软件途径解决了互斥锁的实现。但需要注意限制CPU对内存的访问顺序的优化改变。

扩展到N个线程互斥访问一个资源的filter算法

// initializationlevel[N] = { -1 };     // current level of processes 0...N-1waiting[N-1] = { -1 }; // the waiting process of each level 0...N-2// code for process #ifor(l = 0; l < N-1; ++l) {
    level[i] = l;
    waiting[l] = i;
    while(waiting[l] == i &&
          (there exists k ≠ i, such that level[k] ≥ l)) {
        // busy wait
    }}// critical sectionlevel[i] = -1; // exit section
数组level表示每个线程的等待级别，最小为0，最高为N-1，-1表示未设置。数组waiting模拟了一个阻塞（忙等待）的线程队列，从位置0为入队列，位置越大则入队列的时间越长。每个线程为了进入临界区，需要在队列的每个位置都经过一次，如果没有更高优先级的线程（考察数组level），cd 或者被后入队列的线程推着走（上述程序waiting[l] ≠ i），则当前线程在队列中向前走过一个位置。可见该算法满足互斥性。
由filter算法去反思Peterson算法，可见其中的flags数组表示两个进程的等待级别，而turn变量则是阻塞（忙等待）的线程队列，这个队列只需要容纳一个元素。