c|C/C++ -- 编程中的内存屏障(Memory Barriers) 编程|little|tricks|webkit|c++

http://blog.csdn.net/gugemichael/article/details/8207519

http://blog.csdn.net/gugemichael/article/details/8237891

C/C++ -- 编程中的内存屏障(Memory Barriers) (1)
分类： C/C++ 代码技巧 2012-11-21 14:45 118人阅读评论(0) 收藏举报明天就要transfor去做检索引擎了，今天闲下来了，更新一下博客哈。之前 @高V 同学对本人之前《代码技巧及优化(c/c++)》的文章第六条，有关cache命中和cpu流水优化比较感兴趣，也提出了一些他的看法，今天，我就细化的说一下某些编程的点 -- 内存屏障，以及内存屏障对代码的影响。
OK，首先来说一下什么是"内存屏障"，可以先看一下官方式的说法 http://www.kernel.org/doc/Documentation/memory-barriers.txt，内存屏障其实就是因为编译器优化和CPU对寄存器和cache的使用，导致对内存的操作不能够及时的反映出来，比如cpu写入后，读出来的值可能是旧的内容。举个例子，对一个变量赋值然后读出它的值这一看似“原子”的操作，因为内存是没有ALU计算单元的，所以内存没有计算的能力。而CPU一般情况下是不直接读写内存的(emmintrin.h应用例外)，所以这一个过程可以看作(编译器优化后)：
读取内存数据到cache -->CPU读取cache/寄存器-->CPU的计算-->将结果写入cache/寄存器-->写回数据到内存
有人可能会问，为什么要这么麻烦，因为是编译器优化和CPU优化的结果，内存的时延比CPU高的多，是10ns级别，所以会通过读写寄存器或拆cache优化。这有可能导致一个问题，cache中的数据和内存实际的数据不一致，当多线程情况下，有可能会读"脏数据"，或者带来线程执行结果不一致。这就是所谓的“内存屏障”(但不仅限于此case)。
网上有几篇文章提到的《独辟蹊径品内核》中的代码，本人写了一个近似版本如下：

[cpp]view plain copy print ?

include
#include
#include
#include
// global variable
int flag=1;
void* wait(void *context){
while (flag) {
printf("continue\n");
sleep(1);
}
}
void wakeup(){
flag=0;
}
int main(int argc, char *argv[])
{
pthread_t pid = 0;
pthread_create(&pid,NULL,wait,NULL);
sleep(3);
wakeup();
printf("Done\n");
getchar();
}

按照书中的说法，flag是被其他线程意外修改的话。while循环会被编译器优化，编译器在发现wait函数里并没有修改flag，所以就会对flag进行cache，放在eax寄存器中，内存中的flag实体如果被修改，eax寄存器不会感知。自己试了一下，在没有优化和Gcc O2的情况下程序正常跳出了循环，可能是因为cpu或者linux新版内核或者gcc的新编译特性所致(如果哪位同学了解，可以留言哈)。之后会跟进这个问题，如果有发现，我会贴出来哈。
其实，通过gcc -S看到汇编过程的中间汇编代码也可以看出写东西：

[cpp]view plain copy print ?

wait:
.LFB46:
.cfi_startproc
subq$8, %rsp
.cfi_def_cfa_offset 16
movlflag(%rip), %edx
testl%edx, %edx
je.L4
.p2align 4,,10
.p2align 3
.L5:
movl$.LC0, %edi
callputs
movl$1, %edi
callsleep
"color:#ff6600; ">movlflag(%rip), %eax
testl%eax, %eax
jne .L5
.L4:
addq$8, %rsp
.cfi_def_cfa_offset 8
ret
.cfi_endproc
.LFE46:
.sizewait, .-wait
.p2align 4,,15
.globlwakeup
.typewakeup, @function

