Peterson算法解决竞争条件问题

我在文章Java多线程中的竞争条件、锁以及同步的概念中提到过竞争条件的问题，当时只是提了一下怎么调用Java的API来实现这种同步，其实在目前已经有了多种进程同步的解决方式，比如

屏蔽中断
锁变量
严格轮换法
Peterson算法
TSL指令

这里介绍一下 Peterson算法，其实现以及测试代码如下所示：

#include <unistd.h>
#include <stdio.h>

#define FALSE   0
#define TRUE    1
#define N       2       // Num of process

int flag;

int turn;               // 现在轮到的那个进程
int interested[N];      // TRUE means interested, default is FALSE.

void enter_region(int process);
void leave_region(int process);

int main(int argc, char const *argv[]) {
    pid_t fpid = fork();
    if(fpid > 0) {
        while(TRUE){
            enter_region(1);
        }
    } else if(fpid == 0){
        while(TRUE){
            enter_region(0);
        }
    }
    return 0;
}

void enter_region(int process) {
    int other = 1 - process;    // Get another process
    interested[process] = TRUE;
    turn = process;
    while (turn == process && interested[other] == TRUE);
    /* TEST */
    if(process == 0){
        flag = 0;
        printf("%d ==> %d\n", process, flag);
    }else{
        flag = 1;
        printf("%d ==> %d\n", process, flag);
    }
    leave_region(process);
}

void leave_region(int process) {
    interested[process] = FALSE;
}

其中enter_region是进程进入临界区时的方法，leave_region是离开临界区时执行的方法，方法参数为进程编号。

我们先来重点关注一下while (turn == process && interested[other] == TRUE);这句代码，这种代码的执行方式被称之为忙等待，顾名思义，这是一种比较浪费CPU资源的方式。

假设有两个进程，第一个进程是 0，第二个进程是 1。一开始，没有任何进程处于临界区，现在进程0调用enter_region。他通过设置其数组元素和将turn置为0来标识他希望进入临界区。由于进程 1 并不想进入临界区，所以enter_region很快便返回。如果进程 1 现在调用enter_region，进程1将在此处挂起直到interested[0]变成 FALSE，该事件只有在进程 0 调用leave_region退出临界区时才会发生。

现在考虑两个进程几乎同时调用enter_region的情况。他们都是将自己的进程号存入 turn，但只有后被保存进去的进程号才有效，前一个因被重写而丢失。假设进程 1 是后存入的，则 turn 为 1，当两个进程都运行到 while 语句时，进程 0 将循环 0 次进入临界区，而进程 1 则将不停的循环不能进入临界区，直到进程 0 退出临界区为止。

Peterson算法解决竞争条件问题

参考资料：