百度360必应搜狗淘宝本站头条
wireshark怎么抓包c++ base64for_eachwxsqlite3qt sleep
当前位置：网站首页 > 技术分析 > 正文

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

liebian365 2024-10-30 04:48 4 浏览 0 评论

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，现在几乎所有的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: }

【文章福利】：小编整理了一些个人觉得比较好的学习书籍、视频资料共享在群文件里面，有需要的可以自行添加哦！~点击加入832218493（需要自取）


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原子操作实现无锁的性能分析


3.1测试方法描述


这里由于只是比较性能，所以采用很简单的方式，创建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次，并统计平均值，其结果如下：（单位微秒）

由此可见，无锁操作在性能上远远优于加锁操作，消耗时间仅为加锁操作的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

————————————————

版权声明：本文为CSDN博主「chen19870707」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。

原文链接：https://blog.csdn.net/chen19870707/article/details/41083183

相关推荐

快递查询教程，批量查询物流，一键管理快递

作为商家，每天需要查询许许多多的快递单号，面对不同的快递公司，有没有简单一点的物流查询方法呢？小编的回答当然是有的，下面随小编一起来试试这个新技巧。需要哪些工具？安装一个快递批量查询高手快递单号怎么快...

一键自动查询所有快递的物流信息 支持圆通、韵达等多家快递

对于各位商家来说拥有一个好的快递软件，能够有效的提高自己的工作效率，在管理快递单号的时候都需要对单号进行表格整理，那怎么样能够快速的查询所有单号信息，并自动生成表格呢？1、其实方法很简单，我们不需要一...

快递查询单号查询，怎么查物流到哪了

输入单号怎么查快递到哪里去了呢？今天小编给大家分享一个新的技巧，它支持多家快递，一次能查询多个单号物流，还可对查询到的物流进行分析、筛选以及导出，下面一起来试试。需要哪些工具?安装一个快递批量查询高手...

3分钟查询物流，教你一键批量查询全部物流信息

很多朋友在问，如何在短时间内把单号的物流信息查询出来，查询完成后筛选已签收件、筛选未签收件，今天小编就分享一款物流查询神器，感兴趣的朋友接着往下看。第一步，运行【快递批量查询高手】在主界面中点击【添...

快递单号查询，一次性查询全部物流信息

现在各种快递的查询方式，各有各的好，各有各的劣，总的来说，还是有比较方便的。今天小编就给大家分享一个新的技巧，支持多家快递，一次能查询多个单号的物流，还能对查询到的物流进行分析、筛选以及导出，下面一起...

快递查询工具，批量查询多个快递快递单号的物流状态、签收时间

最近有朋友在问，怎么快速查询单号的物流信息呢？除了官网，还有没有更简单的方法呢？小编的回答当然是有的，下面一起来看看。需要哪些工具？安装一个快递批量查询高手多个京东的快递单号怎么快速查询？进入快递批量...

快递查询软件，自动识别查询快递单号查询方法

当你拥有多个快递单号的时候，该如何快速查询物流信息？比如单号没有快递公司时，又该如何自动识别再去查询呢？不知道如何操作的宝贝们，下面随小编一起来试试。需要哪些工具？安装一个快递批量查询高手快递单号若干...

教你怎样查询快递查询单号并保存物流信息

商家发货，快递揽收后，一般会直接手动复制到官网上一个个查询物流，那么久而久之，就会觉得查询变得特别繁琐，今天小编给大家分享一个新的技巧，下面一起来试试。教程之前，我们来预览一下用快递批量查询高手...

简单几步骤查询所有快递物流信息

在高峰期订单量大的时候，可能需要一双手当十双手去查询快递物流，但是由于逐一去查询，效率极低，追踪困难。那么今天小编给大家分享一个新的技巧，一次能查询多个快递单号的物流，下面一起来学习一下，希望能给大家...

物流单号查询，如何查询快递信息，按最后更新时间搜索需要的单号

最近有很多朋友在问，如何通过快递单号查询物流信息，并按最后更新时间搜索出需要的单号呢？下面随小编一起来试试吧。需要哪些工具？安装一个快递批量查询高手快递单号若干怎么快速查询？运行【快递批量查询高手】...

连续保存新单号功能解析，导入单号查询并自动识别批量查快递信息

快递查询已经成为我们日常生活中不可或缺的一部分。然而，面对海量的快递单号，如何高效、准确地查询每一个快递的物流信息，成为了许多人头疼的问题。幸运的是，随着科技的进步，一款名为“快递批量查询高手”的软件...

快递查询教程，快递单号查询，筛选更新量为1的单号

最近有很多朋友在问，怎么快速查询快递单号的物流，并筛选出更新量为1的单号呢？今天小编给大家分享一个新方法，一起来试试吧。需要哪些工具？安装一个快递批量查询高手多个快递单号怎么快速查询？运行【快递批量查...

掌握批量查询快递动态的技巧，一键查找无信息记录的两种方法解析

在快节奏的商业环境中，高效的物流查询是确保业务顺畅运行的关键。作为快递查询达人，我深知时间的宝贵，因此，今天我将向大家介绍一款强大的工具——快递批量查询高手软件。这款软件能够帮助你批量查询快递动态，一...

从复杂到简单的单号查询，一键清除单号中的符号并批量查快递信息

在繁忙的商务与日常生活中，快递查询已成为不可或缺的一环。然而，面对海量的单号，逐一查询不仅耗时费力，还容易出错。现在，有了快递批量查询高手软件，一切变得简单明了。只需一键，即可搞定单号查询，一键处理单...

物流单号查询，在哪里查询快递

如果在快递单号多的情况，你还在一个个复制粘贴到官网上手动查询，是一件非常麻烦的事情。于是乎今天小编给大家分享一个新的技巧，下面一起来试试。需要哪些工具？安装一个快递批量查询高手快递单号怎么快速查询？...

取消回复欢迎 你 发表评论:

一周热门
最近发表
标签列表
Copyright Your WebSite.Some Rights Reserved.