The interviewer asks you: Do you know what an ABA problem is?

Civet cat for prince

Before we start to elaborate on the problem, let’s take a look at a short story:

After the death of Empress Song Zhenzong in the Northern Song Dynasty, his two beloved concubines Liu Concubine and Li Concubine were both pregnant. Obviously, whoever gave birth to a son was likely to become the main palace. Concubine Liu had been jealous for a long time, fearing that Concubine Li would give birth to a son and be made queen, so she made a plan with Guo Huai, the palace manager, Dutang, and with the cooperation of midwife Youshi, Concubine Li died due to coma during childbirth. Unexpectedly, the fur of a civet cat was stripped off, and it was bloody and shiny and took away the newly born prince. Concubine Liu ordered the palace maid Kou Zhu to strangle the prince to death. Kou Zhu couldn't bear it and secretly handed the prince over to the eunuch Chen Lin. Chen Lin put the prince in a suitcase and sent him to the Eight Wise Kings to raise him. Besides, Zhenzong saw the skinned civet cat and thought that Concubine Li had given birth to a monster, so he demoted her to the cold palace. Soon, Concubine Liu was in labor and gave birth to a son, who was made the prince. Concubine Liu was also named queen. Unexpectedly, six years later, Queen Liu's son died of illness. Zhenzong no longer had any heirs, so he adopted the son of his elder brother Baxian Wang (actually the prince who had been replaced that year) as his adopted son and established him as crown prince.

It can be seen from this story that the prince was replaced by a civet cat when he was born, and finally returned to become the prince by some strange combination of circumstances. Although the result is the same, the process is twists and turns, and the prince really has a bad fate.

Why tell this story? In fact, it has a lot to do with the issue we are going to introduce today. With the same result, I don’t know how many operations have occurred in the middle, so can we think that it has not changed? In different business scenarios, we must carefully consider this issue.

ABA problem description

In a multi-threaded scenario CAS will appear ABA problem, here is a simple science about ABA problem. For example, there are two threads performing CAS operation on the same value (initial value is A) at the same time. The three threads are as follows:

1. Thread 1, the expected value is A, the value to be updated is B
2. Thread 2, the expected value is A, the value to be updated is B

Thread 1 gets the CPU time slice first, while thread 2 is blocked for other reasons. Thread 1 compares the value with the expected value of A, finds that it is equal, and updates the value to B. Then the thread appears at this time 3. The expected value is B, and the value to be updated is A. Thread 3 compares the value with the expected value B. If it is found to be equal, the value is updated to A. At this time, thread 2 recovers from blocking and obtains the CPU time slice. This When thread 2 compares the value with the expected value A, and if it is found to be equal, it updates the value to B. Although thread 2 has also completed the operation, thread 2 does not know that the value has changed from A->B->A. process.

Give me a specific example

Xiao Ming withdrew 50 yuan from the cash machine because the withdrawal Machine problem, there are two threads, changing the balance from 100 to 50 at the same time:

• Thread 1 (cash machine): Get the current value of 100, and expect to update it to 50;
• Thread 2 (cash machine): Get the current value 100, expected to be updated to 50;
• Thread 1 is executed successfully, thread 2 is blocked for some reason ;
• At this time, someone remits 50 to Xiao Ming;
• Thread 3 (default): Get the current value of 50, and expect to update it to 100. At this time, thread 3 is successfully executed and the balance becomes 100;
• Thread 2 recovers from the Block and obtains 100. After comparing, it continues to update the balance to 50.

You can see at this time that the actual balance should be 100 (100-50 50) , but it actually became 50 (100-50 50 -50)This is the ABA problem that brings wrong submission results.

Solution

To solve the ABA problem, you can add a version number. When the value of memory location V is After being modified, the version number will be increased by 1

Code example

Solving ABA problems through AtomicStampedReference

• AtomicStampedReference maintains the object value and version number internally. When creating an AtomicStampedReference object, you need to pass in the initial value and initial version number;

• When AtomicStampedReference sets the object value, both the object value and the status stamp must meet the expected value for the write to succeed.

private static AtomicStampedReference<Integer> atomicStampedReference = new AtomicStampedReference<Integer>(100,1);

