Einführung in die Java CAS-Prinzipanalyse

Java Basic TutorialSpalte stellt die Analyse von Java CAS vor

Empfohlen (kostenlos): Java Basic Tutorial

1. Einführung

Der vollständige Name von CAS It's vergleichen und austauschenEs handelt sich um einen Mechanismus zum Implementieren von Synchronisationsfunktionen in einer Multithread-Umgebung. Eine CAS-Operation enthält drei Operanden – einen Speicherort, einen erwarteten Wert und einen neuen Wert. Die Implementierungslogik von CAS besteht darin, den Wert am Speicherort mit dem erwarteten Wert zu vergleichen. Wenn sie gleich sind, wird der Wert am Speicherort durch den neuen Wert ersetzt. Wenn sie nicht gleich sind, wird keine Operation ausgeführt.

In Java werden CAS-bezogene Implementierungen nicht direkt in Form einer C++-Inline-Assembly implementiert. Java-Code muss über JNI aufgerufen werden. Ich werde die Implementierungsdetails in Kapitel 3 analysieren.

Wie bereits erwähnt, ist der Prozess des CAS-Betriebs nicht schwierig. Aber die obige Erklärung reicht nicht aus. Als nächstes werde ich einige andere Hintergrundkenntnisse vorstellen. Nur mit diesem Hintergrundwissen können wir die späteren Inhalte besser verstehen.

2. Hintergrundeinführung

Wir alle wissen, dass die CPU Daten über den Bus und den Speicher überträgt. Im Multi-Core-Zeitalter kommunizieren mehrere Kerne über denselben Bus mit Speicher und anderer Hardware. Wie unten gezeigt:

Bildquelle: „Vertieftes Verständnis von Computersystemen“

Das obige Bild ist ein relativ einfaches Computerstrukturdiagramm, das jedoch ausreicht, um das Problem zu veranschaulichen. Im Diagramm oben kommuniziert die CPU mit dem Speicher über den Bus, der durch die beiden blauen Pfeile markiert ist. Betrachten wir eine Frage: Wenn mehrere Kerne der CPU gleichzeitig auf demselben Speicher arbeiten, welche Art von Fehlern treten auf, wenn dieser nicht kontrolliert wird? Hier ist eine kurze Erklärung: Unter der Annahme, dass Kern 1 64-Bit-Daten über einen 32-Bit-Bandbreitenbus in den Speicher schreibt, muss Kern 1 zweimal schreiben, um den gesamten Vorgang abzuschließen. Wenn Kern 1 zum ersten Mal 32-Bit-Daten schreibt, liest Kern 2 64-Bit-Daten aus dem von Kern 1 geschriebenen Speicherort. Da Kern 1 noch nicht alle 64-Bit-Daten vollständig in den Speicher geschrieben hat, beginnt Kern 2, Daten von diesem Speicherort zu lesen, sodass die gelesenen Daten chaotisch sein müssen.

Aber eigentlich besteht kein Grund zur Sorge über dieses Problem. Aus dem Intel-Entwicklerhandbuch erfahren wir, dass Intel-Prozessoren ausgehend von Pentium-Prozessoren das atomare Lesen und Schreiben von Quadwords sicherstellen, die an 64-Bit-Grenzen ausgerichtet sind.

Basierend auf der obigen Beschreibung können wir den Schluss ziehen, dass Intel-Prozessoren sicherstellen können, dass speicherausgerichtete Anweisungen mit Einzelzugriff atomar ausgeführt werden. Aber was ist, wenn es sich um eine Anweisung handelt, zweimal auf den Speicher zuzugreifen? Die Antwort ist keine Garantie. Beispielsweise umfasst die Inkrementierungsanweisung inc dword ptr [...]，等价于DEST = DEST + 1。该指令包含三个操作读->改->写 zwei Speicherzugriffe. Stellen Sie sich eine Situation vor, in der der Wert 1 an einer bestimmten Stelle im Speicher gespeichert ist. Nun führen beide CPU-Kerne den Befehl gleichzeitig aus. Der Prozess der abwechselnden Ausführung der beiden Kerne ist wie folgt:

