GC アルゴリズムをアニメーショングラフィックで説明 - ガベージコレクションを動かしましょう。

[[425799]]

Java のガベージコレクションに関しては、私と同じように、多くの友人が、面接で必ず聞かれる質問だという同じ第一反応を示すと思います。GC アルゴリズムとコレクターに関する知識を暗記していなければ、外出時に 8 部構成のエッセイを暗記したと敢えて言うことはできないでしょう。こう言うのは少し恥ずかしいです。この知識が実際に仕事で使われる場面は多くなく、学ぶのもとても退屈です。でも面接官はただ質問するのが好きなので、私たちに何ができるでしょうか？

こうなってしまったら、学ばないわけにはいきません。Hydra は週末の時間を犠牲にして、皆さんのためにアニメーションの絵をいくつか描きました。これらの絵が、皆さんがガベージコレクションアルゴリズムをよりよく理解するのに役立つことを願っています。では、早速基本から始めて、オブジェクトをリサイクルする必要があるかどうかを判断する方法を見てみましょう。

オブジェクトが生きているかどうかを判断する

ガベージコレクションの基本的な目的は、いくつかのアルゴリズムを使用してメモリを管理し、メモリ空間を効果的に利用することです。ガベージコレクションの前に、オブジェクトの生存を判断する必要があります。JVM にはオブジェクトの生存を判断する 2 つのアルゴリズムがあり、以下に紹介します。

1. 参照カウントアルゴリズム

オブジェクトに参照カウンターを追加し、オブジェクトへの参照があるたびにカウンターを 1 増やし、参照が無効になったときにカウンターを 1 減らします。カウンターが 0 の場合、現在のオブジェクトはリサイクル可能であることを意味します。

この方法の原理は単純で、判断も効率的ですが、2 つの問題があります。

ヒープ内のオブジェクトが参照され、クリアされるたびに、カウンターを加算および減算する必要があり、パフォーマンスが低下します。
2 つのオブジェクトが相互に参照する場合、カウンターは 0 に達することはありません。つまり、これら 2 つのオブジェクトがプログラムで使用されなくなったとしても、それらをリサイクルする方法はまだありません。次の例で、循環参照がある場合のカウントの問題を見てみましょう。

パブリックvoid参照(){
  A a = 新しいA();
  Bb = 新しいB();
  a.インスタンス = b;
  b.インスタンス = a;
 }

参照カウントの変更プロセスを次の図に示します。

メソッドが実行された後、スタック内の参照は解放されますが、2 つのオブジェクトが循環参照でヒープメモリ内に残され、2 つのインスタンスの最終的な参照カウントが 0 にならないことがわかります。最終的には、2 つのオブジェクトのメモリが解放されることはありません。まさにこの欠陥のせいで、参照カウントアルゴリズムは GC プロセスで実際には適用されません。

2. 到達可能性解析アルゴリズム

到達可能性分析アルゴリズムは、JVM がガベージを見つけるために使用するデフォルトのアルゴリズムです。到達可能性分析アルゴリズムはガベージを探していると言われていますが、実際にはまだ生きているオブジェクトを探していることに注意してください。この設計の理由は、参照されていないガベージオブジェクトを直接探すと、実装が比較的複雑になり、時間がかかるためです。逆に、生き残ったオブジェクトをマークすると、時間が節約されます。

到達可能性分析アルゴリズムの基本的な考え方は、GC ルートと呼ばれる一連のオブジェクトから開始し、これらのノードから下方向に検索することです。検索パスは参照チェーンと呼ばれます。オブジェクトを GC ルートに接続する参照チェーンがない場合、オブジェクトはもはや存在せず、ガベージとしてリサイクルできることがわかります。

Java では、次のオブジェクトを GC ルートとして使用できます。

仮想マシンスタック（スタックフレームのローカル変数テーブル）で参照されるオブジェクト
メソッド領域の静的属性によって参照されるオブジェクト
メソッド領域内の定数によって参照されるオブジェクト
ネイティブメソッドスタック内の JNI (ネイティブメソッド) によって参照されるオブジェクト
基本データ型に対応するクラスオブジェクト、一部の常駐例外オブジェクト、システムクラスローダーなどのJVM内部参照
同期ロックによって保持されるオブジェクト参照
JVM の内部状況や、JVMTI に登録されたコールバックローカルコードキャッシュなどを反映する JMXBean。
さらに、一時的な GC ルートもいくつかあります。これは、ガベージコレクションでは主に世代別コレクションとローカルコレクションが使用されるためです。世代や領域を越えて参照されるオブジェクトを考慮する場合、正確性を確保するために、これらの関連オブジェクトを GC ルートに追加する必要があります。

