一、什么是CAS原子操作
大家应该还记得操作系统里面关于“原子操作”的概念，一个操作是原子的(atomic)，假设这个操作所处的层(layer)的更高层不能发现其内部实现与结构。原子操作能够是一个步骤，也能够是多个操作步骤。可是其顺序是不能够被打乱，或者分割掉仅仅运行部分。有了这个原子操作这个保证我们就能够实现无锁了。
CAS原子操作在维基百科中的代码描写叙述例如以下:
int compare_and_swap(int* reg, int oldval, int newval)
{
ATOMIC();
int old_reg_val = *reg;
if (old_reg_val == oldval)
*reg = newval;
END_ATOMIC();
return old_reg_val;
}
也就是检查内存*reg里的值是不是oldval，假设是的话。则对其赋值newval。上面的代码总是返回old_reg_value，调用者假设须要知道是否更新成功还须要做进一步推断，为了方便，它能够变种为直接返回是否更新成功，例如以下：
bool compare_and_swap (int *accum, int *dest, int newval)
{
if ( *accum == *dest ) {
*dest = newval;
return true;
}
return false;
}
二、CAS 在各个平台下的实现
2.1 Linux GCC 支持的 CAS
bool __sync_bool_compare_and_swap (type *ptr, type oldval type newval, ...)
2.2 Windows支持的CAS
InterlockedCompareExchange ( __inout LONG volatile *Target,
__in LONG Exchange,
__in LONG Comperand);
2.3C++ 11支持的CAS
template< class T >
bool atomic_compare_exchange_weak( std::atomic<T>* obj,
T* expected, T desired );
三、CAS原子操作实现无锁的性能分析
3.1 测试方法叙述
测试平台是虚拟机下Centos7.4
方法a使用C11的互斥锁mutex，方法b使用Linux的__sync_bool_compare_and_swap，方法c使用C11的compare_exchange_weak
采用控制变量法，每种方法起100个线程控制各自的变量（初始0），保证线程安全，在各自的线程函数中循环10000次加法，然后重复上述操作100次，也就是最后的结果应该都是100*10000*100=1亿。
对比a、b、c三种方法的运行时间。
3.2 测试代码如下(计算时间类在后面给出)：
#include <cstdio>
#include <mutex> // std::mutex
#include <atomic> // std::atomic
#include <thread> // std::thread
using namespace std;
#include "timer.h"
#define TIMES (100)
#define THREDS (100)
#define LOOPNUM (10000)
mutex mm;
size_t a = 0;
void funa()
{
for (int i = 0; i < LOOPNUM; i++)
{
mm.lock();
a++;
mm.unlock();
}
}
size_t b = 0;
void funb()
{
for (int i = 0; i < LOOPNUM; i++)
{
size_t oldb = b;
while (!__sync_bool_compare_and_swap(&b, oldb, oldb + 1))
{
oldb = b;
}
}
}
std::atomic<size_t> c(0);
void func()
{
for (int i = 0; i < LOOPNUM; i++)
{
size_t oldc = c;
while (!c.compare_exchange_weak(oldc, oldc + 1))
{
oldc = c;
}
}
}
int main(int argc, const char *argv[])
{
CUseTime totalTime;
{
CUseTime useTime;
for (int j = 0; j < TIMES; ++j)
{
thread* ttb[THREDS];
for (int i = 0; i < THREDS; i++)
{
ttb[i] = new thread(funa);
}
for (int i = 0; i < THREDS; i++)
{
ttb[i]->join();
delete ttb[i];
ttb[i] = NULL;
}
}
printf("use time %ld ms: C11 \"mutex\" a=%d\n", useTime.GetUseTime(), (int)a);
}
{
CUseTime useTime;
for (int j = 0; j < TIMES; ++j)
{
thread* ttb[THREDS];
for (int i = 0; i < THREDS; i++)
{
ttb[i] = new thread(funb);
}
for (int i = 0; i < THREDS; i++)
{
ttb[i]->join();
delete ttb[i];
ttb[i] = NULL;
}
}
printf("use time %ld ms: linux \"__sync_bool_compare_and_swap\" b=%d\n", useTime.GetUseTime(), (int)b);
}
{
CUseTime useTime;
for (int j = 0; j < TIMES; ++j)
{
thread* ttb[THREDS];
for (int i = 0; i < THREDS; i++)
{
ttb[i] = new thread(func);
}
for (int i = 0; i < THREDS; i++)
{
ttb[i]->join();
delete ttb[i];
ttb[i] = NULL;
}
}
printf("use time %ld ms: C11 \"compare_exchange_weak\" c=%d\n", useTime.GetUseTime(), (int)c);
}
printf("use time %ld ms total\n", totalTime.GetUseTime());
return 0;
}
3.3 测试结果
为了方便对比对文字做了后处理
[zlm@localhost Debug]$ ./test.out
use time 23360 ms: a=100000000 C++11 "mutex"
use time 8850 ms: b=100000000 linux "__sync_bool_compare_and_swap"
use time 24190 ms: c=100000000 C++11 "compare_exchange_weak"
use time 56400 ms: total
[zlm@localhost Debug]$ ./test.out
use time 24950 ms: a=100000000 C++11 "mutex"
use time 8900 ms: b=100000000 linux "__sync_bool_compare_and_swap"
use time 24400 ms: c=100000000 C++11 "compare_exchange_weak"
use time 58250 ms: total
从耗时上可以看出，Linux的__sync_bool_compare_and_swap应该是效果最好的，在保证了线程安全的前提下拥有最少的耗时，几乎是另外两种方式的三分之一。
3.4 消耗时间类头文件
文件名：timer.h
代码如下：
#ifndef _TIMER_
#define _TIMER_
#include <ctime>
class CUseTime
{
public:
CUseTime() : m_start_time(clock()) {}
virtual ~CUseTime() {}
long GetUseTime() { return (clock() - m_start_time) / (CLOCKS_PER_SEC / 1000); };
private:
long m_start_time;
};
#endif // !_TIMER_
参考文章
CAS原子操作实现无锁及性能分析
网友评论