1. Kern 1 liest den Wert 1 von der angegebenen Stelle im Speicher und lädt ihn in das Register
2. Kern 2 liest den Wert 1 von der angegebenen Stelle im Speicher und lädt ihn in das Register
3. Kern 1 Dekrementiere den Wert im Register um 1
4. Kern 2 Dekrementiere den Wert im Register um 1
5. Kern 1 Schreibe den geänderten Wert zurück in den Speicher
6. Kern 2 Schreibe den geänderten Wert Zurück zum Speicher

Nach dem Ausführen des obigen Prozesses ist der Endwert im Speicher 2, und wir haben 3 erwartet, also liegt ein Problem vor. Um dieses Problem zu lösen, muss verhindert werden, dass zwei oder mehr Kerne gleichzeitig denselben Speicherbereich bedienen. Wie kann man es also vermeiden? Dies stellt den Protagonisten dieses Artikels vor – das Sperrpräfix. Eine detaillierte Beschreibung dieser Anweisung finden Sie im Intel Developer Manual Volume 2 Instruction Set Reference, Kapitel 3 Instruction Set Reference A-L. Ich zitiere hier einen Abschnitt davon wie folgt:

LOCK – LOCK#-Signalpräfix aktivieren
Bewirkt, dass das LOCK#-Signal des Prozessors während der Ausführung der begleitenden Anweisung aktiviert wird (wandelt die Anweisung in eine atomare Anweisung um In a). In einer Multiprozessorumgebung stellt das LOCK#-Signal sicher, dass der Prozessor exklusiven Zugriff auf den gemeinsam genutzten Speicher hat, während das Signal aktiviert ist. Die oben beschriebenen Schlüsselpunkte wurden in einer Multiprozessorumgebung durch das LOCK#-Signal hervorgehoben kann die Verarbeitung sicherstellen. Der Server verfügt über die ausschließliche Nutzung eines Teils des gemeinsam genutzten Speichers. Die Sperre kann vor den folgenden Anweisungen hinzugefügt werden: ADD, ADC, AND, BTC, BTR, BTS, CMPXCHG, CMPXCH8B, CMPXCHG16B, DEC, INC, NEG, NOT, OR, SBB, SUB, XOR, XADD und XCHG.

Durch Hinzufügen des Sperrpräfixes vor der Inc-Anweisung können Sie die Anweisung atomar machen. Wenn mehrere Kerne gleichzeitig denselben Inc-Befehl ausführen, tun sie dies seriell und vermeiden so die oben genannte Situation. Hier stellt sich also eine weitere Frage: Wie stellt das Sperrpräfix sicher, dass der Kern ausschließlich einen bestimmten Speicherbereich belegt? Die Antwort lautet wie folgt:

Bei Intel-Prozessoren gibt es zwei Möglichkeiten, um sicherzustellen, dass ein bestimmter Kern des Prozessors einen bestimmten Speicherbereich exklusiv belegt. Die erste Möglichkeit besteht darin, den Bus zu sperren und einem bestimmten Kern die ausschließliche Nutzung des Busses zu überlassen, aber das ist zu teuer. Nachdem der Bus gesperrt wurde, können andere Kerne nicht auf den Speicher zugreifen, was dazu führen kann, dass andere Kerne für kurze Zeit nicht mehr funktionieren. Die zweite Möglichkeit besteht darin, den Cache zu sperren, wenn einige Speicherdaten im Prozessor-Cache zwischengespeichert sind. Das vom Prozessor ausgegebene LOCK#-Signal sperrt nicht den Bus, sondern den Speicherbereich, der der Cache-Zeile entspricht. Andere Prozessoren können in diesem Speicherbereich keine entsprechenden Vorgänge ausführen, solange dieser Speicherbereich gesperrt ist. Im Vergleich zum Sperren des Busses sind die Kosten für das Sperren des Caches offensichtlich geringer. Eine ausführlichere Beschreibung zu Bussperren und Cachesperren finden Sie im Intel Developer’s Manual Volume 3 Software Developer’s Manual, Kapitel 8 Multiple-Processor Management.

3. Quellcode-Analyse

