Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3835655
  • 博文数量: 146
  • 博客积分: 3918
  • 博客等级: 少校
  • 技术积分: 8584
  • 用 户 组: 普通用户
  • 注册时间: 2010-10-17 13:52
个人简介

个人微薄: weibo.com/manuscola

文章分类

全部博文(146)

文章存档

2016年(3)

2015年(2)

2014年(5)

2013年(42)

2012年(31)

2011年(58)

2010年(5)

分类: LINUX

2011-11-12 11:07:40

      最近编码需要实现多线程环境下的计数器操作,统计相关事件的次数。下面是一些学习心得和体会。不敢妄称原创,基本是学习笔记。遇到相关的引用,我会致谢。
    当然我们知道,count++这种操作不是原子的。一个自加操作,本质是分成三步的:
     1 从缓存取到寄存器
     2 在寄存器加1
     3 存入缓存。
    由于时序的因素,多个线程操作同一个全局变量,会出现问题。这也是并发编程的难点。在目前多核条件下,这种困境会越来越彰显出来。
    最简单的处理办法就是加锁保护,这也是我最初的解决方案。看下面的代码:
  1.       pthread_mutex_t count_lock = PTHREAD_MUTEX_INITIALIZER;

  2.       pthread_mutex_lock(&count_lock);
  3.       global_int++;
  4.       pthread_mutex_unlock(&count_lock);
    后来在网上查找资料,找到了__sync_fetch_and_add系列的命令,发现这个系列命令讲的最好的一篇文章,英文好的同学可以直接去看原文。

     __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保护的那行代码作用是一样的,而且也是线程安全的。

  1. __sync_fetch_and_add( &global_int, 1 );
    下面是这群函数的全家福,大家看名字就知道是这些函数是干啥的了。
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反汇编出来的指令,
  1. 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的原文,荣誉属于他,我只是学习他的代码,稍微改动了一点点。比较了两种方式的耗时情况。呵呵咱是菜鸟,不敢枉自剽窃大师作品。向大师致敬。
  1. #define _GNU_SOURCE

  2. #include <stdio.h>
  3. #include <pthread.h>
  4. #include <unistd.h>
  5. #include <stdlib.h>
  6. #include <sched.h>
  7. #include <linux/unistd.h>
  8. #include <sys/syscall.h>
  9. #include <errno.h>
  10. #include<linux/types.h>
  11. #include<time.h>

  12. #define INC_TO 1000000 // one million...

  13. __u64 rdtsc()
  14. {
  15.   __u32 lo,hi;

  16.     __asm__ __volatile__
  17.     (
  18.      "rdtsc":"=a"(lo),"=d"(hi)
  19.     );

  20.     return (__u64)hi<<32|lo;    
  21. }



  22. int global_int = 0;
  23. pthread_mutex_t count_lock = PTHREAD_MUTEX_INITIALIZER;


  24. pid_t gettid( void )
  25. {
  26.     return syscall( __NR_gettid );
  27. }

  28. void *thread_routine( void *arg )
  29. {
  30.     int i;
  31.     int proc_num = (int)(long)arg;
  32.     __u64 begin, end;
  33.     struct timeval tv_begin,tv_end;
  34.     __u64 timeinterval;
  35.     cpu_set_t set;

  36.     CPU_ZERO( &set );
  37.     CPU_SET( proc_num, &set );

  38.     if (sched_setaffinity( gettid(), sizeof( cpu_set_t ), &set ))
  39.     {
  40.         perror( "sched_setaffinity" );
  41.         return NULL;
  42.     }

  43.     begin = rdtsc();
  44.     gettimeofday(&tv_begin,NULL);
  45.     for (i = 0; i < INC_TO; i++)
  46.     {
  47. //     global_int++;
  48.         __sync_fetch_and_add( &global_int, 1 );
  49.     }
  50.     gettimeofday(&tv_end,NULL);
  51.     end = rdtsc();
  52.     timeinterval =(tv_end.tv_sec - tv_begin.tv_sec)*1000000                    +(tv_end.tv_usec - tv_begin.tv_usec);
  53.     fprintf(stderr,"proc_num :%d,__sync_fetch_and_add cost             %llu CPU cycle,cost %llu us\n",                             proc_num,end-begin,timeinterval);

  54.     return NULL;
  55. }


  56. void *thread_routine2( void *arg )
  57. {
  58.     int i;
  59.     int proc_num = (int)(long)arg;
  60.     __u64 begin, end;
  61.   
  62.     struct timeval tv_begin,tv_end;
  63.     __u64 timeinterval;
  64.     cpu_set_t set;

  65.     CPU_ZERO( &set );
  66.     CPU_SET( proc_num, &set );

  67.     if (sched_setaffinity( gettid(), sizeof( cpu_set_t ), &set ))
  68.     {
  69.         perror( "sched_setaffinity" );
  70.         return NULL;
  71.     }


  72.     begin = rdtsc();
  73.     gettimeofday(&tv_begin,NULL);
  74.     
  75.     for(i = 0;i<INC_TO;i++)
  76.     {
  77.         pthread_mutex_lock(&count_lock);
  78.         global_int++;
  79.         pthread_mutex_unlock(&count_lock);
  80.     }

  81.     gettimeofday(&tv_end,NULL);
  82.     end = rdtsc();
  83.     
  84.     
  85.     timeinterval =(tv_end.tv_sec - tv_begin.tv_sec)*1000000                   +(tv_end.tv_usec - tv_begin.tv_usec);
  86.     fprintf(stderr,"proc_num :%d,pthread lock cost %llu CPU                    cycle,cost %llu us\n",proc_num,end-begin                    ,timeinterval);



  87.     return NULL;
  88. }
  89. int main()
  90. {
  91.     int procs = 0;
  92.     int i;
  93.     pthread_t *thrs;

  94.     // Getting number of CPUs
  95.     procs = (int)sysconf( _SC_NPROCESSORS_ONLN );
  96.     if (procs < 0)
  97.     {
  98.         perror( "sysconf" );
  99.         return -1;
  100.     }

  101.     thrs = malloc( sizeof( pthread_t ) * procs );
  102.     if (thrs == NULL)
  103.     {
  104.         perror( "malloc" );
  105.         return -1;
  106.     }

  107.     printf( "Starting %d threads...\n", procs );

  108.     for (i = 0; i < procs; i++)
  109.     {
  110.         if (pthread_create( &thrs[i], NULL, thread_routine,
  111.             (void *)(long)i ))
  112.         {
  113.             perror( "pthread_create" );
  114.             procs = i;
  115.             break;
  116.         }
  117.     }

  118.     for (i = 0; i < procs; i++)
  119.         pthread_join( thrs[i], NULL );

  120.     free( thrs );

  121.     printf( "After doing all the math, global_int value is:              %d\n", global_int );
  122.     printf( "Expected value is: %d\n", INC_TO * procs );

  123.     return 0;
  124. }
     通过我的测试发现:

  1. Starting 4 threads...
  2. proc_num :2,no locker cost 27049544 CPU cycle,cost 12712 us
  3. proc_num :0,no locker cost 27506750 CPU cycle,cost 12120 us
  4. proc_num :1,no locker cost 28499000 CPU cycle,cost 13365 us
  5. proc_num :3,no locker cost 27193093 CPU cycle,cost 12780 us
  6. After doing all the math, global_int value is: 1169911
  7. Expected value is: 4000000
  1. Starting 4 threads...
  2. proc_num :2,__sync_fetch_and_add cost 156602056 CPU cycle,cost 73603 us
  3. proc_num :1,__sync_fetch_and_add cost 158414764 CPU cycle,cost 74456 us
  4. proc_num :3,__sync_fetch_and_add cost 159065888 CPU cycle,cost 74763 us
  5. proc_num :0,__sync_fetch_and_add cost 162621399 CPU cycle,cost 76426 us
  6. After doing all the math, global_int value is: 4000000
  7. Expected value is: 4000000
 
  1. Starting 4 threads...
  2. proc_num :1,pthread lock cost 992586450 CPU cycle,cost 466518 us
  3. proc_num :3,pthread lock cost 1008482114 CPU cycle,cost 473998 us
  4. proc_num :0,pthread lock cost 1018798886 CPU cycle,cost 478840 us
  5. proc_num :2,pthread lock cost 1019083986 CPU cycle,cost 478980 us
  6. After doing all the math, global_int value is: 4000000
  7. Expected value is: 4000000
