Java CAS 原則分析の概要

Java の基本チュートリアルカラムの紹介と分析 Java CAS

##推奨事項 (無料): java 基本チュートリアル

1. はじめに

CAS は、compare and swap の略です。マルチスレッド環境で同期機能を実装するためのものです。 CAS 操作には、メモリ位置、期待値、新しい値という 3 つのオペランドが含まれます。 CAS の実装ロジックでは、メモリ位置の値と期待値を比較し、それらが等しい場合、メモリ位置の値を新しい値に置き換えます。等しくない場合、操作は実行されません。

Java では、Java は CAS を直接実装せず、CAS 関連の実装は C インライン アセンブリの形式で実装されます。 Java コードは JNI 経由で呼び出す必要があります。第 3 章で実装の詳細を分析します。

前述したように、CAS の操作プロセスは難しくありません。しかし、上記の説明だけでは十分ではないので、次にその他の予備知識をいくつか紹介します。この背景知識があるだけで、その後の内容をよりよく理解できます。

2. 背景の紹介

CPU がバスとメモリを介してデータを送信することは誰もが知っています。マルチコア時代では、複数のコアが同じバスを介してメモリや他のハードウェアと通信します。以下に示すように:

画像出典: 「コンピュータ システムの徹底理解」

上の図は、比較的単純なコンピュータの構造図です。 、質問を説明するのに十分です。上の図では、CPU は 2 つの青い矢印でマークされたバスを介してメモリと通信します。 CPU の複数のコアが同じメモリ上で同時に動作する場合、それを制御しないとどのようなエラーが発生しますか?ここで簡単に説明すると、コア 1 が 32 ビット帯域幅のバスを介して 64 ビット データをメモリに書き込むと仮定すると、コア 1 は操作全体を完了するために 2 回書き込む必要があります。コア 1 が初めて 32 ビット データを書き込んだ後、コア 2 はコア 1 によって書き込まれたメモリ位置から 64 ビット データを読み取ります。コア 1 はすべての 64 ビット データをメモリに完全に書き込んでいないため、コア 2 はこのメモリ位置からデータの読み取りを開始するため、読み取られたデータはカオスになるはずです。

しかし、実際には、この問題について心配する必要はありません。 Intel Developer Manual を読むと、Pentium プロセッサ以降、Intel プロセッサは 64 ビット境界にアライメントされたクワッドワードのアトミックな読み取りと書き込みを保証するようになることがわかります。

上記の説明に基づいて、Intel プロセッサはシングルアクセスのメモリアライメント命令がアトミックに実行されることを保証できると結論付けることができます。しかし、それがメモリに 2 回アクセスする命令だった場合はどうなるでしょうか?答えは保証されません。たとえば、インクリメント命令

inc dword ptr [...] は DEST = DEST 1 と同等です。この命令には、2 つのメモリ アクセスを伴う 3 つの操作Read->Modify->Writeが含まれています。値 1 がメモリ内の指定された場所に格納されている状況を考えてみましょう。これで、両方の CPU コアが同時に命令を実行します。 2 つのコアの交互実行のプロセスは次のとおりです。

コア 1 はメモリ内の指定された場所から値 1 を読み取り、レジスタにロードします。
1. コア 2 は読み取りますメモリ内の指定された場所から値 1 を取得し、レジスタにロードします。
2. コア 1 レジスタの値を 1
3. だけデクリメントします。コア 2 レジスタの値を 1
4. だけデクリメントします。
コア 1 変更した値をメモリに書き戻す
5. コア 2 変更した値をメモリに書き戻す

上記の処理を実行すると、メモリ内の最終値は 2 になります。 、そして私たちが期待しているのは3です、これが問題が起こることです。この問題に対処するには、複数のコアが同じメモリ領域を同時に動作させないようにする必要があります。では、それを避けるにはどうすればよいでしょうか?これは、この記事の主役であるロック プレフィックスを紹介します。この命令の詳細な説明については、インテル開発者マニュアル第 2 巻命令セット リファレンスの第 3 章命令セット リファレンス A ～ L を参照してください。以下にその一部をここに引用します。

LOCK—LOCK# 信号プレフィックスをアサート

付随する命令の実行中にプロセッサの LOCK# 信号をアサートします (
命令を次のように変換します)。アトミック命令 ) マルチプロセッサ環境では、LOCK# 信号 は、信号がアサートされている間、プロセッサが共有メモリを排他的に使用できるようにします 。

説明されている重要なポイントマルチプロセッサ環境では、LOCK# 信号によりプロセッサが一部の共有メモリを排他的に使用できることが太字で強調表示されています。ロックは、次の命令の前に追加できます:

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