Mit dem oben genannten Hintergrundwissen können wir jetzt den Quellcode von CAS in Ruhe lesen. Der Inhalt dieses Kapitels analysiert die CompareAndSet-Methode in der Atomklasse AtomicInteger unter dem Paket java.util.concurrent.atomic. Die relevante Analyse lautet wie folgt:

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);
}

Die obige Analyse scheint mehr zu sein, der Hauptprozess jedoch nicht kompliziert. Wenn man sich nicht auf die Details des Codes einlässt, ist er relativ leicht zu verstehen. Als nächstes werde ich die Funktion Atomic::cmpxchg unter der Windows-Plattform analysieren. Lesen Sie weiter.

// 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
  }
}

Der obige Code besteht aus der vorkompilierten Kennung LOCK_IF_MP und der Funktion cmpxchg. Um es etwas klarer zu sehen, ersetzen wir LOCK_IF_MP in der cmpxchg-Funktion durch den tatsächlichen Inhalt. Wie folgt:

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
  }
}

Der Implementierungsprozess von CAS ist hier abgeschlossen. Die Implementierung von CAS ist untrennbar mit der Unterstützung des Prozessors verbunden. Es gibt so viele Codes oben, aber der Kerncode ist eigentlich eine cmpxchg-Anweisung mit einem Sperrpräfix, nämlich lock cmpxchg dword ptr [edx], ecx.

4. ABA-Problematik

Wenn wir über CAS sprechen, müssen wir grundsätzlich über die ABA-Problematik von CAS sprechen. CAS besteht aus drei Schritten, nämlich „Lesen->Vergleichen->Rückschreiben“. Stellen Sie sich eine Situation vor, in der Thread 1 und Thread 2 gleichzeitig CAS-Logik ausführen. Die Ausführungssequenz der beiden Threads ist wie folgt:

1. Zeit 1: Thread 1 führt einen Lesevorgang aus und erhält den ursprünglichen Wert A und dann den Thread wird weggeschaltet
2. Zeitpunkt 2: Thread 2 schließt die CAS-Operation ab und ändert den ursprünglichen Wert von A auf B
3. Zeitpunkt 3: Thread 2 führt die CAS-Operation erneut aus und ändert den ursprünglichen Wert von B auf A
4. Zeitpunkt 4: Thread 1 läuft weiter und vergleicht die Werte (compareValue) mit dem ursprünglichen Wert (oldValue) und es wird festgestellt, dass die beiden Werte gleich sind. Schreiben Sie dann den neuen Wert (newValue) in den Speicher, um die CAS-Operation abzuschließen.

Wie im obigen Prozess gezeigt, weiß Thread 1 nicht, dass der ursprüngliche Wert geändert wurde wird den Vorgang weiter ausführen. Bei ABA-Problemen besteht die übliche Lösung darin, für jede CAS-Operation eine Versionsnummer festzulegen. Das Paket java.util.concurrent.atomic stellt eine Atomklasse AtomicStampedReference bereit, die ABA-Probleme behandeln kann. Interessierte Freunde können es sich selbst ansehen.

5. Zusammenfassung

Mit diesem Schreiben geht dieser Artikel endlich zu Ende. Obwohl das Prinzip von CAS selbst, einschließlich seiner Implementierung, nicht schwierig ist, ist es wirklich nicht einfach, es zu schreiben. Dies erfordert einige Kenntnisse auf niedrigem Niveau. Obwohl ich es verstehen kann, ist es immer noch etwas schwierig, es zu verstehen. Aufgrund meines Mangels an Grundkenntnissen werden einige der oben genannten Analysen zwangsläufig falsch sein. Wenn also ein Fehler vorliegt, können Sie ihn gerne kommentieren. Am besten erklären Sie, warum er falsch ist.

Okay, das war’s für diesen Artikel. Danke fürs Lesen und tschüss.

Anhang

Mehrere Dateien, die im vorherigen Abschnitt zur Quellcode-Analyse verwendet wurden. Die Pfade werden hier veröffentlicht. Es hilft jedem beim Indexieren wie folgt:

Das obige ist der detaillierte Inhalt vonEinführung in die Java CAS-Prinzipanalyse. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!