1 不加锁的情况下,不能返回正确的结果
  测试程序结果显示,正确结果为400万,实际为1169911.

2 线程锁和原子性自加都能返回正确的结果。

3 性能上__sync_fetch_and_add,完爆线程锁。
  从测试结果上看, __sync_fetch_and_add,速度是线程锁的6~7倍


参考文献:
1 主要参考了Alexander Sundler的博文
2 professional assemble language。

阅读(9935) | 评论(8) | 转发(4) |
给主人留下些什么吧!~~

Heartwork2011-12-04 13:59:48

Bean_lee: 兄弟已经很厉害了,你的评论给了我很多的指点,启发很多,督促我继续深入探究下。呵呵我要向你致谢。.....
不用客气,看你的blog我也是受益良多,相互勉励吧。

Bean_lee2011-12-04 13:12:59

Heartwork: 找到了spinlock的相关实现看了一下,也是使用锁总线来保证操作的原子性,另外还使用了一个变量来保存状态。所以spinlock也就不可能比__sync_fetch_and_add更快了.....
兄弟已经很厉害了,你的评论给了我很多的指点,启发很多,督促我继续深入探究下。呵呵我要向你致谢。

Heartwork2011-12-04 12:56:53

Bean_lee: 我的测试结果,__sync_fetch_and_add处理速度是最快的,我今天测试了以下。

自旋锁
root@libin:~/program/C/thread/atom_counter# ./test
Starting 4 threads......
找到了spinlock的相关实现看了一下,也是使用锁总线来保证操作的原子性,另外还使用了一个变量来保存状态。所以spinlock也就不可能比__sync_fetch_and_add更快了……

经验主义害死人啊!

Bean_lee2011-12-03 17:01:19

Heartwork: 锁总线这个代价就太大了,这种细粒度的操作可以用spin lock,pthead库有对应的实现。.....
我的测试结果,__sync_fetch_and_add处理速度是最快的,我今天测试了以下。

自旋锁
root@libin:~/program/C/thread/atom_counter# ./test
Starting 4 threads...
proc_num :1,no locker  cost 10373366371 CPU cycle,cost 4875382 us
proc_num :3,no locker  cost 10406853947 CPU cycle,cost 4891129 us
proc_num :0,no locker  cost 10407395129 CPU cyc

Heartwork2011-11-28 23:11:33

锁总线这个代价就太大了,这种细粒度的操作可以用spin lock,pthead库有对应的实现。