ガベージコレクション
ガベージコレクション（garbage collection; GC）とは、プログラムが動的に確保したメモリ領域のうち、不要になった領域を自動的に解放する機能である。「ガベージコレクション」を直訳すれば「ゴミ収集」となる。1959年ごろ、LISPにおける問題を解決するためジョン・マッカーシーによって発明された[1][2]。
メモリの断片化を解消する機能と併せてガベージコレクションと呼ぶ場合もあるが、厳密にはそのような機能はコンパクションと呼び、区別される。実現手法の一つであるコピーGCでは、ガベージコレクションと共にコンパクションも行われる仕組みになっている。
また、ガベージコレクションを行う主体はガベージコレクタと呼ばれる。ガベージコレクタはタスクやスレッドとして実装される場合が多い。
スマートポインタ(w:Smart pointer)は、参照カウント方式のガベージコレクションは通常煩雑なコーディングを必要とするが、それを必要なく実装したライブラリである。
目次
動作
従来のメモリ管理では、プログラマがプログラムの実行中においてメモリが必要となる期間を考え、必要となった時点でメモリを確保するコードを記述し、不要となった時点で解放するコードを記述していた。
ガベージコレクションを使用すると、メモリを確保するコードは明示的に記述するが、メモリの解放については明示的に記述する必要がなく、ガベージコレクタが不要と判断した時に、自動的にメモリを解放する。確保したメモリが不要かどうかは、プログラムが今後そのメモリにアクセスするかどうかで決まり、スタックや変数テーブルなどから参照をたどってメモリに到達可能かどうかによって判断される。
ガベージコレクションの機能は、初めから言語処理系に組み込まれている場合や、後付けのライブラリなどによって提供される。
特徴
ガベージコレクションはプログラム作成者が明示的にメモリの確保・解放を行う必要が無いため、以下に示すメモリ管理に関連する陥りやすいバグを回避することができる。
- メモリリークの回避
- ガベージコレクションは、オブジェクト（データを格納したメモリ領域）とそれを指し示すポインタを管理するため、オブジェクトは存在しているがそれを指すポインタが無い状態を回避することができる。
- オブジェクトの二重解放の回避
- いったん解放したオブジェクトをさらに解放することを防ぐ。
- 無効なポインタの回避
- たとえば、サブルーチンで確保したオブジェクトへのポインタを呼び出し元に戻す場合に、確保したオブジェクトがローカル変数のため、サブルーチンを抜けるとオブジェクトが破棄されることがある。呼び出し元に戻されたポインタにはあるアドレスが代入されているが、そのアドレスにはオブジェクトが存在せず、ポインタは無効なメモリアドレスを指している。このような無効なポインタをダングリング・ポインタ(Dangling pointer)といい、ガベージコレクションはこの問題を回避する。
ただしガベージコレクションにおいても、今後使用することのないオブジェクトへのポインタをいつまでも保持しているようなコードでは、いつまでもオブジェクトが解放されず、メモリ不足を起こしてしまう。これは論理的な設計の問題であり、ガベージコレクションを持つ処理系においてもこの種のメモリリークは発生する。
メモリ管理に関するバグを回避する以外に、プログラミングスタイルの選択肢を広げる効果も持つ。型変換などのために一時的なオブジェクトを生成する、マルチスレッドを利用したプログラムでスレッド間でオブジェクトを共有して使用する、といった処理はメモリ確保・解放の処理の記述が煩雑となることが多い。しかし、ガベージコレクションを持つ言語処理系においては煩雑な記述を省略することができ、これらの処理をより自然に記述することができる。
多くの実装では、入れ違いにより誤って到達可能なメモリが不可能と判断されないように、ガベージコレクトが開始されると他の処理を止め、本処理が中断される（Stop-the-world ガベージコレクタ） 。CPUを長時間（数百ミリ秒から数十秒）占有することもある。ガベージコレクションの動作タイミングの予測やCPUの占有時間の事前予測などが困難なことから、デッドラインが決められているリアルタイムシステムに使用することは難しい。リアルタイム性を改善したGCとして、インクリメンタルGCやコンカレントGCがある。
実装
ガベージコレクションは、Java言語のように言語処理系に組み込まれたものと、C言語のように言語処理系には存在しないがライブラリを使用することで実現できるものがある。
ガベージコレクションは、プログラム本来の動作とは別に時間のかかる処理である。そこで、ガベージコレクションには本来のプログラムの動作に対して影響が少ないことが求められる。
一般に、デスクトップアプリケーションでは、応答時間を短くするため、ガベージコレクションによるプログラムの停止時間を最小にすることが要求される。また、サーバアプリケーションでは、応答時間よりもスループットを求められることが多く、ガベージコレクションにもスループット性能が高いものが求められる。さらに、機器組み込みアプリケーションでは、機器に搭載されるCPUの能力の低さやメモリ容量の小ささから、リソース消費が小さいものが求められる。また、リアルタイムシステムでは、プログラム動作時間のばらつきを最小にしたいという要求もある。
これらの要求をすべて満たすようなアルゴリズムは存在しないため、さまざまな手法が提案されている。代表的なガベージコレクションアルゴリズムには、以下のものがある。
- 参照カウント
- オブジェクトを参照するポインタの数を数え、参照するポインタの数がゼロになったら解放する方法。循環参照の問題がある。解放が集中したときに、単純な実装だと停止時間が長くなる。
- マーク・アンド・スイープ
- オブジェクトから別のオブジェクトへの参照をたどり、到達出来ないオブジェクトを破棄する方法。
- コピーGC
- 通常使用するメモリ領域と同じ容量のメモリ領域をもうひとつ用意し、ガベージコレクションの際に有効なオブジェクトのみをもう一方のメモリ領域にコピーする方法。メモリ領域をデータ保持に必要な容量の2倍消費すること、コピーの際にオブジェクトのアドレスが変更されることなどの欠点があるが、ガベージコレクションとコンパクションが同時に行える利点がある。
これらのアルゴリズムは複合して使用することもあり、世代別ガベージコレクションではコピーGCとマーク・アンド・スイープの両方のアルゴリズムを使用している。
また、アプリケーション動作への影響の観点から、アプリケーション動作をすべて止めるStop the world方式と、アプリケーション動作と並行して動作するコンカレント方式に分類することができる。
言語による利用可能性
一般論として、高レベルな言語ほどガベージコレクションを言語の標準機能として備えていることが多い。言語に組み込まれていない場合でも、C++のBoehm GCのように、ライブラリとして実装されていることも多い。このアプローチは、オブジェクトの生成と破棄のメカニズムを変更する必要があるなど、欠点がないわけではない。
MLやHaskell、APLなどの関数型言語の多くはガベージコレクションが組み込まれている。特に、関数型言語の先駆けとなったLispは最初にガベージコレクションを取り入れた言語でもある。
Rubyなどといった動的言語も、ガベージコレクションを備えていることが多い（ただしPerl 5やPHP 5.2以前には参照カウント方式のものしかない）。Smalltalk、Java、ECMAScriptのようなオブジェクト指向言語には、たいていガベージコレクションが組み込まれている。特筆すべき例外はC++とDelphiで、それらはデストラクタがその代わりとなっている。Objective-Cには元々ガベージコレクションはなかったが、アップルがMac OS X向けに実装したObjC 2.0では、自社開発したランタイムコレクターを使用している。一方で、GNUstepはBoehm GCを使用している。
ライブラリ
- Boostのsmart_ptr - C++用。参照カウント。
- Boehm-Demers-Weiser conservative garbage collector - C/C++用。マーク・アンド・スイープ。
分散ガベージコレクション
分散コンピューティング環境では、あるホスト内のオブジェクトだけではなく、リモートホスト上に存在するオブジェクトとメッセージのやり取りが行われることがある。このような環境においてローカルなガベージコレクションと同様、不要なオブジェクトを破棄する手法が分散ガベージコレクションである。リモートホストからの参照状態の検出、通信が切れた場合の処理などローカルホストのガベージコレクションとは異なる課題を解決する必要がある。
世代別ガベージコレクション
従来のGCは、対象となるメモリ領域がいっぱいになった時に一気にGCを行なうものであり、この方法では、メモリ領域のサイズが大きくなるに従い、GC時間が長くなっていく欠点がある。この問題に対処するために世代別ガベージコレクションが考案された。 世代別GCでは新領域と古い領域にメモリ領域が分けられ、新規に作成されたオブジェクトは、新領域に配置され、新領域がいっぱいになった時点で、新領域内部だけのGCが走る。このGCはメモリ全体に対するGCに比べると当然のことながら低負荷・高速になる。新領域に対するGCを一定回数生き残ったオブジェクトは、古領域に移動し、古領域がいっぱいになった時に、初めて全てのメモリ領域を対象とするFULL GCが行われる。