public static void main(String[] args) {
//第一个线程
 new Thread(() -> {
  System.out.println("t1拿到的初始版本号:" + atomicStampedReference.getStamp());
  
  //睡眠1秒，是为了让t2线程也拿到同样的初始版本号
  try {
   TimeUnit.SECONDS.sleep(1);
  } catch (InterruptedException e) {
   e.printStackTrace();
  }
  atomicStampedReference.compareAndSet(100, 101,atomicStampedReference.getStamp(),atomicStampedReference.getStamp()+1);
  atomicStampedReference.compareAndSet(101, 100,atomicStampedReference.getStamp(),atomicStampedReference.getStamp()+1);
 },"t1").start();
 
  // 第二个线程
 new Thread(() -> {
  int stamp = atomicStampedReference.getStamp();
  System.out.println("t2拿到的初始版本号:" + stamp);
  
  //睡眠3秒，是为了让t1线程完成ABA操作
  try {
   TimeUnit.SECONDS.sleep(3);
  } catch (InterruptedException e) {
   e.printStackTrace();
  }
  System.out.println("最新版本号:" + atomicStampedReference.getStamp());
  System.out.println(atomicStampedReference.compareAndSet(100, 2019,stamp,atomicStampedReference.getStamp() + 1) + "\t当前值:" + atomicStampedReference.getReference());
 },"t2").start();
}

1. Initial value 100, initial version number 1
2. Threads t1 and t2 get the same initial version number
3. Thread t1 completed the ABA operation, and the version number was incremented to 3
4. Thread t2 completed the CAS operation, and the latest version number has become 3, which is not equal to the version number 1 that thread t2 got before, and the operation failed

Execution results:

t1拿到的初始版本号:1
t2拿到的初始版本号:1
最新版本号:3
false 当前值:100

Solve ABA problem through AtomicMarkableReference

AtomicStampedReferenceYou can add a version number to the reference and track the entire change process of the reference, such as: A -> B -> C -> D -> A. Through AtomicStampedReference, we can know the reference variable It was changed three times during the process. However, sometimes, we don't care how many times the reference variable has been changed, but simply whether it has been changed, so there is AtomicMarkableReference, The only difference between AtomicMarkableReference is that it no longer uses int to identify the reference, but uses a boolean variable to indicate whether the reference variable has been changed.

private static AtomicMarkableReference<Integer> atomicMarkableReference = new AtomicMarkableReference<Integer>(100,false);

public static void main(String[] args) {
// 第一个线程
 new Thread(() -> {
  System.out.println("t1版本号是否被更改:" + atomicMarkableReference.isMarked());
  
  //睡眠1秒，是为了让t2线程也拿到同样的初始版本号
  try {
   TimeUnit.SECONDS.sleep(1);
  } catch (InterruptedException e) {
   e.printStackTrace();
  }
  atomicMarkableReference.compareAndSet(100, 101,atomicMarkableReference.isMarked(),true);
  atomicMarkableReference.compareAndSet(101, 100,atomicMarkableReference.isMarked(),true);
 },"t1").start();
 
  // 第二个线程
 new Thread(() -> {
  boolean isMarked = atomicMarkableReference.isMarked();
  System.out.println("t2版本号是否被更改:" + isMarked);
  
  //睡眠3秒，是为了让t1线程完成ABA操作
  try {
   TimeUnit.SECONDS.sleep(3);
  } catch (InterruptedException e) {
   e.printStackTrace();
  }
  System.out.println("是否更改过:" + atomicMarkableReference.isMarked());
  System.out.println(atomicMarkableReference.compareAndSet(100, 2019,isMarked,true) + "\t当前值:" + atomicMarkableReference.getReference());
 },"t2").start();
}

1. The initial value is 100, and the initial version number has not been modified false
2. Threads t1 and t2 have the same initial version number and have not been modified false
3. Thread t1 completed the ABA operation, and the version number was modified to true
4. Thread t2 completed the CAS operation, and the version number has changed to true, which is not equal to the version number false obtained by thread t2 before, and the operation failed

Results of the:

t1版本号是否被更改:false
t2版本号是否被更改:false
是否更改过:true
false 当前值:100

多说几句

以上是本期关于CAS领域的一个经典ABA问题的解析，不知道你在实际的工作中有没有遇到过，但是在面试中这块是并发知识考查的重点。如果你还没接触过此类的问题，我的建议是你自己将上面的代码运行一下，结合理论去理解一下ABA问题所带来的问题以及如何解决他，这对你日后的开发工作也是有莫大的帮助的！

The above is the detailed content of The interviewer asks you: Do you know what an ABA problem is?. For more information, please follow other related articles on the PHP Chinese website!