Introduction à l'analyse des principes Java CAS

Tutoriel de base JavaIntroduction et analyse des colonnes Java CAS

Recommandé (gratuit) : Tutoriel de base Java

1 Introduction

CAS signifie comparer et échanger A. mécanisme pour implémenter la fonctionnalité de synchronisation dans un environnement multithread. Une opération CAS contient trois opérandes : un emplacement mémoire, une valeur attendue et une nouvelle valeur. La logique d'implémentation de CAS consiste à comparer la valeur à l'emplacement mémoire avec la valeur attendue. Si elles sont égales, remplacez la valeur à l'emplacement mémoire par la nouvelle valeur. S'il n'est pas égal, aucune opération n'est effectuée.

En Java, Java n'implémente pas directement CAS. Les implémentations liées à CAS sont implémentées sous la forme d'un assemblage en ligne C++. Le code Java doit être appelé via JNI. J'analyserai les détails de mise en œuvre au chapitre 3.

Comme mentionné précédemment, le processus de fonctionnement du CAS n'est pas difficile. Mais l’explication ci-dessus ne suffit pas. Ensuite, je présenterai d’autres connaissances de base. Ce n’est qu’avec ces connaissances de base que nous pourrons mieux comprendre le contenu ultérieur.

2. Introduction générale

Nous savons tous que le processeur transmet les données via le bus et la mémoire. À l'ère du multicœur, plusieurs cœurs communiquent avec la mémoire et d'autres matériels via le même bus. Comme indiqué ci-dessous :

Source de l'image : "Compréhension approfondie des systèmes informatiques"

L'image ci-dessus est un diagramme de structure informatique relativement simple, bien que simple. , il suffit d'expliquer la question. Dans le schéma ci-dessus, le CPU communique avec la mémoire via le bus marqué par les deux flèches bleues. Considérons une question : si plusieurs cœurs du processeur fonctionnent sur la même mémoire en même temps, quels types d'erreurs se produiront si elle n'est pas contrôlée ? Voici une brève explication, en supposant que le noyau 1 écrit des données 64 bits dans la mémoire via un bus de bande passante de 32 bits, le noyau 1 doit écrire deux fois pour terminer l'ensemble de l'opération. Si, après que le noyau 1 ait écrit des données 32 bits pour la première fois, le noyau 2 lit les données 64 bits à partir de l'emplacement mémoire écrit par le noyau 1. Étant donné que le noyau 1 n'a pas complètement écrit toutes les données 64 bits dans la mémoire, le noyau 2 commence à lire les données à partir de cet emplacement mémoire, les données lues doivent donc être chaotiques.

Mais il n’y a en réalité aucune raison de s’inquiéter de ce problème. Grâce au manuel du développeur Intel, nous pouvons apprendre qu'à partir des processeurs Pentium, les processeurs Intel assureront la lecture et l'écriture atomiques de quadwords alignés sur des limites de 64 bits.

Sur la base de la description ci-dessus, nous pouvons conclure que les processeurs Intel peuvent garantir que les instructions alignées sur la mémoire à accès unique sont exécutées de manière atomique. Mais que se passe-t-il s’il s’agit d’une instruction pour accéder deux fois à la mémoire ? La réponse n’est pas garantie. Par exemple, l'instruction d'incrémentation inc dword ptr [...] est équivalente à DEST = DEST + 1. Cette instruction contient trois opérations 读->改->写, impliquant deux accès mémoire. Considérons une situation dans laquelle une valeur de 1 est stockée à un emplacement spécifié en mémoire. Désormais, les deux cœurs du processeur exécutent l’instruction en même temps. Le processus d'exécution alternée des deux cœurs est le suivant :

1. Le noyau 1 lit la valeur 1 à partir de l'emplacement spécifié en mémoire et la charge dans le registre.
2. Le noyau 2 lit depuis l'emplacement spécifié dans la mémoire Valeur 1 et chargez-le dans le registre
3. Core 1 Décrémentez la valeur dans le registre de 1
4. Core 2 Décrémentez la valeur dans le registre de 1
5. Core 1 Écrit la valeur modifiée en mémoire
6. Core 2 réécrit la valeur modifiée en mémoire

