在并发处理应用中,一般使用锁的方式来解决竞争问题,但锁的效率比较低,因此,在高并发处理中,无锁队列成为应用的需要。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); 说明: 多一个空结点解决head和tail同时指向同一个结点(只剩下一个结点的时候)的冲突问题。在具体实现上,如果发现只有一个结点,将再次申请新结点 |
行业聚焦 面试交流 职位推荐 开发视频 技术交流 腾讯微博 新浪微博
友情链接:课课家教育 阿里云 鲜果 W3Cfuns前端网 中国企业家 环球企业家 投资界 传媒梦工场 MSN中文网 Android开发者社区 cnbeta 投资中国网 又拍云存储 美通说传播 IT茶馆 网商在线 商业评论网 TechOrange IT时代周刊 3W创新传媒 开源中国社区 二维工坊 Iconfans 推酷 智能电视网 FreeBuf黑客与极客 财经网 DoNews 凤凰财经 新财富 eoe移动开发者社区 i黑马 网易科技 新浪科技 搜狐IT 创业家 创业邦 腾讯财经 福布斯中文网 天下网商 TechWeb 雷锋网 新浪创业 和讯科技 品途O2O 极客公园 艾瑞网 抽屉新热榜 卖家网 人民网通信频道 拉勾网 创新派 简单云主机
手机版|黑名单|守望者在线 在线教育 linux 高级程序设计 C/C++ 大数据
( 蜀ICP备14029946号 )
成都守望者科技有限公司 © 2013-2016 All Rights Reserved