CAS操作与无锁队列

c/c++

浏览数:86

2019-3-28

  • 在多线程编程中,为了保证内存的可见性,我们加入了一些锁的机制,例如信号量,互斥锁,条件变量等等,但是锁的机制不是一个简单的机制,需要加入很多的控制,所以在使用中又有了一些轻量级的同步机制,例如volatile,用来防止多线程中存有缓存以及禁止对指令顺序调优
  • 同时也加入了CPU的CAS操作,Compare and Swap,比较并交换,在大多数处理器架构,CAS的具体是判断一个内存上的数据是否是所判断的值,如果是,那么执行修改;如果不是,那么将不做操作并返回当前值。CAS是一种乐观锁,多线程执行过程中,多个线程去修改内存中的数据,有且只有一个能修改成功,但是失败的线程不会中断或者挂起。

CAS操作

int compare_and_swap (int* reg, int oldval, int newval)
{
  int old_reg_val = *reg;
  if(old_reg_val == oldval)
     *reg = newval;
  return old_reg_val;
}


具体的CAS操作

1、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、C++11中的CAS,C++11中的STL中的atomic类的函数可以让你跨平台。(完整的C++11的原子操作可参看 Atomic Operation Library)

inline bool atomic_compare_exchange(
   _Inout_ int * _Dest,
   _Inout_ int * _Expected_value,
   int _Value
) restrict(amp);

inline bool atomic_compare_exchange(
   _Inout_ unsigned int * _Dest,
   _Inout_ unsigned int * _Expected_value,
   unsigned int _Value
) restrict(amp);

关于无锁队列

无锁队列是为了解决在多线程环境下,多个线程使用队列频繁的加锁解锁过程,这些过程消耗了很多系统资源而CAS操作作为一种轻量级别的同步机制,为锁操作带来了很大的方便

void Push(void* data)
 {
    Node* old_tail;
    Node* node = new Node();
    node->data = data;
    
    do 
    {
       old_tail = tail;
 
       if (!cas(&tail, old_tail, node))
           continue
 
       if (old_tail)
          old_tail->next = node;
       else
          cas(&head, NULL, node);
 
       break;
 
    }while (1);
    
 }

这就是一种简单的无锁队列的实现,而对于无锁队列更深层次的实现可以类推,万变不离其宗,本质上还是比较在多线程运行过程中内存是否发生了改变,如果没有则进行插入操作。

博客参考:http://www.cnblogs.com/catch/…