Peterson算法中turn(will_wait)变量的作用

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

0x0 Peterson算法的实现

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
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,然后两个线程先后进入阻塞循环当中。此时,如果阻塞循环如下:

1
2
3
while(c2); //p1进程
while(c1); //p2进程

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

0x2 引入turn(will_wait)变量

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

1
will_wait = 1; // p1

然后p2执行:

1
will_wait = 2; // p2

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

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

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

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

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

0x3 实验验证

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//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算法只能在单核系统下生效,如果要在多核系统下生效,需要进行以下操作。

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

程序运行结果如下:
no_turn

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

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

0x4

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