Après avoir exécuté le processus ci-dessus, la valeur finale dans la mémoire est 2, et ce à quoi nous nous attendions est 3, c'est ce qui se passe Problème. Pour résoudre ce problème, il est nécessaire d’empêcher deux ou plusieurs cœurs d’exploiter la même zone mémoire en même temps. Alors comment l’éviter ? Ceci présente le protagoniste de cet article – le préfixe de verrouillage. Pour une description détaillée de cette instruction, veuillez vous référer au Manuel du développeur Intel, volume 2, référence du jeu d'instructions, chapitre 3, référence du jeu d'instructions A-L. J'en cite ici une section, comme suit :

LOCK—Assert LOCK# Signal Prefix
Provoque l'affirmation du signal LOCK# du processeur lors de l'exécution de l'instruction qui l'accompagne (transforme l'instruction en une instruction atomique). Dans un environnement multiprocesseur, le signal LOCK# garantit que le processeur a l'usage exclusif de toute mémoire partagée pendant que le signal est affirmé.

Les points clés décrits ci-dessus ont été utilisés. Il est souligné en gras que dans un environnement multiprocesseur, le signal LOCK# peut garantir que le processeur a l'usage exclusif d'une partie de la mémoire partagée. le verrou peut être ajouté avant les instructions suivantes :

ADD, ADC, AND, BTC, BTR, BTS, CMPXCHG, CMPXCH8B, CMPXCHG16B, DEC, INC, NEG, NOT, OR, SBB, SUB, XOR, XADD , et XCHG.

En ajoutant le préfixe lock avant l'instruction inc, vous pouvez rendre l'instruction atomique. Lorsque plusieurs cœurs exécutent la même instruction inc en même temps, ils le feront de manière série, évitant ainsi la situation mentionnée ci-dessus. Il y a donc une autre question ici : comment le préfixe de verrouillage garantit-il que le noyau occupe exclusivement une certaine zone mémoire ? La réponse est la suivante :

Dans les processeurs Intel, il existe deux manières de garantir qu'un certain cœur du processeur occupe exclusivement une certaine zone mémoire. La première consiste à verrouiller le bus et à laisser un certain nombre de personnes utiliser le bus exclusivement, mais cela coûte trop cher. Une fois le bus verrouillé, les autres cœurs ne peuvent pas accéder à la mémoire, ce qui peut empêcher les autres cœurs de fonctionner pendant une courte période. La deuxième méthode consiste à verrouiller le cache si certaines données de la mémoire sont mises en cache dans le cache du processeur. Le signal LOCK# émis par le processeur ne verrouille pas le bus, mais verrouille la zone mémoire correspondant à la ligne de cache. Les autres processeurs ne peuvent pas effectuer d'opérations associées sur cette zone mémoire tant que cette zone mémoire est verrouillée. Par rapport au verrouillage du bus, le coût du verrouillage du cache est évidemment inférieur. Concernant les verrous de bus et de cache, pour une description plus détaillée, veuillez vous référer au Manuel du développeur Intel Volume 3 Manuel du développeur de logiciels, Chapitre 8 Gestion de plusieurs processeurs.

3. Analyse du code source

Avec les connaissances de base ci-dessus, nous pouvons désormais lire tranquillement le code source de CAS. Le contenu de ce chapitre analysera la méthode compareAndSet dans la classe atomique AtomicInteger sous le package java.util.concurrent.atomic L'analyse pertinente est la suivante :

public class AtomicInteger extends Number implements java.io.Serializable {

    // setup to use Unsafe.compareAndSwapInt for updates
    private static final Unsafe unsafe = Unsafe.getUnsafe();
    private static final long valueOffset;

    static {
        try {
            // 计算变量 value 在类对象中的偏移
            valueOffset = unsafe.objectFieldOffset
                (AtomicInteger.class.getDeclaredField("value"));
        } catch (Exception ex) { throw new Error(ex); }
    }

    private volatile int value;
    
    public final boolean compareAndSet(int expect, int update) {
        /*
         * compareAndSet 实际上只是一个壳子，主要的逻辑封装在 Unsafe 的 
         * compareAndSwapInt 方法中
         */
        return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
    }
    
    // ......
}

public final class Unsafe {
    // compareAndSwapInt 是 native 类型的方法，继续往下看
    public final native boolean compareAndSwapInt(Object o, long offset,
                                                  int expected,
                                                  int x);
    // ......
}

// unsafe.cpp
/*
 * 这个看起来好像不像一个函数，不过不用担心，不是重点。UNSAFE_ENTRY 和 UNSAFE_END 都是宏，
 * 在预编译期间会被替换成真正的代码。下面的 jboolean、jlong 和 jint 等是一些类型定义（typedef）：
 * 
 * jni.h
 *     typedef unsigned char   jboolean;
 *     typedef unsigned short  jchar;
 *     typedef short           jshort;
 *     typedef float           jfloat;
 *     typedef double          jdouble;
 * 
 * jni_md.h
 *     typedef int jint;
 *     #ifdef _LP64 // 64-bit
 *     typedef long jlong;
 *     #else
 *     typedef long long jlong;
 *     #endif
 *     typedef signed char jbyte;
 */
UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSwapInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x))
  UnsafeWrapper("Unsafe_CompareAndSwapInt");
  oop p = JNIHandles::resolve(obj);
  // 根据偏移量，计算 value 的地址。这里的 offset 就是 AtomaicInteger 中的 valueOffset
  jint* addr = (jint *) index_oop_from_field_offset_long(p, offset);
  // 调用 Atomic 中的函数 cmpxchg，该函数声明于 Atomic.hpp 中
  return (jint)(Atomic::cmpxchg(x, addr, e)) == e;
