Maison  >  Article  >  Java  >  L'intervieweur vous demande : Savez-vous ce qu'est un problème ABA ?

L'intervieweur vous demande : Savez-vous ce qu'est un problème ABA ?

Java学习指南
Java学习指南avant
2023-07-26 15:09:451238parcourir

La civette échange contre le prince

Avant de commencer à expliquer le problème, jetons un coup d'œil à une courte histoire :

Après la mort de l'impératrice Zhenzong de la dynastie des Song du Nord, ses deux concubines bien-aimées à l'époque, Concubine Liu et Concubine Li. Elles sont toutes enceintes. Il est évident que celui qui donnera naissance à un fils pourra devenir le palais principal. La concubine Liu était jalouse depuis longtemps, craignant que la concubine Li ne donne naissance à un fils et ne devienne reine, alors elle a élaboré un plan avec Guo Huai, le directeur du palais, Dutang, et avec la coopération de la sage-femme Youshi, Concubine Li. est mort du coma pendant l'accouchement. De façon inattendue, la fourrure d'un chat civette a été enlevée, elle était sanglante et brillante et a emporté le prince nouveau-né. La concubine Liu a ordonné à la servante du palais Kou Zhu d'étrangler le prince à mort. Kou Zhu n'a pas pu le supporter et a secrètement remis le prince à l'eunuque Chen Lin. Chen Lin a mis le prince dans une valise et l'a envoyé aux huit rois sages. pour l'élever. De plus, Zhenzong a vu la civette écorchée et a pensé que la concubine Li avait donné naissance à un monstre, alors il l'a rétrogradée au palais froid. Bientôt, la concubine Liu était en travail et a donné naissance à un fils, qui a été nommé prince et a également été nommée reine. De façon inattendue, six ans plus tard, le fils de la reine Liu est mort de maladie. Zhenzong n'avait plus d'héritiers, il adopta donc le fils de son frère aîné Baxian Wang (en fait le prince qui avait été remplacé cette année-là) comme fils adoptif et l'établit comme prince héritier.

On peut voir dans cette histoire que le prince a été remplacé par un chat civette à sa naissance, et est finalement revenu pour devenir le prince par un étrange concours de circonstances. Bien que le résultat soit le même, le processus est tortueux et le prince a vraiment un mauvais sort.

Pourquoi raconter cette histoire ? En fait, cela a beaucoup à voir avec la question que nous allons introduire aujourd’hui. Avec le même résultat, je ne sais pas combien d’opérations ont eu lieu au milieu, alors peut-on penser que cela n’a pas changé ? Dans différents scénarios commerciaux, nous devons examiner attentivement cette question.

Description du problème ABA

Dans un scénario multithreadCAS会出现ABA, voici une science simple sur le problème ABA. Par exemple, il y a deux threads qui effectuent des opérations CAS sur la même valeur (la valeur initiale est. A) en même temps. Ceci Les trois fils sont les suivants :

  1. Thread 1, la valeur attendue est A, la valeur à mettre à jour est B
  2. Thread 2, la valeur attendue est A, la valeur à mettre à jour est B

Thread 1 obtient la tranche de temps CPU d'abord, tandis que le thread 2 obtient la tranche de temps CPU en premier pour d'autres raisons. La raison est bloquée. La valeur du thread 1 est comparée à la valeur attendue de A. Elle s'avère égale, puis la valeur est mise à jour vers B. Ensuite. à ce moment, le thread 3 apparaît, la valeur attendue est B, la valeur à mettre à jour est A et la valeur du thread 3 est la même que la valeur attendue. Comparez la valeur B et si elle s'avère égale, mettez à jour. la valeur à A. À ce moment, le thread 2 récupère du blocage et obtient la tranche de temps CPU. À ce moment, la valeur du thread 2 est comparée à la valeur attendue A. Si elle s'avère égale, la valeur est mise à jour. à B. , bien que le thread 2 ait également terminé l'opération, le thread 2 ne sait pas que la valeur a suivi le processus de modification de A->B->A.

Donnez-moi un exemple précis

Xiao Ming a retiré 50 yuans du distributeur automatique de billets. En raison d'un problème avec le distributeur automatique de billets, il y a eu deux fils de discussion et le solde est passé de 100 à 50 en même temps. heure :

  • Thread 1 (cash machine) : obtenez la valeur actuelle 100, prévoyez une mise à jour à 50 ;
  • Thread 2 (cash machine) : obtenez la valeur actuelle 100, attendez-vous à une mise à jour à 50 ;
  • Le fil 1 a été exécuté avec succès, le fil 2 est bloqué pour une raison quelconque ;
  • À ce moment-là, quelqu'un remet 50 à Xiao Ming ;
  • Thread 3 (par défaut) : obtient la valeur actuelle de 50 et s'attend à ce qu'elle soit être mis à jour à 100. À ce moment, le thread 3 est exécuté avec succès et le solde devient 100
  • Le thread 2 récupère du bloc et obtient 100. Après comparaison, il continue de mettre à jour le solde à 50.
  • Vous pouvez voir à ce stade que le solde réel devrait être
C'est le problème ABA qui entraîne des résultats de soumission erronés.

100(100-50+50),但是实际上变为了50(100-50+50-50)

Solution Pour résoudre le problème ABA, vous pouvez ajouter un numéro de version. Chaque fois que la valeur de l'emplacement mémoire V est modifiée, le numéro de version est augmenté de 1

.

Exemple de code

Résolution des problèmes ABA via AtomicStampedReference

  • AtomicStampedReference conserve la valeur de l'objet et le numéro de version en interne. Lors de la création d'un objet AtomicStampedReference, vous devez transmettre la valeur initiale et numéro de version initiale ;

  • Lorsque AtomicStampedReference définit la valeur de l'objet, la valeur de l'objet et le tampon d'état doivent correspondre à la valeur attendue pour que l'écriture réussisse.

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. Valeur initiale 100, numéro de version initiale 1
2. Les threads t1 et t2 obtiennent le même numéro de version initial
3. Le thread t1 termine l'opération ABA et le numéro de version est augmenté à 3
4. .Thread t2 L'opération CAS est terminée. Le dernier numéro de version est devenu 3, ce qui n'est pas égal au numéro de version 1 obtenu par le thread t2 auparavant. Résolvez le problème ABA via AtomicMarkableReference

, La seule différence entre AtomicMarkableReference est qu'il n'utilise plus int pour identifier la référence, mais utilise une variable booléenne pour indiquer si la variable de référence a été modifiée.

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

1. La valeur initiale est 100, le numéro de version initial n'a pas été modifié faux 2 Les fils de discussion t1 et t2 ont obtenu le même numéro de version initial et n'ont pas été modifiés faux

3. Opération, et le numéro de version a été modifié vrai

4. Le fil t2 a terminé l'opération CAS, ce qui n'est pas égal au numéro de version faux obtenu par le fil t2 auparavant. L'opération a échoué

Exécution. résultat : AtomicStampedReference可以给引用加上版本号,追踪引用的整个变化过程,如:A -> B -> C -> D -> A,通过AtomicStampedReference,我们可以知道,引用变量中途被更改了3次。但是,有时候,我们并不关心引用变量更改了几次,只是单纯的关心是否更改过,所以就有了AtomicMarkableReference

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

多说几句

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Déclaration:
Cet article est reproduit dans:. en cas de violation, veuillez contacter admin@php.cn Supprimer