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 の公式アカウントまでご連絡ください。