二重ロックDCLの罠【訳】

13476 ワード

二重検査ロック(DCL)は、マルチスレッドにおいて怠け者のロードを効率的に実現するために広く用いられている方法である.しかしながら、追加の同期がない場合、プラットフォームに関係のないJAVA実装においても、信頼性の高い作業は行われない可能性がある.C++などの他の言語の実装では、プロセッサのメモリモデル、コンパイラの再ソート、コンパイラと同期ライブラリの相互作用に依存します.これらの問題はC++では不確定であるため,具体的な挙動を特定することはできない.C++にはメモリバリアを使用して正常に動作するように表示されますが、メモリバリアはJAVAでは無効です.実際、JAVA同時プログラミング実戦16.2.4におけるDCLの記述によれば、DCLは実際には廃棄されたモードである.他のスレッドの安全な怠け者ロードモードを使用すると、同じ利点が得られます.
次のコードを考慮します.

// Single threaded version
class Foo { 
  private Helper helper = null;
  public Helper getHelper() {
    if (helper == null) 
        helper = new Helper();
    return helper;
    }
  // other functions and members...
  }

マルチスレッド環境で上記のコードを使用すると、多くの問題が発生します.最も明らかなのは、2つ以上のHelperオブジェクトが作成されることです(後述します).この問題を解決するために、最も簡単な方法はgetHelper()メソッドにsynchronizedを加えることです.以下のようにします.

// Correct multithreaded version
class Foo { 
  private Helper helper = null;
  public synchronized Helper getHelper() {
    if (helper == null) 
        helper = new Helper();
    return helper;
    }
  // other functions and members...
  }

以上のコードはgetHelper()を呼び出すたびに同期を実行します.二重チェックロックの意味は、helperが作成された場合の再同期を回避しようとすることです.しかし、このコードは、コンパイラがメモリを最適化および共有するプロセッサの下で信頼性が低い.
信頼性が低い
信頼性の低い動作を招く原因はいくつかありますが、明らかな原因について説明します.存在する問題を理解することによって、私たちは二重検査ロックの意味に存在する問題を修復しようとしたが、私たちの修復は役に立たないかもしれない.私たちは一緒になぜ役に立たないのかを見て、これらの原因を理解して、私たちはもっと良い方法を探してみたが、役に立たないかもしれない.まだ微妙な原因があるからだ.
信頼性が低い最初の理由は
最も明らかな理由は、Helperオブジェクトを初期化するライトコマンドと、helperプロパティを初期化するライトコマンドが並べ替えられる可能性があるからです.したがって、getHelper()メソッドを呼び出すスレッドにはnon-null helperオブジェクト参照が表示されるかもしれませんが、コンストラクタで設定した値ではなく、helperのデフォルト値が表示されます.
コンパイラがコンストラクタを内蔵して呼び出す場合、コンパイラは、コンストラクタが例外を放出して同期を実行しないことを確認する場合、Helper()オブジェクトを初期化する書き込み命令とhelper属性を初期化する書き込み命令を完全に並べ替えることができます.コンパイラがこれらの書き込みコマンドを並べ替えなくても、マルチプロセッサおよびメモリシステムでは、他のプロセッサのスレッドが表示されることを確認するために書き込みコマンドを並べ替えます.Doug Lea大神はもっと詳しい文章を書いたSynchronization and the Java Memory Model
次のテスト例では、なぜ信頼性が低いのかを示します.
Paul Jakubikは二重チェックロックが信頼できない動作の例を発見した.

