前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >CAS和ABA问题

CAS和ABA问题

作者头像
用户1212940
发布2022-04-13 13:17:19
4020
发布2022-04-13 13:17:19
举报
文章被收录于专栏:Lambda

定义

无锁编程是指在不使用锁的情况下,在多线程环境下实现多变量的同步。即在没有线程阻塞的情况下实现同步。这样可以避免竞态、死锁等问题。

原理

CAS是指Compare-and-swap或Compare-and-Set CAS是一个原子操作,用于多线程环境下的同步。它比较内存中的内容和给定的值,只有当两者相同时(说明其未被修改),才会修改内存中的内容。 实现如下:

代码语言:javascript
复制
int compare_and_swap(int* reg, int oldval, int newval)
{
  ATOMIC();
  int old_reg_val = *reg;
  if (old_reg_val == oldval)
     *reg = newval;
  END_ATOMIC();
  return old_reg_val;
}

代码语言:javascript
复制
bool compare_and_swap(int *accum, int *dest, int newval)
{
  if (*accum == *dest) {
      *dest = newval;
      return true;
  } else {
      *accum = *dest;
      return false;
  }
}

返回bool值得好处是可以知道是否设置成功。

在实际环境中,使用的是:

代码语言:javascript
复制
bool __sync_bool_compare_and_swap (type *ptr, type oldval, type newval, ...)
type __sync_val_compare_and_swap (type *ptr, type oldval, type newval, ...)

在使用CAS时,需要先获取操作变量的值并放到oldval中,之后调用cas函数,直到调用成功。例如给变量val赋值

代码语言:javascript
复制
while(true)
{
    int oldval=val;
    if(__sync_bool_compare_and_swap(&val, oldval, newval))
        break;
}

ABA问题

在多线程环境中,使用lock-free的CAS时,如果一个线程对变量修改2次,第2次修改后的值和第1次修改前的值相同,那么可能就会出现ABA问题。以上面的例子为例: 假设有两个线程P1和P2,P1执行完int oldval=val后被其他线程抢占。P2线程在此期间修改了val的值(可能多次修改),但最终val的值和修改前一样。当P1线程之后运行CAS函数时,并不能发现这个问题。这就是ABA问题。

解决方法

一个常用的方法是添加额外的“tag”或“stamp”位来标记是指针是否被修改过。

参考: Compare-and-swap

ABA problem

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018/04/26 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 定义
  • 原理
  • ABA问题
    • 解决方法
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档