Java面试题之CAS和ABA问题

简介: 原子操作可以是一个步骤,也可以是多个操作步骤,但是其顺序不能被打乱,也不可以被切割而只执行其中的一部分(不可中断性)。将整个操作视为一个整体,资源在该次操作中保持一致,这是原子性的核心特征。

目录

一、原子操作


原子操作可以是一个步骤,也可以是多个操作步骤,但是其顺序不能被打乱,也不可以被切割而只执行其中的一部分(不可中断性)。将整个操作视为一个整体,资源在该次操作中保持一致,这是原子性的核心特征。

二、CAS(Compare And Swap)


1、CAS概述

CAS属于硬件同步原语,处理器提供了基本内存操作的原子性保证。


CAS操作需要输入两个数值,一个旧值A(期望操作前的值)和一个新值B,在操作期间先对旧值进行比较,若没有发生变化,才交换成新值,发生了变化则不交换。


Java中的sum.misc.Unsafe类,提供了compareAndSwapInt()和compareAndSwapLong()等几个方法实现CAS。

6.png


2、CAS加自旋实现原子性操作示例

public class CustomAtomicCounter {
  private volatile int i = 0;
  private static Unsafe unsafe = null;
  private static long valueOffset;
  static {
    try {
      Field field = Unsafe.class.getDeclaredField("theUnsafe");
      field.setAccessible(true);
      unsafe = (Unsafe) field.get(null);
      valueOffset = unsafe.objectFieldOffset(CustomAtomicCounter.class.getDeclaredField("i"));
    } catch (NoSuchFieldException | IllegalAccessException e) {
      e.printStackTrace();
    }
  }
  public void add() {
    int current = 0;
    do {
      current = unsafe.getIntVolatile(this, valueOffset);
    } while (!unsafe.compareAndSwapInt(this, valueOffset, current, current + 1));
  }
  public int getValue() {
    return i;
  }
  public static void main(String[] args) throws InterruptedException {
    CustomAtomicCounter counter = new CustomAtomicCounter();
    for (int count = 0; count < 10000; count++) {
      new Thread(() -> {
        counter.add();
      }).start();
    }
    Thread.sleep(3000L);
    System.out.println(counter.getValue());
  }
}

备注:可以看到控制台输出为10000

三、CAS的三个小问题


CAS若使用不当,会引发如下三个小问题:

  • 循环 + CAS,自旋的实现让所有线程都处于高频运行,争抢CPU执行时间的状态。如果操作不成功,会带来很大的CPU资源消耗。
  • 仅针对单个变量的操作,不能用于多个变量实现原子操作。
  • ABA问题。

四、ABA问题


1、ABA问题详解

先看下面这幅图:

7.png

上图中thread1经过CAS操作之后把i的值从0改为1,最终又改回了1,而thread2在等待thread1执行完操作后,接着又通过CAS操作将值改为了1。

备注:其实i的值实际上已经被修改过了,这个时候的i已经不是之前的了,一句话,已经被用过了。

2、ABA问题示例之不安全的栈

这里我们以数据结构栈(先进后出)为示例,展现ABA问题,不安全的栈代码示例如下:

public class Node {
  public final String value;
  public Node next;
  public Node(String value) {
    this.value = value;
  }
  @Override
  public String toString() {
    return "Node[" + "value='" + value + '\'' + ']';
  }
}
public class UnsafeStack {
 private AtomicReference<Node> top = new AtomicReference<>();
 /**
  * 入栈
  * @param node
  */
 public void push(Node node) {
  Node oldTop = null;
  do {
   oldTop = top.get();
   node.next = oldTop;
  } while (!top.compareAndSet(oldTop, node)); // CAS操作替换栈顶
 }
 public Node pop(int timeInMillis) {
  Node newTop = null;
  Node oldTop = null;
  do {
   oldTop = top.get();
   if (oldTop == null) {
    return null;
   }
   newTop = oldTop.next;
   // 模拟延时
   if (timeInMillis > 0) {
    LockSupport.parkNanos(1000 * 1000 * timeInMillis);
   }
  } while (!top.compareAndSet(oldTop, newTop)); // CAS操作替换栈顶
  return oldTop;
 }
 public Node peek() {
  return top.get();
 }
}

3、代码测试用例

这里我们用两个线程模拟入栈和出栈的动作,操作步骤如下:

  1. 主线程:先对栈进行初始化,B入栈A入栈,栈顶指向A。
  2. 线程2:A出栈B出栈D入栈C入栈A再次入栈,栈顶仍然指向A。
  3. 线程1:A出栈
public class AbaProblemExample {
  public static void main(String[] args) {
    UnsafeStack stack = new UnsafeStack();
    stack.push(new Node("B")); // B入栈
    stack.push(new Node("A")); // A入栈
    Thread thread1 = new Thread(() -> {
      // A出栈
      Node node = stack.pop(500);
      System.out.println(Thread.currentThread().getName() + " " + node);
    });
    thread1.start();
    Thread thread2 = new Thread(() -> {
      LockSupport.parkNanos(1000 * 1000 * 300);
      // A出栈
      Node nodeA = stack.pop(0);
      System.out.println(Thread.currentThread().getName() + " " + nodeA);
      // B出栈
      Node nodeB = stack.pop(0);
      System.out.println(Thread.currentThread().getName() + " " + nodeB);
      stack.push(new Node("D"));
      stack.push(new Node("C"));
      // A再次入栈,因此栈顶依然是A
      stack.push(nodeA);
    });
    thread2.start();
    // 休眠两秒
    LockSupport.parkNanos(1000 * 1000 * 1000 * 2);
    System.out.println("开始遍历UnsafeStack:");
    Node node = null;
    while ((node = stack.pop(0)) != null) {
      System.out.println(node);
    }
  }
}