public class DoubleCheckTest
  {
 // static data to aid in creating N singletons
  static final Object dummyObject = new Object(); // for reference init
  static final int A_VALUE = 256; // value to initialize 'a' to
  static final int B_VALUE = 512; // value to initialize 'b' to
  static final int C_VALUE = 1024;
  static ObjectHolder[] singletons;  // array of static references
  static Thread[] threads; // array of racing threads
  static int threadCount; // number of threads to create
  static int singletonCount; // number of singletons to create
  
  static volatile int recentSingleton;

  // I am going to set a couple of threads racing,
  // trying to create N singletons. Basically the
  // race is to initialize a single array of 
  // singleton references. The threads will use
  // double checked locking to control who 
  // initializes what. Any thread that does not
  // initialize a particular singleton will check 
  // to see if it sees a partially initialized view.
  // To keep from getting accidental synchronization,
  // each singleton is stored in an ObjectHolder 
  // and the ObjectHolder is used for 
  // synchronization. In the end the structure
  // is not exactly a singleton, but should be a
  // close enough approximation.
  // 

  // This class contains data and simulates a 
  // singleton. The static reference is stored in
  // a static array in DoubleCheckFail.
  static class Singleton
    {
    public int a;
    public int b;
    public int c;
    public Object dummy;

    public Singleton()
      {
      a = A_VALUE;
      b = B_VALUE;
      c = C_VALUE;
      dummy = dummyObject;
      }
    }

  static void checkSingleton(Singleton s, int index)
    {
    int s_a = s.a;
    int s_b = s.b;
    int s_c = s.c;
    Object s_d = s.dummy;
    if(s_a != A_VALUE)
      System.out.println("[" + index + "] Singleton.a not initialized " +
s_a);
    if(s_b != B_VALUE)
      System.out.println("[" + index 
                         + "] Singleton.b not intialized " + s_b);
    
    if(s_c != C_VALUE)
      System.out.println("[" + index 
                         + "] Singleton.c not intialized " + s_c);
    
    if(s_d != dummyObject)
      if(s_d == null)
        System.out.println("[" + index 
                           + "] Singleton.dummy not initialized," 
                           + " value is null");
      else
        System.out.println("[" + index 
                           + "] Singleton.dummy not initialized," 
                           + " value is garbage");
    }

  // Holder used for synchronization of 
  // singleton initialization. 
  static class ObjectHolder
    {
    public Singleton reference;
    }

  static class TestThread implements Runnable
    {
    public void run()
      {
      for(int i = 0; i < singletonCount; ++i)
        {
    ObjectHolder o = singletons[i];
        if(o.reference == null)
          {
          synchronized(o)
            {
            if (o.reference == null) {
              o.reference = new Singleton();
          recentSingleton = i;
          }
            // shouldn't have to check singelton here
            // mutex should provide consistent view
            }
          }
        else {
          checkSingleton(o.reference, i);
      int j = recentSingleton-1;
      if (j > i) i = j;
      }
        } 
      }
    }

  public static void main(String[] args)
    {
    if( args.length != 2 )
      {
      System.err.println("usage: java DoubleCheckFail" +
                         "  ");
      }
    // read values from args
    threadCount = Integer.parseInt(args[0]);
    singletonCount = Integer.parseInt(args[1]);
    
    // create arrays
    threads = new Thread[threadCount];
    singletons = new ObjectHolder[singletonCount];

    // fill singleton array
    for(int i = 0; i < singletonCount; ++i)
      singletons[i] = new ObjectHolder();

    // fill thread array
    for(int i = 0; i < threadCount; ++i)
      threads[i] = new Thread( new TestThread() );

    // start threads
    for(int i = 0; i < threadCount; ++i)
      threads[i].start();

    // wait for threads to finish
    for(int i = 0; i < threadCount; ++i)
      {
      try
        {
        System.out.println("waiting to join " + i);
        threads[i].join();
        }
      catch(InterruptedException ex)
        {
        System.out.println("interrupted");
        }
      }
    System.out.println("done");
    }
  }

Symantec JITで動作している場合、正しく動作しません.Symantec JIT

singletons[i].reference = new Singleton();

次のコマンドにコンパイルします.

0206106A   mov         eax,0F97E78h
0206106F   call        01F6B210                  ; allocate space for
                                                 ; Singleton, return result in eax
