找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索

[ Ngnix与高并发服务器 ] 【守望者 高并发】使用CAS实现高效并发处理

2014-10-26 22:30| 发布者: watchmen | 查看: 2458 | 收藏

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

在并发处理应用中,一般使用锁的方式来解决竞争问题,但锁的效率比较低,因此,在高并发处理中,无锁队列成为应用的需要。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同时指向同一个结点(只剩下一个结点的时候)的冲突问题。在具体实现上,如果发现只有一个结点,将再次申请新结点
 implementing lockfree_queue.pdf (173.95 KB, 下载次数: 60)  kdb_CAS.rar (149.63 KB, 下载次数: 75)

推荐阅读

[守望者   java初中级视频]22_javaNIO,AIO编程
[守望者 java初中级视频]22_javaNIO,
内容简介:本课程介绍阻塞,非阻塞,同步和异步的基本概念,介绍javaNIO,AIO
[守望者 算法视频]01_数据存储(链表与数组)
[守望者 算法视频]01_数据存储(链表与
本章重点介绍数据的在计算机的存储方式 :连续存储(数组)与链式存储,同时
[守望者   java初中级视频]00_java初中级课程学习导航
[守望者 java初中级视频]00_java初中
内容简介:全面贾少这套视频课程学习需要具备的理论基础,以及适合的学习人群
[守望者 算法视频]08_数据查找_hash算法
[守望者 算法视频]08_数据查找_hash算
守望者:普通逐个查找O(n),组织方式可以无序的数组或者普通链表。已经排序的
[守望者 linux视频]01_开发工具与开发平台
[守望者 linux视频]01_开发工具与开发
本课主要介绍gcc,gdb等系列开发工具,开始编写程序之旅。要求理解Linux开发平
[守望者 linux视频]02 进程内存管理与valgrind的使用
[守望者 linux视频]02 进程内存管理与v
本课主要介绍Linux可执行文件与进程内存结构, Linux进程结构及内存申请与释放
[守望者 C和指针]11_高级指针_C_面向对象
[守望者 C和指针]11_高级指针_C_面向对
(1) 彻底解决指针、取地址后的类型问题。(2) 回调函数示例。
[守望者 算法视频]02_数据逻辑组织_线性关联_栈与队列
[守望者 算法视频]02_数据逻辑组织_线
数组与链表是数据存储的基本方法。栈与队列是两种特殊的数据成员管理方式。栈
[守望者  java初中级视频]01_java环境搭建
[守望者 java初中级视频]01_java环境
内容介绍:学习如何搭建一个java的开发环境,配置JAVA_HOME,Classpath,path等
[守望者 算法视频]07_数据查找_普通查找与二分查找
[守望者 算法视频]07_数据查找_普通查
守望者:二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;
[守望者 算法视频]03_数据逻辑组织_树_二叉树
[守望者 算法视频]03_数据逻辑组织_树_
树是为了解决链表查找时是线性特点,树采用一分为多的方式,例如二叉树采用一
[守望者  java初中级视频]02_java语法基础
[守望者 java初中级视频]02_java语法
内容简介:介绍java语法的基础,包括常量,变量,作用域,以及常用运算符,对
[守望者 C和指针] 01_C语言快速上手
[守望者 C和指针] 01_C语言快速上手
01C程序设计快速上手课程基础 前导课程:熟悉使用Windows,熟悉编程工具(VS
[守望者 Linux 视频]09_执行单元_进程异步_信号
[守望者 Linux 视频]09_执行单元_进程
本章重点介绍Linux系统下信号的基本原理,异步与同步区别,信号的产生,安装
[守望者 算法视频]05_数据逻辑组织__红黑树
[守望者 算法视频]05_数据逻辑组织__红
守望者:1972年 由Rudolf Bayer发明的,他称之为“对称二叉B树”,它现代的名

行业聚焦  面试交流  职位推荐  开发视频   技术交流  腾讯微博  新浪微博

友情链接:课课家教育  阿里云  鲜果  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