运行测试用例,控制台输出如下:

Thread-1 Node[value='A']
Thread-1 Node[value='B']
Thread-0 Node[value='A']
开始遍历UnsafeStack:
Node[value='B']

备注:其实栈中的内容已经被thread2修改过了,栈中的内容从栈顶到栈底应该为 C → D,理论上遍历栈的输出应该为:Node[value='C']Node[value='D']

4、ABA问题解决方案之线程安全的栈

其实ABA问题也容易解决,带上版本号就行了。虽然值还是原来的值,被用过了,但是我们可以记录被用过的次数。

基于版本号实现的线程安全的栈如下:

public class ConcurrentStack {
  private AtomicStampedReference<Node> top = new AtomicStampedReference<>(null, 0);
  /**
   * 入栈
   * @param node
   */
  public void push(Node node) {
    Node oldTop = null;
    int version = 0;
    do {
      version = top.getStamp();
      oldTop = top.getReference();
      node.next = oldTop;
    } while (!top.compareAndSet(oldTop, node, version, version + 1)); // CAS操作替换栈顶
  }
  public Node pop(int timeInMillis) {
    Node newTop = null;
    Node oldTop = null;
    int version = 0;
    do {
      oldTop = top.getReference();
      version = top.getStamp();
      if (oldTop == null) {
        return null;
      }
      newTop = oldTop.next;
      // 模拟延时
      if (timeInMillis > 0) {
        LockSupport.parkNanos(1000 * 1000 * timeInMillis);
      }
    } while (!top.compareAndSet(oldTop, newTop, version, version + 1)); // CAS操作替换栈顶
    return oldTop;
  }
  public Node peek() {
    return top.getReference();
  }
}

再次运行AbaProblemExample测试用例,将其中的UnsafeStack替换为ConcurrentStack即可,控制台输出如下:

Thread-1 Node[value='A']
Thread-1 Node[value='B']
Thread-0 Node[value='A']
开始遍历UnsafeStack:
Node[value='C']
Node[value='D']

备注:可以看到加上版本号后,再次模拟出入栈,我们的遍历结果是正确的。

目录
打赏
0
1
0
0
676
分享
相关文章
Java社招面试中的高频考点:Callable、Future与FutureTask详解
大家好,我是小米。本文主要讲解Java多线程编程中的三个重要概念:Callable、Future和FutureTask。它们在实际开发中帮助我们更灵活、高效地处理多线程任务,尤其适合社招面试场景。通过 Callable 可以定义有返回值且可能抛出异常的任务;Future 用于获取任务结果并提供取消和检查状态的功能;FutureTask 则结合了两者的优势,既可执行任务又可获取结果。掌握这些知识不仅能提升你的编程能力,还能让你在面试中脱颖而出。文中结合实例详细介绍了这三个概念的使用方法及其区别与联系。希望对大家有所帮助!
172 60
Java社招面试题:一个线程运行时发生异常会怎样?
大家好,我是小米。今天分享一个经典的 Java 面试题:线程运行时发生异常,程序会怎样处理?此问题考察 Java 线程和异常处理机制的理解。线程发生异常,默认会导致线程终止,但可以通过 try-catch 捕获并处理,避免影响其他线程。未捕获的异常可通过 Thread.UncaughtExceptionHandler 处理。线程池中的异常会被自动处理,不影响任务执行。希望这篇文章能帮助你深入理解 Java 线程异常处理机制,为面试做好准备。如果你觉得有帮助,欢迎收藏、转发!
60 14
Java 面试必问!线程构造方法和静态块的执行线程到底是谁?
大家好,我是小米。今天聊聊Java多线程面试题:线程类的构造方法和静态块是由哪个线程调用的?构造方法由创建线程实例的主线程调用,静态块在类加载时由主线程调用。理解这些细节有助于掌握Java多线程机制。下期再见! 简介: 本文通过一个常见的Java多线程面试题,详细讲解了线程类的构造方法和静态块是由哪个线程调用的。构造方法由创建线程实例的主线程调用,静态块在类加载时由主线程调用。理解这些细节对掌握Java多线程编程至关重要。
43 13
Java线程调度揭秘:从算法到策略,让你面试稳赢!
在社招面试中,关于线程调度和同步的相关问题常常让人感到棘手。今天,我们将深入解析Java中的线程调度算法、调度策略,探讨线程调度器、时间分片的工作原理,并带你了解常见的线程同步方法。让我们一起破解这些面试难题,提升你的Java并发编程技能!
77 16
Java 高级面试技巧:yield() 与 sleep() 方法的使用场景和区别
本文详细解析了 Java 中 `Thread` 类的 `yield()` 和 `sleep()` 方法,解释了它们的作用、区别及为什么是静态方法。`yield()` 让当前线程释放 CPU 时间片,给其他同等优先级线程运行机会,但不保证暂停;`sleep()` 则让线程进入休眠状态,指定时间后继续执行。两者都是静态方法,因为它们影响线程调度机制而非单一线程行为。这些知识点在面试中常被提及,掌握它们有助于更好地应对多线程编程问题。
61 9
Java面试必问!run() 和 start() 方法到底有啥区别?
在多线程编程中,run和 start方法常常让开发者感到困惑。为什么调用 start 才能启动线程,而直接调用 run只是普通方法调用?这篇文章将通过一个简单的例子,详细解析这两者的区别,帮助你在面试中脱颖而出,理解多线程背后的机制和原理。
66 12
Java Dubbo 面试题
Java Dubbo相关基础面试题
Java MyBatis 面试题
Java MyBatis相关基础面试题
Java JVM 面试题
Java JVM(虚拟机)相关基础面试题
Java Druid 面试题
Java Druid 连接池相关基础面试题

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等