http://blog.sina.com.cn/s/blog_6f5b220601013zw3.html
非常好的原子操作,不用加锁:__sync_fetch_and_add
GCC 提供的原子操作
gcc从4.1.2提供了__sync_*系列的built-in函数,用于提供加减和逻辑运算的原子操作。
其声明如下:
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, ...)
这两组函数的区别在于第一组返回更新前的值,第二组返回更新后的值。
type可以是1,2,4或8字节长度的int类型,即:
int8_t / uint8_t
int16_t / uint16_t
int32_t / uint32_t
int64_t / uint64_t
后面的可扩展参数(...)用来指出哪些变量需要memory barrier,因为目前gcc实现的是full
barrier(类似于linux kernel
中的mb(),表示这个操作之前的所有内存操作不会被重排序到这个操作之后),所以可以略掉这个参数。
bool __sync_bool_compare_and_swap (type *ptr, type oldval type newval, ...)
type __sync_val_compare_and_swap (type *ptr, type oldval type newval, ...)
这两个函数提供原子的比较和交换,如果*ptr == oldval,就将newval写入*ptr,
第一个函数在相等并写入的情况下返回true.
第二个函数在返回操作之前的值。
发出一个full barrier.
关于memory
barrier,cpu会对我们的指令进行排序,一般说来会提高程序的效率,但有时候可能造成我们不希望得到的结果,举一个例子,比如我们有一个硬件设
备,它有4个寄存器,当你发出一个操作指令的时候,一个寄存器存的是你的操作指令(比如READ),两个寄存器存的是参数(比如是地址和size),最后
一个寄存器是控制寄存器,在所有的参数都设置好之后向其发出指令,设备开始读取参数,执行命令,程序可能如下:
write1(dev.register_addr,addr);
write1(dev.register_cmd,READ);
write1(dev.register_control,GO);
如果最后一条write1被换到了前几条语句之前,那么肯定不是我们所期望的,这时候我们可以在最后一条语句之前加入一个memory
barrier,强制cpu执行完前面的写入以后再执行最后一条:
write1(dev.register_size,size);
write1(dev.register_addr,addr);
write1(dev.register_cmd,READ);
__sync_synchronize();
write1(dev.register_control,GO);
memory barrier有几种类型:
acquire
barrier : 不允许将barrier之后的内存读取指令移到barrier之前(linux
kernel中的wmb())。
release
barrier : 不允许将barrier之前的内存读取指令移到barrier之后 (linux
kernel中的rmb())。
full
barrier :
以上两种barrier的合集(linux kernel中的mb())。
还有两个函数:
type __sync_lock_test_and_set (type *ptr, type value, ...)
将*ptr设为value并返回*ptr操作之前的值。
void __sync_lock_release (type *ptr, ...)
将*ptr置0
示例程序:
#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>
static int count = 0;
void *test_func(void *arg)
{
int i=0;
for(i=0;i<20000;++i){
__sync_fetch_and_add(&count,1);
}
return NULL;
}
int main(int argc, const char *argv[])
{
pthread_t id[20];
int i = 0;
for(i=0;i<20;++i){
pthread_create(&id[i],NULL,test_func,NULL);
}
for(i=0;i<20;++i){
pthread_join(id[i],NULL);
}
printf("%d\n",count);
return 0;
}
参考:
http://refspecs.freestandards.org/elf/IA64-SysV-psABI.pdf
section 7.4
2.
http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Atomic-Builtins.html#Atomic-Builtins
感谢作者:http://blog.csdn.net/i_am_jojo/article/details/7591743
最近编码需要实现多线程环境下的计数器操作,统计相关事件的次数。下面是一些学习心得和体会。不敢妄称原创,基本是学习笔记。遇到相关的引用,我会致谢。
当然我们知道,count++这种操作不是原子的。一个自加操作,本质是分成三步的:
1 从缓存取到寄存器
2 在寄存器加1
3 存入缓存。
由于时序的因素,多个线程操作同一个全局变量,会出现问题。这也是并发编程的难点。在目前多核条件下,这种困境会越来越彰显出来。
最简单的处理办法就是加锁保护,这也是我最初的解决方案。看下面的代码:
pthread_mutex_t count_lock = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_lock(&count_lock);
global_int++;
pthread_mutex_unlock(&count_lock);
后来在网上查找资料,找到了__sync_fetch_and_add系列的命令,发现这个系列命令讲的最好的一篇文章,英文好的同学可以直接去看原文。Multithreaded
simple data type access and atomic variables
__sync_fetch_and_add系列一共有十二个函数,有加/减/与/或/异或/等函数的原子性操作函数,__sync_fetch_and_add,顾名思义,现fetch,然后自加,返回的是自加以前的值。以count
=
4为例,调用__sync_fetch_and_add(&count,1),之后,返回值是4,然后,count变成了5.
有__sync_fetch_and_add,自然也就有__sync_add_and_fetch,呵呵这个的意思就很清楚了,先自加,在返回。他们哥俩的关系与i++和++i的关系是一样的。被谭浩强他老人家收过保护费的都会清楚了。
有了这个宝贝函数,我们就有新的解决办法了。对于多线程对全局变量进行自加,我们就再也不用理线程锁了。下面这行代码,和上面被pthread_mutex保护的那行代码作用是一样的,而且也是线程安全的。
__sync_fetch_and_add( &global_int, 1 );
下面是这群函数的全家福,大家看名字就知道是这些函数是干啥的了。
在用gcc编译的时候要加上选项
-march=i686
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);
需要提及的是,这个type不能够瞎搞。下面看下__sync_fetch_and_add反汇编出来的指令,
804889d: f0 83 05 50 a0 04 08 lock addl $0x1,0x804a050
我们看到了,addl前面有个lock,这行汇编指令码前面是f0开头,f0叫做指令前缀,Richard Blum
老爷子将指令前缀分成了四类,有兴趣的同学可以看下。其实我也没看懂,intel的指令集太厚了,没空看。总之老爷子解释了,lock前缀的意思是对内存区域的排他性访问。
? Lock and repeat prefixes
? Segment override and branch hint prefixes
? Operand size override prefix
? Address size override prefix
前文提到,lock是锁FSB,前端串行总线,front serial
bus,这个FSB是处理器和RAM之间的总线,锁住了它,就能阻止其他处理器或者core从RAM获取数据。当然这种操作是比较费的,只能操作小的内存可以这样做,想想我们有memcpy
,如果操作一大片内存,锁内存,那么代价就太昂贵了。所以前文提到的_sync_fetch_add_add家族,type只能是int
long ,long long(及对应unsigned类型)。
下面提供了函数,是改造的Alexander
Sundler的原文,荣誉属于他,我只是学习他的代码,稍微改动了一点点。比较了两种方式的耗时情况。呵呵咱是菜鸟,不敢枉自剽窃大师作品。向大师致敬。
#define _GNU_SOURCE
#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#include <stdlib.h>
#include <sched.h>
#include <linux/unistd.h>
#include <sys/syscall.h>
#include <errno.h>
#include<linux/types.h>
#include<time.h>
#define INC_TO 1000000 // one million...
__u64 rdtsc()
{
__u32 lo,hi;
__asm__
__volatile__
(
"rdtsc":"=a"(lo),"=d"(hi)
);
return
(__u64)hi<<32|lo;
}
int global_int = 0;
pthread_mutex_t count_lock = PTHREAD_MUTEX_INITIALIZER;
pid_t gettid( void )
{
return
syscall( __NR_gettid );
}
void *thread_routine( void *arg )
{
int i;
int proc_num
= (int)(long)arg;
__u64 begin,
end;
struct
timeval tv_begin,tv_end;
__u64
timeinterval;
cpu_set_t
set;
CPU_ZERO(
&set );
CPU_SET(
proc_num, &set );
if
(sched_setaffinity( gettid(), sizeof( cpu_set_t ),
&set ))
{
perror( "sched_setaffinity" );
return NULL;
}
begin =
rdtsc();
gettimeofday(&tv_begin,NULL);
for (i = 0;
i < INC_TO; i++)
{
//
global_int++;
__sync_fetch_and_add( &global_int, 1 );
}
gettimeofday(&tv_end,NULL);
end =
rdtsc();
timeinterval
=(tv_end.tv_sec -
tv_begin.tv_sec)*1000000
+(tv_end.tv_usec - tv_begin.tv_usec);
fprintf(stderr,"proc_num :%d,__sync_fetch_and_add
cost
%llu CPU cycle,cost %llu
us\n",
proc_num,end-begin,timeinterval);
return
NULL;
}
void *thread_routine2( void *arg )
{
int i;
int proc_num
= (int)(long)arg;
__u64 begin,
end;
struct
timeval tv_begin,tv_end;
__u64
timeinterval;
cpu_set_t
set;
CPU_ZERO(
&set );
CPU_SET(
proc_num, &set );
if
(sched_setaffinity( gettid(), sizeof( cpu_set_t ),
&set ))
{
perror( "sched_setaffinity" );
return NULL;
}
begin =
rdtsc();
gettimeofday(&tv_begin,NULL);
for(i =
0;i<INC_TO;i++)
{
pthread_mutex_lock(&count_lock);
global_int++;
pthread_mutex_unlock(&count_lock);
}
gettimeofday(&tv_end,NULL);
end =
rdtsc();
timeinterval
=(tv_end.tv_sec -
tv_begin.tv_sec)*1000000
+(tv_end.tv_usec - tv_begin.tv_usec);
fprintf(stderr,"proc_num :%d,pthread lock cost %llu
CPU
cycle,cost %llu
us\n",proc_num,end-begin
,timeinterval);
return
NULL;
}
int main()
{
int procs =
0;
int i;
pthread_t
*thrs;
//
Getting number of CPUs
procs =
(int)sysconf( _SC_NPROCESSORS_ONLN );
if (procs
< 0)
{
perror( "sysconf" );
return -1;
}
thrs =
malloc( sizeof( pthread_t ) * procs );
if (thrs ==
NULL)
{
perror( "malloc" );
return -1;
}
printf(
"Starting %d threads...\n", procs );
for (i =
0; i < procs; i++)
{
if (pthread_create( &thrs[i], NULL,
thread_routine,
(void *)(long)i ))
{
perror( "pthread_create" );
procs = i;
break;
}
}
for (i =
0; i < procs; i++)
pthread_join( thrs[i], NULL );
free(
thrs );
printf(
"After doing all the math, global_int value
is:
%d\n", global_int );
printf(
"Expected value is: %d\n", INC_TO * procs );
return
0;
}
通过我的测试发现:
Starting 4 threads...
proc_num :2,no locker cost 27049544 CPU cycle,cost 12712 us
proc_num :0,no locker cost 27506750 CPU cycle,cost 12120 us
proc_num :1,no locker cost 28499000 CPU cycle,cost 13365 us
proc_num :3,no locker cost 27193093 CPU cycle,cost 12780 us
After doing all the math, global_int value is: 1169911
Expected value is: 4000000
Starting 4 threads...
proc_num :2,__sync_fetch_and_add cost 156602056 CPU cycle,cost
73603 us
proc_num :1,__sync_fetch_and_add cost 158414764 CPU cycle,cost
74456 us
proc_num :3,__sync_fetch_and_add cost 159065888 CPU cycle,cost
74763 us
proc_num :0,__sync_fetch_and_add cost 162621399 CPU cycle,cost
76426 us
After doing all the math, global_int value is: 4000000
Expected value is: 4000000
Starting 4 threads...
proc_num :1,pthread lock cost 992586450 CPU cycle,cost 466518
us
proc_num :3,pthread lock cost 1008482114 CPU cycle,cost 473998
us
proc_num :0,pthread lock cost 1018798886 CPU cycle,cost 478840
us
proc_num :2,pthread lock cost 1019083986 CPU cycle,cost 478980
us
After doing all the math, global_int value is: 4000000
Expected value is: 4000000
1 不加锁的情况下,不能返回正确的结果
测试程序结果显示,正确结果为400万,实际为1169911.
2 线程锁和原子性自加都能返回正确的结果。
3 性能上__sync_fetch_and_add,完爆线程锁。
从测试结果上看, __sync_fetch_and_add,速度是线程锁的6~7倍