02061074   mov         dword ptr [ebp],eax       ; EBP is &singletons[i].reference 
                                                ; store the unconstructed object here.
02061077   mov         ecx,dword ptr [eax]       ; dereference the handle to
                                                 ; get the raw pointer
02061079   mov         dword ptr [ecx],100h      ; Next 4 lines are
0206107F   mov         dword ptr [ecx+4],200h    ; Singleton's inlined constructor
02061086   mov         dword ptr [ecx+8],400h
0206108D   mov         dword ptr [ecx+0Ch],0F84030h

ご覧のようにsingletons[i].referenceの付与はSingletonのコンストラクタの前で実行され、これは既存のJAVAメモリモデルの下で完全に合法的であり、C、C++でも同様に合法的である(メモリモデルの概念はない).
次の修正は依然として信頼できない可能性があります.
以上の説明について、多くの人が次のコードを示しています.

// (Still) Broken multithreaded version
// "Double-Checked Locking" idiom
class Foo { 
  private Helper helper = null;
  public Helper getHelper() {
    if (helper == null) {
      Helper h;
      synchronized(this) {
        h = helper;
        if (h == null) 
            synchronized (this) {
              h = new Helper();
            } // release inner synchronization lock
        helper = h;
        } 
      }    
    return helper;
    }
  // other functions and members...
  }

このコードはHelperオブジェクトの構造を内蔵した同期コードブロックに配置する.直感的な考え方はsynchronizedが解放した後のバリアによって問題を回避し,helper属性の付与とHelperオブジェクトの構造に対する命令の再ソートを阻止することである.しかし、この直感は絶対的に間違っている.synchronizedルールは、synchronizationの解放などのmonitorexitがsynchronizationの解放前に実行されることを保証するしかないからです.monitorexit以降の命令がsynchronizedの解放前に実行されないことを保証するルールはありません.コンパイラにとってhelper=h;付与文が裏層同期ブロック内に移動するのは完全に合理的で合法的である(これはまた前の問題になった).多くのプロセッサでは、このような一方向メモリバリアの命令が提供されており、双方向の完全なメモリバリアの意味を取得するには、パフォーマンスが低下します.
双方向のメモリバリアを実行するために書き込みを強制することができますが、これは醜く、低効率で、JAVAメモリモデルに捨てられた方法です.この方法は使わないでください.興味があれば、BidirectionalMemoryBarrierを参照してください.しかしながら、双方向のメモリバリアを使用しても、必ずしも正しく動作するとは限らない.なぜなら、一部のシステムでは、helperプロパティもメモリバリアを使用する必要があるからです.何が原因ですか.これは、プロセッサが独自のローカルキャッシュを持っているためです.メモリバリアなどのプロセッサキャッシュコンシステンシ命令を実行しない限り、他のプロセッサがメモリバリアを使用してグローバルメモリに強制的に書き込まれても、現在のプロセッサはローカルで失効したキャッシュを読み取る可能性があります.Alpha processorのように
静的単一例
作成した単一のオブジェクトが静的である場合は、単純で優雅な方法で正しく動作することを保証します.単一の例を静的属性として1つのクラスに定義すると、JAVAの意味は、この静的属性が参照されたときに初期化(怠惰ロード)され、他のスレッドが初期化後の結果に正しくアクセスできることを保証します.コードは次のとおりです.

class HelperSingleton {
  static Helper singleton = new Helper();
  }

32ビットの元のタイプで正しく動作
Double-Checked Lockingはオブジェクト参照では正しく動作しませんが、int、floatなどの32ビットの元のタイプでは正しく動作します.longやdoubleでも正常に動作しないため、64ビットの元のタイプの読み取りと書き込みは原子操作であることは保証されません.