inc 命令の前にロック プレフィックスを追加すると、命令をアトミックにすることができます。複数のコアが同じ inc 命令を同時に実行する場合、それらはシリアル方式で実行されるため、上記の状況は回避されます。ここで別の質問がありますが、ロック プレフィックスはどのようにしてコアが特定のメモリ領域を排他的に占有することを保証するのでしょうか?答えは次のとおりです。

Intel プロセッサでは、プロセッサの特定のコアが特定のメモリ領域を排他的に占有するようにする方法が 2 つあります。 1 つ目の方法は、バスをロックして特定のコアにバスを独占的に使用させることですが、これはコストがかかりすぎます。バスがロックされると、他のコアはメモリにアクセスできなくなり、他のコアが短時間動作を停止する可能性があります。 2 番目の方法は、一部のメモリ データがプロセッサ キャッシュにキャッシュされている場合に、キャッシュをロックすることです。プロセッサが発行する LOCK# 信号はバスをロックするのではなく、キャッシュ ラインに対応するメモリ領域をロックします。このメモリ領域がロックされている間、他のプロセッサはこのメモリ領域に対して関連する操作を実行できません。バスをロックする場合と比較して、キャッシュをロックするコストは明らかに小さくなります。バス ロックとキャッシュ ロックの詳細については、Intel Developer's Manual Volume 3 Software Developer's Manual、第 8 章マルチプロセッサ管理を参照してください。

3. ソース コードの分析

上記の背景知識を踏まえて、CAS のソース コードをゆっくり読むことができます。この章の内容では、java.util.concurrent.atomic パッケージにあるアトミック クラス AtomicInteger の CompareAndSet メソッドを分析します。関連する分析は次のとおりです:

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

上記の分析はさらに多いようですが、主な処理は複雑ではありません。コードの詳細にこだわらなければ、比較的簡単に理解できます。次に、Windows プラットフォームでの Atomic::cmpxchg 関数を分析します。読む。

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

上記のコードは、LOCK_IF_MP プリコンパイル済み識別子と cmpxchg 関数で構成されています。もう少しわかりやすくするために、cmpxchg 関数の LOCK_IF_MP を実際の内容に置き換えてみましょう。

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

CAS の実装プロセスはここで終了です CAS の実装はプロセッサのサポートと切り離せません。上記には非常に多くのコードがありますが、コア コードは実際にはロック プレフィックスが付いた cmpxchg 命令、つまり lock cmpxchg dword ptr [edx], ecx です。

4. ABA 問題

CAS について話すときは、基本的に CAS の ABA 問題について話さなければなりません。 CAS は、「読み取り -> 比較 -> ライトバック」という 3 つのステップで構成されます。スレッド 1 とスレッド 2 が CAS ロジックを同時に実行する状況を考えます。2 つのスレッドの実行シーケンスは次のとおりです:

1. 時間 1: スレッド 1 が読み取り操作を実行し、オリジナルの値 A に戻り、スレッドがスイッチド アウェイになりました。
2. 時間 2: スレッド 2 が CAS 操作を完了し、元の値を A から B に変更します。
3. 時間 3: スレッド 2 が再度 CAS 操作を実行し、値が変更されます。元の値を B から A
4. 瞬間 4: スレッド 1 が実行を再開し、比較値 (compareValue) と元の値 (oldValue) を比較し、2 つの値が等しいことがわかります。次に、新しい値 (newValue) をメモリに書き込み、CAS 操作を完了します。

上記のプロセスと同様、スレッド 1 は元の値が変更されたことを認識せず、変更されているように見えます。変化がないため、プロセスは引き続き実行されます。 ABA の問題の場合、通常の解決策は、CAS 操作ごとにバージョン番号を設定することです。 java.util.concurrent.atomic パッケージは、ABA の問題を処理できるアトミック クラス AtomicStampedReference を提供します。特定の実装はここでは分析されません。興味のある友人は自分で確認してください。

5. まとめ

これを書きながら、この記事もいよいよ終わりに近づいてきました。 CAS の原理自体は実装も含めて難しくありませんが、実際に書くのは簡単ではありません。これには低レベルの知識が必要で、理解はできますが、理解するのはまだ少し難しいです。私には基礎知識が不足しているため、上記の分析の一部は必然的に間違っている可能性があります。間違いがある場合は、お気軽にコメントしてください。もちろん、なぜ間違っているのかを説明するのが最善です。ありがとうございます。

さて、この記事はここまでです。読んでくれてありがとう、それではさようなら。

付録

前のソース コード分析セクションで使用したいくつかのファイルへのパスがここに掲載されています。次のように、誰もがインデックスを付けるのに役立ちます:

#atomic_windows_x86.inline.hppopenjdk/hotspot/src/os_cpu/windows_x86/vm/atomic_windows_x86.inline.hpp

ファイル名	パス
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

以上がJava CAS 原則分析の概要の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。