&＃xfeff;&＃xfeff;
原文链接
http://blog.csdn.net/pennyliang/article/details/5993138
从该博客开始&＃xff0c;会有一些小系列预计有4-5篇博文来介绍&＃xff0c;锁的应用和实践&＃xff0c;我们常常听到spin lock&＃xff0c;wait-free&＃xff0c;lock-free&＃xff0c;这到底是怎么回事&＃xff0c;我们能不能自己实现一个spin lock&＃xff0c;原理是什么&＃xff1f;这个小系列就讨论这个内容。
首先我们来看两个基本操作compare_and_swap和fetch_and_add&＃xff0c;基本上lock-free的操作都会依赖这两个基本的原子操作。特别是compare_and_swap这个原子操作&＃xff0c;它源于IBM System 370&＃xff0c;其包含三个参数&＃xff1a;&＃xff08;1&＃xff09;共享内存的地址(*p)&＃xff0c;&＃xff08;2&＃xff09;该地址期望的值(old_value)&＃xff0c;&＃xff08;3&＃xff09;一个新值(new_value)。只有当*p &＃61;&＃61; old_value时&＃xff0c;才产生交换操作&＃xff0c;返回真值&＃xff0c;否则返回假值&＃xff0c;相当于如下代码 &＃xff1a;template
bool CAS(T* addr, T exp, T val) //只有在整个函数过程具有原子性时才正确&＃xff0c;实际的代码参照下面的汇编代码。
{
if&＃xff08;*addr &＃61;&＃61; exp&＃xff09;{
*addr &＃61; val;
return true&＃xff1b;
}
return false&＃xff1b;
}
在下面的代码中我们会看到compare_and_swap使用了lock指令&＃xff0c;用于锁总线&＃xff0c;setz会判断cmpxchg指令后ZF符号位是否置位&＃xff0c;可以知道是否发生了一次交换。以下是一段可以执行的代码&＃xff0c;void* sum(void*)函数通过不同的编译命令生成不同的代码&＃xff0c;其结果都是用10个线程对一个全局变量进行加和的简单操作。但分别采用了pthread提供的mutex&＃xff0c;fetch_and_add方法,完全无锁的方法&＃xff0c;应用cas的三种方式&＃xff0c;其中sum_with_cas_imp_yield就基本是spinlock的实现了。
下一篇我来公布在我的测试机的实验结果&＃xff0c;并且继续探讨其他lock-free的话题。
#include
#include
#include
#include
#include
#include
#if defined(__x86_64__)
#define ATOMICOPS_WORD_SUFFIX "q" //64位环境下使用cmpxchgq命令
#else
#define ATOMICOPS_WORD_SUFFIX "l" //32位环境下使用cmpxchgl命令
#endif
static inline bool
compare_and_swap(volatile size_t *p, size_t val_old, size_t val_new){
char ret;
__asm__ __volatile__("lock; cmpxchg" ATOMICOPS_WORD_SUFFIX " %3, %0; setz %1"//lock命令锁总线&＃xff0c;因此可以保证多核同步
: "&＃61;m"(*p), "&＃61;q"(ret) //setz为ZF符号位是否置位&＃xff0c;用于设置返回值
: "m"(*p), "r" (val_new), "a"(val_old)
: "memory");
return (bool)ret;
}
static inline size_t
fetch_and_add(volatile size_t *p, size_t add){
unsigned int ret;
__asm__ __volatile__("lock; xaddl %0, %1"
:"&＃61;r" (ret), "&＃61;m" (*p)
: "0" (add), "m" (*p)
: "memory");
return ret;
};
struct my_cas
{
my_cas(unsigned char t):m_val_old(t){}
size_t m_val_old;
inline void try_continue(size_t val_old,size_t val_new){
while(!compare_and_swap(&m_val_old,val_old,val_new)){};
}
inline void add(size_t val_new){
fetch_and_add(&m_val_old,val_new);
}
};
volatile size_t g_uCount;
pthread_mutex_t g_tLck&＃61;PTHREAD_MUTEX_INITIALIZER;
my_cas mutex(1);
const size_t cnt_num &＃61; 10000000;
void* sum_with_mutex_lock(void*)
{
for(int i&＃61;0;i
pthread_mutex_lock(&g_tLck);
g_uCount &＃43;&＃61; 1;
pthread_mutex_unlock(&g_tLck);
}
};
void* sum_with_f_and_a(void*) //用fetch_and_add原子操作来保证结果正确性。
{
for(int i&＃61;0;i
fetch_and_add(&g_uCount,1);
}
};
void* sum_with_cas(void*) //用CAS原子操作来模拟锁操作。
{
for(int i&＃61;0;i
{
mutex.try_continue(1,0);
g_uCount &＃43;&＃61; 1;
mutex.try_continue(0,1);
}
}
void* sum_with_cas_imp(void*)
{
for(int i&＃61;0;i
for(;;) {
size_t u &＃61; g_uCount;
if(compare_and_swap(&g_uCount,u,u&＃43;1)){ //在上一条语句和本条语句之间&＃xff0c;g_uCount无篡改则进行加1&＃xff0c;
break; //break出该循环&＃xff0c;否则重试&＃xff0c;直到成功。
}
}
}
}
void* sum_with_cas_imp_yield(void*)
{
for(int i&＃61;0;i
for(;;) {
register size_t c &＃61; 1000; //
while(c){
size_t u &＃61; g_uCount;
if(compare_and_swap(&g_uCount,u,u&＃43;1)){
break;
}
c--;
}
if(!c){
syscall(SYS_sched_yield); //增加一次让渡CPU的机会&＃xff0c;spin lock通常应有这种策略
}
}
}
}
void* sum_just_free(void*)
{
for(int i&＃61;0;i
g_uCount &＃43;&＃61; 1;
}
}
void* sum(void*)
{
#ifdef M_LOCK
sum_with_mutex_lock(NULL);
#endif
#ifdef FETCH_AND_ADD
sum_with_f_and_a(NULL);
#endif
#ifdef FREE
sum_just_free(NULL);
#endif
#ifdef CAS
sum_with_cas(NULL);
#endif
#ifdef CAS_IMP
sum_with_cas_imp(NULL);
#endif
#ifdef CAS_IMP_YIELD
sum_with_cas_imp_yield(NULL);
#endif
};
int main()
{
pthread_t* thread &＃61; (pthread_t*) malloc(10*sizeof( pthread_t));
for(int i&＃61;0;i<10;&＃43;&＃43;i){
pthread_create(&thread[i],NULL,sum,NULL);
}
for(int i&＃61;0;i<10;&＃43;&＃43;i){
pthread_join(thread[i],NULL);
}
printf("g_uCount:%d/n",g_uCount);
}
用以下编译命令编译出6个程序
g&＃43;&＃43; test.cpp -o test_free -D FREE -lpthread
g&＃43;&＃43; test.cpp -o test_fetchandadd -D FETCH_AND_ADD -lpthread
g&＃43;&＃43; test.cpp -o test_mlock -D M_LOCK -lpthread
g&＃43;&＃43; test.cpp -o test_cas -D CAS -lpthread
g&＃43;&＃43; test.cpp -o test_cas_imp -D CAS_IMP –lpthread
g&＃43;&＃43; test.cpp –o test_cas_imp_yield –D CAS_IMP_YIELD -lpthread
京公网安备 11010802041100号