UNSAFE_END

// atomic.cpp
unsigned Atomic::cmpxchg(unsigned int exchange_value,
                         volatile unsigned int* dest, unsigned int compare_value) {
  assert(sizeof(unsigned int) == sizeof(jint), "more work to do");
  /*
   * 根据操作系统类型调用不同平台下的重载函数，这个在预编译期间编译器会决定调用哪个平台下的重载
   * 函数。相关的预编译逻辑如下：
   * 
   * atomic.inline.hpp：
   *    #include "runtime/atomic.hpp"
   *    
   *    // Linux
   *    #ifdef TARGET_OS_ARCH_linux_x86
   *    # include "atomic_linux_x86.inline.hpp"
   *    #endif
   *   
   *    // 省略部分代码
   *    
   *    // Windows
   *    #ifdef TARGET_OS_ARCH_windows_x86
   *    # include "atomic_windows_x86.inline.hpp"
   *    #endif
   *    
   *    // BSD
   *    #ifdef TARGET_OS_ARCH_bsd_x86
   *    # include "atomic_bsd_x86.inline.hpp"
   *    #endif
   * 
   * 接下来分析 atomic_windows_x86.inline.hpp 中的 cmpxchg 函数实现
   */
  return (unsigned int)Atomic::cmpxchg((jint)exchange_value, (volatile jint*)dest,
                                       (jint)compare_value);
}

L'analyse ci-dessus semble être longue, mais. le processus principal n’est pas compliqué. Si vous ne vous attardez pas sur les détails du code, il est relativement facile à comprendre. Ensuite, j'analyserai la fonction Atomic::cmpxchg sous la plateforme Windows. Continuez à lire.

// atomic_windows_x86.inline.hpp
#define LOCK_IF_MP(mp) __asm cmp mp, 0  \
                       __asm je L0      \
                       __asm _emit 0xF0 \
                       __asm L0:
              
inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value) {
  // alternative for InterlockedCompareExchange
  int mp = os::is_MP();
  __asm {
    mov edx, dest
    mov ecx, exchange_value
    mov eax, compare_value
    LOCK_IF_MP(mp)
    cmpxchg dword ptr [edx], ecx
  }
}

Le code ci-dessus est constitué de l'identifiant précompilé LOCK_IF_MP et de la fonction cmpxchg. Pour y voir un peu plus clair, remplaçons LOCK_IF_MP dans la fonction cmpxchg par le contenu réel. Comme suit :

inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value) {
  // 判断是否是多核 CPU
  int mp = os::is_MP();
  __asm {
    // 将参数值放入寄存器中
    mov edx, dest    // 注意: dest 是指针类型，这里是把内存地址存入 edx 寄存器中
    mov ecx, exchange_value
    mov eax, compare_value
    
    // LOCK_IF_MP
    cmp mp, 0
    /*
     * 如果 mp = 0，表明是线程运行在单核 CPU 环境下。此时 je 会跳转到 L0 标记处，
     * 也就是越过 _emit 0xF0 指令，直接执行 cmpxchg 指令。也就是不在下面的 cmpxchg 指令
     * 前加 lock 前缀。
     */
    je L0
    /*
     * 0xF0 是 lock 前缀的机器码，这里没有使用 lock，而是直接使用了机器码的形式。至于这样做的
     * 原因可以参考知乎的一个回答：
     *     https://www.zhihu.com/question/50878124/answer/123099923
     */ 
    _emit 0xF0
L0:
    /*
     * 比较并交换。简单解释一下下面这条指令，熟悉汇编的朋友可以略过下面的解释:
     *   cmpxchg: 即“比较并交换”指令
     *   dword: 全称是 double word，在 x86/x64 体系中，一个 
     *          word = 2 byte，dword = 4 byte = 32 bit
     *   ptr: 全称是 pointer，与前面的 dword 连起来使用，表明访问的内存单元是一个双字单元
     *   [edx]: [...] 表示一个内存单元，edx 是寄存器，dest 指针值存放在 edx 中。
     *          那么 [edx] 表示内存地址为 dest 的内存单元
     *          
     * 这一条指令的意思就是，将 eax 寄存器中的值（compare_value）与 [edx] 双字内存单元中的值
     * 进行对比，如果相同，则将 ecx 寄存器中的值（exchange_value）存入 [edx] 内存单元中。
     */
    cmpxchg dword ptr [edx], ecx
  }
}

Ceci conclut le processus de mise en œuvre de CAS La mise en œuvre de CAS est indissociable du support du processeur. Il y a tellement de codes ci-dessus, mais le code principal est en fait une instruction cmpxchg avec un préfixe de verrouillage, c'est-à-dire lock cmpxchg dword ptr [edx], ecx.

4. Problèmes ABA

Quand on parle de CAS, nous devons essentiellement parler des problèmes ABA du CAS. CAS se compose de trois étapes, à savoir "lecture->comparer->écriture". Considérons une situation où le thread 1 et le thread 2 exécutent la logique CAS en même temps. La séquence d'exécution des deux threads est la suivante :

1. Temps 1 : le thread 1 effectue une opération de lecture et obtient l'original. valeur A, puis le thread Switched away
2. Time 2 : Thread 2 termine l'opération CAS et modifie la valeur d'origine de A à B
3. Time 3 : Thread 2 effectue à nouveau l'opération CAS et change la valeur d'origine de B en A
4. Moment 4 : le fil 1 reprend son exécution, compare la valeur de comparaison (compareValue) avec la valeur d'origine (oldValue) et constate que les deux valeurs sont égales. Ensuite, écrivez la nouvelle valeur (newValue) dans la mémoire pour terminer l'opération CAS

comme dans le processus ci-dessus. Le fil de discussion 1 ne sait pas que la valeur d'origine a été modifiée. À son avis, il y en a. aucun changement, donc le processus continuera à s'exécuter. Pour les problèmes ABA, la solution habituelle consiste à définir un numéro de version pour chaque opération CAS. Le package java.util.concurrent.atomic fournit une classe atomique AtomicStampedReference qui peut gérer les problèmes ABA. L'implémentation spécifique ne sera pas analysée ici. Les amis intéressés peuvent la vérifier par eux-mêmes.

5. Résumé

En écrivant ceci, cet article touche enfin à sa fin. Bien que le principe du CAS lui-même, y compris sa mise en œuvre, ne soit pas difficile, il n’est vraiment pas facile à écrire. Cela implique des connaissances de bas niveau. Même si je peux le comprendre, c'est quand même un peu difficile à comprendre. En raison de mon manque de connaissances sous-jacentes, certaines des analyses ci-dessus seront inévitablement fausses. Donc, s'il y a une erreur, n'hésitez pas à commenter. Bien sûr, il est préférable d'expliquer pourquoi c'est faux. Merci.

D’accord, c’est tout pour cet article. Merci d'avoir lu et au revoir.

Annexe

Les chemins de plusieurs fichiers utilisés dans la section précédente d'analyse du code source sont publiés ici. Cela aidera tout le monde à indexer, comme suit :

文件名	路径
Unsafe.java	openjdk/jdk/src/share/classes/sun/misc/Unsafe.java
unsafe.cpp	openjdk/hotspot/src/share/vm/prims/unsafe.cpp
atomic.cpp	openjdk/hotspot/src/share/vm/runtime/atomic.cpp
atomic_windows_x86.inline.hpp	openjdk/hotspot/src/os_cpu/windows_x86/vm/atomic_windows_x86.inline.hpp

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!