首页 > 代码库 > 使用CAS实现高效并发处理

使用CAS实现高效并发处理

2024-07-18 19:52:26   229人阅读

在并发处理应用中，一般使用锁的方式来解决竞争问题，但锁的效率比较低，因此，在高并发处理中，无锁队列成为应用的需要。CAS无锁算法主要依赖于处理器的支持，绝大多数处理器都支持：

X86平台：CMPXCHG 汇编指令。
在一个指令周期内执行完成，因此是原子性的。
这一原理性操作过程如果采用C描述如下：
intcompare_and_swap (int* reg, int oldval, int newval)
{
  int old_reg_val = *reg;
  if (old_reg_val == oldval)
     *reg = newval;
  return old_reg_val;
}

boolcompare_and_swap (int *accum, int *dest, int newval)
{
  if ( *accum == *dest ) {
      *dest = newval;
      return true;
  }
  return false;
}

API函数GCC4.1   
bool__sync_bool_compare_and_swap (type *ptr, type oldval, type newval, ...)
type__sync_val_compare_and_swap (type *ptr, type oldval, type newval, ...)

Linux内核中实现方法：
ARM实现版本
staticinline int atomic_cmpxchg(atomic_t *ptr, int old, int new)
{
unsigned long oldval, res;

smp_mb();/*内存屏障*/

do {
          __asm__ __volatile__("@atomic_cmpxchg\n"
          "ldrex        %1, [%2]\n"
          "mov          %0, #0\n"
          "teq  %1, %3\n"
          "strexeq %0, %4, [%2]\n"
             : "=&r" (res), "=&r" (oldval)
             : "r" (&ptr->counter), "Ir" (old),"r" (new)
             : "cc");
} while (res);

smp_mb();

return oldval;
}

X86版本
staticinline unsigned long __cmpxchg(volatile void *ptr, unsigned long old,
                                   unsigned long new, int size)
{
unsigned long prev;
switch (size) {
case 1:
          asm volatile(LOCK_PREFIX"cmpxchgb %b2,%1"
                         : "=a"(prev),"+m"(*__xg(ptr))
                         : "q"(new), "0"(old)
                         : "memory");
          return prev;
case 2:
          asm volatile(LOCK_PREFIX"cmpxchgw %w2,%1"
                         : "=a"(prev),"+m"(*__xg(ptr))
                         : "r"(new), "0"(old)
                         : "memory");
          return prev;
case 4:
          asm volatile(LOCK_PREFIX"cmpxchgl %2,%1"
                         : "=a"(prev),"+m"(*__xg(ptr))
                         : "r"(new), "0"(old)
                         : "memory");
          return prev;
}
return old;
}

应用代码
无锁队列的具体应用示例
以下是作者在某NOSQL数据库中针对高并发情况使用无锁队列的应用示例。
typedefstruct _pool
{
……
    node_object *pool_link_head;   
    node_object *pool_link_tail;        
}pool;
获取结点
    do
    {
        ptr = pool->pool_link_head;
        if(ptr->next == NULL)
        {
            DERROR("pool empty,but norealloc.exit.....\n");
            KDB_EXIT;
        }
   }while(B_CAS(&(pool->pool_link_head), ptr , ptr->next) !=TRUE);

pool->free_count++; /*this is not thread safe, may use atomic_t */
    return ptr;
释放结点：
1    do{
2       ptr = pool->pool_link_tail;
3    }while(B_CAS(&(ptr->next),NULL,temp)!= TRUE );
4   
5    pool->free_count++;         /*during this  critical area ,no other thread can modify thepool ds*/
6
7    B_CAS(&(pool->pool_link_tail),oldtail , temp);


联系
我们