转自：http://blog.csdn.net/chen19870707/article/details/39899743
权声明：本文为博主原创文章，未经博主允许不得转载。
眉目传情之匠心独运的kfifo
-
Author：Echo Chen（陈斌）
-
Email：chenb19870707@gmail.com
-
Date：October 8th, 2014
学不考儒，务掇精华；文不按古，匠心独运。Linux kernal 鬼斧神工，博大精深，让人叹为观止，拍手叫绝。然匠心独运的设计并非扑朔迷离、盘根错节，真正的匠心独运乃辞简理博、化繁为简，在简洁中昭显优雅和智慧，kfifo就是这样一种数据结构，它就是这样简约高效，匠心独运，妙不可言，下面就跟大家一起探讨学习。
一、kfifo概述
本文分析的原代码版本 2.6.32.63 kfifo的头文件 include/linux/kfifo.h kfifo的源文件 kernel/kfifo.c kfifo是一种"First In First Out “数据结构，它采用了前面提到的环形缓冲区来实现，提供一个无边界的字节流服务。采用环形缓冲区的好处为，当一个数据元素被用掉后，其余数据元素不需要移动其存储位置，从而减少拷贝提高效率。更重要的是，kfifo采用了并行无锁技术，kfifo实现的单生产/单消费模式的共享队列是不需要加锁同步的。
1: struct kfifo {
2: unsigned char *buffer; /* the buffer holding the data */
3: unsigned int size; /* the size of the allocated buffer */
4: unsigned int in; /* data is added at offset (in % size) */
5: unsigned int out; /* data is extracted from off. (out % size) */
6: spinlock_t *lock; /* protects concurrent modifications */
7: };buffer 用于存放数据的缓存 size 缓冲区空间的大小，在初化时，将它向上圆整成2的幂 in 指向buffer中队头 out 指向buffer中的队尾 lock 如果使用不能保证任何时间最多只有一个读线程和写线程，必须使用该lock实施同步。 它的结构如图：
这看起来与普通的环形缓冲区没有什么差别，但是让人叹为观止的地方就是它巧妙的用 in 和 out 的关系和特性，处理各种操作，下面我们来详细分析。
二、kfifo内存分配和初始化
首先，看一个很有趣的函数，判断一个数是否为2的次幂，按照一般的思路，求一个数n是否为2的次幂的方法为看 n % 2 是否等于0， 我们知道“取模运算”的效率并没有 “位运算” 的效率高，有兴趣的同学可以自己做下实验。下面再验证一下这样取2的模的正确性，若n为2的次幂，则n和n-1的二进制各个位肯定不同 (如8(1000)和7(0111))，&出来的结果肯定是0；如果n不为2的次幂，则各个位肯定有相同的 (如7(0111) 和6(0110))，&出来结果肯定为0。是不是很巧妙？
1: bool is_power_of_2(unsigned long n)
2: {3: return (n != 0 && ((n & (n - 1)) == 0));
4: }再看下kfifo内存分配和初始化的代码，前面提到kfifo总是对size进行2次幂的圆整，这样的好处不言而喻，可以将kfifo->size取模运算可以转化为与运算，如下：
kfifo->in % kfifo->size 可以转化为 kfifo->in & (kfifo->size – 1)“取模运算”的效率并没有 “位运算” 的效率高还记得不，不放过任何一点可以提高效率的地方。
1: struct kfifo *kfifo_alloc(unsigned int size, gfp_t gfp_mask, spinlock_t *lock)
2: {3: unsigned char *buffer;
4: struct kfifo *ret;
5:6: /*
7: * round up to the next power of 2, since our 'let the indices
8: * wrap' technique works only in this case.
9: */
10: if (!is_power_of_2(size)) {
11: BUG_ON(size > 0x80000000);12: size = roundup_pow_of_two(size);13: }14:15: buffer = kmalloc(size, gfp_mask);16: if (!buffer)
17: return ERR_PTR(-ENOMEM);
18:19: ret = kfifo_init(buffer, size, gfp_mask, lock);20:21: if (IS_ERR(ret))
22: kfree(buffer);23:24: return ret;
25: }三、kfifo并发无锁奥秘---内存屏障
为什么kfifo实现的单生产/单消费模式的共享队列是不需要加锁同步的呢？天底下没有免费的午餐的道理人人都懂，下面我们就来看看kfifo实现并发无锁的奥秘。
我们知道 编译器编译源代码时，会将源代码进行优化，将源代码的指令进行重排序，以适合于CPU的并行执行。然而，内核同步必须避免指令重新排序，优化屏障（Optimization barrier）避免编译器的重排序优化操作，保证编译程序时在优化屏障之前的指令不会在优化屏障之后执行。
举个例子，如果多核CPU执行以下程序：
1: a = 1;2: b = a + 1;3: assert(b == 2);假设初始时a和b的值都是0，a处于CPU1-cache中，b处于CPU0-cache中。如果按照下面流程执行这段代码：
1 CPU0执行a=1;
2 因为a在CPU1-cache中，所以CPU0发送一个read invalidate消息来占有数据
3 CPU0将a存入store buffer
4 CPU1接收到read invalidate消息，于是它传递cache-line，并从自己的cache中移出该cache-line
5 CPU0开始执行b=a+1;
6 CPU0接收到了CPU1传递来的cache-line，即“a=0”
7 CPU0从cache中读取a的值，即“0”
8 CPU0更新cache-line，将store buffer中的数据写入，即“a=1”
9 CPU0使用读取到的a的值“0”，执行加1操作，并将结果“1”写入b（b在CPU0-cache中，所以直接进行）
10 CPU0执行assert(b == 2); 失败软件可通过读写屏障强制内存访问次序。读写屏障像一堵墙，所有在设置读写屏障之前发起的内存访问，必须先于在设置屏障之后发起的内存访问之前完成，确保内存访问按程序的顺序完成。Linux内核提供的内存屏障API函数说明如下表。内存屏障可用于多处理器和单处理器系统，如果仅用于多处理器系统，就使用smp_xxx函数，在单处理器系统上，它们什么都不要。
smp_rmb
适用于多处理器的读内存屏障。 smp_wmb
适用于多处理器的写内存屏障。 smp_mb
适用于多处理器的内存屏障。 如果对上述代码加上内存屏障,就能保证在CPU0取a时，一定已经设置好了a = 1:
这里只是简单介绍了内存屏障的概念，如果想对内存屏障有进一步理解,请参考我的译文《为什么需要内存屏障》。1: void foo(void)
2: {3: a = 1;4: smp_wmb();5: b = a + 1;6: }四、kfifo的入队__kfifo_put和出队__kfifo_get操作
__kfifo_put是入队操作，它先将数据放入buffer中，然后移动in的位置，其源代码如下：
1: unsigned int __kfifo_put(struct kfifo *fifo,
2: const unsigned char *buffer, unsigned int len)
3: {4: unsigned int l;
5:6: len = min(len, fifo->size - fifo->in + fifo->out);7:8: /*
9: * Ensure that we sample the fifo->out index -before- we
10: * start putting bytes into the kfifo.
11: */
12:13: smp_mb();14:15: /* first put the data starting from fifo->in to buffer end */
16: l = min(len, fifo->size - (fifo->in & (fifo->size - 1)));17: memcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l);18:19: /* then put the rest (if any) at the beginning of the buffer */
20: memcpy(fifo->buffer, buffer + l, len - l);21:22: /*
23: * Ensure that we add the bytes to the kfifo -before-
24: * we update the fifo->in index.
25: */
26:27: smp_wmb();28:29: fifo->in += len;30:31: return len;
32: }6行，环形缓冲区的剩余容量为fifo->size - fifo->in + fifo->out，让写入的长度取len和剩余容量中较小的，避免写越界；13行，加内存屏障，保证在开始放入数据之前，fifo->out取到正确的值（另一个CPU可能正在改写out值）16行，前面讲到fifo->size已经2的次幂圆整，而且kfifo->in % kfifo->size 可以转化为 kfifo->in & (kfifo->size – 1)，所以fifo->size - (fifo->in & (fifo->size - 1)) 即位 fifo->in 到 buffer末尾所剩余的长度，l取len和剩余长度的最小值，即为需要拷贝l 字节到fifo->buffer + fifo->in的位置上。17行，拷贝l 字节到fifo->buffer + fifo->in的位置上，如果l = len，则已拷贝完成，第20行len – l 为0，将不执行，如果l = fifo->size - (fifo->in & (fifo->size - 1)) ，则第20行还需要把剩下的 len – l 长度拷贝到buffer的头部。27行，加写内存屏障，保证in 加之前，memcpy的字节已经全部写入buffer，如果不加内存屏障，可能数据还没写完，另一个CPU就来读数据，读到的缓冲区内的数据不完全，因为读数据是通过 in – out 来判断的。29行，注意这里 只是用了 fifo->in += len而未取模，这就是kfifo的设计精妙之处，这里用到了unsigned int的溢出性质，当in 持续增加到溢出时又会被置为0，这样就节省了每次in向前增加都要取模的性能，锱铢必较，精益求精，让人不得不佩服。__kfifo_get是出队操作，它从buffer中取出数据，然后移动out的位置，其源代码如下：1: unsigned int __kfifo_get(struct kfifo *fifo,
2: unsigned char *buffer, unsigned int len)
3: {4: unsigned int l;
5:6: len = min(len, fifo->in - fifo->out);7:8: /*
9: * Ensure that we sample the fifo->in index -before- we
10: * start removing bytes from the kfifo.
11: */
12:13: smp_rmb();14:15: /* first get the data from fifo->out until the end of the buffer */
16: l = min(len, fifo->size - (fifo->out & (fifo->size - 1)));17: memcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l);18:19: /* then get the rest (if any) from the beginning of the buffer */
20: memcpy(buffer + l, fifo->buffer, len - l);21:22: /*
23: * Ensure that we remove the bytes from the kfifo -before-
24: * we update the fifo->out index.
25: */
26:27: smp_mb();28:29: fifo->out += len;30:31: return len;
32: }6行，可去读的长度为fifo->in – fifo->out，让读的长度取len和剩余容量中较小的，避免读越界；
13行，加读内存屏障，保证在开始取数据之前，fifo->in取到正确的值（另一个CPU可能正在改写in值）
16行，前面讲到fifo->size已经2的次幂圆整，而且kfifo->out % kfifo->size 可以转化为 kfifo->out & (kfifo->size – 1)，所以fifo->size - (fifo->out & (fifo->size - 1)) 即位 fifo->out 到 buffer末尾所剩余的长度，l取len和剩余长度的最小值，即为从fifo->buffer + fifo->in到末尾所要去读的长度。
17行，从fifo->buffer + fifo->out的位置开始读取l长度，如果l = len，则已读取完成，第20行len – l 为0，将不执行，如果l =fifo->size - (fifo->out & (fifo->size - 1)) ，则第20行还需从buffer头部读取 len – l 长。27行，加内存屏障，保证在修改out前，已经从buffer中取走了数据，如果不加屏障，可能先执行了增加out的操作，数据还没取完，令一个CPU可能已经往buffer写数据，将数据破坏，因为写数据是通过fifo->size - (fifo->in & (fifo->size - 1))来判断的 。29行，注意这里 只是用了 fifo->out += len 也未取模，同样unsigned int的溢出性质，当out 持续增加到溢出时又会被置为0，如果in先溢出，出现 in < out 的情况，那么 in – out 为负数（又将溢出），in – out 的值还是为buffer中数据的长度。这里图解一下 in 先溢出的情况，size = 64， 写入前 in = 4294967291， out = 4294967279 ，数据 in – out = 12;写入 数据16个字节，则 in + 16 = 4294967307，溢出为 11，此时 in – out = –4294967268，溢出为28，数据长度仍然正确， 由此可见，在这种特殊情况下，这种计算仍然正确，是不是让人叹为观止，妙不可言？五、扩展
kfifo设计精巧，妙不可言，但主要为内核提供服务，内存屏障函数也主要为内核提供服务，并未开放出来，但是我们学习到了这种设计巧妙之处，就可以依葫芦画瓢，写出自己的并发无锁环形缓冲区，这将在下篇文章中给出，至于内存屏障函数的问题，好在gcc 4.2以上的版本都内置提供__sync_synchronize()这类的函数，效果相差不多。《眉目传情之并发无锁环形队列的实现》给出自己的并发无锁的实现，有兴趣的朋友可以参考一下。
Reference
1.http://blog.csdn.net/xujianqun/article/details/7800813
2.http://zh.wikipedia.org/wiki/%E7%92%B0%E5%BD%A2%E7%B7%A9%E8%A1%9D%E5%8D%80#.E7.94.A8.E6.B3.95
3.http://blog.csdn.net/linyt/article/details/5764312
-
Echo Chen：Blog.csdn.net/chen19870707
权声明：本文为博主原创文章，未经博主允许不得转载。
眉目传情之匠心独运的kfifo
-
Author：Echo Chen（陈斌）
-
Email：chenb19870707@gmail.com
-
Date：October 8th, 2014
学不考儒，务掇精华；文不按古，匠心独运。Linux kernal 鬼斧神工，博大精深，让人叹为观止，拍手叫绝。然匠心独运的设计并非扑朔迷离、盘根错节，真正的匠心独运乃辞简理博、化繁为简，在简洁中昭显优雅和智慧，kfifo就是这样一种数据结构，它就是这样简约高效，匠心独运，妙不可言，下面就跟大家一起探讨学习。
一、kfifo概述
本文分析的原代码版本 2.6.32.63 kfifo的头文件 include/linux/kfifo.h kfifo的源文件 kernel/kfifo.c kfifo是一种"First In First Out “数据结构，它采用了前面提到的环形缓冲区来实现，提供一个无边界的字节流服务。采用环形缓冲区的好处为，当一个数据元素被用掉后，其余数据元素不需要移动其存储位置，从而减少拷贝提高效率。更重要的是，kfifo采用了并行无锁技术，kfifo实现的单生产/单消费模式的共享队列是不需要加锁同步的。
1: struct kfifo {
2: unsigned char *buffer; /* the buffer holding the data */
3: unsigned int size; /* the size of the allocated buffer */
4: unsigned int in; /* data is added at offset (in % size) */
5: unsigned int out; /* data is extracted from off. (out % size) */
6: spinlock_t *lock; /* protects concurrent modifications */
7: };buffer 用于存放数据的缓存 size 缓冲区空间的大小，在初化时，将它向上圆整成2的幂 in 指向buffer中队头 out 指向buffer中的队尾 lock 如果使用不能保证任何时间最多只有一个读线程和写线程，必须使用该lock实施同步。 它的结构如图：
这看起来与普通的环形缓冲区没有什么差别，但是让人叹为观止的地方就是它巧妙的用 in 和 out 的关系和特性，处理各种操作，下面我们来详细分析。
二、kfifo内存分配和初始化
首先，看一个很有趣的函数，判断一个数是否为2的次幂，按照一般的思路，求一个数n是否为2的次幂的方法为看 n % 2 是否等于0， 我们知道“取模运算”的效率并没有 “位运算” 的效率高，有兴趣的同学可以自己做下实验。下面再验证一下这样取2的模的正确性，若n为2的次幂，则n和n-1的二进制各个位肯定不同 (如8(1000)和7(0111))，&出来的结果肯定是0；如果n不为2的次幂，则各个位肯定有相同的 (如7(0111) 和6(0110))，&出来结果肯定为0。是不是很巧妙？
1: bool is_power_of_2(unsigned long n)
2: {3: return (n != 0 && ((n & (n - 1)) == 0));
4: }再看下kfifo内存分配和初始化的代码，前面提到kfifo总是对size进行2次幂的圆整，这样的好处不言而喻，可以将kfifo->size取模运算可以转化为与运算，如下：
kfifo->in % kfifo->size 可以转化为 kfifo->in & (kfifo->size – 1)“取模运算”的效率并没有 “位运算” 的效率高还记得不，不放过任何一点可以提高效率的地方。
1: struct kfifo *kfifo_alloc(unsigned int size, gfp_t gfp_mask, spinlock_t *lock)
2: {3: unsigned char *buffer;
4: struct kfifo *ret;
5:6: /*
7: * round up to the next power of 2, since our 'let the indices
8: * wrap' technique works only in this case.
9: */
10: if (!is_power_of_2(size)) {
11: BUG_ON(size > 0x80000000);12: size = roundup_pow_of_two(size);13: }14:15: buffer = kmalloc(size, gfp_mask);16: if (!buffer)
17: return ERR_PTR(-ENOMEM);
18:19: ret = kfifo_init(buffer, size, gfp_mask, lock);20:21: if (IS_ERR(ret))
22: kfree(buffer);23:24: return ret;
25: }三、kfifo并发无锁奥秘---内存屏障
为什么kfifo实现的单生产/单消费模式的共享队列是不需要加锁同步的呢？天底下没有免费的午餐的道理人人都懂，下面我们就来看看kfifo实现并发无锁的奥秘。
我们知道 编译器编译源代码时，会将源代码进行优化，将源代码的指令进行重排序，以适合于CPU的并行执行。然而，内核同步必须避免指令重新排序，优化屏障（Optimization barrier）避免编译器的重排序优化操作，保证编译程序时在优化屏障之前的指令不会在优化屏障之后执行。
举个例子，如果多核CPU执行以下程序：
1: a = 1;2: b = a + 1;3: assert(b == 2);假设初始时a和b的值都是0，a处于CPU1-cache中，b处于CPU0-cache中。如果按照下面流程执行这段代码：
1 CPU0执行a=1;
2 因为a在CPU1-cache中，所以CPU0发送一个read invalidate消息来占有数据
3 CPU0将a存入store buffer
4 CPU1接收到read invalidate消息，于是它传递cache-line，并从自己的cache中移出该cache-line
5 CPU0开始执行b=a+1;
6 CPU0接收到了CPU1传递来的cache-line，即“a=0”
7 CPU0从cache中读取a的值，即“0”
8 CPU0更新cache-line，将store buffer中的数据写入，即“a=1”
9 CPU0使用读取到的a的值“0”，执行加1操作，并将结果“1”写入b（b在CPU0-cache中，所以直接进行）
10 CPU0执行assert(b == 2); 失败软件可通过读写屏障强制内存访问次序。读写屏障像一堵墙，所有在设置读写屏障之前发起的内存访问，必须先于在设置屏障之后发起的内存访问之前完成，确保内存访问按程序的顺序完成。Linux内核提供的内存屏障API函数说明如下表。内存屏障可用于多处理器和单处理器系统，如果仅用于多处理器系统，就使用smp_xxx函数，在单处理器系统上，它们什么都不要。
smp_rmb
适用于多处理器的读内存屏障。 smp_wmb
适用于多处理器的写内存屏障。 smp_mb
适用于多处理器的内存屏障。 如果对上述代码加上内存屏障,就能保证在CPU0取a时，一定已经设置好了a = 1:
这里只是简单介绍了内存屏障的概念，如果想对内存屏障有进一步理解,请参考我的译文《为什么需要内存屏障》。1: void foo(void)
2: {3: a = 1;4: smp_wmb();5: b = a + 1;6: }四、kfifo的入队__kfifo_put和出队__kfifo_get操作
__kfifo_put是入队操作，它先将数据放入buffer中，然后移动in的位置，其源代码如下：
1: unsigned int __kfifo_put(struct kfifo *fifo,
2: const unsigned char *buffer, unsigned int len)
3: {4: unsigned int l;
5:6: len = min(len, fifo->size - fifo->in + fifo->out);7:8: /*
9: * Ensure that we sample the fifo->out index -before- we
10: * start putting bytes into the kfifo.
11: */
12:13: smp_mb();14:15: /* first put the data starting from fifo->in to buffer end */
16: l = min(len, fifo->size - (fifo->in & (fifo->size - 1)));17: memcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l);18:19: /* then put the rest (if any) at the beginning of the buffer */
20: memcpy(fifo->buffer, buffer + l, len - l);21:22: /*
23: * Ensure that we add the bytes to the kfifo -before-
24: * we update the fifo->in index.
25: */
26:27: smp_wmb();28:29: fifo->in += len;30:31: return len;
32: }6行，环形缓冲区的剩余容量为fifo->size - fifo->in + fifo->out，让写入的长度取len和剩余容量中较小的，避免写越界；13行，加内存屏障，保证在开始放入数据之前，fifo->out取到正确的值（另一个CPU可能正在改写out值）16行，前面讲到fifo->size已经2的次幂圆整，而且kfifo->in % kfifo->size 可以转化为 kfifo->in & (kfifo->size – 1)，所以fifo->size - (fifo->in & (fifo->size - 1)) 即位 fifo->in 到 buffer末尾所剩余的长度，l取len和剩余长度的最小值，即为需要拷贝l 字节到fifo->buffer + fifo->in的位置上。17行，拷贝l 字节到fifo->buffer + fifo->in的位置上，如果l = len，则已拷贝完成，第20行len – l 为0，将不执行，如果l = fifo->size - (fifo->in & (fifo->size - 1)) ，则第20行还需要把剩下的 len – l 长度拷贝到buffer的头部。27行，加写内存屏障，保证in 加之前，memcpy的字节已经全部写入buffer，如果不加内存屏障，可能数据还没写完，另一个CPU就来读数据，读到的缓冲区内的数据不完全，因为读数据是通过 in – out 来判断的。29行，注意这里 只是用了 fifo->in += len而未取模，这就是kfifo的设计精妙之处，这里用到了unsigned int的溢出性质，当in 持续增加到溢出时又会被置为0，这样就节省了每次in向前增加都要取模的性能，锱铢必较，精益求精，让人不得不佩服。__kfifo_get是出队操作，它从buffer中取出数据，然后移动out的位置，其源代码如下：1: unsigned int __kfifo_get(struct kfifo *fifo,
2: unsigned char *buffer, unsigned int len)
3: {4: unsigned int l;
5:6: len = min(len, fifo->in - fifo->out);7:8: /*
9: * Ensure that we sample the fifo->in index -before- we
10: * start removing bytes from the kfifo.
11: */
12:13: smp_rmb();14:15: /* first get the data from fifo->out until the end of the buffer */
16: l = min(len, fifo->size - (fifo->out & (fifo->size - 1)));17: memcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l);18:19: /* then get the rest (if any) from the beginning of the buffer */
20: memcpy(buffer + l, fifo->buffer, len - l);21:22: /*
23: * Ensure that we remove the bytes from the kfifo -before-
24: * we update the fifo->out index.
25: */
26:27: smp_mb();28:29: fifo->out += len;30:31: return len;
32: }6行，可去读的长度为fifo->in – fifo->out，让读的长度取len和剩余容量中较小的，避免读越界；
13行，加读内存屏障，保证在开始取数据之前，fifo->in取到正确的值（另一个CPU可能正在改写in值）
16行，前面讲到fifo->size已经2的次幂圆整，而且kfifo->out % kfifo->size 可以转化为 kfifo->out & (kfifo->size – 1)，所以fifo->size - (fifo->out & (fifo->size - 1)) 即位 fifo->out 到 buffer末尾所剩余的长度，l取len和剩余长度的最小值，即为从fifo->buffer + fifo->in到末尾所要去读的长度。
17行，从fifo->buffer + fifo->out的位置开始读取l长度，如果l = len，则已读取完成，第20行len – l 为0，将不执行，如果l =fifo->size - (fifo->out & (fifo->size - 1)) ，则第20行还需从buffer头部读取 len – l 长。27行，加内存屏障，保证在修改out前，已经从buffer中取走了数据，如果不加屏障，可能先执行了增加out的操作，数据还没取完，令一个CPU可能已经往buffer写数据，将数据破坏，因为写数据是通过fifo->size - (fifo->in & (fifo->size - 1))来判断的 。29行，注意这里 只是用了 fifo->out += len 也未取模，同样unsigned int的溢出性质，当out 持续增加到溢出时又会被置为0，如果in先溢出，出现 in < out 的情况，那么 in – out 为负数（又将溢出），in – out 的值还是为buffer中数据的长度。这里图解一下 in 先溢出的情况，size = 64， 写入前 in = 4294967291， out = 4294967279 ，数据 in – out = 12;写入 数据16个字节，则 in + 16 = 4294967307，溢出为 11，此时 in – out = –4294967268，溢出为28，数据长度仍然正确， 由此可见，在这种特殊情况下，这种计算仍然正确，是不是让人叹为观止，妙不可言？五、扩展
kfifo设计精巧，妙不可言，但主要为内核提供服务，内存屏障函数也主要为内核提供服务，并未开放出来，但是我们学习到了这种设计巧妙之处，就可以依葫芦画瓢，写出自己的并发无锁环形缓冲区，这将在下篇文章中给出，至于内存屏障函数的问题，好在gcc 4.2以上的版本都内置提供__sync_synchronize()这类的函数，效果相差不多。《眉目传情之并发无锁环形队列的实现》给出自己的并发无锁的实现，有兴趣的朋友可以参考一下。
Reference
1.http://blog.csdn.net/xujianqun/article/details/7800813
2.http://zh.wikipedia.org/wiki/%E7%92%B0%E5%BD%A2%E7%B7%A9%E8%A1%9D%E5%8D%80#.E7.94.A8.E6.B3.95
3.http://blog.csdn.net/linyt/article/details/5764312
-
Echo Chen：Blog.csdn.net/chen19870707