このうち、最初の 4 つはより重要であり、最も頻繁に言及されるので、他の項目については簡単に学習するだけで十分です。 JVM がガベージオブジェクトを検索する方法を理解した後、さまざまなガベージコレクションアルゴリズムがどのように実行されるかを見てみましょう。

ガベージコレクションアルゴリズム

1. マークスイープアルゴリズム

マークアンドスイープアルゴリズムは、非常に基本的なガベージコレクションアルゴリズムです。ヒープ内の有効なメモリ領域が使い果たされると、STW (Stop the World) がトリガーされ、その後、マーキングとスイープの 2 段階でガベージコレクションが実行されます。

マーキング: GCルートノードからスキャンし、生き残ったすべてのオブジェクトをマークし、到達可能なオブジェクトとして記録します。
クリア: ヒープメモリ空間全体をスキャンし、到達可能なオブジェクトとしてマークされていないオブジェクトが見つかった場合は、リサイクルされます。

次の図で、2 段階の実行プロセスを簡単に見てみましょう。

ただし、このアルゴリズムにはいくつかの問題があります。

GC の進行中に STW が発生し、アプリケーション全体が停止し、ユーザーエクスペリエンスが低下します。
マーキングフェーズとクリアフェーズの両方の効率は比較的低いです。マーキングフェーズではルートセットからのスキャンが必要であり、クリアフェーズではヒープ内のすべてのオブジェクトを走査する必要があります。
残存していないオブジェクトのみが処理され、クリア後に不連続なメモリフラグメントが大量に生成されます。その結果、プログラムが実行時に大きなオブジェクトを割り当てる必要がある場合、十分な連続メモリを見つけることができず、新しいガベージコレクションアクションがトリガーされます。

さらに、JVM は実際にはガベージオブジェクトをトラバースして内部データを削除するのではなく、ガベージオブジェクトの最初と最後のアドレスを保存します。メモリを再度割り当てるときに、アドレスリストから直接割り当てます。この対策により、一部のマークスイープアルゴリズムの効率が向上します。

2. レプリケーションアルゴリズム

レプリケーションアルゴリズムは主に新世代で使用されます。メモリを同じサイズの 2 つのブロックに分割し、一度にそのうちの 1 つだけを使用します。任意の時点で、動的に割り当てられたすべてのオブジェクトは、メモリ空間の 1 つにのみ割り当てることができ、他のメモリ空間は空いています。レプリケーションアルゴリズムは 2 つのステップに分けられます。

いずれかのメモリブロックの有効なメモリ領域が使い果たされると、JVM はアプリケーションの実行を停止し、コピーアルゴリズムの GC スレッドを開始して、残っているオブジェクトを別の空きメモリ領域にコピーします。コピーされたオブジェクトはメモリアドレスに従って厳密に順序付けられ、GCスレッドは生き残ったオブジェクトのメモリ参照アドレスを新しいメモリアドレスを指すように更新します。
コピーが完了すると、使用済み領域が一度にクリーンアップされ、使用済みメモリ領域と空きメモリ領域が交換され、メモリのリサイクルごとにメモリ領域の半分がリサイクルされます。

次の図でレプリケーションアルゴリズムの実行プロセスを見てみましょう。

コピーアルゴリズムの利点は、マークスイープアルゴリズムのメモリ断片化の欠点を補うことですが、いくつかの問題もあります。

メモリの半分しか使用されていないため、メモリ使用率が低くなり、無駄が生じます。

オブジェクトの生存率が高い場合、多くのオブジェクトをコピーし、そのアプリケーションアドレスを更新する必要があり、非常に長い時間がかかります。

上記の欠点から、複製アルゴリズムが必要な場合、オブジェクトの生存率が比較的低くなければならないという前提条件があることがわかります。したがって、オブジェクトが頻繁に「生まれて死ぬ」可能性が高い新しい世代では、複製アルゴリズムがより頻繁に使用されます。

3. マークソートアルゴリズム

マークスイープアルゴリズムはマークスイープアルゴリズムと非常によく似ており、主に旧世代で使用されます。それは次の 2 つのステップに分けられます。

