最近在操作系统上学习了Peterson算法，其使用了3个变量就实现了纯软件的线程同步，即两个线程的标记变量c1, c2以及一个turn变量。但是对于其为什么要使用第三个变量还不是很了解，今天特意研究了一下，终于发现了第三个变量的作用。

0x0 Peterson算法的实现

以下给出Peterson算法在windows下的一种简单实现：

int c1 = 0, c2 = 0, will_wait;

DWORD WINAPI p1(LPVOID p)
{
	int counter = 0;
	int tmp1, tmp2, r;
	do{
		//加锁
		c1 = 1;
		will_wait = 1;
		while(c2 && (will_wait == 1));
		tmp1 = accnt1;
		tmp2 = accnt2;
		r = rand();
		accnt1 = tmp1 + r;
		accnt2 = tmp2 - r;
		counter++;
		
	}while(accnt1 + accnt2 == 0 && (c1 = 0) == 0);
	printf("%d\n", counter);
	return 0;
}

DWORD WINAPI p2(LPVOID p)
{


	int counter = 0;
	int tmp1, tmp2, r;
	do{
		//加锁
		c2 = 1;
		will_wait = 2;
		while(c1 && (will_wait == 2));
		
		tmp1 = accnt1;
		tmp2 = accnt2;
		r = rand();
		accnt1 = tmp1 + r;
		accnt2 = tmp2 - r;
		counter++;
		
	}while(accnt1 + accnt2 == 0 && (c2 = 0) == 0 );
	printf("%d\n", counter);
	return 0;
}


int main()
{
	system("pause");
	HANDLE hFirst = CreateThread(NULL, 0, p1, NULL, 0, NULL);
	HANDLE hSecond = CreateThread(NULL, 0, p2, NULL, 0, NULL);

	WaitForSingleObject(hFirst, INFINITE);
	WaitForSingleObject(hSecond, INFINITE);
	system("pause");
	return 0;
}

在该程序中，主程序开辟两个新的线程p1和p2，如果程序运行出现问题，则accnt1和accnt2的值相加不为0，则该线程退出。

0x0 简单的情况

从最简单的情况思考，当线程1首先进入临界区(Critical section)时，其值设为1，而当线程2准备进入临界区时，会判断c1是否为1，若为1，则会进入循环等待。当线程1退出后，c1=0，线程2得以进入临界区。通过这种方式，实现了两个线程之间的同步。

那么，为什么还需要一个turn变量呢？

0x1 另一种情况

要理解turn变量的作用，需要考虑另外一种情况。

假设两个线程几乎同时加锁，则其在加锁时的代码可以认为是混杂执行的。c1,c2都被设为1，然后两个线程先后进入阻塞循环当中。此时，如果阻塞循环如下：

while(c2); //p1进程

while(c1); //p2进程

则两个进程都会进入阻塞状态，互相阻塞，无法继续进行。

0x2 引入turn（will_wait）变量

下面考虑存在turn变量的情况。两个线程分别将c1,c2设为1，然后继续执行，都将turn设为自己对应的序号（1或2）。但是由于其执行顺序必然有先后，因此先赋值的会被覆盖掉，最终的值变为另一个线程的值。假设p1先执行

will_wait = 1;  // p1

然后p2执行：

will_wait = 2; // p2

最终，will_wait变量的值将变为2。

而当两个线程进入到阻塞循环当中去时，由于判断条件如下：

while(c2 && (will_wait == 1)); //p1

while(c1 && (will_wait == 2)); //p2

对于线程1来说，不满足循环条件（will_wait不等于1），则程序会继续运行，进入临界区。而对于线程2来说，满足阻塞循环的条件，会阻塞在该循环中，直到p1释放锁。

0x3 实验验证

为了验证不使用turn变量时，程序会进入互相阻塞状态。可以将两个线程改为如下代码：

//p1代码，p2类似
DWORD WINAPI p1(LPVOID p)
{
    int counter = 0;
    int tmp1, tmp2, r;
    do{
        //加锁
        c1 = 1;
        while(c2);
        tmp1 = accnt1;
        tmp2 = accnt2;
        r = rand();
        accnt1 = tmp1 + r;
        accnt2 = tmp2 - r;
        counter++;
        printf("1: running\n");
    }while(accnt1 + accnt2 == 0 && (c1 = 0) == 0);
    printf("%d\n", counter);
    return 0;
}

可以看出，如果程序能够正常进入临界区，则会不断循环输出1: running。另外，需要注意的是，Peterson算法只能在单核系统下生效，如果要在多核系统下生效，需要进行以下操作。

首先在main函数的开始位置，添加一行system("pause");
运行程序，程序会等待用户按任意键继续运行。
在任务管理器中找到该程序，点右键（win10下需要转到详细信息页点右键），选择设置相关性，然后只选中一个CPU核心。
回到编写的程序，按任意键继续运行。

程序运行结果如下： no_turn

而添加will_wait变量之后，程序的运行结果如下： with_turn

可以看出，在没有加turn变量时，线程1执行了两次之后，就进入了相互阻塞状态，两个线程都不继续运行。而加了turn变量之后，程序则会持续运行下去，不断输出，同时也没有出现同步问题导致进程被终止的情况。

0x4

由此证明，turn变量在Peterson算法中是为了保证程序不会出现相互阻塞而产生的，不可缺少。