Memory Barrier

November 15, 2007 – 12:49 pm

今天在 freecity 的 DistributedSys 版看到在讨论 memory consistency 的问题,潜水的时候看到 shifan 给的两篇文章,其中一篇 barrier 中有一个例子,就是在没有 barrier 的情况下顺序乱掉了,对这个东西一直一知半解,所以也决定实践一把,就照着类似地写了一个程序:

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
#include <windows.h>
#include <stdio.h>
 
#define ITERATIONS 500000000
 
typedef volatile unsigned int T;
T var1 = 0;
 
DWORD WINAPI writer(T *pvar2)
{
	while (1)
	{
		var1 = var1 + 1;
		*pvar2 = *pvar2 + 1;
	}
	return 0;
}
 
DWORD WINAPI reader(T *pvar2)
{
	SYSTEMTIME begin, end;
	unsigned int i, failcount = 0;
	double seconds;
 
	GetSystemTime(&begin);
 
	for (i = 0; i < ITERATIONS; ++i)
	{
		unsigned int v2 = *pvar2;
		unsigned int v1 = var1;
		if (v2 > v1)
			++failcount;
	}
 
	GetSystemTime(&end);
 
	seconds = (end.wMinute*60 + end.wSecond + end.wMilliseconds/1000.0)
		- (begin.wMinute*60 + begin.wSecond + begin.wMilliseconds/1000.0);
 
	printf("in %2.1lf seconds, failure count = %u(%2.1lf%%)\n",
			seconds,
			failcount,
			100.0 * failcount / ITERATIONS);
 
	return 0;
}
 
int main()
{
	T var2 = 0;
	HANDLE htwriter, htreader;
	htwriter = CreateThread(NULL, 0, writer, &var2, 0, NULL);
	htreader = CreateThread(NULL, 0, reader, &var2, 0, NULL);
 
	WaitForSingleObject(htreader, 1000000);
 
	return 0;
}

正好我也是双核的,可是我不知道 API 里面如何做原文里的 utilBindThreadToCPU 函数,运行的结果几乎一直都是 0 ,最后加大迭代数,才终于得到了一个 failure :

barrier

而且运行了几次总是 1 个,1 这个数字还是很特殊的,我甚至都怀疑是哪里出问题了,可是又找不到问题。不过那篇文章里有这样一段:

And on the other end, we have strongly ordered memory models that do very little reordering, like the – here it comes – x86. No matter how many times I run that code, even on a double-dualie Intel Mac Pro, I never saw any failures. Why not? My understanding (and here it grows fuzzy) is that early multiprocessing setups were strongly ordered because modern reordering tricks weren’t that useful – memory was still pretty fast, y’know, relatively speaking, so there wasn’t much win to be had. So developers blithely assumed the good times would never end, and we’ve been wearing the backwards compatibility shackles ever since.

不知道是我的 CPU 坏了还是我程序写得有问题或者是都没有问题,只是那篇文章的作者的 RP 不如我好,让我碰到了一个 Failure ,但是总之 CPU 很狡猾,喜欢抠字眼就是了,你没有专门给它提出来要保持顺序它说不定就会偷偷把顺序给你换了。

CPU 为什么要交换顺序呢?我在那个帖子跟贴问了一下,alpha 和 Weiton 给我提供了一些信息,我大概了解了一下。这个技术叫做“乱序执行 (Out-of-Order Execution)”,在操作系统层面上,我们有多任务,其中一个好处就是在等待磁盘等比较慢的设备反应的时候可以切换到其他任务执行,而不是一直在那里干等浪费时间,同样,在 CPU 级别,从内存取一个数据也是非常慢的,为了避免空闲等待,可以在这个时候去分派其他指令的执行,就有可能造成乱序了,不过 CPU 最后会把得到的结果按照原来的顺序排列再返回回来,所以如果没有副作用的话,从外面是看不出来 CPU 有没有乱序执行的了。

至于为什么在单核的时候就不会有 failure 呢?因为单核的时候只有一个 CPU 能执行,不同的线程执行必然需要线程切换才行,而线程切换会把所有的 memory request 都 request 掉,并清空 pipeline 等,因此 OoO 的效果在线程切换之后已经看不到了,就不可能影响到其他线程了,于是就不会产生 failure 了。

Update 2010.06.29: he da 在一年多以前指出了我这篇文章中的问题,原本准备认真看它给的信息然后再修正这篇文章的,结果一直拖了好久好久,自己平时接触的东西也离这方面越来越远,所以还是直接 quote 一下他当时给我指出的错误吧:

你的程序得到一个failure的原因不是因为乱序执行 (Out-of-Order Execution),而是writer线程运行比reader线程快很多,这样有可能 v1 加到了 2 的 32 次方,溢出变为 0 了,这个时候 v2 可能还没有加到溢出,就会大于 v1 了……我打印测试了,确实是 v1 为 0 到 20 的一个数,而 v2 这个时候还小于 4G,这个时候就会打印出 failure 了。

windows 使用 SetThreadAffinityMask 函数替代 utilBindThreadToCPU ,附件是我的测试程序。得不到 failure 的原因主要是我们使用的 intel cpu,其模式是 strongly ordered memory models 。要测试出来得使用powerpc 或者其它非 strongly ordered memory models 的 cpu。

  1. 5 Responses to “Memory Barrier”

  2. 你们没学体系结构?
    http://camino.rutgers.edu/cs505/lecture5.html

    By Jack on Nov 15, 2007

  3. 体系结构好像是大四学的。

    By pluskid on Nov 15, 2007

  4. 开始回忆啦?回到百度空间,发现乱乱的,删掉了许多分类。

    By quark on Nov 16, 2007

  5. utilBindThreadToCPU,windows下面,应该是GetProcessAffinityMask/GetProcessAffinityMask
    Linux新的kernel好像也支持类似的调用:
    sched_setaffinity.
    是看Ogre3D代码学来的。

    和这个事情有点相关的,就是Linux下面的gettimeofday, 还有那个clock在多核模式下是有bug的. 说白了也很简单,gettimeofday依赖于cpu的一个时钟计数器,多核情况下,就会出一样的问题。

    By is on Jul 13, 2008

  6. 恩,这学期学了体系结构、流水线这些东西,对 CPU 为什么会乱序执行以及 Memory Barrier 存在的必要性总算是能理解了。 :)

    By pluskid on Jul 13, 2008

Post a Comment