(我不是汇编大牛，错了别炮轰哈)，其中标红的语句16~18行可以看出，循环只是检测eax寄存器是不是0(不太熟悉汇编的朋友可能会为什么test %eax,%eax，这只是一个优化因为与操作比cmp要快)，可以看出，确实是在不断的读寄存器而不是内存。
到此，大家对“内存屏障”估计也有了一个初步的认识，内存屏障主要分三类：编译器优化(如上case) / 缓存优化 / CPU乱序执行(后面文章会提到)
大家可能会问，那岂不这样会造成很多问题。其实不一定，据本人的知识范围，大部分内存屏障导致的问题都出现在内核态，用户态需要注意的方面不多。而且用户也有相应的解决方案，最简单的就是锁机制，还有volatile关键字，可以把可能出现的cache读脏的数据volatile int tmp = 0; 这样每次操作都会从内存获取。
之后的文章会深入一下“内存屏障”和CPU乱序的问题。缓存优化导致的内存屏障，基本在新的硬件上得到了比较好的解决，而且在用户态下基本感知不到。只要大家合适的用好多线程的锁机制和volatile的正确运用即可。

C/C++ -- 编程中的内存屏障(Memory Barriers) (2)
分类： C/C++ 2012-11-29 12:47 213人阅读评论(0) 收藏举报在前面的文章里，主要介绍了一下内存屏障的基本认识，和基本原理。本文针对之前的思路继续聊一聊该如何处理相应的问题，以及一些多线程程序编程的技巧。

【c|C/C++ -- 编程中的内存屏障(Memory Barriers)】

1.Volatile关键字
2.Linux pthread线程锁
3.Linux gcc 4.2之后的__sync_fetch_and_add
4.双Buffer实现Lock free无锁
4.多读一写数据结构实现Lock free无锁

1. 在上篇文章中，提到了c/c++里的volatitle关键字，这个关键字的官方解释如下： "就象大家更熟悉的const一样，volatile是一个类型修饰符（type specifier）。它是被设计用来修饰被不同线程访问和修改的变量。如果没有volatile，基本上会导致这样的结果：要么无法编写多线程程序，要么编译器失去大量优化的机会。"--- 摘自《百度百科》其核心旨意其实就是防止编译器对其进行优化(可以预防上文中提到的编译器导致的内存屏障)，也就是每次cpu要获取一个变量，都要去内存中重新读取，而不会还缓存在自己的Cache中。应用的场景就例如while(!stop)这种大量执行判断的时候，每次都会去内存读取真实的值，而写入变量值的时候，也会写到内存地址中。但这样会组织编译器的优化，对这个变量的读取写入会比较慢(相对CPU的ns级别来说)。
2. 如果想彻底避免多线程之间的同步问题，或者临界区(多线程同时访问的集合)中不一定是一个变量，可能是一段代码一些逻辑，那么这时候，“锁”就会派上用场了： “锁”的理念就是对临界区上一把“ 排他性”的标记，其他线程运行到这里时候，如果想获取同一把锁就要阻塞等待。Linux中的锁主要分为：pthread_mutex互斥锁/pthread_wrlock读写锁/pthread_spinlock自旋锁，几个的异同可以参考本人另外一篇文章《Linux锁的适用场景》。这样就可以对其间的代码访问进行同步，如： [cpp]view plain copy print ?

pthread_mutex_t lock;
pthread_mutex_init(&lock,NULL);
pthread_mutex_lock(&lock);
g_count++;
pthread_mutex_unlock(&lock);

其中的 g_count++并不是原子操作，可以拆分成三步，即： 取值->+1->写回值。经过加锁以后即可实现同步。 Linux的“锁”，是一种强制性质“悲观锁”，也就是锁实现强制的，很容易导致“死锁”。并且性能不好，如果多个线程里访问临界区过多，锁过多的情况下，反而不如单线程的性能(此结论因项目环境而言)。所以单线程环境中必须去锁， 在多线程环境下要尽量少锁，要尽量缩短lock->unlock中间的代码和时间。
3. 如果项目使用的编译器是gcc 4.2以上(可通过gcc -v查看)，那么编译器内置了一种对atomic_t原子指令的支持： [cpp]view plain copy print ?

