面接官はガベージコレクションアルゴリズムについて質問するのが大好きです

[[438235]]

この記事はWeChatの公開アカウント「Programmer Bus」から転載したもので、著者はQishiyiです。この記事の転載についてはProgrammer Bus公式アカウントまでご連絡ください。

序文

しばらく前に1次面接に合格したアバアバは、2次面接に招待されました。今回、彼女が出会った面接官は、引き続き彼女を困惑させ、GCアルゴリズムに関する質問をします。

家に帰って通知を待つ

インタビュアー: JVM ガベージコレクションについてご存知ですか?

アバアバ：うん、少しは分かるよ。

インタビュアー: では、JVM はどのようにしてオブジェクトがガベージであるかどうかを判断するのでしょうか?

アバアバ：到達可能性解析という手法があるようですね。

アバアバ：つまり、到達可能なオブジェクトは生き物として判断され、到達不可能なオブジェクトは「ゴミ」とみなされます。

インタビュアー: うーん...あなたが知っているガベージコレクションアルゴリズムについて教えてください。

アババアババ:

明確にマークされたアルゴリズム

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

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

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

インタビュアー：えーと...これらのアルゴリズムはご存知ですか？

アバアバ：うーん…よく分からない…

インタビュアー: はい、今日はこれで終わりです。戻って次の連絡をお待ちください。

アバアバ：わかりました。

残念ながら、面接には不合格となりました。あなたの履歴書は当社の人材プールに追加されました。次回お会いできるのを楽しみにしています...

その場でオファーを受け取る

インタビュアー: JVM ガベージコレクションについてご存知ですか?

アバアバ：うん、少しは分かるよ。

インタビュアー: では、JVM はどのようにしてオブジェクトがガベージであるかどうかを判断するのでしょうか?

Aba Aba: 方法は 2 つあります。1 つは参照カウント方式、もう 1 つは到達可能性分析方式です。

Aba Aba: 参照カウント方式は、オブジェクトに参照カウンタを与える方法です。オブジェクトへの参照があるたびに、参照カウンタが 1 増加します。参照が切断されるたびに、参照カウンタが 1 減少します。このように、参照カウンタが 0 の場合、オブジェクトは役に立たないもの、いわゆる「ガベージ」と見なされます。ただし、この方法には大きな欠点があり、循環参照を処理できません。

Aba Aba: 循環参照のあるオブジェクトへの外部参照があります。この状況は問題ないように見えますが、メソッド領域で参照を切断すると問題が露呈します。

アバアバ: 循環参照オブジェクトの外部参照が切断されている状況。

Aba Aba: 上記の切断された参照の場合、オブジェクト A とオブジェクト B は外部参照がないため、ガベージになっていることは明らかです。ただし、相互参照 (循環参照) のため、参照カウンタの値は 1 となり、リサイクルできません。この欠点により、参照カウント方式は実際には JVM では使用されません。

Aba Aba: 到達可能性分析方法は、GC ルートのオブジェクトを下方向に検索することです。この検索されたパスは「参照チェーン」と呼ばれます。オブジェクトが GC ルートのどの参照チェーンにもリンクされていない場合、そのオブジェクトは「デッド」であると判断されます。一般に、このオブジェクトを「到達不能」と呼びます。

インタビュアー: 先ほど GC ルートについてお話がありましたが、どのオブジェクトを GC ルートとして使用できるのかご存知ですか?

Aba Aba: はい、分かりました。GC ルートとして使用できるオブジェクトは主に 4 種類あります。

仮想マシンスタックで参照されるオブジェクト
メソッド領域内の静的属性によって参照されるオブジェクト
メソッド領域内の定数によって参照されるオブジェクト
ネイティブメソッドスタックで参照されるオブジェクト

アバアバ：下の写真を見ると彼らの関係がよく分かります。

