CAS原子操作实现无锁及性能分析

时间:2023-01-13 11:55:32

CAS原子操作实现无锁及性能分析

  • Author:Echo Chen(陈斌)

  • Email:chenb19870707@gmail.com

  • Blog:Blog.csdn.net/chen19870707

  • Date:Nov 13th, 2014

    近期在研究nginx的自旋锁的时候,又见到了GCC CAS原子操作,于是决定动手分析下CAS实现的无锁究竟性能怎样,网上关于CAS实现无锁的文章非常多。但少有研究这样的无锁的性能提升的文章,这里就以实验结果和我自己的理解逐步展开。

  • 1.什么是CAS原子操作

    在研究无锁之前。我们须要首先了解一下CAS原子操作——Compare & Set,或是 Compare & Swap,如今差点儿所CAS原子操作实现无锁及性能分析有的CPU指令都支持CAS的原子操作,X86下相应的是
    CMPXCHG 汇编指令。

    大家应该还记得操作系统里面关于“原子操作”的概念,一个操作是原子的(atomic),假设这个操作所处的层(layer)的更高层不能发现其内部实现与结构。原子操作能够是一个步骤,也能够是多个操作步骤。可是其顺序是不能够被打乱,或者分割掉仅仅运行部分。有了这个原子操作这个保证我们就能够实现无锁了。

    CAS原子操作在*中的代码描写叙述例如以下:

       1: int compare_and_swap(int* reg, int oldval, int newval)
       2: {
       3:   ATOMIC();
       4:   int old_reg_val = *reg;
       5:   if (old_reg_val == oldval)
       6:      *reg = newval;
       7:   END_ATOMIC();
       8:   return old_reg_val;
       9: }
  • 也就是检查内存*reg里的值是不是oldval,假设是的话。则对其赋值newval。上面的代码总是返回old_reg_value,调用者假设须要知道是否更新成功还须要做进一步推断,为了方便,它能够变种为直接返回是否更新成功,例如以下:

  •    1: bool compare_and_swap (int *accum, int *dest, int newval)
       2: {
       3:   if ( *accum == *dest ) {
       4:       *dest = newval;
       5:       return true;
       6:   }
       7:   return false;
       8: }

    除了CAS还有下面原子操作:

    • Fetch And Add,一般用来对变量做 +1 的原子操作。
         1: << atomic >>
         2: function FetchAndAdd(address location, int inc) {
         3:     int value := *location
         4:     *location := value + inc
         5:     return value
         6: }
       
      Test-and-set,写值到某个内存位置并传回其旧值。汇编指令BST。
         1: #define LOCKED 1
         2:  
         3: int TestAndSet(int* lockPtr) {
         4:     int oldValue;
         5:  
         6:     // Start of atomic segment
         7:     // The following statements should be interpreted as pseudocode for
         8:     // illustrative purposes only.
         9:     // Traditional compilation of this code will not guarantee atomicity, the
        10:     // use of shared memory (i.e. not-cached values), protection from compiler
        11:     // optimization, or other required properties.
        12:     oldValue = *lockPtr;
        13:     *lockPtr = LOCKED;
        14:     // End of atomic segment
        15:  
        16:     return oldValue;
        17: }
       
    • Test and Test-and-set,用来实现多核环境下相互排斥锁。
         1: boolean locked := false // shared lock variable
         2: procedure EnterCritical() {
         3:   do {
         4:     while (locked == true) skip // spin until lock seems free
         5:   } while TestAndSet(locked) // actual atomic locking
         6: }

    2.CAS 在各个平台下的实现

    2.1 Linux GCC 支持的 CAS

    GCC4.1+版本号中支持CAS的原子操作(完整的原子操作可參看GCC Atomic Builtins

       1: bool __sync_bool_compare_and_swap (type *ptr, type oldval type newval, ...)
       2: type __sync_val_compare_and_swap (type *ptr, type oldval type newval, ...)

    2.2  Windows支持的CAS

    在Windows下。你能够使用以下的Windows API来完毕CAS:(完整的Windows原子操作可參看MSDN的InterLocked Functions

  •    1: InterlockedCompareExchange ( __inout LONG volatile *Target,
       2:                                 __in LONG Exchange,
       3:                                 __in LONG Comperand);

    2.3  C++ 11支持的CAS

    C++11中的STL中的atomic类的函数能够让你跨平台。(完整的C++11的原子操作可參看 Atomic Operation Library

       1: template< class T >
       2: bool atomic_compare_exchange_weak( std::atomic<T>* obj,
       3:                                    T* expected, T desired );
       4: template< class T >
       5: bool atomic_compare_exchange_weak( volatile std::atomic<T>* obj,
       6:                                    T* expected, T desired );
  • 3.CAS原子操作实现无锁的性能分析

    • CAS原子操作实现无锁及性能分析3.1測试方法描写叙述

    这里因为仅仅是比較性能,所以採用非常easy的方式。创建10个线程并发运行,每一个线程中循环对全局变量count进行++操作(i++)。循环加2000000次。这必定会涉及到并发相互排斥操作,在同一台机器上分析 加普通相互排斥锁、CAS实现的无锁、Fetch And Add实现的无锁消耗的时间,然后进行分析。

    3.2 加普通相互排斥锁代码

       1: #include <stdio.h>
       2: #include <stdlib.h>
       3: #include <pthread.h>
       4: #include <time.h>
       5: #include "timer.h"
       6:  
       7: pthread_mutex_t mutex_lock;
       8: static volatile int count = 0;
       9: void *test_func(void *arg)
      10: {
      11:         int i = 0;
      12:         for(i = 0; i < 2000000; i++)
      13:         {
      14:                 pthread_mutex_lock(&mutex_lock);
      15:                 count++;
      16:                 pthread_mutex_unlock(&mutex_lock);
      17:         }
      18:         return NULL;
      19: }
      20:  
      21: int main(int argc, const char *argv[])
      22: {
      23:     Timer timer; // 为了计时,暂时封装的一个类Timer。
      24:     timer.Start();    // 计时開始
      25:     pthread_mutex_init(&mutex_lock, NULL);
      26:     pthread_t thread_ids[10];
      27:     int i = 0;
      28:     for(i = 0; i < sizeof(thread_ids)/sizeof(pthread_t); i++)
      29:     {
      30:         pthread_create(&thread_ids[i], NULL, test_func, NULL);
      31:     }
      32:  
      33:     for(i = 0; i < sizeof(thread_ids)/sizeof(pthread_t); i++)
      34:     {
      35:         pthread_join(thread_ids[i], NULL);
      36:     }
      37:  
      38:     timer.Stop();// 计时结束
      39:     timer.Cost_time();// 打印花费时间
      40:     printf("结果:count = %d\n",count);
      41:  
      42:     return 0;
      43: }

    注:Timer类仅作统计时间用,事实上如今文章最后给出。

    3.2 CAS实现的无锁

       1: #include <stdio.h>
       2: #include <stdlib.h>
       3: #include <pthread.h>
       4: #include <unistd.h>
       5: #include <time.h>
       6: #include "timer.h"
       7:  
       8: int mutex = 0;
       9: int lock = 0;
      10: int unlock = 1;
      11:  
      12: static volatile int count = 0;
      13: void *test_func(void *arg)
      14: {
      15:         int i = 0;
      16:         for(i = 0; i < 2000000; i++)
      17:     {
      18:         while (!(__sync_bool_compare_and_swap (&mutex,lock, 1) ))usleep(100000);
      19:          count++;
      20:          __sync_bool_compare_and_swap (&mutex, unlock, 0);
      21:         }
      22:         return NULL;
      23: }
      24:  
      25: int main(int argc, const char *argv[])
      26: {
      27:     Timer timer;
      28:     timer.Start();
      29:     pthread_t thread_ids[10];
      30:     int i = 0;
      31:  
      32:     for(i = 0; i < sizeof(thread_ids)/sizeof(pthread_t); i++)
      33:     {
      34:             pthread_create(&thread_ids[i], NULL, test_func, NULL);
      35:     }
      36:  
      37:     for(i = 0; i < sizeof(thread_ids)/sizeof(pthread_t); i++)
      38:     {
      39:             pthread_join(thread_ids[i], NULL);
      40:     }
      41:  
      42:     timer.Stop();
      43:     timer.Cost_time();
      44:     printf("结果:count = %d\n",count);
      45:  
      46:     return 0;
      47: }
      48:  

    3.4 Fetch And Add 原子操作

       1: #include <stdio.h>
       2: #include <stdlib.h>
       3: #include <pthread.h>
       4: #include <unistd.h>
       5: #include <time.h>
       6: #include "timer.h"
       7:  
       8: static volatile int count = 0;
       9: void *test_func(void *arg)
      10: {
      11:         int i = 0;
      12:         for(i = 0; i < 2000000; i++)
      13:         {
      14:             __sync_fetch_and_add(&count, 1);
      15:         }
      16:         return NULL;
      17: }
      18:  
      19: int main(int argc, const char *argv[])
      20: {
      21:     Timer timer;
      22:     timer.Start();
      23:     pthread_t thread_ids[10];
      24:     int i = 0;
      25:  
      26:     for(i = 0; i < sizeof(thread_ids)/sizeof(pthread_t); i++){
      27:             pthread_create(&thread_ids[i], NULL, test_func, NULL);
      28:     }
      29:  
      30:     for(i = 0; i < sizeof(thread_ids)/sizeof(pthread_t); i++){
      31:             pthread_join(thread_ids[i], NULL);
      32:     }
      33:  
      34:     timer.Stop();
      35:     timer.Cost_time();
      36:     printf("结果:count = %d\n",count);
      37:     return 0;
      38: }
      39:  

    4 实验结果和分析

    在同一台机器上,各执行以上3份代码10次,并统计平均值。其结果例如以下:(单位微秒)

    CAS原子操作实现无锁及性能分析

    由此可见。无锁操作在性能上远远优于加锁操作,消耗时间仅为加锁操作的1/3左右,无锁编程方式确实能够比传统加锁方式效率高,经上面測试能够发现,能够快到3倍左右。所以在极力推荐在高并发程序中採用无锁编程的方式能够进一步提高程序效率。

    5.时间统计类Timer

    timer.h

       1: #ifndef TIMER_H
       2: #define TIMER_H
       3:  
       4: #include <sys/time.h>
       5: class Timer
       6: {
       7: public:    
       8:     Timer();
       9:     // 開始计时时间
      10:     void Start();
      11:     // 终止计时时间
      12:     void Stop();
      13:     // 又一次设定
      14:     void Reset();
      15:     // 耗时时间
      16:     void Cost_time();
      17: private:
      18:     struct timeval t1;
      19:     struct timeval t2;
      20:     bool b1,b2;
      21: };
      22: #endif

    timer.cpp

       1: #include "timer.h"
       2: #include <stdio.h>
       3:  
       4: Timer::Timer()
       5: {
       6:     b1 = false;
       7:     b2 = false;
       8: }
       9: void Timer::Start()
      10: {
      11:     gettimeofday(&t1,NULL);  
      12:     b1 = true;
      13:     b2 = false;
      14: }
      15:  
      16: void Timer::Stop()
      17: {    
      18:     if (b1 == true)
      19:     {
      20:         gettimeofday(&t2,NULL);  
      21:         b2 = true;
      22:     }
      23: }
      24:  
      25: void Timer::Reset()
      26: {    
      27:     b1 = false;
      28:     b2 = false;
      29: }
      30:  
      31: void Timer::Cost_time()
      32: {
      33:     if (b1 == false)
      34:     {
      35:         printf("计时出错,应该先运行Start()。然后运行Stop(),再来运行Cost_time()");
      36:         return ;
      37:     }
      38:     else if (b2 == false)
      39:     {
      40:         printf("计时出错,应该运行完Stop()。再来运行Cost_time()");
      41:         return ;
      42:     }
      43:     else
      44:     {
      45:         int usec,sec;
      46:         bool borrow = false;
      47:         if (t2.tv_usec > t1.tv_usec)
      48:         {
      49:             usec = t2.tv_usec - t1.tv_usec;
      50:         }
      51:         else
      52:         {
      53:             borrow = true;
      54:             usec = t2.tv_usec+1000000 - t1.tv_usec;
      55:         }
      56:  
      57:         if (borrow)
      58:         {
      59:             sec = t2.tv_sec-1 - t1.tv_sec;
      60:         }
      61:         else
      62:         {
      63:             sec = t2.tv_sec - t1.tv_sec;
      64:         }
      65:         printf("花费时间:%d秒 %d微秒\n",sec,usec);
      66:     }
      67: }
      68:  
  • 6.參考

  • 1.http://blog.csdn.net/hzhsan/article/details/25837189
  • 2.http://coolshell.cn/articles/8239.html
  • -

  • Echo Chen:Blog.csdn.net/chen19870707

    -

  • CAS原子操作实现无锁及性能分析的更多相关文章

    1. C&plus;&plus;11原子操作与无锁编程(转)

      不讲语言特性,只从工程角度出发,个人觉得C++标准委员会在C++11中对多线程库的引入是有史以来做得最人道的一件事:今天我将就C++11多线程中的atomic原子操作展开讨论:比较互斥锁,自旋锁(sp ...

    2. 具体CAS操作实现&lpar;无锁算法&rpar;

      具体CAS操作 上一篇讲述了CAS机制,这篇讲解CAS具体操作. 什么是悲观锁.乐观锁?在java语言里,总有一些名词看语义跟本不明白是啥玩意儿,也就总有部分面试官拿着这样的词来忽悠面试者,以此来找优 ...

    3. 锁、CAS操作和无锁队列的实现

      https://blog.csdn.net/yishizuofei/article/details/78353722 锁的机制 锁和人很像,有的人乐观,总会想到好的一方面,所以只要越努力,就会越幸运: ...

    4. CAS简介和无锁队列的实现

      Q:CAS的实现 A:gcc提供了两个函数 bool __sync_bool_compare_and_swap (type *ptr, type oldval, type newval, ...)// ...

    5. 使用Interlocked在多线程下进行原子操作,无锁无阻塞的实现线程运行状态判断

      巧妙地使用Interlocked的各个方法,再无锁无阻塞的情况下判断出所有线程的运行完成状态. 昨晚耐着性子看完了clr via c#的第29章<<基元线程同步构造>>,尽管这 ...

    6. C&plus;&plus;性能榨汁机之无锁编程

      C++性能榨汁机之无锁编程 来源 http://irootlee.com/juicer_lock_free/ 前言 私以为个人的技术水平应该是一个螺旋式上升的过程:先从书本去了解一个大概,然后在实践中 ...

    7. Atitit。Cas机制&&num;160&semi;软件开发&&num;160&semi;编程语言&&num;160&semi;无锁机制&&num;160&semi;java&&num;160&semi;c&num;&&num;160&semi;php

      Atitit.Cas机制 软件开发 编程语言 无锁机制 java c# php 1. 为什么需要无锁操作1 2. 硬件支持 cas  atomic2 3. 无锁编程(Lock-Free)就是在某些应用 ...

    8. 使用C&plus;&plus;11实现无锁stack(lock-free stack&rpar;

      前几篇文章,我们讨论了如何使用mutex保护数据及使用使用condition variable在多线程中进行同步.然而,使用mutex将会导致一下问题: 等待互斥锁会消耗宝贵的时间 — 有时候是很多时 ...

    9. boost 无锁队列

      一哥们翻译的boost的无锁队列的官方文档 原文地址:http://blog.csdn.net/great3779/article/details/8765103 Boost_1_53_0终于迎来了久 ...

    随机推荐

    1. mysql 存储过程在批处理数据中的应用

      最近批处理数据的时候,突然想到:为什么不使用存储过程进行数据批处理? 为什么要进行批处理? 自答:减少数据库连接次数,提高效率. 存储过程批处理数据的优点:一次编译,永久执行. 这次的批处理逻辑较简单 ...

    2. 读JS高级——第五章-引用类型 &lowbar;记录

      <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/ ...

    3. D3&period;js 让图表动起来

      D3 支持制作动态的图表.有时候,图表的变化需要缓慢的发生,以便于让用户看清楚变化的过程,也能给用户不小的友好感. 一.什么是动态效果 绘制完成后不再发生变化的,这是静态的图表. 动态的图表,是指图表 ...

    4. 懒与馋的平衡:餐饮O2O市场广阔,发展不易

      餐饮行业是众多行业中O2O起步较早的,现在方兴未艾的团购站点中最先涉足的领域就有餐饮版块.长时间的合作推广,很多餐饮商家已经从中尝到甜头,可以说餐饮行业市场基础培育的比較好,所以餐饮O2O 已经是大势 ...

    5. 实现基本的CRUD功能

      文] 使用 MVC 5 的 EF6 Code First 入门 系列:实现基本的CRUD功能 2014-04-28 16:29 by Bce, 428 阅读, 0 评论, 收藏, 编辑 英文渣水平,大 ...

    6. bootstrap学习: 基本组件以及布局;

      1.下拉菜单: <div class="btn-group"> <button type="button" class="btn b ...

    7. windows service卸载

      .使用组合键win+r 调出服务页面 2.查看想要删除的服务的名称:如: 3.执行删除操作

    8. Appium学习笔记2&lowbar;Android获取元素篇

      在利用Appium做自动化测试时,最重要的一步就是获取对应的元素值,根据元素来对对象进行对应的操作,如果获得对象元素呢? Appium Server Console其实提供了一个界面对话框" ...

    9. 使用ResourceBundle读取配置文件

      在Java语言中,使用一种以.properties为扩展名的文本文件作为资源文件,该类型的文件的内容格式为类似: 12 #注释语句 some_key=some_value 形式.以#开头的行作为注释行 ...

    10. Java并发程序设计(三) Java内存模型和线程安全

      Java内存模型和线程安全 一 .原子性 原子性是指一个操作是不可中断的.即使是在多个线程一起执行的时候,一个操作一旦开始,就不会被其它线程干扰. 思考:i++是原子操作吗?  二.有序性 Java代 ...