// Correct Double-Checked Locking for 32-bit primitives
class Foo { 
  private int cachedHashCode = 0;
  public int hashCode() {
    int h = cachedHashCode;
    if (h == 0) 
    synchronized(this) {
      if (cachedHashCode != 0) return cachedHashCode;
      h = computeHashCode();
      cachedHashCode = h;
      }
    return h;
    }
  // other functions and members...
  }

実際,computeHashCode()が返す結果が同じであると仮定し,副作用(べき乗など)がない場合,これらのsynchronizedをすべて取り除くことができる.次のようになります.

// Lazy initialization 32-bit primitives
// Thread-safe if computeHashCode is idempotent
class Foo { 
  private int cachedHashCode = 0;
  public int hashCode() {
    int h = cachedHashCode;
    if (h == 0) {
      h = computeHashCode();
      cachedHashCode = h;
      }
    return h;
    }
  // other functions and members...
  }

メモリバリアを正しく動作させる
表示されたメモリバリア命令を使用すると、Double-Checked Lockingを正しく動作させることができます.C++言語を使用する場合は、Doug Schmidtの本から次のコードを取得できます.

// C++ implementation with explicit memory barriers
// Should work on any platform, including DEC Alphas
// From "Patterns for Concurrent and Distributed Objects",
// by Doug Schmidt
template  TYPE *
Singleton::instance (void) {
    // First check
    TYPE* tmp = instance_;
    // Insert the CPU-specific memory barrier instruction
    // to synchronize the cache lines on multi-processor.
    asm ("memoryBarrier");
    if (tmp == 0) {
        // Ensure serialization (guard
        // constructor acquires lock_).
        Guard guard (lock_);
        // Double check.
        tmp = instance_;
        if (tmp == 0) {
                tmp = new TYPE;
                // Insert the CPU-specific memory barrier instruction
                // to synchronize the cache lines on multi-processor.
                asm ("memoryBarrier");
                instance_ = tmp;
        }
    return tmp;
    }

ThreadLocalを使用してDouble-Checked Lockingで発生した問題を解決
Alexander Terekhovの使用は非常にスマートなThreadLocalベースの実装を提案した.各スレッドは、必要な同期が行われたかどうかを判断するために、スレッドのローカルIDを保存します.

 class Foo {
     /** If perThreadInstance.get() returns a non-null value, this thread
        has done synchronization needed to see initialization
        of helper */
         private final ThreadLocal perThreadInstance = new ThreadLocal();
         private Helper helper = null;
         public Helper getHelper() {
             if (perThreadInstance.get() == null) createHelper();
             return helper;
         }
         private final void createHelper() {
             synchronized(this) {
                 if (helper == null)
                     helper = new Helper();
             }
         // Any non-null value would do as the argument here
             perThreadInstance.set(perThreadInstance);
         }
  }

この技術の性能はあなたが使用しているJDKバージョンによって異なり、Sunが実現したJDK 2の中でThreadLocalの性能は低く、JDK 3の性能は著しく向上し、JDK 4の性能はもっと良いです.Doug Lea大神が書いたPerformance of techniques for correctly implementing lazy initializationを参照してください
volatileの使用
JDK 5以降で使用される新しいメモリモデルは、volatileの意味を拡張し、読み書き命令の再ソートを禁止します.helperプロパティをvolatileと宣言すればいいです.

// Works with acquire/release semantics for volatile
// Broken under current semantics for volatile
  class Foo {
        private volatile Helper helper = null;
        public Helper getHelper() {
            if (helper == null) {
                synchronized(this) {
                    if (helper == null)
                        helper = new Helper();
                }
            }
            return helper;
        }
    }

可変オブジェクトの使用
Helperが可変オブジェクト(Helperのすべてのプロパティがfinal)である場合、volatileを使用してプロパティを宣言しなくても正常に動作します.これは、String、Integerなどの可変オブジェクトの参照が32ビットの元のタイプに似ているためです.
原文The「Double-Checked Locking is Broken」Declaration

Leetcode-7-反転整数

JAva反射メカニズムの深い研究