• Linux：无锁化编程 __sync_fetch_and_add原理及其实现分析

    背景

    linux支持的哪些操作是具有原子特性的？知道这些东西是理解和设计无锁化编程算法的基础。

    我们知道，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

    1. type __sync_fetch_and_add (type *ptr, type value);
    2. type __sync_fetch_and_sub (type *ptr, type value);
    3. type __sync_fetch_and_or (type *ptr, type value);
    4. type __sync_fetch_and_and (type *ptr, type value);
    5. type __sync_fetch_and_xor (type *ptr, type value);
    6. type __sync_fetch_and_nand (type *ptr, type value);
    7. type __sync_add_and_fetch (type *ptr, type value);
    8. type __sync_sub_and_fetch (type *ptr, type value);
    9. type __sync_or_and_fetch (type *ptr, type value);
    10. type __sync_and_and_fetch (type *ptr, type value);
    11. type __sync_xor_and_fetch (type *ptr, type value);
    12. 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的原文，荣誉属于他，我只是学习他的代码，稍微改动了一点点。比较了两种方式的耗时情况。呵呵咱是菜鸟，不敢枉自剽窃大师作品。向大师致敬。

    1. #define _GNU_SOURCE
    2.  
    3. #include <stdio.h>
    4. #include <pthread.h>
    5. #include <unistd.h>
    6. #include <stdlib.h>
    7. #include <sched.h>
    8. #include <linux/unistd.h>
    9. #include <sys/syscall.h>
    10. #include <errno.h>
    11. #include<linux/types.h>
    12. #include<time.h>
    13.  
    14. #define INC_TO 1000000 // one million...
    15.  
    16. __u64 rdtsc()
    17. {
    18.   __u32 lo,hi;
    19.  
    20.     __asm__ __volatile__
    21.     (
    22.      "rdtsc":"=a"(lo),"=d"(hi)
    23.     );
    24.  
    25.     return (__u64)hi<<32|lo;
    26. }
    27.  
    28.  
    29.  
    30. int global_int = 0;
    31. pthread_mutex_t count_lock = PTHREAD_MUTEX_INITIALIZER;
    32.  
    33.  
    34. pid_t gettid( void )
    35. {
    36.     return syscall( __NR_gettid );
    37. }
    38.  
    39. void *thread_routine( void *arg )
    40. {
    41.     int i;
    42.     int proc_num = (int)(long)arg;
    43.     __u64 begin, end;
    44.     struct timeval tv_begin,tv_end;
    45.     __u64 timeinterval;
    46.     cpu_set_t set;
    47.  
    48.     CPU_ZERO( &set );
    49.     CPU_SET( proc_num, &set );
    50.  
    51.     if (sched_setaffinity( gettid(), sizeof( cpu_set_t ), &set ))
    52.     {
    53.         perror( "sched_setaffinity" );
    54.         return NULL;
    55.     }
    56.  
    57.     begin = rdtsc();
    58.     gettimeofday(&tv_begin,NULL);
    59.     for (i = 0; i < INC_TO; i++)
    60.     {
    61. //     global_int++;
    62.         __sync_fetch_and_add( &global_int, 1 );
    63.     }
    64.     gettimeofday(&tv_end,NULL);
    65.     end = rdtsc();
    66.     timeinterval =(tv_end.tv_sec - tv_begin.tv_sec)*1000000                    +(tv_end.tv_usec - tv_begin.tv_usec);
    67.     fprintf(stderr,"proc_num :%d,__sync_fetch_and_add cost             %llu CPU cycle,cost %llu us\n",                             proc_num,end-begin,timeinterval);
    68.  
    69.     return NULL;
    70. }
    71.  
    72.  
    73. void *thread_routine2( void *arg )
    74. {
    75.     int i;
    76.     int proc_num = (int)(long)arg;
    77.     __u64 begin, end;
    78.  
    79.     struct timeval tv_begin,tv_end;
    80.     __u64 timeinterval;
    81.     cpu_set_t set;
    82.  
    83.     CPU_ZERO( &set );
    84.     CPU_SET( proc_num, &set );
    85.  
    86.     if (sched_setaffinity( gettid(), sizeof( cpu_set_t ), &set ))
    87.     {
    88.         perror( "sched_setaffinity" );
    89.         return NULL;
    90.     }
    91.  
    92.  
    93.     begin = rdtsc();
    94.     gettimeofday(&tv_begin,NULL);
    95.  
    96.     for(i = 0;i<INC_TO;i++)
    97.     {
    98.         pthread_mutex_lock(&count_lock);
    99.         global_int++;
    100.         pthread_mutex_unlock(&count_lock);
    101.     }
    102.  
    103.     gettimeofday(&tv_end,NULL);
    104.     end = rdtsc();
    105.  
    106.  
    107.     timeinterval =(tv_end.tv_sec - tv_begin.tv_sec)*1000000                   +(tv_end.tv_usec - tv_begin.tv_usec);
    108.     fprintf(stderr,"proc_num :%d,pthread lock cost %llu CPU                    cycle,cost %llu us\n",proc_num,end-begin                    ,timeinterval);
    109.  
    110.  
    111.  
    112.     return NULL;
    113. }
    114. int main()
    115. {
    116.     int procs = 0;
    117.     int i;
    118.     pthread_t *thrs;
    119.  
    120.     // Getting number of CPUs
    121.     procs = (int)sysconf( _SC_NPROCESSORS_ONLN );
    122.     if (procs < 0)
    123.     {
    124.         perror( "sysconf" );
    125.         return -1;
    126.     }
    127.  
    128.     thrs = malloc( sizeof( pthread_t ) * procs );
    129.     if (thrs == NULL)
    130.     {
    131.         perror( "malloc" );
    132.         return -1;
    133.     }
    134.  
    135.     printf( "Starting %d threads...\n", procs );
    136.  
    137.     for (i = 0; i < procs; i++)
    138.     {
    139.         if (pthread_create( &thrs[i], NULL, thread_routine,
    140.             (void *)(long)i ))
    141.         {
    142.             perror( "pthread_create" );
    143.             procs = i;
    144.             break;
    145.         }
    146.     }
    147.  
    148.     for (i = 0; i < procs; i++)
    149.         pthread_join( thrs[i], NULL );
    150.  
    151.     free( thrs );
    152.  
    153.     printf( "After doing all the math, global_int value is:              %d\n", global_int );
    154.     printf( "Expected value is: %d\n", INC_TO * procs );
    155.  
    156.     return 0;
    157. }

    测试发现：

    1 不加锁的情况下，不能返回正确的结果
      测试程序结果显示，正确结果为400万，实际为1169911.

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

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

    且看以下测试结果：

    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

  • 相关阅读:
    python中使用pytest框架集成allure测试报告
    Spring中Bean的作用域
    java毕业设计软件基于SpringBoot在线电影订票|影院购票系统
    ES6 Class(类) 总结（九）
    Linux SSH免密登录
    刷题日记【第十一篇】-笔试必刷题【小易的升级之路+找出字符串中第一个只出现一次的字符+微信红包+计算字符串的编辑距离】
    二：对表进行基本CRUD操作
    blob相关
    Redis快速入门----------客户端使用
    免费学习Linux！
  • 原文地址：https://blog.csdn.net/hhd1988/article/details/127545400