Aba Aba: 参照チェーン上のオブジェクトのみが「生きている」と判断され、参照チェーン上にないオブジェクトは「死んでいる」と判断され、ゴミとしてリサイクルされることがわかります。

インタビュアー：いい説明ですね。ヒープ内のオブジェクトをリサイクルするだけでなく、メソッド領域のガベージもリサイクルされるのでしょうか？

Aba Aba: メソッド領域にもガベージコレクションがあり、主に廃棄された定数や役に立たないクラスをリサイクルします。

インタビュアー: うーん...あなたが知っているガベージコレクションアルゴリズムについて教えてください。

Aba Aba: ガベージコレクションアルゴリズムには主に 4 つの種類があります。

明確にマークされたアルゴリズム
マークスイープアルゴリズム
レプリケーションアルゴリズム
世代別コレクションアルゴリズム

Aba Aba: マーククリアアルゴリズムは2段階に分かれています。第1段階は「マーキング」、第2段階は「クリア」です。まず、クリアするオブジェクト、つまり灰色の部分を全てマークし、その後リサイクルします。

Aba Aba: マークスイープアルゴリズムを使用してヒープ内のガベージをクリーンアップすると、多くのスペースフラグメントが生成されます。これらのスペースフラグメントにより、新しいオブジェクトにメモリを割り当てることが困難になります。それだけでなく、マークスイープアルゴリズムのマーキング段階とスイープ段階の両方での効率はそれほど高くありません。

Aba Aba: マークアンドコンパクトアルゴリズムは、過度のメモリ断片化の問題を解決するために生まれました。

Aba Aba: 効率の問題を解決するために、メモリブロックを 2 つの同じサイズのブロックに分割し、毎回 1 つのブロックのみを使用するというレプリケーションアルゴリズムも登場しました。メモリブロックが使い果たされると、このメモリブロック内の生き残ったオブジェクトは別のメモリブロックに転送され、その後、このメモリブロック内のすべてのオブジェクトがクリアされます。

Aba Aba: コピーアルゴリズムは実装が簡単で便利、効率的で、メモリの断片化の問題を考慮する必要がありません。ただし、メモリを元のサイズの半分に減らすコストは間違いなく非常に高くなります。

Aba Aba: さらに、新世代のオブジェクトのほとんどは 1 日で生まれて死んでしまいます。1:1 のスペース比率に従ってレプリケーションアルゴリズムを使用すると、メモリのパフォーマンスに大きな影響が出ます。

Aba Aba: 世代別アルゴリズムは、ヒープ領域を分割し、異なる領域の条件に応じて対応するガベージコレクションアルゴリズムを適用します。

Aba Aba: 下の図は新世代を改良したものです。新世代はエデン領域と生存領域に分かれています。生存領域はさらに 2 つの領域 (s0 と s1) に分かれています。図に示すように、それらの比率は 8:1:1 です。新しいオブジェクトは、まず Eden 領域に割り当てられます。フラグメントが多すぎるため、マークスイープアルゴリズムはここでは適用できません。オブジェクトに割り当てる連続したスペースが十分にない場合、ガベージコレクションが引き続きトリガーされ、パフォーマンスに大きな影響を与えます。

アバアバ：従来のGCでは、GCプロセスがもたらす「STOP-THE-WORLD」を回避することは不可能であり、一般的にSTWと呼ばれています。STWはシステムのパフォーマンスに大きな影響を与えるため、STWを排除するか、STW時間を短縮するかが特に重要です。実際、世代別アルゴリズムは特定のアルゴリズムではありません。これまでのマークスイープ、マークコンパクト、コピーアルゴリズムとは異なり、世代別アルゴリズムはヒープを分割するだけで、異なる領域で異なるアルゴリズムを使用して、STW時間を各領域に細分化し、STW時間が長時間続かないようにすることで、システムパフォーマンスを向上させるという目的を達成します。

面接官: とてもわかりやすく詳しく説明していただきました。とてもよかったです。明日は仕事に来られますか?