マーキング: マークアンドスイープアルゴリズムと同様に、最初にオブジェクトがマークされ、生き残ったオブジェクトが GC ルートノードを通じてスキャンされてマーキングされます。

配置: 残っているすべてのオブジェクトを一方の端の空き領域に移動し、メモリアドレスに従って順番に並べ替え、対応する参照ポインタを更新してから、終了メモリアドレスを除くすべてのメモリ領域をクリーンアップします。

マークスイープアルゴリズムの実行プロセスを次の図に示します。

マークスイープアルゴリズムは、前の 2 つのアルゴリズムを改善し、ある程度まで欠点を補っていることがわかります。

マークスイープアルゴリズムと比較して、メモリ空間の断片化の欠点を補う。
コピーアルゴリズムと比較すると、メモリスペースの半分を無駄にするという欠点を補う。

しかし同時に、マークコンパクトアルゴリズムにも欠点があります。一方では、すべての生きているオブジェクトをマークする必要があり、他方では、オブジェクトの移動操作と参照アドレスを更新する操作も追加されます。したがって、マークコンパクトアルゴリズムの使用コストは高くなります。

4. 世代別コレクションアルゴリズム

実際、Java のガベージコレクターは、1 つのガベージコレクションアルゴリズムだけを使用するわけではありません。現在のガベージコレクターのほとんどは、世代別コレクションアルゴリズムを使用しています。 JVM は一般に、オブジェクトの異なる生存サイクルに応じてメモリを複数のブロックに分割します。一般的に、ヒープメモリは新しい世代と古い世代に分割され、各世代の特性に応じて最適なガベージコレクションアルゴリズムが選択されます。主なアイデアは次のとおりです。

新しい世代では、多数のオブジェクトが収集されるたびに消滅するため、ガベージコレクションを完了するために少数のオブジェクトのコピーと参照の変更のみを必要とするコピーアルゴリズムを選択できます。

古い世代では、オブジェクトの生存率が比較的高く、レプリケーションアルゴリズムを使用してもパフォーマンスと効率を効果的に向上させることはできません。さらに、割り当てる追加のスペースがないため、ガベージコレクションにはマークスイープまたはマークコンパクトアルゴリズムが選択されます。

図を通して、さまざまなアルゴリズムの主な応用分野を簡単に見てみましょう。

特定の分野で特定のアルゴリズムが選ばれる理由については、3 つのアルゴリズムの特性と密接に関係しています。3 つの側面から比較してみましょう。

実行効率: アルゴリズムの時間計算量から見ると、コピーアルゴリズムが最も優れており、次にマークスイープアルゴリズムが続き、マークスイープアルゴリズムが最も低くなります。
メモリ使用率: マークスイープとマークスイープアルゴリズムは高く、コピーアルゴリズムは最も低い
メモリの整頓性: コピーアルゴリズムとマークスイープアルゴリズムは比較的整頓されており、マークスイープアルゴリズムは最も整頓性が低いです。

多くの違いがありますが、マークする必要があることに加えて、もう 1 つの類似点があります。つまり、gc スレッドが動作を開始すると、動作中のすべてのスレッドを STW によって一時停止する必要があるということです。

要約する

この記事では、まずガベージコレクションの基本的な問題を紹介しました。どのようなオブジェクトがガベージとしてリサイクルされるのでしょうか。JVM は、到達可能性分析アルゴリズムを通じてこの重要な問題を解決し、それに基づいてさまざまな一般的なガベージコレクションアルゴリズムを導出します。異なるアルゴリズムにはそれぞれ長所と短所があり、その特性に応じて異なる時代に適用されます。

この記事では非常に多くのことを説明しましたが、これらはまだ基本的な知識です。JVM のガベージコレクションを徹底的にマスターしたい場合は、ガベージコレクター、メモリ割り当てなど、理解すべき知識がまだたくさんありますが、今日はここで紹介します。この図解による説明を通じて、ガベージコレクションアルゴリズムをよりよく理解するのに役立つことを願っています。

この記事はWeChat公式アカウント「码农参上」から転載したもので、以下のQRコードからフォローできます。この記事を転載する場合は、Coder Canshang の公式アカウントまでご連絡ください。

<<: 世界中のもう一人の自分と話すのはどんな感じでしょうか?世界初のAI人間観察者が誕生

>>: 複数の都市が共同で人工知能コンピューティングネットワークを点灯し、人工知能産業の発展を促進する