type __sync_fetch_and_add (type *ptr, type value);
type __sync_fetch_and_sub (type *ptr, type value);
type __sync_fetch_and_or (type *ptr, type value);
type __sync_fetch_and_and (type *ptr, type value);
type __sync_fetch_and_xor (type *ptr, type value);
type __sync_fetch_and_nand (type *ptr, type value);
type __sync_add_and_fetch (type *ptr, type value);
type __sync_sub_and_fetch (type *ptr, type value);
type __sync_or_and_fetch (type *ptr, type value);
type __sync_and_and_fetch (type *ptr, type value);
type __sync_xor_and_fetch (type *ptr, type value);
type __sync_nand_and_fetch (type *ptr, type value);

这些 Gcc内置函数可以实现对int,long,long long基本类型的 + / - / 前置++ / 后置++ / & / ^ / | / -- 等基本操作，比如操作一个全局计数器递增，就可以用: [cpp]view plain copy print ?

__sync_fetch_and_add (&globel,1);

实现原子操作，其内部不是用pthread等锁来实现的，而是直接用了lock的汇编指令来实现，汇编了一下上面的代码： [cpp]view plain copy print ?

leal40(%esp), %eax
lock addl$1, (%eax)
.loc 3 353 0
movl40(%esp), %edx
movl$.LC7, %eax

可以看出，这是靠底层CPU指令来支持的(有文章称intel对此支持比较好，AMD不好)。有资料现实，同样递增计数器，使用这种内置的支持比pthread_mutex的锁支持要快5~6倍(出于篇幅，这里本人就不做测试了)。写多线程的程序其实有的时候，可以通过代码技巧和算法来避免“锁”和“同步”，下面就来介绍一个lock free(无锁)的技巧。
4.双Buffer切换实现Lock Free ：试想一个这样的场景，有两个线程，线程A负责处理用户的请求，相应用户请求，其间要从线程B的缓冲区获取一些数据，线程B的缓冲区是一块内存，这块内存定时或者不间断会更新一次，这块内存就成为了两个线程的临界区(线程B刷新此内存时，线程A可能正在读取)。按照常规的做法，我们可能通过加锁来避免同时访问，但这样的话，因为这块内存可能没秒被访问100次，而30s更新一次，这样的话，每次访问都加锁和解锁，会带来很多无用功，性能也会下降。所以我们这里采用一种优化策略： 双Buffer切换。顾名思义，就是有两个同样结构的内存块，同一时刻只有一个内存块提供服务，如果发生了更新或写入，则把新数据放在另一个内存块做，等到做完了，通过"指针"(此处的指针泛指指向资源的句柄)改变指向，指向新的内存块，即完成了切换，原内存块在新内存块完之前，仍然提供服务。
5. 对于一些多读一写的数据结构，这里用LinkLisk链表来举例：多个线程读一个LinkList，后台有个线程会根据数据更新来写这个LinkList，也可以做到lock free。首先，拿插入来举例，插入的顺序决定了是否lock free。有两种情况： 一、先修改前面节点的next指针，再把新节点的next指针指向原来节点的下一个： [cpp]view plain copy print ?

node_t* tmp = pre_node->next;
pre_node->next = new_node;
new_node->next = tmp;

这里存在的问题就是，修改完前驱节点时，另一个线程介入了，会根据新的链接关系，走到这个新节点，而新节点的next却是NULL，导致了不同步。
二，可以先修改新节点的next，然后修改原节点的next即可，不会出现访问异常。
类比这种方法，也可以推广到Hash表的冲突拉链中。所以，如果我们的上下文是多读一写的，就可以通过适当的编程技巧来避免过度的同步。