未加星标

Sequential Consistency,Cache-Coherence及Memory barrier

字体大小 | |
[系统(linux) 所属分类 系统(linux) | 发布者 店小二03 | 时间 2016 | 作者 红领巾 ] 0人收藏点击收藏

如今多核CPU在服务器中已经是标配,如何更好的发挥多核CPU进行并行计算相信是每个后端开发都会遇到的难题。这篇文章主要是梳理一下我最近学习的一些关于C++多线程编程的知识。

并发 VS 并行

提到并发编程,有很多不同的编程模型,如多进程、多线程、协程,还可以结合使用I/O多路复用技术来进行异步并发编程,由此产生了很多不同类型的并发编程技巧来解决各类场景下的问题。

其中,协程模型也称为“用户态线程”,在用户态对程序流进行切换,避免了系统上下文切换的开销,属于 并发 而不是 并行 的(协程也可以和多进程、多线程模型结合,此处不做探讨),多进程和多线程的编程模型是真正 并行 的,即多个程序流是真正同时运行的,因此可以更好的利用多核优势,由于多线程之间共用进程地址空间,所以多线程模型相对多进程模型而言可以减少一些进程间的通信开销。

多线程同步

然而,凡事有利必有弊,共用进程地址空间带来了性能上的提高必然也会产生一些复杂的问题,及引入了线程间同步的问题。多个线程如果不加保护的访问共享的变量,必然会引发严重问题,这些在线程间共享的变量被称为“ 临界区 ”,最为经典的例子就是多个线程同时对单变量执行递增操作,相信诸位都已经听到耳朵起茧,就不再展开了。

在多线程编程中,常用的同步方式是使用pthread库中提供的线程同步手段(暂不考虑C++11中提供的线程库),如互斥锁、自旋锁、信号量、条件变量等等,但这些方法不是本文的主要内容,因此也不做展开,有兴趣的同学可以自行阅读《UNIX环境高级编程》中关于多线程同步的章节。

PS:在linux内核中由于内核线程共用内核地址空间,所以内核线程之间也需要使用线程同步机制进行保护,Linux内核中所使用的几种常见同步机制分析见我之前的文章。

Lockless

到这里一切都很好,我们可以使用多线程作为并行编程手段,并且使用pthread提供的同步机制对临界区进行保护,pthread库为我们屏蔽了底层的复杂性,在我们看来多核CPU是透明的计算资源,而不需要特别为多核CPU进行太多的考虑。

然而,随着对性能的要求进一步提高,当我们需要达到更大的并发度时,pthread库提供的同步手段将成为瓶颈,因此在需要高性能的程序中往往会借助于一些lock-free的编程技术来提高程序的性能,这样的程序中不再使用pthread所提供的保护元语,必须自行处理多核CPU环境中产生的各种问题,这样不显式使用底层锁同步机制的程序我们成为是lockless的(注:lockless不是lock-free,比如常见的使用CAS操作做循环等待是lockless的,但是却不是lock-free的,lock-free是另一个重要的概念,本文中不涉及)。

什么是Cache-Coherence

那么,多核环境和单核究竟有什么不同?实际上,问题的来源是cache。我们都知道,因为CPU的运行速度比内存访问速度快很多(百倍的量级差距),所以每个CPU都有自己的cache来加速对内存的访问(局部性原理),如下图:


Sequential Consistency,Cache-Coherence及Memory barrier

这样造成的一个问题是同一份数据有可能会分布在各个CPU的cache中,和分布式系统一样,数据的副本会带来一致性问题,事实上,在同一时间,同一变量在不同的CPU上会有不同的值,如下图:


Sequential Consistency,Cache-Coherence及Memory barrier

举个例子,当CPU 0刚刚修改了内存中某处的值时,最新的值是先写入到CPU 0的局部cache中,等待cache line淘汰才会被写回内存,如果此时另一个CPU(如CPU 7)想要访问内存中同一位置的值,则不论是CPU 7的局部cache中还是内存中都没有最新值,最新值只存在于CPU 0的局部cache中,因此我们需要一个机制来保证cache在不同CPU间的一致性,这个机制就是Cache-Coherence Protocal。

