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 [...]，等價(jià)于DEST = DEST + 1。該指令包含三個(gè)操作讀->改->寫 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?{
????????????//?計(jì)算變量?value?在類對(duì)象中的偏移
????????????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?實(shí)際上只是一個(gè)殼子，主要的邏輯封裝在?Unsafe?的?
?????????*?compareAndSwapInt?方法中
?????????*/
????????return?unsafe.compareAndSwapInt(this,?valueOffset,?expect,?update);
????}
????
????//?......
}

public?final?class?Unsafe?{
????//?compareAndSwapInt?是?native?類型的方法，繼續(xù)往下看
????public?final?native?boolean?compareAndSwapInt(Object?o,?long?offset,
??????????????????????????????????????????????????int?expected,
??????????????????????????????????????????????????int?x);
????//?......
}

//?unsafe.cpp
/*
?*?這個(gè)看起來(lái)好像不像一個(gè)函數(shù)，不過(guò)不用擔(dān)心，不是重點(diǎn)。UNSAFE_ENTRY?和?UNSAFE_END?都是宏，
?*?在預(yù)編譯期間會(huì)被替換成真正的代碼。下面的?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);
??//?根據(jù)偏移量，計(jì)算?value?的地址。這里的?offset?就是?AtomaicInteger?中的?valueOffset
??jint*?addr?=?(jint?*)?index_oop_from_field_offset_long(p,?offset);
??//?調(diào)用?Atomic?中的函數(shù)?cmpxchg，該函數(shù)聲明于?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");
??/*
???*?根據(jù)操作系統(tǒng)類型調(diào)用不同平臺(tái)下的重載函數(shù)，這個(gè)在預(yù)編譯期間編譯器會(huì)決定調(diào)用哪個(gè)平臺(tái)下的重載
???*?函數(shù)。相關(guān)的預(yù)編譯邏輯如下：
???*?
???*?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
???*?
???*?接下來(lái)分析?atomic_windows_x86.inline.hpp?中的?cmpxchg?函數(shù)實(shí)現(xiàn)
???*/
??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?{
????//?將參數(shù)值放入寄存器中
????mov?edx,?dest????//?注意:?dest?是指針類型，這里是把內(nèi)存地址存入?edx?寄存器中
????mov?ecx,?exchange_value
????mov?eax,?compare_value
????
????//?LOCK_IF_MP
????cmp?mp,?0
????/*
?????*?如果?mp?=?0，表明是線程運(yùn)行在單核?CPU?環(huán)境下。此時(shí)?je?會(huì)跳轉(zhuǎn)到?L0?標(biāo)記處，
?????*?也就是越過(guò)?_emit?0xF0?指令，直接執(zhí)行?cmpxchg?指令。也就是不在下面的?cmpxchg?指令
?????*?前加?lock?前綴。
?????*/
????je?L0
????/*
?????*?0xF0?是?lock?前綴的機(jī)器碼，這里沒(méi)有使用?lock，而是直接使用了機(jī)器碼的形式。至于這樣做的
?????*?原因可以參考知乎的一個(gè)回答：
?????*?????https://www.zhihu.com/question/50878124/answer/123099923
?????*/?
????_emit?0xF0
L0:
????/*
?????*?比較并交換。簡(jiǎn)單解釋一下下面這條指令，熟悉匯編的朋友可以略過(guò)下面的解釋:
?????*???cmpxchg:?即“比較并交換”指令
?????*???dword:?全稱是?double?word，在?x86/x64?體系中，一個(gè)?
?????*??????????word?=?2?byte，dword?=?4?byte?=?32?bit
?????*???ptr:?全稱是?pointer，與前面的?dword?連起來(lái)使用，表明訪問(wèn)的內(nèi)存單元是一個(gè)雙字單元
?????*???[edx]:?[...]?表示一個(gè)內(nèi)存單元，edx?是寄存器，dest?指針值存放在?edx?中。
?????*??????????那么?[edx]?表示內(nèi)存地址為?dest?的內(nèi)存單元
?????*??????????
?????*?這一條指令的意思就是，將?eax?寄存器中的值（compare_value）與?[edx]?雙字內(nèi)存單元中的值
?????*?進(jìn)行對(duì)比，如果相同，則將?ecx?寄存器中的值（exchange_value）存入?[edx]?內(nèi)存單元中。
?????*/
????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!