ガベージコレクションの基礎

wikipediaより：ほぼまるまるコピーになってしまった。

ガベージコレクション（garbage collection; GC）とは、プログラムが動的に確保したメモリ領域のうち、不要になった領域を自動的に解放する機能である。

「コンパクション」とは、：

メモリの断片化を解消する機能と併せてガベージコレクションと呼ぶ場合もあるが、厳密にはそのような機能はコンパクションと呼び、区別される。

動作方法は：(wikiの要約)

(要約)従来のメモリ管理では、メモリが必要となる期間を考え、必要となった時点でメモリを確保、不要となった時点で開放するコードを記述していた。

GCを使用すると(メモリを確保するコードは明示的に記述するが)、メモリの開放については明示的に記述する必要がなく、ガベージコレクタが不要と判断した時に、自動的にメモリを開放する。確保したメモリが不要かどうかは、プログラムが今後そのメモリにアクセスするかどうかで決まり、スタックや変数テーブルなどから参照をたどってメモリに到達可能かどうかによって判断される。

ガベージコレクションの機能は、初めから言語処理系に組み込まれている場合や、後付けのライブラリなどによって提供される。

特徴 :

ガベージコレクションはプログラム作成者が明示的にメモリの確保・解放を行う必要が無いため、以下に示すメモリ管理に関連する陥りやすいバグを回避することができる。

メモリリークの回避

    ガベージコレクションは、オブジェクト（データを格納したメモリ領域）とそれを指し示すポインタを管理するため、オブジェクトは存在しているがそれを指すポインタが無い状態を回避することができる。

オブジェクトの二重解放の回避

    いったん解放したオブジェクトをさらに解放することを防ぐ。

無効なポインタの回避

    たとえば、サブルーチンで確保したオブジェクトへのポインタを呼び出し元に戻す場合に、確保したオブジェクトがローカル変数のため、サブルーチンを抜けるとオブジェクトが破棄されることがある。呼び出し元に戻されたポインタにはあるアドレスが代入されているが、そのアドレスにはオブジェクトが存在せず、ポインタは無効なメモリアドレスを指している。このような無効なポインタをダングリング・ポインタ(Dangling pointer)といい、ガベージコレクションはこの問題を回避する。

ただしガベージコレクションにおいても、今後使用することのないオブジェクトへのポインタをいつまでも保持しているようなコードでは、いつまでもオブジェクトが解放されず、メモリ不足を起こしてしまう。これは論理的な設計の問題であり、ガベージコレクションを持つ処理系においてもこの種のメモリリークは発生する。

メモリ管理に関するバグを回避する以外に、プログラミングスタイルの選択肢を広げる効果も持つ。型変換などのために一時的なオブジェクトを生成する、マルチスレッドを利用したプログラムでスレッド間でオブジェクトを共有して使用する、といった処理はメモリ確保・解放の処理の記述が煩雑となることが多い。しかし、ガベージコレクションを持つ言語処理系においては煩雑な記述を省略することができ、これらの処理をより自然に記述することができる。

多くの実装では、入れ違いにより誤って到達可能なメモリが不可能と判断されないように、ガベージコレクトが開始されると他の処理を止め、本処理が中断される(Stop-the-world ガベージコレクタ) 。CPUを長時間（数百ミリ秒から数十秒）占有することもある。ガベージコレクションの動作タイミングの予測やCPUの占有時間の事前予測などが困難なことから、デッドラインが決められているリアルタイムシステムに使用することは難しい。リアルタイム性を改善したGCとして、インクリメンタルGCやコンカレントGCがある。

手法：複数の手法がある。

参照カウント

    オブジェクトを参照するポインタの数を数え、参照するポインタの数がゼロになったら解放する方法。循環参照の問題がある。解放が集中したときに、単純な実装だと停止時間が長くなる。

マーク・アンド・スイープ

    オブジェクトから別のオブジェクトへの参照をたどり、到達出来ないオブジェクトを破棄する方法。

コピーGC

    通常使用するメモリ領域と同じ容量のメモリ領域をもうひとつ用意し、ガベージコレクションの際に有効なオブジェクトのみをもう一方のメモリ領域にコピーする方法。メモリ領域をデータ保持に必要な容量の2倍消費すること、コピーの際にオブジェクトのアドレスが変更されることなどの欠点があるが、ガベージコレクションとコンパクションが同時に行える利点がある。

これらのアルゴリズムは複合して使用することもあり、世代別ガベージコレクションではコピーGCとマーク・アンド・スイープの両方のアルゴリズムを使用している。

また、アプリケーション動作への影響の観点から、アプリケーション動作をすべて止めるStop the world方式と、アプリケーション動作と並行して動作するコンカレント方式に分類することができる。

Objective-Cでは：

Objective-Cのガベージコレクションは、保守的であり、コピーは行わず(ゆえにコンパクションも行わない)、マーク・アンド・スイープでコレクションを行い、世代別コレクションをサポートする(http://news.mynavi.jp/column/objc/098/index.htmlより引用)

Objective-Cのガベージコレクションの特徴として、コピーは行わなず、したがってコンパクションも行わない