MESI是一种使用最广泛的Cache-Coherence Protocal,Intel使用的MESIF就是在MESI协议基础上改进而来。为了理解原理的目的,我们只需要了解MESI协议就可以了。

MESI这四个字母分别代表了每一个cache line可能处于的四种状态:“Modified”、“Exclusive”、“Shared”和“Invalid”:

Modified :处于该状态的cache line刚刚被该CPU修改过,且该修改还没有同步到其他的CPU及内存中,这个状态的cache line是被这个CPU所“拥有”的,所以这个CPU必须负责将这个cache line写回内存或是交给其他的CPU。 Exclusive :和Modified状态很接近,区别在于CPU已经“拥有”了这个cache line,但还没有修改cache line的值,可以在任意时刻修改并不需要询问其他的CPU。 Shared :处于该状态的cache line被多个CPU所共享,所以CPU无法直接修改该cache line,只可以读取其上的值。 Invalid :这个状态是所有cache line的初始状态,表明该cache line为空,没有存储数据。

当CPU对cache line进行操作时,就会导致cache line的状态发生变化,这样的变化往往需要通过在CPU之间传递消息来完成,MESI的状态转换图如下:


Sequential Consistency,Cache-Coherence及Memory barrier

图中所列出的状态变化都值得仔细考量,为了下文叙述方便,我在这里重点描述其中一种情况:多个CPU都持有同一cache line,初始状态为“Shared”,当其中一个CPU想要修改该cache line的内容时,它向其他所有CPU发送“Invalidate”消息,其他CPU收到消息以后必须将该cache line的状态修改为“Invalid”,随后回复“Invalidate Acknowledge”消息给发送方CPU,当发送方CPU收到所有的“Invalidate Acknowledge”消息后,就可以将该cache line修改为“Exclusive”状态并执行数据修改了。

上述过程实际是一次cache line“所有权”的获取过程,其他的状态过程切换见RCU一哥书中的表述。

False sharing

在这里我们先开个小差,讨论下另外一个问题――False sharing。

如我们所见,这个cache line“所有权”的获取过程涉及到了多个CPU之间的消息通信,相比起直接在单核上进行操作一定是低效的,然而此处有一个陷阱:在我们编程时通常是以变量为思考单元的,但这里CPU之间争夺“所有权”的单元是cache line(通常为64字节),那么就会下图中的一种情况:在一个并行的程序中,一个线程不断写入变量X,另一个线程不断写入变量Y,本来是没有冲突的,但是两个变量在内存中落在了同一cache line上,这就是导致执行过程中在两个CPU之间不断发生该cache line“所有权”的争夺,导致性能的下降,这个问题就叫False sharing(名字也很直观)。


Sequential Consistency,Cache-Coherence及Memory barrier

知道了问题发生的原因,解决起来就不难了,既然是因为多个本不相干的变量落在同一cache line上产生的冲突,那么我们只要在这些变量之间添加适当的padding,使得他们落在不同的cache line上就可以了,这在GNU C中可以通过设置变量属性 __attribute__ ( ( aligned ( 64 ) ) ) 解决。

让我们写个代码来实际验证这个问题:

/* * Demo program for showing the drawback of "false sharing" * * Use it with perf! * * Compile: g++ -O2 -o false_share false_share.cpp -lpthread * Usage: perf stat -e cache-misses ./false_share <loopcount> <is_aligned> */ #include <pthread.h> #include <stdio.h> #include <stdlib.h> #include <time.h> #include <sys/time.h> #include <sys/resource.h> #define CACHE_ALIGN_SIZE 64 #define CACHE_ALIGNED __attribute__((aligned(CACHE_ALIGN_SIZE))) int gLoopCount; inline int64_tcurrent_time() { struct timeval t; if (gettimeofday(&t, NULL) < 0) { } return (static_cast<int64_t>(t.tv_sec) * static_cast<int64_t>(1000000) + static_cast<int64_t>(t.tv_usec)); } struct value { int64_tval; }; valuedata[2] CACHE_ALIGNED; struct aligned_value { int64_tval; } CACHE_ALIGNED; aligned_valuealigned_data[2] CACHE_ALIGNED; void* worker1(int64_t *val) { printf("worker1 start...\n"); volatile int64_t &v = *val; for (int i = 0; i < gLoopCount; ++i) { v += 1; } printf("worker1 exit...\n"); } // duplicate worker function for perf report void* worker2(int64_t *val) { printf("worker2 start...\n"); volatile int64_t &v = *val; for (int i = 0; i < gLoopCount; ++i) { v += 1; } printf("worker2 exit...\n"); } int main(int argc, char *argv[]) { pthread_trace_thread_1; pthread_trace_thread_2; bool is_aligned; /* Check arguments to program*/ if(argc != 3) { fprintf(stderr, "USAGE: %s <loopcount> <is_aligned>\n", argv[0]); exit(1); } /* Parse argument */ gLoopCount = atoi(argv[1]); /* Don't bother with format checking */ is_aligned = atoi(argv[2]); /* Don't bother with format checking */ printf("size of unaligned data : %d\n", sizeof(data)); printf("size of aligned data : %d\n", sizeof(aligned_data)); void *val_0, *val_1; if (is_aligned) { val_0 = (void *)&aligned_data[0].val; val_1 = (void *)&aligned_data[1].val; } else { val_0 = (void *)&data[0].val; val_1 = (void *)&data[1].val; } int64_tstart_time = current_time(); /* Start the threads */ pthread_create(&race_thread_1, NULL, (void* (*)(void*))worker1, val_0); pthread_create(&race_thread_2, NULL, (void* (*)(void*))worker2, val_1); /* Wait for the threads to end */ pthread_join(race_thread_1, NULL); pthread_join(race_thread_2, NULL); int64_tend_time = current_time(); printf("time : %d us\n", end_time - start_time); return 0; }

代码很简单,不需要太多解释,重点看下perf结果:

[[email protected]]$ perfstat -e cache-misses ./false_share 100000000 0 sizeofunaligneddata : 16 sizeofaligneddata: 128 worker2start... worker1start... worker1exit... worker2exit... time : 452451 us Performancecounterstatsfor './false_share 100000000 0': 3,105,245 cache-misses 0.455033803 secondstimeelapsed [[email protected]]$ perfstat -e cache-misses ./false_share 100000000 1 sizeofunaligneddata : 16 sizeofaligneddata: 128 worker1start... worker2start... worker1exit... worker2exit... time : 326994 us Performancecounterstatsfor './false_share 100000000 1': 27,735 cache-misses 0.329737667 secondstimeelapsed

可以看出在进行了aligned之后减少了非常多cache-misses,运行速度也加快了很多。

PS:这个代码只能定性的说明False sharing对性能是有影响的,如果想要定量的分析False sharing对性能的影响,那就需要结合所使用CPU的架构来做具体分析。

Reorder

回到正题,在有了Cache-Coherence协议之后,似乎一切看上去都很完美,即使在多核环境下,cache之间仍然维持了一致,似乎我们并不需要考虑什么?

可惜的是,事实并非如此…

CPU的设计者实在是太聪明了,为了提高CPU的性能,CPU设计者做出了非常多的优化,以至于在外界看来,似乎CPU在以完全不可理喻的方式运行…CPU是不是疯了?为了解释这一点,我们首先需要明白CPU对执行顺序的约定是怎样的.

美好的Sequential Consistency

在程序员的直觉里,不论多核与否,所有线程的执行顺序(内存读写顺序)都应该和我们源码中所写的保持一致,并且所有核看到的某个线程的执行顺序(内存读写顺序)都应该是一致的,这就是Sequential Consistency。

然而,现在的多核CPU由于性能发展的要求,采用了各种各样的手段来加快运算速度,Sequential Consistency对CPU性能的提高是一个很强的阻碍,因此现在的CPU大都选择不同程度的违背Sequential Consistency的要求来达到提高执行速度的目的,CPU所提供保障的底线是: 在单核

本文系统(linux)相关术语:linux系统 鸟哥的linux私房菜 linux命令大全 linux操作系统

分页:12
转载请注明
本文标题:Sequential Consistency,Cache-Coherence及Memory barrier
本站链接:http://www.codesec.net/view/484292.html
分享请点击:


1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责;
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性,不作出任何保证或承若;
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。
登录后可拥有收藏文章、关注作者等权限...
技术大类 技术大类 | 系统(linux) | 评论(0) | 阅读(28)