私は、java（ダブルチェック）Singleton（シングルトン）パターンがスレッドセーフではなく修正できないということが、プログラミングの世界ではよく知られている事実であるということを発見しました。理由を説明する3つの記事がここにあります（[1]、[2]、[3]）。これらの記事では、Singletonパターンの特定の実装を提供し、これらの実装がどのように壊れる可能性があるかを公正に解説し、一般化された主張で結論が出されています。
言及する価値があるのは、Jeremy Manson氏やBill Pugh氏（java 1.5メモリモデルの作者）が中心となって署名した「The ‘Double-Checked Locking is Broken’ Declaration」 [4] において、彼らがjava 1.5でのダブルチェックされたSingletonパターンの修正を提案したことです（「Fixing Double-Checked Locking using Volatile」部分）。
java同期に関するどのような議論でも、大規模で十分に定義されていないjava最適化について考える必要があります。Java Language Specification Third Edition (リンク)(JLS3) [5] では、次のようにコメントされています。
本仕様は、実装者に対し、アクションの並べ替えや不要な同期の排除など、無数のコード変換を実行する多大な自由を提供します。
この記事の主な目的は、プログラミング言語最適化の「境界条件」をテストすることです。このタスクには、非標準のアプローチが必要です。私はその開発をここで試みます。
プログラミング言語の同期構造のどのような提供も、最適化で許可されることと許可されないことの原則を使用しない限り、非常に不安定な基盤の上にあります。私のアイデアは、もし最適化が、一般的に受け入れられている原則の違反によってのみコードを壊す可能性がある場合、そのような最適化は不可能（または少なくとも不適当）であるということを示すことです。そして、我々はこのポジションにいる場合、どのようなプログラミング言語についても主張できます。javaについてはその必要がありません。実際、javaは同期プリミティブを使用し、C#はlockを使用し、CはMutexを使ったPOSIXプリミティブを使用していましたし、C++もまたMutex（Win32およびSolaris上）、Python - さらにlock、Ruby Mutexを使用します。問題は、具体例から早合点せずに推論によって一般化を試みることができるかということです。
JLS3は、次のイントラスレッドセマンティクス（intra-thread semantics）の定義を使用しています。
シングルスレッドプログラムのセマンティクスは、スレッド内でreadアクションによって確認された値に基づいてスレッドの動作の完全な予測を可能にします。各スレッドのアクションは単独で、そのスレッドのセマンティクスによって制御されるものとして動作する必要があります。
私たちは、次に示した、この定義のより弱い形式を使用します。
プログラミング言語実装は、コンパイル時/ランタイムの最適化がシングルスレッド実行においてメソッドレベルまで（インラインメソッドは含みません）、最適化されていないコードのセマンティクスを保持する場合、最小のイントラスレッドセマンティクス（最小のITS）を提供します。
最小のITSがメソッドレベルで壊れている場合、プログラムレベルでも壊れている可能性があることを示すのは容易です。
定 義： プログラミング言語実装は、言語同期プリミティブが次の2つの条件を満たす場合に最小の同期を提供する
CS1: 1つのスレッドのみ同期ブロックに入ることができる
CS2: スレッドのすべての共有変数は同期ブロックに入るときにメインメモリから更新され、同期ブロックから出るときにメインメモリに保存される
定 義： オブジェクトにリファレンスを返すメソッドは、十分に作成されていないオブジェクトへのリファレンスを取得することがこのメソッドで可能な場合に、ファントムオブジェクト効果を生成する
この記事で私は、1つのSingleton実装の相対的一貫性を調査します（『Mathematical Logic』という本を手本にします）。より正確に言うと、次の主張の例証を試みます。
A: プログラミング言語実装が最小のITSと最小の同期を提供する場合、gOracleパターン(*)の使用は一貫している
このために、次のステートメントの証明を試みます。
B: プログラミング言語実装が最小のITSと最小の同期を提供する場合、gOracleパターン(*)はファントムオブジェクト効果を生成できない
今から私はjavaプログラミング言語のコンテキストに移りますが、次の内容はすべて上記に挙げたどの言語にも適用できると確信しています。
では、gOracleパターンとは何でしょうか? その名前が示唆するように、私が取り入れるオラクル（oracle）は、古代ギリシャ（Greek）のオラクル（神託）に類似したものです。私のオラクルは、static boolean oracle(int h)の署名と1つの非常に特別なクオリティを持つメソッドになります ? javaコンパイラやjavaランタイムに関して、このメソッドで生成される値を予測する方法はありません。しかし、秘密を打ち明けますと、メソッドは常にtrueを返します。そのようなメソッドの作成に関する質問には後ほど立ち返るとして、今はそれがいかに簡単であるかということを断言させてください。
私のgOracle Singleton実装は、次のとおりです。
class Singleton {
static private Singleton instance = null;
static private boolean bInited = false;
private Singleton() {…}
public static Singleton getInstance() {
if (!bInited || instance==null) { // FIRST CHECK
synchronized (Singleton.class) {
if (!bInited) { // INNER IF-BLOCK, SECOND CHECK
instance = new Singleton();
int hash = instance.hashCode();
bInited = oracle(hash);
}
}
}
return instance;
}
static boolean oracle(int h) {…}
}
今から、gOracleに対する答弁を開始します。
鍵となるアイデアは、java最適化がgetInstance()メソッドについてファントムオブジェクト効果をもたらす場合、最小のITSは壊れるであろうことを示すことです。ある意味で、シングルスレッドモードにおける、そのような最適化されたコードの実行は、最適化されていないコードの実行とは異なる結果をもたらす可能性があります。
|
1. 同期ブロックに最初に入るスレッドをi-threadと呼びましょう。このスレッドは、最初にローカルメモリにしか存在しない場合でも最終的にbInited変数の値を変更します。 2. コンパイラにはgetInstance()コードを変換する能力があり、ランタイムには演算子の実行順序を変更する能力がありますが、こうした最適化は、単独で実行されるi-threadの最小のITSを壊すことは許されません。 3. hash = instance.hashCode()呼び出しの結果は、インスタンスオブジェクトが作成される前は予測不可能です。 注1: java APIによると、デフォルトのhashCode()は通常、オブジェクトの内部アドレスを整数値に変換する形で実装されます。しかし、それが予測不可能性には不十分な場合は、SingletonのhashCode()を次のように実装することを検討できます。
そして、コンパイラまたはランタイムに、コンストラクタ後にオリジナルのコード順で配置されたDate.getTime()の値をコンストラクタ内またはコンストラクタ前に予測させます! 4. bInited = oracle(hash)呼び出しは、instance.hashCode()呼び出しの結果を使用し、我々の前提のとおり、予測不可能です。 5. そのため、コンパイラまたはランタイム最適化は、Singletonオブジェクトが完全に作成されてi-threadのローカルメモリのインスタンス変数に割り当てられる前にbInited変数の値（true）を割り当てることはできません。 6.i-threadが同期ブロックを出た後かつ他のスレッドがそのブロックに入る前に、メインメモリのインスタンス変数およびbInited変数の値には、i-threadローカルメモリからの値が設定されます。どちらのセット演算子もアトミックです。 7. 次に、他のすべてのスレッドの動作について考え、最小のITSセマンティクスにおいて、それをw-threadと呼びましょう。つまり、w-threadの実行順序をSingletonコードの指定どおりに取ることができますが、共有変数は「予期せぬ」値を持つ可能性があります。今からそれについて見ていきます。 次の表記を使用しましょう。
8.a. w-threadは同期ブロックでi-threadがブロックから出るのを待機します。簡単なことです。最初にi-threadが同期ブロックから出て、その後javaはi-threadローカル変数をメインメモリに同期させます。 I(bInited) => M(bInited) I(instance) => M(instance) 次に、w-threadが同期ブロックに入ると、javaはw-threadローカル変数をメインメモリから同期させます M(bInited) => W(bInited) M(instance) => W(instance) これで、w-threadは、共有変数の正確なビュー、つまりi-threadが持つビューと同じものを得ます。 8.b. i-threadが同期ブロックから出るとき、w-threadはFIRST CHECK演算子の内部または前にあります。 W(bInited)およびW(instance)は、I(bInited)およびI(instance)がM(bInited)およびM(instance)に同期される前または後のいずれかにメインメモリから初期化されることに注意してください。t-threadが同期ブロックから出た後に起こります。W(bInited)およびW(instance)はそれぞれ、初期値（クラスSingletonで定義されているもの）またはi-threadによって生成された値のいずれかのみを、可能なあらゆる組み合わせで持つことができます。 次に、w-threadは変数W(bInited)の値を最初にチェックします。 値がfalseの場合、基本的に事例7.aのように、w-threadは同期ブロックにジャンプします。 W(bInited)==trueの場合、i-threadはすでにI(bInited)=trueを割り当て済みで、javaはすでにチェーンに沿って同期させています I(bInited) => M(bInited) => W(bInited) そのため、i-threadはすでにSingletonオブジェクトを初期化済みで、少なくともI(instance)がそのオブジェクトを参照しています。 次に、w-threadはW(instance)変数の値をチェックします。W(instance)==nullの場合、javaはまだチェーンに沿って同期させていません。 I(instance) => M(instance) => W(instance) しかし心配ありません。事例7.aのように、w-threadだけ同期ブロックの入り口にジャンプし、そこでインスタンスの新しい値を発見します。 ただし、W(instance)=!nullの場合、W(instance)が持つことのできる唯一の値は、I(instance)の値だけです。そのため、w-threadは、Singletonの完全に作成されたインスタンスを返します。 9. したがって、getInstance()メソッドでインスタンス変数を取得するどのスレッドについても、Singletonオブジェクトがすでに作成されており、ithreadによって完全に初期化されていることが保証されます。 |
言い換えれば、コンパイラ/ランタイム最適化がgOracleパターンを壊すことができる唯一の方法は、そのコードのシングルスレッド実行を壊すことによるものです（最小の同期があることを前提とします）。これは、（javaに関して）主張Bを証明しており、主張Aを例証しています。答弁を終えます。
結果: どのJDK 1.4でも実装は最小のITS要件を提供し、gOracleパターンはそこでファントムオブジェクト効果を生成することはできません。
gOracleのそうしたオラクルを探す方法についての質問に立ち返りましょう。次のようなnon-trivialな数学的命題はどうでしょうか。
- 三角形の二辺の和は他の一辺よりも長いか等しい
- すべての正整数は素数の積として表すことができる
2つめの命題を取り、次のようなオラクルを実装しましょう。
static boolean oracle(int hash) {
Random rand = new Random(Date.getTime());
int iNum = rand.nextInt() + hash;
iNum = iNum % 100; // optional line
if( found iNum presentation as product of primes )
return true
else
return false;
}
コンパイラデザイナーは神でもオラクルでもなく、コンパイラまたはランタイムにjavaコードでのFundamental Theorem of Arithmetic(リンク)（算術の基本定理）[6]やユークリッド幾何学（Euclid Geometry Axioms）の使用を認識するように教えることができないということに、あなたが同意してくれることを願います。そして、フェルマーの大定理（Big Ferma Theorem）があります。
(*) 私のSingletonパターンの実装に「gOracle」という名前を取り入れたのは、「未来の予測」のアイデアとそれが古代ギリシャ人によってどのように使用されていたかのギリシャ起源を表現するためです。Oracle Corpの製品と混同しないでください。
参考記事
1.Double-checked locking and the Singleton pattern (リンク)、peter Haggar著
2. Double-checked locking: Clever, but broken(リンク)、Brian Goetz著
3. Java theory and practice: Fixing the Java Memory Model (リンク)、Brian Goetz著
4. The "Double-Checked Locking is Broken" Declaration (リンク)、Jeremy Manson、Bill Pugh …著
5. Java Language Specification (リンク), Third Edition
6.Fundamental theorem of arithmetic (リンク)
原文はこちらです：http://www.infoq.com/articles/code-optimization-singleton
（このArticleは2008年11月14日に原文が掲載されました）